什么是Java parallelStream最有效的List-Type？

Question

我有一个List<String> toProcess我想进一步处理的

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

哪个是最佳列表类型(如LinkedList,ArrayList等),以便从多线程中获得最佳速度的初始列表？

附加信息:预期的元素计数范围大小为10 ^ 3-10 ^ 5,但单个元素可以变得相当大(10 ^ 5-10 ^ 6个字符).

---

另外我可以在String[]所有地方使用,因为字符串的数量保证不会改变(结果将包含与toProcess一样多的元素).

---

无论哪种方式,我必须在最后按顺序迭代所有元素.目前我使用foreach-loop来组合最终结果.这可以很容易地改为常规for循环.

Answer 1

如果您确定输出元素的数量等于输入元素的数量,并且您对结果满意,那么肯定使用toArray而不是收集器.如果管道始终具有固定大小,则目标阵列将预先分配正确的大小,并行操作将其结果直接存入正确位置的目标阵列:无复制,重新分配或合并.

如果你想要a List,你总是可以使用包装结果Arrays.asList,但当然你不能在结果中添加或删除元素.

收藏家

如果上述条件之一不成立,那么您需要与收藏家打交道,这些收藏家有不同的权衡.

收集器通过以线程限制的方式操作中间结果来并行工作.然后将中间结果合并到最终结果中.有两种操作需要考虑:1)将各个元素累积到中间结果中,以及2)将中间结果合并(或组合)成最终结果.

在LinkedList和之间ArrayList,它可能ArrayList会更快,但你应该对此进行基准测试以确定.请注意默认情况下Collectors.toList使用ArrayList,尽管在将来的版本中可能会更改.

链表

正在累积的每个元素(LinkedList.add)涉及分配新的列表节点并将其挂钩到列表的末尾.将节点挂钩到列表非常快,但这涉及到每个单个流元素的分配,这可能会随着累积的进行而产生较小的垃圾收集.

合并(LinkedList.addAll)也非常昂贵.第一步是将源列表转换为数组; 这是通过循环遍历列表的每个节点并将元素存储到临时数组中来完成的.然后,代码遍历此临时数组,并将每个元素添加到目标列表的末尾.如上所述,这导致为每个元素分配新节点.因此合并操作非常昂贵,因为它遍历源列表中的每个元素两次并且导致每个元素的分配,这可能引入垃圾收集开销.

数组列表

每个元素的累积通常涉及将其附加到包含在其中的数组的末尾ArrayList.这通常非常快,但如果数组已满,则必须重新分配并复制到更大的数组中.增长策略ArrayList是将新数组分配为比当前数组大50%,因此重新分配与添加的元素数量的对数成比例,这也不算太糟糕.但是,必须复制所有元素,这意味着可能需要多次复制早期元素.

合并一个ArrayList可能比它便宜得多LinkedList.将数据转换ArrayList为数组涉及从源到临时数组的元素的批量复制(不是一次一个).必要时调整目标数组的大小(在这种情况下很可能),需要所有元素的批量副本.然后将源元素从临时数组批量复制到目标,该目标已预先调整大小以容纳它们.

讨论

考虑到上述情况,它似乎ArrayList会更快LinkedList.然而,即使收集到一个ArrayList需要一些不必要的重新分配和复制许多元素,可能需要几次.潜在的未来优化将用于Collectors.toList将元素累积到针对快速附加访问而优化的数据结构中,优选地已经预先调整大小以容纳预期数量的元素的数据结构.支持快速合并的数据结构也是可能的.

如果你需要做的就是遍历最终结果,那么滚动你自己的具有这些属性的数据结构应该不会太困难.如果它不需要是一个完整的列表,那么应该可以进行重大的简化.它可以累积到预先调整大小的列表中以避免重新分配,并且合并将简单地将它们收集到树结构或列表列表中.请参阅JDK的SpinedBuffer(私有实现类)以获取想法.