3

我最近发现了一个错误，其中

StreamSupport.intStream(/* a Spliterator.ofInt */, true)
    .limit(20)

被调用Spliterator.ofInt.tryAdvance超过 20 次。当我将其更改为

StreamSupport.intStream(/* a Spliterator.ofInt */, true)
    .sequential()
    .limit(20)

问题消失了。为什么会这样？tryAdvance当有副作用时，有什么方法可以对并行流进行严格限制，而不是在Spliterator? （这是为了测试一些返回无限流的方法，但是测试需要在没有“X 毫秒循环”构造的复杂情况下达到最终结束。）

4

3 回答 3

4

limit关于如何以及trySplit应该如何交互似乎存在根本性的误解。不应该有trySplit比指定更多的调用的假设limit是完全错误的。

的目的trySplit是将源数据分成两部分，在最好的情况下分成两半，因为应该trySplit尝试平衡拆分。因此，如果您有一个包含 100 万个元素的源数据集，则成功的拆分会生成两个源数据集，每个数据集包含 50 万个元素。limit(20)这与您可能已应用于流完全无关，除了我们事先知道，如果拆分器具有SIZED|SUBSIZED特征，我们可以删除第二个数据集，因为请求的前20 个元素只能在第一个中找到五十万。

很容易计算出，在最好的情况下，即平衡拆分，我们已经需要 15 次拆分操作，每次都删除上半部分，然后才能在前 20 个元素之间进行拆分，以便我们处理前 20 个元素元素并行。

这可以很容易地证明：

class DebugSpliterator extends Spliterators.AbstractIntSpliterator {
    int current, fence;
    DebugSpliterator() {
        this(0, 1_000_000);
    }
    DebugSpliterator(int start, int end) {
        super(end-start, ORDERED|SIZED|SUBSIZED);
        current = start;
        fence = end;
    }
    @Override public boolean tryAdvance(IntConsumer action) {
        if(current<fence) {
            action.accept(current++);
            return true;
        }
        return false;
    }
    @Override public OfInt trySplit() {
        int mid = (current+fence)>>>1;
        System.out.println("trySplit() ["+current+", "+mid+", "+fence+"]");
        return mid>current? new DebugSpliterator(current, current=mid): null;
    }
}

StreamSupport.stream(new DebugSpliterator(), true)
    .limit(20)
    .forEach(x -> {});

在我的机器上，它打印：

trySplit() [0, 500000, 1000000]
trySplit() [0, 250000, 500000]
trySplit() [0, 125000, 250000]
trySplit() [0, 62500, 125000]
trySplit() [0, 31250, 62500]
trySplit() [0, 15625, 31250]
trySplit() [0, 7812, 15625]
trySplit() [0, 3906, 7812]
trySplit() [0, 1953, 3906]
trySplit() [0, 976, 1953]
trySplit() [0, 488, 976]
trySplit() [0, 244, 488]
trySplit() [0, 122, 244]
trySplit() [0, 61, 122]
trySplit() [0, 30, 61]
trySplit() [0, 15, 30]
trySplit() [15, 22, 30]
trySplit() [15, 18, 22]
trySplit() [15, 16, 18]
trySplit() [16, 17, 18]
trySplit() [0, 7, 15]
trySplit() [18, 20, 22]
trySplit() [18, 19, 20]
trySplit() [7, 11, 15]
trySplit() [0, 3, 7]
trySplit() [3, 5, 7]
trySplit() [3, 4, 5]
trySplit() [7, 9, 11]
trySplit() [4, 4, 5]
trySplit() [9, 10, 11]
trySplit() [11, 13, 15]
trySplit() [0, 1, 3]
trySplit() [13, 14, 15]
trySplit() [7, 8, 9]
trySplit() [1, 2, 3]
trySplit() [8, 8, 9]
trySplit() [5, 6, 7]
trySplit() [14, 14, 15]
trySplit() [17, 17, 18]
trySplit() [11, 12, 13]
trySplit() [12, 12, 13]
trySplit() [2, 2, 3]
trySplit() [10, 10, 11]
trySplit() [6, 6, 7]

当然，这远远超过 20 次拆分尝试，但完全合理，因为必须拆分数据集，直到我们在所需目标范围内有子范围才能并行处理它。

我们可以通过删除导致此执行策略的元信息来强制执行不同的行为：

StreamSupport.stream(new DebugSpliterator(), true)
    .filter(x -> true)
    .limit(20)
    .forEach(x -> {});

由于 Stream API 不知道谓词的行为，因此管道失去了它的SIZED特性，导致

trySplit() [0, 500000, 1000000]
trySplit() [500000, 750000, 1000000]
trySplit() [500000, 625000, 750000]
trySplit() [625000, 687500, 750000]
trySplit() [625000, 656250, 687500]
trySplit() [656250, 671875, 687500]
trySplit() [0, 250000, 500000]
trySplit() [750000, 875000, 1000000]
trySplit() [250000, 375000, 500000]
trySplit() [0, 125000, 250000]
trySplit() [250000, 312500, 375000]
trySplit() [312500, 343750, 375000]
trySplit() [125000, 187500, 250000]
trySplit() [875000, 937500, 1000000]
trySplit() [375000, 437500, 500000]
trySplit() [125000, 156250, 187500]
trySplit() [250000, 281250, 312500]
trySplit() [750000, 812500, 875000]
trySplit() [281250, 296875, 312500]
trySplit() [156250, 171875, 187500]
trySplit() [437500, 468750, 500000]
trySplit() [0, 62500, 125000]
trySplit() [875000, 906250, 937500]
trySplit() [62500, 93750, 125000]
trySplit() [812500, 843750, 875000]
trySplit() [906250, 921875, 937500]
trySplit() [0, 31250, 62500]
trySplit() [31250, 46875, 62500]
trySplit() [46875, 54687, 62500]
trySplit() [54687, 58593, 62500]
trySplit() [58593, 60546, 62500]
trySplit() [60546, 61523, 62500]
trySplit() [61523, 62011, 62500]
trySplit() [62011, 62255, 62500]

这显示了较少trySplit的调用，但没有改进；查看数字显示现在超出了结果元素范围的范围（如果我们使用我们的知识，所有元素都将通过过滤器）被处理，更糟糕的是，结果元素的范围完全被单个拆分器覆盖，导致没有并行处理我们的结果元素，所有其他线程都是处理之后被丢弃的元素。

当然，我们可以通过改变

int mid = (current+fence)>>>1;

至

int mid = fence>20? 20: (current+fence)>>>1;

所以

StreamSupport.stream(new DebugSpliterator(), true)
    .limit(20)
    .forEach(x -> {});

结果是

trySplit() [0, 20, 1000000]
trySplit() [0, 10, 20]
trySplit() [10, 15, 20]
trySplit() [10, 12, 15]
trySplit() [12, 13, 15]
trySplit() [0, 5, 10]
trySplit() [15, 17, 20]
trySplit() [5, 7, 10]
trySplit() [0, 2, 5]
trySplit() [17, 18, 20]
trySplit() [2, 3, 5]
trySplit() [5, 6, 7]
trySplit() [15, 16, 17]
trySplit() [6, 6, 7]
trySplit() [16, 16, 17]
trySplit() [0, 1, 2]
trySplit() [7, 8, 10]
trySplit() [8, 9, 10]
trySplit() [1, 1, 2]
trySplit() [3, 4, 5]
trySplit() [9, 9, 10]
trySplit() [18, 19, 20]
trySplit() [10, 11, 12]
trySplit() [13, 14, 15]
trySplit() [11, 11, 12]
trySplit() [4, 4, 5]
trySplit() [14, 14, 15]

但这不是一个通用的分离器，但如果限制不是 20，它的性能就会很差。

如果我们可以将限制合并到拆分器中，或者更一般地说，合并到流源中，我们就不会有这个问题。因此list.stream().limit(x)，您可以调用list.subList(0, Math.min(x, list.size())).stream()，而不是random.ints().limit(x)，使用random.ints(x)，而不是Stream.generate(generator).limit(x)您可以使用或使用此答案LongStream.range(0, x).mapToObj( index -> generator.get())的工厂方法。

对于任意流源/拆分器，应用limit对于并行流来说可能非常昂贵，这甚至被记录在案。好吧，首先产生副作用trySplit是一个坏主意。

于 2017-10-04T08:52:32.653 回答
2

我不认为这是一个错误，但仍然是一个非常有趣的想法，tryAdvance可能会产生副作用。

据我了解，当您trySplit拆分为单个元素批次时，这完全有可能。

例如，您有一个数组，并且您想将它（通过trySplit）拆分为子数组的多个部分，每个子数组不少于 4 个元素。在这种情况下，当您无法再拆分时（Spliterator例如，当前至少有 4 个元素），何时开始处理 -forEachRemaning将被调用；反过来，它将默认调用tryAdvancecurrent 中的每个元素Spliterator，如默认实现所示：

default void forEachRemaining(Consumer<? super T> action) {
    do { } while (tryAdvance(action));
}

显然，由于您正在并行工作 - 一旦 Thread 开始工作（读取executing it's forEachRemaning），它就不能再停止了 - 会有更多元素命中tryAdvance。

因此，除了将其集成到自身之外，我真的认为没有其他方法可以做到这一点Spliterator；我认为这应该有效：

  static class LimitingSpliterator<T> implements Spliterator<T> {

    private int limit;

    private final Supplier<T> generator;

    private LimitingSpliterator(Supplier<T> generator, int limit) {
        this.limit = limit;
        this.generator = generator;
    }

    static <T> LimitingSpliterator<T> of(Supplier<T> supplier, int limit) {
        return new LimitingSpliterator<>(supplier, limit);
    }

    @Override
    public boolean tryAdvance(final Consumer<? super T> consumer) {
        Objects.requireNonNull(consumer);
        if (limit > 0) {
            --limit;
            generator.get();
            consumer.accept(generator.get());
            return true;
        }
        return false;
    }

    @Override
    public void forEachRemaining(final Consumer<? super T> consumer) {
        while (limit > 0) {
            consumer.accept(generator.get());
            --limit;
        }
    }

    @Override
    public LimitingSpliterator<T> trySplit() {
        int half = limit >> 2;
        limit = limit - half;
        return new LimitingSpliterator<>(generator, half);
    }

    @Override
    public long estimateSize() {
        return limit << 2;
    }

    @Override
    public int characteristics() {
        return SIZED;
    }
}
于 2017-10-03T08:51:38.047 回答
0

对于我的用例，解决方案是使用： LongStream.range(0, streamSize).unordered().parallel().mapToInt(ignored -> nextInt()) 注意：这是用于来自 PRNG 的随机数流，可能会不断重新播种。

于 2018-08-13T20:19:51.837 回答