排序并行流时遇到顺序错误

Question

我有一个记录课程：

public class Record implements Comparable<Record>
{
   private String myCategory1;
   private int    myCategory2;
   private String myCategory3;
   private String myCategory4;
   private int    myValue1;
   private double myValue2;

   public Record(String category1, int category2, String category3, String category4,
      int value1, double value2)
   {
      myCategory1 = category1;
      myCategory2 = category2;
      myCategory3 = category3;
      myCategory4 = category4;
      myValue1 = value1;
      myValue2 = value2;
   }

   // Getters here
}

我创建了一个包含很多记录的大列表。只有第二个和第五个值，即i/10000和i，稍后分别由getter使用。

List<Record> list = new ArrayList<>();
for (int i = 0; i < 115000; i++)
{
    list.add(new Record("A", i / 10000, "B", "C", i, (double) i / 100 + 1));
}

请注意，前10000条记录的类别2为0，接下来的10000条记录的类别1等，而值1按顺序为0-114999。

我创建了一个既并行又排序的流。

Stream<Record> stream = list.stream()
   .parallel()
   .sorted(
       //(r1, r2) -> Integer.compare(r1.getCategory2(), r2.getCategory2())
   )
   //.parallel()
;

我有一个ForkJoinPool，它维护8个线程，这是我电脑上的内核数。

ForkJoinPool pool = new ForkJoinPool(8);

我使用这里描述的技巧将流处理任务提交给我自己的ForkJoinPool，而不是常见的ForkJoinPool。

List<Record> output = pool.submit(() ->
    stream.collect(Collectors.toList()
)).get();

我希望并行排序操作将尊重流的相遇顺序，并且它将是一个稳定的排序，因为由数组列表返回的拆分器是有序的。

然而，按顺序打印出结果列表的元素的简单代码表明情况并非如此。

for (Record record : output)
{
     System.out.println(record.getValue1());
}

输出，压缩：

0
1
2
3
...
69996
69997
69998
69999
71875  // discontinuity!
71876
71877
71878
...
79058
79059
79060
79061
70000  // discontinuity!
70001
70002
70003
...
71871
71872
71873
71874
79062  // discontinuity!
79063
79064
79065
79066
...
114996
114997
114998
114999

输出的size（）为115000，所有元素似乎都在那里，只是顺序略有不同。

所以我写了一些检查代码来查看排序是否稳定。如果它是稳定的，那么所有value e1值都应该保持顺序。此代码验证订单，打印任何差异。

int prev = -1;
boolean verified = true;
for (Record record : output)
{
    int curr = record.getValue1();
    if (prev != -1)
    {
        if (prev + 1 != curr)
        {
            System.out.println("Warning: " + prev + " followed by " + curr + "!");
            verified = false;
        }
    }
    prev = curr;
}
System.out.println("Verified: " + verified);

输出：

Warning: 69999 followed by 71875!
Warning: 79061 followed by 70000!
Warning: 71874 followed by 79062!
Warning: 99999 followed by 100625!
Warning: 107811 followed by 100000!
Warning: 100624 followed by 107812!
Verified: false

如果我执行以下任一操作，这种情况将持续存在：

>

用ThreadPoolExecutor替换ForkJoinPool。

ThreadPoolExecutor pool = new ThreadPoolExecutor(8, 8, 0, TimeUnit.SECONDS, new ArrayBlockingQueue<>(10));

通过直接处理Stream来使用常见的ForkJoinPool。

List<Record> output = stream.collect(Collectors.toList());

在我调用排序后调用parallel（）。

Stream<Record> stream = list.stream().sorted().parallel();

调用并行流（）而不是stream（）。并行（）。

Stream<Record> stream = list.parallelStream().sorted();

使用比较器进行排序。请注意，此排序标准与我为可比较接口定义的“自然”顺序不同，尽管从一开始就已经按顺序排列的结果开始，但结果仍然应该是相同的。

Stream<Record> stream = list.stream().parallel().sorted(
    (r1, r2) -> Integer.compare(r1.getCategory2(), r2.getCategory2())
);

如果我不在流上执行以下操作之一，我只能获得这个以保持遭遇顺序：

• 不要调用parallel（）

有趣的是，没有排序的parallel（）保留了顺序。

在上述两种情况下，输出为：

Verified: true

我的Java版本是1.8.0_05。这种异常也发生在Ideone上，它似乎运行Java 8u25。

使现代化

在撰写本文时，我已经将JDK升级到最新版本1.8.045，问题没有改变。

问题

结果列表中的记录顺序（输出）是否由于排序不稳定、未保留相遇顺序或其他原因而无序？

当我创建并行流并对其排序时，如何确保保留相遇顺序？




Answer 1

它看起来像数组。parallelSort在某些情况下不稳定。很好的发现。流并行排序是根据<代码>数组实现的。parallelSort，因此它也会影响流。下面是一个简化示例：

public class StableSortBug {
    static final int SIZE = 50_000;

    static class Record implements Comparable<Record> {
        final int sortVal;
        final int seqNum;

        Record(int i1, int i2) { sortVal = i1; seqNum = i2; }

        @Override
        public int compareTo(Record other) {
            return Integer.compare(this.sortVal, other.sortVal);
        }
    }

    static Record[] genArray() {
        Record[] array = new Record[SIZE];
        Arrays.setAll(array, i -> new Record(i / 10_000, i));
        return array;
    }

    static boolean verify(Record[] array) {
        return IntStream.range(1, array.length)
                        .allMatch(i -> array[i-1].seqNum + 1 == array[i].seqNum);
    }

    public static void main(String[] args) {
        Record[] array = genArray();
        System.out.println(verify(array));
        Arrays.sort(array);
        System.out.println(verify(array));
        Arrays.parallelSort(array);
        System.out.println(verify(array));
    }
}

在我的机器（2核x 2线程）上，这将打印以下内容：

true
true
false

当然，它应该打印true三次。这是在当前的JDK 9开发版本上。鉴于您已经尝试过的，如果它发生在迄今为止的所有JDK 8版本中，我不会感到惊讶。奇怪的是，减小大小或除数会改变行为。20,000的大小和10,000的除数是稳定的，50,000的大小和1,000的除数也是稳定的。似乎问题与比较相等与并行拆分大小的足够大的值运行有关。

OpenJDK问题JDK-8076446涵盖了这个bug。