Почему ConcurrentSkipListSet восходящих итераторов «быстрее», чем нисходящих? - PullRequest
0 голосов
/ 07 июня 2018

Я использую метод downndingIterator для ConcurrentSkipListSet.Я только что проверил документацию и заметил следующий комментарий:

'По возрастанию упорядоченные представления и их итераторы быстрее, чем по убыванию.'

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

К сожалению, он не предоставляет больше информации по этому вопросу.Какая разница в производительности?это важно?и почему разница в производительности?

Ответы [ 2 ]

0 голосов
/ 07 июня 2018

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

@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

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

enter image description here

0 голосов
/ 07 июня 2018

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

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

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

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

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

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

...