Le strutture dati funzionali/immutabili possono ancora essere utili per la concorrenza in un contesto non garbage collection?

Uno dei punti di forza delle strutture di dati immutabili è che sono automaticamente parallelizzabili. Se non si sta verificando alcuna mutazione, i riferimenti a una struttura dati funzionale possono essere passati tra i thread senza alcun blocco.Le strutture dati funzionali/immutabili possono ancora essere utili per la concorrenza in un contesto non garbage collection?

Ho avuto modo di pensare a come le strutture dati funzionali sarebbero state implementate in C++. Supponiamo di avere un conteggio di riferimento su ciascun nodo della nostra struttura dati. (Strutture di dati funzionale struttura azionaria tra vecchi e aggiornate membri di una struttura di dati, in modo da nodi non apparterrebbero univocamente ad una particolare struttura di dati.)

Il problema è che se i conteggi di riferimento sono in fase di aggiornamento in diversi thread, quindi i nostri dati la struttura non è più thread-safe. E il collegamento di un mutex a ogni singolo nodo è costoso e vanifica lo scopo di utilizzare strutture di dati immutabili per la concorrenza.

C'è un modo per rendere le strutture di dati immutabili simultanei lavorano in C++ (e altri ambienti raccolti non spazzatura)?

fonte

2011-08-31 Rob Lachlan

Non sono un esperto in questo, ma è possibile memorizzare il numero di riferimenti per-filo, e solo mettere un blocco su di loro per verificare se tutte le discussioni hanno raggiunto riferimento zero su un nodo. Ma sono sicuro che ci sono soluzioni più eleganti di questo o forse il conteggio dei riferimenti in generale. – sinelaw

Qui è una struttura di dati immutabili popolare per C++ http://www.sgi.com/tech/stl/Rope.html – ybungalobill

si poteva guardare implementazioni di 'shared_ptr', che si affaccia esattamente lo stesso problema con bisogno di un efficiente filettatura conteggio di riferimento sicuro –

Esistono algoritmi di conteggio dei riferimenti senza blocco, vedere, ad es. Lock-Free Reference Counting, Atomic Reference Counting Pointers.

Si noti inoltre che il C++ 0x (che probabilmente diventerà C++ 11 presto) contiene tipi interi atomiche soprattutto per scopi come questo.

fonte

2011-08-31 06:56:50

Non sono sicuro di essere qui, ma non utilizzerei il conteggio dei riferimenti per ridurre le prestazioni da O (log n) a O (n), perché dovresti aggiornare i conti di tutti i nodi della tua "progenie" appena creata della raccolta riutilizza? Ciò sconfigge lo scopo di una collezione immutabile per la maggior parte dei casi d'uso che immagino. Ma per favore correggimi se sbaglio! –

@le_me Non ho idea di quale sia la struttura dati che Rob stava cercando di avere, quindi non posso dire nulla delle sue caratteristiche temporali. Potrebbe essere O (log n), potrebbe essere O (n^3), potrebbe essere O (exp (n)) o qualsiasi altra cosa.L'effetto del conteggio dei riferimenti richiederebbe una seconda analisi, a seconda del modello di utilizzo. Inoltre, avere dei riferimenti era la sua idea, non la mia. Potrei aver risposto alla parte sbagliata di un problema XY, ovviamente, ma credo che il tuo commento sarebbe stato meglio inserito nella domanda, dove è stato suggerito il conteggio dei riferimenti. –

Volevo solo aggiungere informazioni alla soluzione specifica che hai presentato. Penso che sia importante notare che il conteggio dei riferimenti ha una penalizzazione delle prestazioni con una complessità temporale probabilmente superiore rispetto alla raccolta stessa. Per esempio. [Le raccolte immutabili di Microsofts sembrano avere complessità O (log n)] (https://blogs.msdn.microsoft.com/bclteam/2012/12/18/preview-of-immutable-collections-released-on-nuget/) o meno per qualsiasi operazione. In tal caso, il conteggio dei riferimenti influirebbe negativamente sulle prestazioni per i grandi insiemi di dati. –

Beh, garbage collection lingue hanno anche la questione degli ambienti multi-threaded (e non è facile per le strutture mutevoli).

Avete dimenticato che a differenza di dati arbitrari, contatori possono essere incrementato e decrementato atomicamente, quindi un mutex non sarebbe necessario. Significa comunque che è necessario mantenere la sincronizzazione della cache tra i processori, il che può costare molto se un singolo nodo viene aggiornato.

fonte

2011-08-31 06:48:22

Guarda i contatori sciatti (http://www.usenix.org/events/osdi10/tech/full_papers/Boyd-Wickizer.pdf) come un modo per implementare i contatori di riferimento che non causano la stessa contesa della cache. Il documento di riferimento menziona anche diversi altri approcci a cui guardare. – Karmastan

@ Karmastan: grazie per l'articolo! Non sono sicuro che funzionerebbe anche secondo l'articolo "Questa operazione è costosa, quindi i contatori sciatti dovrebbero essere usati solo per oggetti che sono relativamente raramente disallocati", ma l'idea stessa è interessante. Un'altra tecnica di cui avevo letto è di mantenere i contatori separati dagli oggetti e di avere un singolo thread aggiornarli, con le code TLS per il buffer delle operazioni inc/dec. –

Le strutture dati funzionali/immutabili possono ancora essere utili per la concorrenza in un contesto non garbage collection?

risposta

Problemi correlati