Spliterator什么时候应该停止分裂？

Question

我知道设置并行处理会有开销,Stream如果项目很少或者每个项目的处理速度很快,单个线程中的处理速度会更快.

但是,是否存在类似的阈值trySplit(),将问题分解为较小的块会产生相反的效果？我在想类似于合并排序切换到最小块的插入排序.

如果是这样,阈值是否取决于过程中物品的相对成本trySplit()和消耗tryAdvance()？例如,考虑一个分裂操作,它比推进数组索引要复杂得多 - 分割一个词法排序的多集排列.是否存在允许客户在创建并行流时指定拆分下限的约定,具体取决于其使用者的复杂程度？启发式Spliterator可以用来估计下限本身吗？

或者,或者,让a的下限为Spliterator1 是否总是安全的,让工作窃取算法负责选择是否继续拆分？

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并在应切换到基于数组的拆分时估算阈值。