为什么 ConcurrentSkipListSet 升序迭代器 'faster' 而不是降序迭代器？

Question

我在 ConcurrentSkipListSet 上使用 descendingIterator 方法。我刚刚查看了文档并注意到以下评论：

“升序视图及其迭代器比降序视图更快。”

见https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListSet.html#descendingIterator--

遗憾的是，它没有提供任何关于此的更多信息。有什么样的性能差异？重要吗？为什么会有性能差异？

Answer 1

如果您查看 Skip Lists 的 Wikipedia 页面，您会发现它们实际上是一种复杂的链表形式，链接指向列表条目的排序方向。（图表清楚地说明了这一点......）

当您向前遍历跳过列表时，您只是在跟踪链接。每个 next() 调用都是一个 O(1) 操作。

当您反向遍历跳过列表时，每个 next() 调用都必须在返回的最后一个键之前找到键 。这是一个 O(logN) 操作。

（但是，向后遍历跳跃列表仍然比向后遍历单链表快得多。对于每个 next() 调用，这将是 O(N) ...）

如果您深入了解，您会发现 ConcurrentSkipListSet 实际上是 ConcurrentSkipListMap 的包装器。在 class 中，地图的跳过列表表示中的 Node 对象形成单链……在升序键方向上。它遵循（从之前的）升序迭代比降序迭代更快。

性能差异将是显着的，并且由于 O(1) 与 O(logN) 的差异，随着集合大小的增加，性能差异将变得更加显着。

Answer 2

除了Stephen的回答，我写了一个简单的Benchmark：

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@State(Scope.Thread)
public class ConcurrentSkipListSetIteratorTest {

    @Fork(1)
    @Benchmark
    public void ascItr(SetupParams params) {
        Iterator<Integer> itr = params.cslset.iterator();
        while (itr.hasNext()) itr.next();
    }

    @Fork(1)
    @Benchmark
    public void dscItr(SetupParams params) {
        Iterator<Integer> itr = params.cslset.descendingIterator();
        while (itr.hasNext()) itr.next();
    }

    @State(Scope.Benchmark)
    public static class SetupParams {

        private ConcurrentSkipListSet<Integer> cslset;

        @Setup(Level.Invocation)
        public void setUp() {
            cslset = new SplittableRandom()
                .ints(100_000, 0, 100_000)
                .boxed()
                .collect(Collectors.toCollection(ConcurrentSkipListSet::new));
        }
    }
}

主要方法：

public static void main(String[] args) throws RunnerException {
    Options opt = new OptionsBuilder()
        .include(ConcurrentSkipListSetIteratorTest.class.getSimpleName())
        .jvmArgs("-ea", "-Xms512m", "-Xmx1024m")
        .shouldFailOnError(true)
        .build();
    new Runner(opt).run();
}

此外，这里是 JDK 10 repository 中适当用于升序和降序迭代器的代码示例：

private void ascend() {
    ...
    for (;;) {
        // there is a link to the next node
        next = next.next; // O(1) operation
        ...
    }
}

private void descend() {
    ...
    for (;;) {
        // but, there is no link to the previous node
        next = m.findNear(lastReturned.key, LT, cmp); // O(logN) operation
        ...
    }
}

10_000 个元素的最终结果：

Benchmark  Mode  Cnt  Score   Error  Units
ascItr     avgt    5  0,075 ± 0,029  ms/op
dscItr     avgt    5  0,810 ± 0,116  ms/op

对于 100_000 个元素：

Benchmark  Mode  Cnt   Score   Error  Units
ascItr     avgt    5   2,764 ± 1,160  ms/op
dscItr     avgt    5  11,110 ± 0,937  ms/op

可视化性能差异：

为什么 ConcurrentSkipListSet 升序迭代器 'faster' 而不是降序迭代器？

Why are ConcurrentSkipListSet ascending Iterators 'faster' than descending ones?

java

collections

iterator

java.util.concurrent