Salta la lista contro l’albero di ricerca binaria

Di recente mi sono imbattuto nella struttura dei dati nota come elenco dei salti . Sembra avere un comportamento molto simile a un albero di ricerca binario.

Perché dovresti voler usare una lista di skip su un albero di ricerca binario?

Gli elenchi saltati sono più suscettibili di accesso / modifica concorrente. Herb Sutter ha scritto un articolo sulla struttura dei dati in ambienti concorrenti. Ha più informazioni approfondite.

L’implementazione più frequente di un albero di ricerca binario è un albero rosso-nero . I problemi concomitanti arrivano quando l’albero viene modificato, spesso ha bisogno di riequilibrare. L’operazione di ribilanciamento può influire su ampie porzioni dell’albero, che richiederebbero un blocco mutex su molti dei nodes dell’albero. L’inserimento di un nodo in un elenco di salto è molto più localizzato, solo i nodes direttamente collegati al nodo interessato devono essere bloccati.


Aggiornamento dai commenti di Jon Harrops

Ho letto l’ultima programmazione concorrente di Fraser e Harris senza serrature . Cose davvero buone se sei interessato a strutture di dati prive di lock. Il documento si concentra sulla memoria transazionale e su un’operazione teorica MCAS multi-confronta-e-swap. Entrambi sono simulati nel software poiché nessun hardware li supporta ancora. Sono abbastanza impressionato dal fatto che siano stati in grado di build MCAS nel software.

Non ho trovato la memoria transazionale particolarmente interessante in quanto richiede un garbage collector. Anche la memoria transazionale del software è afflitta da problemi di prestazioni. Tuttavia, sarei molto eccitato se la memoria transazionale dell’hardware diventasse mai comune. Alla fine è ancora una ricerca e non sarà utile per il codice di produzione per un altro decennio.

Nella sezione 8.2 confrontano le prestazioni di diverse implementazioni di alberi simultanee. Riassumerò i loro risultati. Vale la pena di scaricare il pdf in quanto ha alcuni grafici molto istruttivi alle pagine 50, 53 e 54.

  • Bloccare le liste dei salti sono incredibilmente veloci. Scendono incredibilmente bene con il numero di accessi concorrenti. Questo è ciò che rende skip list speciali, altre strutture di dati basate su lock tendono a gracchiare sotto pressione.
  • Gli elenchi di salti bloccati sono sempre più veloci rispetto agli elenchi di salti bloccati ma solo a fatica.
  • Gli elenchi di salti transazionali sono costantemente 2-3 volte più lenti delle versioni di blocco e senza blocco.
  • bloccare gli alberi rosso-nero gracidare sotto accesso concorrente. Le loro prestazioni si riducono linearmente con ogni nuovo utente concorrente. Delle due note versioni di albero rosso-nero con blocco, una ha essenzialmente un blocco globale durante il ribilanciamento dell’albero. L’altro utilizza l’escalation di blocco elaborata (e complicata), ma ancora non esegue in modo significativo la versione di blocco globale.
  • gli alberi rosso-nero senza blocco non esistono (non è più vero, vedi Aggiornamento).
  • gli alberi transazionali rosso-neri sono paragonabili agli skip-list transazionali. È stato molto sorprendente e molto promettente. Memoria transazionale, anche se più lenta se molto più facile da scrivere. Può essere facile come cercare e sostituire rapidamente sulla versione non concorrente.

Aggiornare
Ecco la carta sugli alberi senza serratura : Alberi rosso-nero senza serratura che usano CAS .
Non l’ho esaminato a fondo, ma a prima vista sembra solido.

Innanzitutto, non è ansible confrontare in modo equo una struttura di dati randomizzata con una che offre garanzie sul caso peggiore.

Un elenco di salto è equivalente a un albero di ricerca binaria bilanciato in modo casuale (RBST) nel modo in cui viene spiegato in modo più dettagliato in “Esplorare la dualità tra elenchi di salto e alberi di ricerca binaria” di Dean e Jones.

Al contrario, è ansible avere liste skip deterministiche che garantiscono le peggiori prestazioni, cfr. Munro et al.

A fronte di quanto affermato in precedenza, è ansible avere implementazioni di alberi di ricerca binari (BST) che funzionano bene nella programmazione concorrente. Un potenziale problema con i BST focalizzati sulla concorrenza è che non è ansible ottenere facilmente le stesse garanzie sul bilanciamento come si farebbe con un albero rosso-nero (RB). (Ma gli elenchi di salti “standard”, ad esempio randomizzati, non ti danno queste garanzie.) C’è un compromesso tra il mantenimento del bilanciamento in ogni momento e un accesso concorrente buono (e facile da programmare), quindi gli alberi RB rilassati sono solitamente usati quando si desidera una buona concorrenza. Il rilassamento consiste nel non riequilibrare l’albero subito. Per un sondaggio un po ‘datato (1998) si veda Hanke “The Performance of Concurrent Red-Black Tree Algorithms” [ps.gz] .

Uno dei miglioramenti più recenti su questi è il cosiddetto albero cromatico (in pratica si ha un peso tale che il nero sarebbe 1 e il rosso sarebbe zero, ma si consentono anche valori intermedi). E come si comporta un albero cromatico contro la skip list? Vediamo cosa Brown et al. “Una tecnica generale per alberi non bloccanti” (2014) ha da dire:

con 128 thread, il nostro algoritmo supera la skiplist non bloccante di Java del 13% al 156%, l’albero AVL basato su lock di Bronson et al. dal 63% al 224% e un RBT che utilizza la memoria transazionale del software (STM) da 13 a 134 volte

EDIT da aggiungere: l’elenco skip basato su lock di Pugh, che è stato benchmark in Fraser e Harris (2007) “Concurrent Programming Without Lock” come avvicinandosi alla loro versione lock-free (un punto ampiamente insistito nella risposta top qui), è anche ottimizzato per una buona operazione concomitante, cfr. “Manutenzione concorrente di elenchi di salti” di Pugh, anche se in un modo piuttosto mite. Ciononostante, un nuovo articolo del 2009 “Un algoritmo di skip-list semplice e ottimista” di Herlihy et al., Che propone un’implementazione basata su blocchi simultaneamente più semplice di quella di Pugh, criticò Pugh per non aver fornito una prova di correttezza convincente abbastanza per loro. Tralasciando questo (forse troppo pedante) problema, Herlihy et al. mostra che la loro implementazione basata su lock più semplice di una skip list non riesce a scalare e all’implementazione lock-free di JDK, ma solo per contesa alta (50% di inserimenti, 50% di eliminazioni e 0% di ricerche) … che Fraser e Harris non ha provato affatto; Fraser e Harris hanno testato solo il 75% di ricerche, il 12,5% di inserti e il 12,5% di eliminazioni (nella lista di salto con elementi ~ 500K). La più semplice implementazione di Herlihy et al. si avvicina anche alla soluzione lock-free del JDK in caso di bassa contesa che hanno testato (70% di ricerche, 20% di inserimenti, 10% di eliminazioni); in realtà hanno battuto la soluzione lock-free per questo scenario quando hanno reso il loro skip list abbastanza grande, cioè passando da 200K a 2M di elementi, in modo che la probabilità di contesa su qualsiasi blocco diventasse trascurabile. Sarebbe stato bello se Herlihy et al. aveva superato il loro impiccagione sulle prove di Pugh e testato la sua implementazione, ma purtroppo non l’hanno fatto.

EDIT2: Ho trovato un (pubblicato nel 2015) motherlode di tutti i benchmark: “Più di quanto tu abbia mai voluto sapere sulla sincronizzazione di Gramoli”: Synchrobench, Misurazione dell’impatto della sincronizzazione sugli algoritmi simultanei ” : Ecco un’immagine estratta relativa a questa domanda.

inserisci la descrizione dell'immagine qui

“Algo.4” è un precursore (più vecchio, versione 2011) di Brown e altri già menzionato sopra. (Non so quanto sia migliore o peggiore la versione 2014). “Algo.26” è Herlihy di cui sopra; come potete vedere, viene scaricato per gli aggiornamenti e molto peggio per le CPU Intel utilizzate qui che per le CPU Sun della carta originale. “Algo.28” è ConcurrentSkipListMap dal JDK; non funziona come si poteva sperare rispetto ad altre implementazioni di skip list basate su CAS. I vincitori in alta contesa sono “Algo.2” un algoritmo basato su lock (!!) descritto da Crain et al. in “Un albero di ricerca binaria favorevole alla contesa” e “Algo.30” è la “skiplist rotante” da “Strutture dati logaritmiche per multicore” . “Algo.29” è la “Lista salta non bloccante senza hot spot” . Tieni presente che Gramoli è un coautore di tutti e tre questi documenti sull’algoritmo del vincitore. “Algo.27” è l’implementazione in C ++ dell’elenco dei salti di Fraser.

La conclusione di Gramoli è che è molto più facile rovinare un’implementazione concomitante di alberi basata su CAS piuttosto che rovinare una lista skip simile. E sulla base delle cifre, è difficile non essere d’accordo. La sua spiegazione per questo fatto è:

La difficoltà nel progettare un albero privo di blocco deriva dalla difficoltà di modificare più riferimenti atomici. Gli elenchi di salto sono costituiti da torri collegate tra loro tramite puntatori successivi e in cui ciascun nodo punta al nodo immediatamente sottostante. Sono spesso considerati simili agli alberi perché ogni nodo ha un successore nella torre successiva e al di sotto di esso, tuttavia, una distinzione principale è che il puntatore verso il basso è generalmente immutabile, semplificando quindi la modifica atomica di un nodo. Questa distinzione è probabilmente la ragione per cui le liste di salto superano gli alberi sottoposti a forti contese, come osservato nella Figura [sopra].

Superare questa difficoltà è stata una preoccupazione chiave nel recente lavoro di Brown e altri. Hanno un intero documento separato (2013) “Pragmatic Primitives for Non-blocking Data Structures” sulla costruzione di primitive di composti LL / SC compositi multi-record, che chiamano LLX / SCX, implementati loro stessi usando CAS (machine-level). Brown et al. ha utilizzato questo blocco LLX / SCX nella loro implementazione dell’albero 2014 (ma non nel loro 2011).

Penso che forse valga la pena di ricapitolare qui le idee fondamentali della “skiplist” “no hot spot” / contention-friendly (CF) . Adotta un’idea essenziale dagli alberi RB rilassati (e strutture di dati frettolosamente simili): le torri non vengono più costruite immediatamente dopo l’inserimento, ma vengono ritardate fino a quando c’è meno conflitto. Viceversa, la cancellazione di una torre alta può creare molte contese; questo è stato osservato nel lontano passato di Pugh nel 1990, ed è per questo che Pugh ha introdotto l’inversione del puntatore sulla cancellazione (un bocconcino che la pagina di Wikipedia sulle liste dei salti continua a non menzionare fino ad oggi, ahimè). La lista salta CF fa un ulteriore passo avanti e ritarda l’eliminazione dei livelli superiori di una torre alta. Entrambi i tipi di operazioni ritardate nelle liste di salto CF vengono eseguite da un thread garbage-collector separato (basato su CAS), che i suoi autori chiamano “thread di adattamento”.

Il codice Synchrobench (compresi tutti gli algoritmi testati) è disponibile all’indirizzo: https://github.com/gramoli/synchrobench . L’ultimo Brown et al. l’implementazione (non inclusa in quanto sopra) è disponibile su http://www.cs.toronto.edu/~tabrown/chromatic/ConcurrentChromaticTreeMap.java Qualcuno ha a disposizione una macchina core 32+? J / K Il mio punto è che puoi gestirli da soli.

Inoltre, oltre alle risposte fornite (facilità di implementazione combinata con prestazioni paragonabili a un albero bilanciato). Trovo che implementare l’attraversamento in ordine (avanti e indietro) sia molto più semplice perché un elenco skip ha effettivamente una lista collegata all’interno della sua implementazione.

In pratica, ho trovato che la performance di B-tree sui miei progetti ha funzionato per essere migliore di skip-list. Le liste di salto sembrano più facili da capire, ma l’implementazione di un B-tree non è così difficile.

L’unico vantaggio di cui sono a conoscenza è che alcune persone intelligenti hanno elaborato come implementare una lista skip simultanea senza blocco che utilizza solo operazioni atomiche. Ad esempio, Java 6 contiene la class ConcurrentSkipListMap e puoi leggere il codice sorgente se sei pazzo.

Ma non è troppo difficile scrivere una variante di B-tree simultanea – l’ho vista fare da qualcun altro – se dividi e annulli in modo preventivo i nodes “nel caso in cui cammini lungo l’albero allora non dovrai preoccupati dei deadlock e hai solo bisogno di tenere un blocco su due livelli dell’albero alla volta. L’overhead di sincronizzazione sarà un po ‘più alto ma l’albero B è probabilmente più veloce.

Dall’articolo di Wikipedia che hai citato:

Θ (n) operazioni, che ci costringono a visitare ogni nodo in ordine ascendente (come la stampa dell’intero elenco) offrono l’opportunità di eseguire una derassizzazione dietro le quinte della struttura di livello della skip-list in modo ottimale, portando la lista dei salti a O (log n) tempo di ricerca. […] Una skip list, sulla quale di recente non abbiamo eseguito [nessuna di queste] operazioni (n), non offre le stesse garanzie assolute di performance nel caso peggiore di strutture di dati ad albero bilanciate più tradizionali , perché è sempre ansible (anche se con una probabilità molto bassa) che i coin-flip usati per build la skip list produrranno una struttura mal bilanciata

EDIT: quindi è un trade-off: Skip Lists usa meno memoria a rischio di degenerare in un albero sbilanciato.

Gli elenchi di salto vengono implementati utilizzando le liste.

Esistono soluzioni libere di blocco per elenchi concatenati e doppiamente collegati – ma non esistono soluzioni senza blocco che utilizzano direttamente solo CAS per qualsiasi struttura di dati O (logn).

È tuttavia ansible utilizzare elenchi basati su CAS per creare elenchi di salti.

(Si noti che MCAS, che è stato creato utilizzando CAS, consente strutture di dati arbitrarie e un albero rosso-nero di prova della concezione è stato creato utilizzando MCAS).

Così, per quanto siano dispari, si rivelano molto utili 🙂

Le liste di salto hanno il vantaggio di rimuovere i blocchi. Ma il tempo runt dipende da come viene deciso il livello di un nuovo nodo. Di solito questo viene fatto usando Random (). Su un dizionario di 56000 parole, l’elenco dei salti richiedeva più tempo di un albero di diffusione e l’albero richiedeva più tempo di una tabella di hash. I primi due non potevano eguagliare il runtime della tabella hash. Inoltre, la matrice della tabella hash può essere bloccata in modo simultaneo.

Skip List e liste ordinate simili vengono utilizzate quando è necessaria la località di riferimento. Per esempio: trovare i voli successivi e prima di una data in un’applicazione.

Un albero di ricerca di ricerca binaria inmemoria è grande e usato più frequentemente.

Salta la lista Vs Splay Tree Vs Hash Table Runtime sul dizionario find op