Skip List vs Árbol de Búsqueda Binario

En primer lugar, no se puede comparar de manera justa una estructura de datos aleatoria con una que le da garantías en el peor de los casos.

Una lista de saltos es equivalente a un árbol de búsqueda binario equilibrado aleatoriamente (RBST) de la manera que se explica con más detalle en Dean y Jones "Explorando la Dualidad entre las Listas de Saltos y los Árboles de Búsqueda Binarios".

Al revés, también puede tener listas de exclusión deterministas que garantizan el peor rendimiento del caso, cf. Munro et al.

En contra de lo que algunos afirman anteriormente, puede tener implementaciones de árboles de búsqueda binarios (BST) que funcionan bien en la programación concurrente. Un problema potencial con los BSTs centrados en la concurrencia es que no puede obtener fácilmente las mismas garantías de equilibrio que obtendría de un árbol rojo-negro (RB). (Pero" estándar", es decir, randomzided, saltar listas no le dan estas garantías tampoco.) Hay un equilibrio entre mantener el equilibrio en todo momento y bueno (y fácil de programar) acceso concurrente, por lo que relajado los árboles RB se utilizan generalmente cuando se desea una buena concurrencia. La relajación consiste en no reequilibrar el árbol de inmediato. Para una encuesta algo anticuada (1998) ver Hanke "The Performance of Concurrent Red-Black Tree Algorithms" [ps.gz] .

Una de las mejoras más recientes en estos es el llamado árbol cromático (básicamente tienes algo de peso tal que el negro sería 1 y el rojo sería cero, pero también permites valores intermedios). ¿Y cómo le va a un árbol cromático contra la lista de saltos? Veamos lo que Brown et al. "A General Technique for Non-blocking Trees" (2014) tienen que decir:

Con 128 hilos, nuestro algoritmo supera a la lista de esquí no bloqueante de Java por 13% a 156%, el árbol AVL basado en lock de Bronson et al. en 63% a 224%, y un RBT que usa memoria transaccional de software (STM) en 13 a 134 veces

EDITAR para agregar: La lista de exclusión basada en bloqueos de Pugh, que fue benchmarked in Fraser and Harris (2007) "Concurrent Programming Without Lock" as coming close to their own lock-free version (a point amply insisted upon in the top answer here), is also tweaked for good concurrent operation, cf. Pugh "Concurrent Maintenance of Skip Lists", aunque de una manera bastante suave. Sin embargo, un artículo nuevo / 2009 "A Simple Optimistic skip-list Algorithm" por Herlihy et al., que propone una supuestamente más simple (que la de Pugh) implementación de listas de salto concurrentes, criticó a Pugh por no proporcionar una prueba de corrección lo suficientemente convincente para ellos. Dejando de lado este (tal vez demasiado pedante) escrúpulo, Herlihy et al. mostrar que su implementación basada en bloqueos más simple de una lista de exclusión en realidad no puede escalar, así como la implementación libre de bloqueos del JDK de la misma, pero solo para alta contención (inserciones del 50%, eliminaciones del 50% y búsquedas del 0%)... que Fraser y Harris no probaron en absoluto; Fraser y Harris solo probaron búsquedas del 75%, 12.5% inserciones y 12.5% elimina(en la lista de exclusión con ~500K elementos). La implementación más simple de Herlihy et al. también se acerca a la solución sin bloqueo del JDK en el caso de baja contención que probaron (búsquedas del 70%, inserciones del 20%, eliminaciones del 10%); en realidad vencieron a la solución sin bloqueo para este escenario cuando hicieron su lista de saltos lo suficientemente grande, es decir, pasando de 200K a 2M elementos, de modo que la probabilidad de contención en cualquier bloqueo se volvió insignificante. Habría sido bueno si Herlihy et al. habían superado su taparrabos por la prueba de Pugh y probado su implementación también, pero por desgracia no lo hicieron.

EDIT2: He encontrado una (2015 publicado) motherlode de todos los puntos de referencia: Gramoli "Más de lo que Siempre Quiso Saber acerca de la Sincronización. Synchrobench, Midiendo el Impacto de la Sincronización en Algoritmos Concurrentes " : Aquí hay una imagen extraída relevante para esta pregunta.

"Algo.4 " es un precursor (más antiguo, versión de 2011) de Brown et al.se mencionó anteriormente. (No se cuánto mejor o peor es la versión de 2014). "Algo.26 " es el de Herlihy mencionado anteriormente; como se puede ver, se destroza en las actualizaciones, y mucho peor en las CPU Intel utilizadas aquí que en las CPU Sun del documento original. "Algo.28 " es ConcurrentSkipListMap del JDK; no funciona tan bien como uno podría haber esperado en comparación con otras implementaciones de listas de exclusión basadas en CAS. Los ganadores bajo alta contienda son " Algo.2 " un algoritmo basado en bloqueos (!!) descrito por Crain et al. en "A Contention-Friendly Binary Search Tree" y "Algo.30 "es la" lista de esqui giratoria "de " Estructuras de datos logarítmicas para multicores " . "Algo.29"es el " Sin punto caliente sin bloqueo skip list " . Tenga en cuenta que Gramoli es coautor de los tres de estos trabajos de algoritmo ganador. "Algo.27 " es la implementación en C++ de la lista de saltos de Fraser.

La conclusión de Gramoli es que es mucho más fácil arruinar una implementación de árbol concurrente basada en CAS que es arruinar una lista de saltos similar. Y basado en las cifras, es difícil estar en desacuerdo. Su explicación para este hecho es:

La dificultad en el diseño de un árbol que está libre de bloqueos se deriva de la dificultad de modificar múltiples referencias atómicamente. Saltar listas consisten en torres unidas entre sí a través de punteros sucesores y en la que cada nodo apunta al nodo inmediatamente debajo de él. Son a menudo se considera similar a los árboles porque cada nodo tiene un sucesor en la torre sucesora y debajo de ella, sin embargo, una distinción importante es que el puntero descendente es generalmente inmutable por lo tanto simplificando la modificación atómica de un nodo. Esta distinción es probablemente la razón por la que las listas de omisión superan a los árboles bajo una fuerte contención como se observa en la figura [arriba].

Superar esta dificultad fue una preocupación clave en Brown et al.'s reciente trabajo. Tienen un documento completamente separado (2013) " Pragmatic Primitives for Non-blocking Data Estructuras " en la construcción de múltiples registros LL/SC compuestos "primitivos", que llaman LLX/SCX, ellos mismos implementados utilizando CAS (a nivel de máquina). Brown et al. usó este bloque de construcción LLX/SCX en su implementación concurrente de árbol de 2014 (pero no en su implementación concurrente de árbol de 2011).

Creo que quizás también vale la pena resumir aquí las ideas fundamentales de la lista de saltos "no hot spot"/amigable con la contención (CF) . Se añade una idea esencial de los árboles RB relajado (y concrrency similar friedly estructuras de datos): las torres ya no se construyen inmediatamente después de la inserción, sino que se retrasan hasta que haya menos contención. Por el contrario, la eliminación de una torre alta puede crear muchas disputas; esto se observó ya en el artículo concurrente de Pugh de 1990, por lo que Pugh introdujo la inversión del puntero en la eliminación (un dato que la página de Wikipedia en las listas de salto todavía no menciona hasta el día de hoy, por desgracia). La lista de saltos CF lleva esto un paso más allá y retrasa la eliminación de los niveles superiores de un torre alta. Ambos tipos de operaciones retrasadas en las listas de omisión de CF son llevadas a cabo por un hilo separado (basado en CAS) similar a un recolector de basura, que sus autores llaman el "hilo de adaptación".

El código Synchrobench (incluyendo todos los algoritmos probados) está disponible en: https://github.com/gramoli/synchrobench . El último Brown et al. implementation (not included in the above) is available at http://www.cs.toronto.edu / ~tabrown/chromatic/ConcurrentChromaticTreeMap.java Hace ¿alguien tiene una máquina de más de 32 núcleos disponible? J / K Mi punto es que pueden ejecutar esto ustedes mismos.

También, además de las respuestas dadas (facilidad de implementación combinada con un rendimiento comparable a un árbol equilibrado). Encuentro que implementar el recorrido en orden (hacia adelante y hacia atrás) es mucho más simple porque una lista de omisión efectivamente tiene una lista vinculada dentro de su implementación.

En la práctica, he encontrado que el rendimiento del árbol B en mis proyectos ha funcionado mejor que las listas de omisión. Las listas de salto parecen más fáciles de entender, pero implementar un árbol B no es que difícil.

La única ventaja que conozco es que algunas personas inteligentes han descubierto cómo implementar una lista de saltos concurrentes sin bloqueo que solo usa operaciones atómicas. Por ejemplo, Java 6 contiene la clase ConcurrentSkipListMap, y puede leer el código fuente en ella si loco.

Pero tampoco es demasiado difícil escribir una variante concurrente del árbol B-ya lo he visto hecho por alguien más - si divide y fusiona nodos de forma preventiva "por si acaso" mientras camina por el árbol, entonces no tendrá que preocuparse por bloqueos y solo tendrá que mantener un bloqueo en dos niveles del árbol a la vez. La sobrecarga de sincronización será un poco más alta, pero el árbol B es probablemente más rápido.

Del artículo de Wikipedia que usted citó:

Las operaciones Θ(n), que nos obligan a visitar cada nodo en orden ascendente (como imprimir toda la lista) proporcionan la oportunidad de realizar una desandomización detrás de escena de la estructura de niveles de la lista de exclusión de una manera óptima, llevando la lista de exclusión a un tiempo de búsqueda O(log n). [...] Una lista de saltos, sobre la cual no hemos operaciones realizadas recientemente [cualquiera de estas] Θ(n), no proporcionar el mismo absoluto en el peor de los casos garantías de rendimiento, como más datos tradicionales de árbol balanceado estructuras , porque es siempre posible (aunque con muy baja probability) that the coin-flips used para construir la lista de salto producirá una estructura mal equilibrada

EDIT: por lo tanto, es una compensación: Las listas de omisión usan menos memoria con el riesgo de que degeneren en un árbol desequilibrado.

Las listas de omisión se implementan usando listas.

Las soluciones lock free existen para listas de enlaces individuales y dobles, pero no hay soluciones lock free que usen directamente solo CAS para cualquier estructura de datos O(logn).

Sin embargo, puede usar listas basadas en CAS para crear listas de omisión.

(Tenga en cuenta que los MCAS, que se crean utilizando CAS, permiten estructuras de datos arbitrarias y se ha creado un árbol de prueba de concepto rojo-negro utilizando MCAS).

Así que, por impares que sean, resultan ser muy útil :-)

Las listas de exclusión tienen la ventaja de eliminar bloqueos. Pero, el tiempo de ejecución depende de cómo se decida el nivel de un nuevo nodo. Usualmente esto se hace usando Random(). En un diccionario de 56000 palabras, skip list tomó más tiempo que un árbol de splay y el árbol tomó más tiempo que una tabla de hash. Los dos primeros no pudieron coincidir con el tiempo de ejecución de la tabla hash. Además, la matriz de la tabla hash también se puede bloquear de forma simultánea.

La lista de exclusión y listas ordenadas similares se utilizan cuando la localidad de se necesita referencia. Por ejemplo: encontrar vuelos próximos y antes de una fecha en una solicitud.

Un árbol de splay de búsqueda binaria inmemory es genial y se usa con más frecuencia.

Saltar Lista Vs Árbol Splay Vs Tabla Hash Tiempo de ejecución en el diccionario find op