什么是Java parallelStream中最高效的列表类型？

Question

我有一个 List<String> toProcess，我想进一步处理它。

toProcess.parallelStream().map(/*some function*/).collect(Collectors.toList());

哪种列表类型（例如LinkedList、ArrayList等）是用于多线程时获得最佳速度的初始列表？

额外信息：预期元素数量范围在10^3-10^5之间，但单个元素可能会变得很大（10^5-10^6个字符）。

或者我可以在所有地方使用String[]，因为字符串的数量保证不会改变（results将包含与toProcess相同数量的元素）。

无论哪种方式，最终都必须按顺序迭代所有元素。目前我使用foreach循环来组装最终结果。这可以很容易地更改为常规for循环。

- JFBM

---

OT，但很有意思：http://zeroturnaround.com/rebellabs/java-parallel-streams-are-bad-for-your-health/ - Thomas Junk

@ThomasJunk 幸运的是，我的程序唯一目的就是将一个方法应用于一堆字符串，并将组装后的输出写入文件。但还是谢谢，这教会了我小心处理Java-8和Web应用程序。 - JFBM

我会随便选一个列表并进行基准测试，然后尝试几种其他类型，看看是否有任何区别。 - Brendan Long

Answer 1

如果您确定输出元素的数量等于输入元素的数量，并且您满意使用数组作为结果，那么一定要使用toArray而不是收集器。如果管道在整个过程中具有固定的大小，则目标数组将预先分配正确的大小，并且并行操作将其结果直接存储到目标数组的正确位置：无需复制、重新分配或合并。

如果您想要一个List，则可以始终使用Arrays.asList包装结果，但是当然不能向结果添加或删除元素。 收集器 如果上述条件之一不成立，则需要处理收集器，它们具有不同的权衡。

收集器通过以线程限制的方式在中间结果上操作来并行工作。然后将中间结果合并到最终结果中。有两个操作需要考虑：1）将单个元素累积到中间结果中，2）将中间结果合并（或组合）到最终结果中。

在LinkedList和ArrayList之间，ArrayList很可能更快，但您应该进行基准测试以确保。请注意，Collectors.toList默认使用ArrayList，尽管这可能会在未来版本中更改。 LinkedList 每个被累加的元素(LinkedList.add)都涉及分配一个新的列表节点并将其连接到列表的末尾。将节点连接到列表非常快，但这涉及为每个单独的流元素分配内存，这可能会在累积过程中产生轻微的垃圾收集。

合并(LinkedList.addAll)也非常昂贵。第一步是将源列表转换为数组；这是通过循环遍历列表的每个节点并将元素存储到临时数组中来完成的。然后，代码遍历此临时数组，并将每个元素添加到目标列表的末尾。如上所述，这会导致为每个元素分配一个新节点。因此，合并操作非常昂贵，因为它两次迭代源列表中的每个元素，并为每个元素分配内存，这可能会引入垃圾收集开销。 ArrayList 每个元素的累加通常涉及将其附加到ArrayList中包含的数组的末尾。这通常非常快，但如果数组已满，则必须重新分配并复制到更大的数组中。 ArrayList的增长策略是将新数组分配为当前数组的50％以上，因此重新分配与添加的元素数量的对数成比例，这不太糟糕。但是，所有元素都必须复制过去，这意味着早期的元素可能需要多次复制。

合并一个 ArrayList 可能比 LinkedList 更便宜。将 ArrayList 转换为数组涉及从源中批量复制（而不是逐个复制）元素到临时数组中。如果需要，目标数组将调整大小（在这种情况下很可能），需要批量复制所有元素。然后，源元素从临时数组批量复制到已经预先调整大小以容纳它们的目标中。

讨论

根据上述内容，似乎 ArrayList 比 LinkedList 快。但是，即使收集到 ArrayList 中也需要一些不必要的重新分配和复制多个元素，可能会进行多次。潜在的未来优化是，Collectors.toList 积累元素到一个针对快速追加访问进行了优化的数据结构中，最好是一个已经预先调整大小以容纳预期元素数量的数据结构。支持快速合并的数据结构也是一种可能性。

如果您只需要遍历最终结果，那么编写具有这些属性的自定义数据结构应该不太困难。如果它不需要成为完整的列表，那么可以积累到预先调整大小的列表中以避免重新分配，并且合并将简单地将它们聚集到树结构或列表中。请参见 JDK 的 SpinedBuffer（一个私有实现类）以获取想法。

- Stuart Marks

---

我认为让Collectors.toList在内部使用SpinedBuffer应该是一个简单的改变（当前版本中它没有这样做相当令人惊讶），然而，使用适当容量预分配列表非常困难，因为Collector API缺乏一种允许Stream告诉Collector所需容量的方法... - Holger

如果Java提供了一种内部方法来在常数时间内连接两个LinkedList列表，那么LinkedList的故事似乎会更好。我想知道为什么他们没有这样做？ - Brandon

@BrandonMintern java.util.concurrent 包中有 BlockingQueue.drainTo() 方法，它似乎具有正确的语义：元素从源中移除并在单个操作中添加到目标中。然而，LinkedList 没有实现 BlockingQueue 接口。因此，专注于快速合并的数据结构（例如 SpinedBuffer）可能更加有前途。 - Stuart Marks

Answer 2

考虑到上下文切换的成本，以及多线程的一般性质，切换到不同类型的列表所带来的性能提升通常是微不足道的。即使你使用次优的列表 - 也不会有太大影响。

^{如果您真的很在意，那么由于缓存局部性，ArrayList 可能 做得更好，但这要视情况而定。}

- Benjamin Gruenbaum

---

你不情愿的回答“ArrayList”是正确的，但你错过了更重要的部分。是的，局部性很重要，但这主要是单线程思维; 在评估并行算法的可扩展性时，您非常关心源代码可以被递归地有效地拆分的程度。ArrayList在这方面也表现出色，所以你的答案是正确的，但大多数原因是错误的。 - Brian Goetz

我所指的缓存局部性是将数组分割成N个位用于N个线程，使得所有N个线程都可以将该数组保留在缓存中。我的勉强回答无论如何都不相关，因为那些不是缓存遗忘算法的算法看起来根本不像这样 - 它们很少用Java（或任何其他不能让你指定内存布局的语言）编写，并且它们肯定不使用.parallelStream（顺便说一下 - 我喜欢.parallelStream，因为它非常方便地实现并行化）。 - Benjamin Gruenbaum

Answer 3

一般来说，与LinkedList相比，ArrayList更易于并行化，因为数组容易被分割成几个部分交给每个线程处理。

然而，如果你的终端操作是将结果写入文件，则并行化可能不会对你有任何帮助，因为你很可能会受到I/O限制而不是CPU限制。

- Misha