java - ¿Por qué los iteradores ascendentes ConcurrentSkipListSet son ''más rápidos'' que los descendientes?

collections iterator

Question

Estoy usando el método descendingIterator en ConcurrentSkipListSet. Acabo de revisar la documentación y noté el siguiente comentario:

''Las vistas ordenadas ascendentes y sus iteradores son más rápidas que las descendientes''.

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

Lamentablemente no proporciona más información sobre esto. ¿Qué tipo de diferencia de rendimiento hay? es significativo? ¿Y por qué hay una diferencia de rendimiento?

Answer 1

Además de la respuesta de Stephen, escribí un punto de referencia simple:

@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));
        }
    }
}

Método principal:

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();
}

Además, aquí hay un ejemplo de código del repository JDK 10 que se utiliza en los iteradores ascendentes y descendentes de manera apropiada:

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
        ...
    }
}

Resultados finales para 10_000 elementos:

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

Y para los 100_000 elementos:

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

Visualización de la diferencia de rendimiento:

Answer 2

Si mira la página de Wikipedia para Saltar listas , verá que efectivamente son una forma complicada de lista enlazada con los enlaces que van en la dirección de un orden de las entradas de la lista. (El diagrama ilustra esto claramente ...)

Cuando recorre la lista de saltos en la dirección de avance, simplemente está siguiendo los enlaces. Cada llamada next() es una operación O (1).

Cuando recorre la lista de omisión en la dirección inversa, cada llamada next() debe encontrar la clave antes de devolver la última clave. Esta es una operación O (logN).

(Sin embargo, desplazar una lista de omisión hacia atrás es aún sustancialmente más rápido que atravesar una lista enlazada de forma individual hacia atrás. Eso sería O (N) para cada next() llamada ...)

Si mira debajo del capó, verá que un ConcurrentSkipListSet es en realidad un envoltorio para un ConcurrentSkipListMap . En esa clase, los objetos Node en la representación de lista de omisión del mapa forman cadenas enlazadas individualmente ... en la dirección de la llave ascendente. De lo anterior se deduce que la iteración ascendente es más rápida que la iteración descendente.

La diferencia de rendimiento será significativa y se volverá más significativa a medida que aumente el tamaño del conjunto debido a la diferencia O (1) frente a O (logN).