Tốc độ phân bổ bộ nhớ danh sách luồng Java 8 vòng lặp với preallocation

Question

Tôi tự hỏi làm thế nào Java 8 stream xử lý cấp phát bộ nhớ nếu hoạt động đầu cuối là một bộ sưu tập danh sách.

Hãy xem xét ví dụ

List<Integer> result = myList.stream().map(doWhatever).collect(Collectors.toList()); 

vs

List<Integer> result = new ArrayList<>(myList.size()); 
for(String s : myList) { 
    result.add(doWhatever.apply(s)); 
} 

Trong trường hợp sử dụng một dòng suối, vẫn chưa biết cách lớn trong danh sách sẽ phát triển, có nghĩa là phải có một số loại phân bổ lại. Giả định này có đúng không?

Loại danh sách kết quả có một số loại danh sách được liên kết và cho phép truy cập chậm hơn vào các phần tử hơn ArrayList không?

Tôi có nên sử dụng các luồng có bộ sưu tập danh sách nếu tôi biết kích thước của danh sách kết quả từ đầu không?

Answer 1

Đằng sau những cảnh Collectors.toList() sẽ cho phép để thu thập các yếu tố kết quả của Stream của bạn thành một ArrayList tạo với constructor mặc định như vậy với công suất mặc định của 10 nên thực sự là một việc tái phân bổ sẽ được yêu cầu trong trường hợp kích thước vượt quá 10.

Nếu bạn muốn sử dụng triển khai khác nhau của List, hãy sử dụng toCollection(Supplier<C> collectionFactory) là bộ thu chung hơn cho phép cung cấp nhà máy của mục tiêu Collection.

Ví dụ, nếu bạn muốn thu thập các yếu tố vào một LinkedList thay vào đó bạn có thể viết lại mã của bạn như sau:

List<Integer> result = myList.stream() 
    .map(doWhatever) 
    .collect(Collectors.toCollection(LinkedList::new)); 

Giả sử rằng bạn muốn một ArrayList với công suất mặc định của 100, các nhà sưu tập sẽ là Collectors.toCollection(() -> new ArrayList<>(100)).

Answer 2

Nếu bạn xem mã nguồn cho Collectors.toList(), không có mã nào không phân bổ trước.

public static <T> Collector<T, ?, List<T>> toList() { 
     return new CollectorImpl<>((Supplier<List<T>>) ArrayList::new, List::add, 
           (left, right) -> { left.addAll(right); return left; }, 
           CH_ID); 
    } 

Nó chỉ tạo ra một mới ArrayList với kích thước mặc định, sau đó thay đổi kích thước trên lời gọi tiếp theo của add/addAll.

Answer 3

Collectors.toList() không chỉ định bất kỳ điều gì về việc triển khai. Nếu bạn quan tâm, hãy sử dụng toCollection(ArrayList::new).

Tôi có nên sử dụng các luồng có bộ sưu tập danh sách nếu tôi biết kích thước của danh sách kết quả từ đầu không?

Không, hãy tiếp tục và sử dụng chúng. Phân bổ là rẻ và chi phí là tối thiểu liên quan đến chiến thắng conciseness. Việc sắp xếp danh sách thường là một tối ưu hóa sớm.

Answer 4

Trong trường hợp sử dụng luồng, không biết danh sách sẽ lớn đến mức nào, có nghĩa là phải có một số loại phân bổ lại. Giả định này có đúng không?

Nó biết đường ống trước đó, kích thước của nó và tạo ra một ArrayList<> với cấu hình mặc định không nhìn vào đó. Nó không quan trọng khi bạn đang làm việc với một mảng được tối ưu hóa động.

Là loại danh sách kết quả một số loại danh sách được liên kết và cho phép truy cập chậm hơn vào các phần tử hơn ArrayList?

Một ArrayList được sử dụng bởi mặc định, nhưng bạn có thể tự do cung cấp nhà cung cấp và ác quy của riêng bạn để thay đổi hành vi này:

stream.collect(() -> new ArrayList<>(SIZE), ArrayList::add, ArrayList::addAll); 

nên tôi không sử dụng con suối với nhà sưu tập danh sách nếu tôi biết kích thước của danh sách kết quả ngay từ đầu?

Đừng nghĩ về điều đó. Cùng với cú pháp súc tích, API luồng cung cấp nhiều thứ mạnh mẽ (như song song) mà bạn có thể sử dụng.

Answer 5

Hiện nay, các nhà sưu tập toList() được thực hiện bằng cách sử dụng và trả lại một ArrayList (lưu ý rằng container được sử dụng trong bộ sưu tập không phải lúc nào cũng phải phù hợp với loại kết quả cuối cùng của). Cách này, giao diện thu thập được xác định, bộ thu không có khả năng định cỡ trước danh sách. Nhưng về nguyên tắc, do việc triển khai Stream chuẩn và việc triển khai thu thập toList() được xác định trước là một phần của cùng một thư viện, có thể có một giao tiếp không chuẩn trong các triển khai trong tương lai (hoặc các JRE thay thế) trong đó luồng phát hiện bộ thu toList() phương thức collect và thực hiện thao tác được tối ưu hóa. Nhưng khi sử dụng bộ thu toList(), ví dụ: với tư cách là người thu gom ở hạ lưu của bộ sưu tập groupingBy, không có kích thước có thể dự đoán được.

Nếu bạn cho rằng con suối có thể dự đoán kích thước của nó, giống như trong myList.stream().map(doWhatever) ví dụ của bạn, giải pháp hiệu quả nhất, do việc thực hiện hiện nay, là

List<ElementType> result=Arrays.asList(stream.toArray(ElementType[]::new)); 

như hoạt động sẽ sử dụng các kích thước được biết đến, ngay cả trong song song, hoặc đặc biệt là khi được sử dụng với luồng song song khi có thể dự đoán được kích thước phụ, do không có bước hợp nhất, nghĩa là tất cả công nhân sẽ ghi trực tiếp vào mảng kết quả.

Thật không may, nếu ElementType không phải là loại có thể xác minh lại, bạn phải sử dụng thao tác không được kiểm tra tại đây.

Nếu kích thước không thể dự đoán được, giải pháp này có thể vẫn hiệu quả hơn so với bộ thu toList() hiện tại, nhưng có thể bị mất so với triển khai trong tương lai có thể sử dụng bộ nhớ phi tuyến tính.

---

Vì vậy, biến thể được tối ưu hóa chỉ phù hợp với một thiết lập nhất định. Đối với hầu hết các kịch bản, bộ thu toList() là đủ hoặc thậm chí có thể tốt hơn bất kỳ sự thay thế nào trong các triển khai có thể trong tương lai.

Answer 6

Đối với các luồng lớn song song, tôi thấy rằng toList() thực sự có vấn đề về hiệu suất nghiêm trọng vì danh sách các bộ tích lũy được lặp lại nhiều lần - dẫn đến cái gì đó giống O (N^2) hơn O (N).

Dưới đây là một ToList thay thế() Collector chứa dữ liệu trong một ConcurrentLinkedQueue cho đến giai đoạn kết thúc - cho một dòng suối 400.000 yếu tố, thời gian hoạt động thu gom đi từ 1500ms xuống còn khoảng 30:

http://pastebin.com/Bi93uig6