java - Spliterator 什么时候应该停止 split ？

Question

我明白 there is overhead in setting up并行 Stream 的处理，如果项目很少或每个项目的处理速度很快，则单线程中的处理速度更快。

但是，trySplit() 是否有类似的阈值？ ，将问题分解成更小的 block 会适得其反吗？我正在类比最小块的合并排序切换到插入排序。

如果是这样，阈值是否取决于 trySplit() 和 consuming 的相对成本tryAdvance() 过程中的项目？考虑一个比推进数组索引复杂得多的拆分操作——例如，拆分一个按词法排序的多集排列。是否有约定让客户在创建并行流时指定拆分的下限，具体取决于消费者的复杂性？ Spliterator 可以用来估计下限本身的启发式方法吗？

或者，让 Spliterator 的下限为 1 并让工作窃取算法负责选择是否继续拆分是否总是安全的？

Answer 1

通常，您不知道传递给 tryAdvance 或 forEachRemaining 的消费者完成了多少工作。流管道和 FJP 都不知道这一点，因为它取决于用户提供的代码。它可以比拆分过程快得多或慢得多。例如，您可能有两个元素的输入，但每个元素的处理需要一个小时，因此拆分此输入是非常合理的。

我通常会尽可能多地拆分输入。可以使用三个技巧来改进拆分:

1. 如果很难均匀分割，但您可以跟踪(或至少粗略估计)每个子部分的大小，请随意不均匀分割。流实现将为更大的部分做更多的进一步拆分。不要忘记 SIZED 和 SUBSIZED 特性。

2. 将拆分的困难部分移至下一个 tryAdvance/forEachRemaining 调用。例如，假设您有已知数量的排列，并且在 trySplit 中您将跳转到其他排列。像这样:

   public class MySpliterator implements Spliterator<String> {
       private long position;
       private String currentPermutation;
       private final long limit;
   
       MySpliterator(long position, long limit, String currentPermutation) {
           this.position = position;
           this.limit = limit;
           this.currentPermutation = currentPermutation;
       }
   
       @Override
       public Spliterator<String> trySplit() {
           if(limit - position <= 1)
               return null;
           long newPosition = (position+limit)>>>1;
           Spliterator<String> prefix = 
                    new MySpliterator(position, newPosition, currentPermutation);
           this.position = newPosition;
           this.currentPermutation = calculatePermutation(newPosition); // hard part
           return prefix;
       }
   
       ...
   }
   

   将困难的部分移至下一个 tryAdvance 调用，如下所示:

   @Override
   public Spliterator<String> trySplit() {
       if(limit - position <= 1)
           return null;
       long newPosition = (position+limit)>>>1;
       Spliterator<String> prefix = 
                new MySpliterator(position, newPosition, currentPermutation);
       this.position = newPosition;
       this.currentPermutation = null;
       return prefix;
   }
   
   @Override
   public boolean tryAdvance(Consumer<? super String> action) {
       if(currentPermutation == null)
           currentPermutation = calculatePermutation(position); // hard part
       ...
   }
   

   这样困难的部分也将与前缀处理并行执行。

3. 如果当前拆分器中剩余的元素不多(例如，少于 10 个)并且请求拆分，则最好只前进到一半的元素，将它们收集到数组中，然后创建此前缀的基于数组的拆分器(类似于它在 AbstractSpliterator.trySplit() 中的完成方式)。您可以在这里控制所有代码，因此您可以提前测量正常 trySplit 比 tryAdvance 慢多少，并估计何时应该切换到基于数组的拆分的阈值。