Encounter thứ tự sai khi sắp xếp một dòng song song

Question

Tôi có một lớp Record:

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 
} 

tôi có thể tạo một danh sách lớn của rất nhiều hồ sơ. Chỉ có giá trị thứ hai và thứ năm, i/10000 và i, được sử dụng sau này, bởi getters getCategory2() và getValue1() tương ứng.

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)); 
} 

Lưu ý rằng 10.000 hồ sơ đầu tiên có một category2 của 0, sau đó tới 10.000 có 1, vv, trong khi các value1 giá trị là 0-114.999 tuần tự.

Tôi tạo một Stream là cả hai parallel và sorted.

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

Tôi có một ForkJoinPool duy trì 8 đề, đó là số lõi tôi có trên máy tính của tôi.

ForkJoinPool pool = new ForkJoinPool(8); 

Tôi sử dụng thủ thuật described here to submit a stream processing task to my own ForkJoinPool instead of the common ForkJoinPool.

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

tôi mong đợi rằng song song sorted hoạt động sẽ tôn trọng trật tự cuộc gặp gỡ của con suối, và rằng nó sẽ là một loại ổn định, vì Spliterator trả về bởi ArrayList là ORDERED.

Tuy nhiên, mã đơn giản in ra các phần tử của kết quả Listoutput theo thứ tự cho thấy rằng nó không hoàn toàn đúng.

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

Output, ngưng tụ:

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 

Các size() của output là 115000, và tất cả những yếu tố dường như có mặt ở đó, chỉ trong một trật tự hơi khác nhau.

Vì vậy, tôi đã viết một số mã kiểm tra để xem nếu sort là ổn định. Nếu giá trị này ổn định, thì tất cả giá trị value1 sẽ vẫn giữ nguyên. Mã này xác minh thứ tự, in bất kỳ sự khác biệt nào.

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); 

Output:

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 

Tình trạng này kéo dài nếu tôi làm bất cứ điều nào sau đây:

• Thay ForkJoinPool với một ThreadPoolExecutor.

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

• Sử dụng phổ biến ForkJoinPool bằng cách xử lý Stream trực tiếp.

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

• Gọi parallel()sau tôi gọi sorted.

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

• Gọi parallelStream() thay vì stream().parallel().

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

• Sắp xếp sử dụng Comparator. Lưu ý rằng tiêu chí sắp xếp này khác với thứ tự "tự nhiên" mà tôi đã xác định cho giao diện Comparable, mặc dù bắt đầu với kết quả đã được sắp xếp theo thứ tự từ đầu, kết quả sẽ vẫn như cũ.

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

Tôi chỉ có thể có được điều này để giữ gìn trật tự gặp gỡ nếu tôi không làm một trong các cách sau trên Stream:

• Đừng gọi parallel().
• Đừng gọi bất kỳ tình trạng quá tải nào của sorted.

Điều thú vị là, parallel() mà không cần sắp xếp thứ tự.

Trong cả hai trường hợp nêu trên, đầu ra là:

Verified: true 

phiên bản My Java là 1.8.0_05. Điều bất thường này cũng là occurs on Ideone, có vẻ như đang chạy Java 8u25.

Cập nhật

Tôi đã nâng cấp JDK của tôi lên phiên bản mới nhất như các văn bản này, 1.8.0_45, và vấn đề là không thay đổi.

Câu hỏi

là thứ tự kỷ lục trong kết quả List (output) ra khỏi trật tự vì loại là bằng cách nào đó không ổn định, vì trật tự cuộc gặp gỡ không được bảo quản, hoặc một lý do nào khác?

Làm cách nào để đảm bảo rằng thứ tự cuộc gặp gỡ được giữ nguyên khi tôi tạo luồng song song và sắp xếp nó?

Answer 1

Dường như Arrays.parallelSort không ổn định trong một số trường hợp. Vâng phát hiện. Việc sắp xếp song song luồng được thực hiện theo điều khoản của Arrays.parallelSort, do đó, nó cũng ảnh hưởng đến luồng. Dưới đây là một ví dụ đơn giản:

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)); 
    } 
} 

Trên máy tính của tôi (2 lõi x 2 chủ đề) này in như sau:

true 
true 
false 

Tất nhiên, đó là nghĩa vụ để in true ba lần. Đây là bản build JDK 9 dev hiện tại.Tôi sẽ không ngạc nhiên nếu nó xảy ra trong tất cả các bản phát hành JDK 8 cho đến nay, cho những gì bạn đã thử. Thật kỳ lạ, việc giảm kích thước hoặc số chia sẽ thay đổi hành vi. Một kích thước 20.000 và một ước của 10.000 là ổn định, và một kích thước của 50.000 và một ước của 1.000 cũng ổn định. Có vẻ như vấn đề phải làm với một giá trị đủ lớn chạy so sánh bằng với kích thước phân chia song song.

Sự cố OpenJDK JDK-8076446 bao gồm lỗi này.