java - ¿Por qué los iteradores ascendentes ConcurrentSkipListSet son ''más rápidos'' que los descendientes?
collections iterator (2)
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''.
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?
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:
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).