Почему ConcurrentSkipListSet возрастает, итераторы "быстрее", чем нисходящие?

Ответ 1

Если вы посмотрите на страницу Википедии " Пропустить списки", вы увидите, что они представляют собой сложную форму связанного списка со ссылками, идущими в направлении упорядочения записей списка. (На диаграмме это ясно видно...)

Когда вы перемещаете список пропусков в прямом направлении, вы просто следуете ссылкам. Каждый next() вызов является операцией O (1).

Когда вы перемещаете список пропусков в обратном направлении, каждый next() вызов должен найти ключ перед возвратом последнего ключа. Это операция O (logN).

(Тем не менее, перемещение списка пропусков в обратном направлении по-прежнему значительно быстрее, чем перемещение одиночно связанного списка назад. Это будет O (N) для каждого next() вызова next()...)

Если вы посмотрите под капот, вы увидите, что ConcurrentSkipListSet на самом деле является оберткой для ConcurrentSkipListMap. В этом классе объекты Node в представлении списка пропусков карты образуют односвязные цепи... в направлении восходящего ключа. Из предыдущего следует, что возрастающая итерация быстрее, чем нисходящая итерация.

Разница в производительности будет значительной, и она станет более значительной по мере увеличения установленного размера из-за разности O (1) по сравнению с O (logN).

Ответ 2

В дополнение к ответу Стивена я написал простой контрольный показатель:

@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 который используется в восходящем и нисходящем итераторах соответственно:

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

Визуализация разницы в производительности: