Tại sao lọc theo nguyên tắc trong một dòng vô hạn các số dùng mãi mãi nếu được xử lý song song?

Question

tôi là tạo ra một dòng vô hạn các số nguyên bắt đầu từ 200 triệu, lọc dòng này sử dụng một thực hiện kiểm tra tính nguyên tố ngây thơ để tạo tải và hạn chế kết quả đến 10.

Predicate<Integer> isPrime = new Predicate<Integer>() { 
    @Override 
    public boolean test(Integer n) { 
     for (int i = 2; i < n; i++) { 
      if (n % i == 0) return false; 
     } 
     return true; 
    } 
}; 

Stream.iterate(200_000_000, n -> ++n) 
    .filter(isPrime) 
    .limit(10) 
    .forEach(i -> System.out.print(i + " ")); 

này hoạt động như mong đợi.

Bây giờ, nếu tôi thêm lệnh gọi song song() trước khi lọc, không có gì được tạo và quá trình xử lý không hoàn thành.

Stream.iterate(200_000_000, n -> ++n) 
    .parallel() 
    .filter(isPrime) 
    .limit(10) 
    .forEach(i -> System.out.print(i + " ")); 

Ai đó có thể chỉ cho tôi đúng hướng những gì đang xảy ra ở đây?

EDIT: Tôi không tìm kiếm các triển khai thử nghiệm nguyên thủy tốt hơn (nó được dự định là triển khai dài) nhưng để giải thích về tác động tiêu cực của việc sử dụng luồng song song.

Answer 1

Quá trình xử lý thực sự hoàn thành, mặc dù có thể mất khá nhiều thời gian tùy thuộc vào số lượng chuỗi phần cứng trên máy của bạn. API documentation về giới hạn cảnh báo rằng nó có thể chậm cho các luồng song song.

Trên thực tế, luồng song song trước tiên chia tính toán cho nhiều phần theo mức song song có sẵn, thực hiện tính toán cho mọi phần, sau đó ghép các kết quả lại với nhau. Bạn có bao nhiêu phần trong nhiệm vụ của mình? Một cho mỗi chủ đề FJP chung (= Runtime.getRuntime().availableProcessors()) cộng (đôi khi?) Một cho chuỗi hiện tại nếu nó không có trong FJP. Bạn có thể kiểm soát nó bằng cách thêm

System.setProperty("java.util.concurrent.ForkJoinPool.common.parallelism", "4"); 

Thực tế cho công việc của bạn số bạn đặt thấp hơn, nó sẽ tính toán nhanh hơn.

Cách chia nhiệm vụ không giới hạn? Bạn nhiệm vụ cụ thể được xử lý bởi IteratorSpliterator mà trySplit phương pháp tạo khối ngày càng tăng kích thước bắt đầu từ 1024. Bạn có thể thử bằng cách tự hỏi:

Spliterator<Integer> spliterator = Stream.iterate(200_000_000, n -> ++n).spliterator(); 
Spliterator[] spliterators = new Spliterator[10]; 
for(int i=0; i<spliterators.length; i++) { 
    spliterators[i] = spliterator.trySplit(); 
} 
for(int i=0; i<spliterators.length; i++) { 
    System.out.print((i+1)+": "); 
    spliterators[i].tryAdvance(System.out::println); 
}  

Vì vậy, đoạn đầu tiên xử lý số phạm vi 200,000,000-200.001.023, những con số xử lý thứ hai trong phạm vi 200001024-200003071, v.v. Nếu bạn chỉ có 1 chuỗi phần cứng, nhiệm vụ của bạn sẽ được chia thành hai phần, vì vậy 3072 sẽ được kiểm tra. Nếu bạn có 8 phần cứng, nhiệm vụ của bạn sẽ được chia thành 9 khối và 46080 số sẽ được kiểm tra. Chỉ sau khi tất cả các khối được xử lý thì tính toán song song sẽ dừng lại. Các heuristic chia tách các nhiệm vụ cho một khối lớn không hoạt động tốt trong trường hợp của bạn, nhưng bạn sẽ thấy hiệu suất tăng có những số nguyên tố xung quanh khu vực đó xuất hiện một lần trong vài nghìn con số.

Có lẽ kịch bản cụ thể của bạn có thể được tối ưu hóa nội bộ (tức là dừng tính toán nếu chuỗi đầu tiên phát hiện điều kiện giới hạn đó đã đạt được). Vui lòng báo cáo lỗi cho trình theo dõi lỗi Java.

---

Cập nhật sau khi đào hơn bên trong API Suối tôi kết luận rằng hành vi hiện tại là một lỗi, raised an issue và đăng một patch. Nó có khả năng là bản vá sẽ được chấp nhận cho JDK9 và thậm chí có thể quay trở lại nhánh JDK 8u. Với bản vá của tôi, phiên bản song song vẫn không cải thiện hiệu năng, nhưng ít nhất thời gian làm việc của nó có thể so sánh với thời gian làm việc theo tuần tự.

Answer 2

Lý do tại sao parallel suối dùng để lâu là do thực tế rằng tất cả các dòng song song sử dụng common fork-join thread pool và kể từ khi bạn đang gửi một nhiệm vụ chạy dài (vì thực hiện lại isPrime phương pháp là không hiệu quả), bạn đang chặn tất cả các chủ đề trong hồ bơi và kết quả là tất cả các tác vụ khác sử dụng luồng song song đều bị chặn.

Để làm cho phiên bản song song nhanh hơn, bạn có thể triển khai isPrime hiệu quả hơn. Ví dụ:

Predicate<Integer> isPrime = new Predicate<Integer>() { 
     @Override 
     public boolean test(Integer n) { 
      if(n < 2) return false; 
      if(n == 2 || n == 3) return true; 
      if(n%2 == 0 || n%3 == 0) return false; 
      long sqrtN = (long)Math.sqrt(n)+1; 
      for(long i = 6L; i <= sqrtN; i += 6) { 
       if(n%(i-1) == 0 || n%(i+1) == 0) return false; 
      } 
      return true; 
     } 
    }; 

Và ngay lập tức bạn sẽ thấy sự cải thiện về hiệu suất. Nói chung tránh sử dụng luồng song song khi có tồn tại khả năng chặn luồng trong hồ bơi