Prima di .NET 4.0, se avevamo bisogno di usare la classe Dizionario in un ambiente multithread, non avevamo altra scelta che implementare la sincronizzazione dei thread da soli per mantenere i thread sicuri.
Molti sviluppatori hanno certamente implementato una soluzione thread-safe simile, sia creando un tipo di dizionario thread-safe completamente nuovo, sia semplicemente incapsulando un oggetto Dizionario in una classe e aggiungendo un meccanismo di blocco a tutti i metodi, che chiamiamo "Dizionario + Blocchi".
Ma ora abbiamo ConcurrentDictionary. La descrizione thread-safe della documentazione della classe Dictionary su MSDN afferma che, se è necessario utilizzare un'implementazione thread-safe, si deve usare ConcurrentDictionary.
Quindi, ora che abbiamo una classe di dizionario thread-safe, non dobbiamo più implementarla noi stessi. Fantastico, vero?
Origine del problema
In effetti, ho usato CocurrentDictionary solo una volta, nel mio test per testarne la reattività. Poiché andava bene nei test, l'ho subito sostituito con la mia classe, ho fatto qualche test, e poi qualcosa è andato storto.
Allora, cosa è andato storto? Non avevi detto sicuro per i fili?
Dopo ulteriori test, ho trovato la causa principale del problema. Ma per qualche motivo, la versione 4.0 di MSDN non include una descrizione della firma del metodo GetOrAdd che richieda di passare un parametro di tipo delegato. Dopo aver guardato la versione 4.5, ho trovato questa nota:
Se chiami GetOrAdd simultaneamente su thread diversi, addValueFactory può essere chiamato più volte, ma la sua coppia chiave/valore potrebbe non essere aggiunta al dizionario per ogni chiamata.
Questo è il problema che ho incontrato. Poiché non era stato precedentemente descritto nella documentazione, ho dovuto fare ulteriori test per confermare il problema. Ovviamente, il problema che sto incontrando riguarda il mio utilizzo; in generale, uso il tipo dizionario per memorizzare in cache alcuni dati:
Questi dati sono molto lenti da generare;
Questi dati possono essere creati solo una volta, perché la seconda creazione lancerà un'eccezione, oppure più creazioni possono portare a perdite di risorse, ecc.;
Ho avuto un problema con la seconda condizione. Se entrambi i thread scoprono che un dato non esiste, verrà creato una sola volta, ma un solo risultato verrà salvato con successo. E l'altro?
Se il processo che crei fa un'eccezione, puoi usare try: Catch (non abbastanza elegante, ma risolve il problema). Ma cosa succede se una risorsa viene creata e non riciclata?
Si potrebbe dire che un oggetto viene creato e verrà raccolto come rifiuto se non viene più citato in esso. Tuttavia, considerate cosa accadrebbe se la situazione descritta di seguito si verificasse:
Genera codice dinamicamente con Emit. Ho usato questo approccio in un framework Remoting e ho messo tutte le implementazioni in un assembly che non poteva essere riciclato. Se un tipo viene creato due volte, il secondo esisterà sempre, anche se non è mai stato utilizzato.
Crea un thread direttamente o indirettamente. Ad esempio, dobbiamo costruire un componente che utilizzi un thread proprietario per elaborare messaggi asincroni e si basi sull'ordine in cui vengono ricevuti. Quando il componente viene istanziato, viene creato un thread. Quando questa istanza componente viene distrutta, anche il thread viene terminato. Ma se cancelliamo il riferimento all'oggetto dopo aver distrutto il componente, il thread non termina per qualche motivo e contiene il riferimento all'oggetto. Poi, se il filo non muore, nemmeno l'oggetto verrà riciclato.
Esegui un'operazione P/Invoke. Richiedere che il numero di tempi di chiusura per l'handle ricevuto sia lo stesso del numero di aperture.
Certo, ci sono molte situazioni simili. Ad esempio, un oggetto dizionario manterrà una connessione a un servizio su un server remoto, che può essere richiesto solo una volta, e se viene richiesto una seconda volta, l'altro servizio penserà che si sia verificato un errore e lo registrerà nel registro. (In un'azienda per cui ho lavorato, c'erano alcune sanzioni legali per questa condizione.) ）
Quindi, è facile vedere che Dictionary + Locks non può essere sostituito in fretta con ConcurrentDictionary, anche se la documentazione dice che è thread-safe.
Analizza il problema
Ancora non capisci?
È vero che questo problema potrebbe non sorgere con l'approccio Dizionario + Serrature. Poiché questo dipende dall'implementazione specifica, vediamo questo esempio semplice:
Nel codice sopra, teniamo il blocco sul dizionario prima di iniziare a interrogare il valore chiave. Se la coppia chiave-valore specificata non esiste, verrà creata direttamente. Allo stesso tempo, poiché abbiamo già un lock su quel dizionario, possiamo aggiungere coppie chiave-valore direttamente al dizionario. Poi rilascia il blocco del dizionario e restituisci il risultato. Se due thread interrogano lo stesso valore chiave contemporaneamente, il primo thread che ottiene il blocco del dizionario completerà la creazione dell'oggetto, mentre l'altro thread aspetterà il completamento di questa creazione e otterrà il risultato del valore chiave creato dopo aver ottenuto il blocco del dizionario.
È una cosa buona, vero?
Non lo è affatto! Non credo che creare un oggetto in parallelo come questo, dove alla fine ne viene usato solo uno, non crei il problema che ho descritto.
La situazione e il problema su cui sto cercando di elaborare potrebbero non essere sempre riproducibili, in un ambiente parallelo possiamo semplicemente creare due oggetti e poi scartarne uno. Quindi, come confrontiamo esattamente Dictionary + Locks e ConcurrentDictionary?
La risposta è: dipende dalla strategia di utilizzo della serratura e da come viene usato il dizionario.
Gioco 1: Creare lo stesso oggetto in parallelo
Innanzitutto, supponiamo che un oggetto possa essere creato due volte, quindi cosa succede se due thread creano questo oggetto contemporaneamente?
In secondo luogo, quanto tempo dedichiamo a creazioni simili?
Possiamo semplicemente costruire un esempio in cui istanziare un oggetto richiede 10 secondi. Quando il primo thread crea l'oggetto 5 secondi dopo, la seconda implementazione cerca di chiamare il metodo GetOrAdd per ottenere l'oggetto e, dato che l'oggetto non esiste ancora, inizia anche a crearlo.
In questa condizione, abbiamo 2 CPU che lavorano in parallelo per 5 secondi, e quando il primo thread termina di funzionare, il secondo thread deve comunque continuare a funzionare per 5 secondi per completare la costruzione dell'oggetto. Quando il secondo thread termina di costruire l'oggetto, scopre che un oggetto esiste già e sceglie di usare l'oggetto esistente e scartare direttamente il nuovo oggetto creato.
Se il secondo thread semplicemente aspetta e la seconda CPU fa qualche altro lavoro (eseguire altri thread o applicazioni, risparmiando un po' di energia), otterrà l'oggetto desiderato dopo 5 secondi invece che 10 secondi.
Quindi, in queste condizioni, Dizionario + Serrature vince una piccola partita.
Gioco 2: Visita diversi oggetti in parallelo
No, la situazione che hai detto non è affatto vera!
Beh, l'esempio sopra è un po' particolare, ma descrive il problema, solo che questo uso è più estremo. Quindi, considera cosa succede se il primo thread sta creando un oggetto, e il secondo thread deve accedere a un altro oggetto chiave-valore, e quell'oggetto chiave-valore esiste già?
In ConcurrentDictionary, il design senza blocco rende le letture molto veloci perché non c'è alcun blocco sulla lettura. Nel caso di Dizionario + Serrature, l'operazione di lettura sarà bloccata mutuamente esclusiva, anche se si tratta di una chiave completamente diversa, il che ovviamente rallenterà l'operazione di lettura.
In questo modo, ConcurrentDictionary ha ritirato un gioco.
Nota: Qui considero che tu abbia compreso diversi concetti come Bucket/Nodo/Entry nella classe del dizionario; altrimenti è consigliato leggere l'articolo di Ofir Makmal "Comprendere il dizionario generico in profondità", che spiega bene questi concetti.
La terza partita del gioco: leggi di più e scrivi single
Cosa succede se usi Multiple Readers e Single Writer invece di un blocco completo sul dizionario in Dictionary + Locks?
Se un thread sta creando un oggetto e mantiene un lock aggiornabile fino a quando l'oggetto non viene creato, il lock viene aggiornato a un lock di scrittura, allora l'operazione di lettura può essere eseguita in parallelo.
Possiamo anche risolvere il problema lasciando un'operazione di lettura inattiva per 10 secondi. Ma se ci sono molte più letture che scritture, scopriremo che ConcurrentDictionary è ancora veloce perché implementa letture in modalità senza blocchi.
Usare ReaderWriterLockSlim per i dizionari peggiora le letture, e generalmente si consiglia di usare Full Lock per i dizionari invece di ReaderWriterLockSlim.
Quindi, in queste condizioni, ConcurrentDictionary ha vinto un'altra partita.
Nota: Ho trattato le classi YieldReaderWriterLock e YieldReaderWriterLockSlim in articoli precedenti. Utilizzando questo blocco di lettura-scrittura, la velocità è stata notevolmente migliorata (ora evoluta in SpinReaderWriterLockSlim) e permette di eseguire più letture in parallelo con poco o nessun impatto. Anche se continuo a usare questo metodo, un ConcurrentDictionary senza blocchi sarebbe ovviamente più veloce.
Partita 4: Aggiungi più coppie chiave-valore
Lo scontro non è ancora finito.
E se avessimo più valori chiave da aggiungere, e tutti non si scontrano e vengono assegnati in bucket diversi?
All'inizio questa domanda mi sembrava curiosa, ma ho fatto un test che non si adattava del tutto. Ho usato un dizionario di tipi <int, int> e la fabbrica di costruzione dell'oggetto restituiva un risultato negativo direttamente come chiave.
Mi aspettavo che ConcurrentDictionary fosse il più veloce, ma si è rivelato il più lento. Dizionario + Serrature, invece, funziona più velocemente. Perché?
Questo perché ConcurrentDictionary alloca i nodi e li colloca in bucket diversi, ottimizzando per soddisfare il design senza lock-free per le operazioni di lettura. Tuttavia, quando si aggiungono elementi chiave-valore, il processo di creazione di un nodo diventa costoso.
Anche in condizioni parallele, allocare un blocco nodo richiede comunque più tempo rispetto all'uso di un blocco completo.
Quindi, Dictionary + Locks vince questa partita.
Giocare al quinto gioco: la frequenza delle operazioni di lettura è più alta
Francamente, se avessimo un delegato che può istanziare rapidamente gli oggetti, non avremmo bisogno di un Dizionario. Possiamo chiamare direttamente il delegato per ottenere l'oggetto, giusto?
In effetti, la risposta è anche che dipende dalla situazione.
Immagina che il tipo di chiave sia una stringa e contenga mappe di percorso per varie pagine nel server web, e il valore corrispondente sia un tipo di oggetto che contiene la registrazione degli utenti attuali che accedono alla pagina e il numero di tutte le visite alla pagina da quando il server è iniziato.
Creare un oggetto del genere è quasi istantaneo. E dopo, non è necessario creare un nuovo oggetto, basta cambiare i valori salvati al suo interno. Quindi è possibile permettere la creazione di un modo due volte fino a quando non viene usata una sola istanza. Tuttavia, poiché ConcurrentDictionary alloca le risorse dei nodi più lentamente, l'uso di Dictionary + Locks comporterà tempi di creazione più rapidi.
Quindi, con questo esempio è molto speciale, vediamo anche che Dictionary + Locks funziona meglio in questa condizione, richiedendo meno tempo.
Anche se l'allocazione dei nodi in ConcurrentDictionary è più lenta, non ho provato a inserire 100 milioni di elementi dati per testare il tempo. Perché ovviamente ci vuole molto tempo.
Ma nella maggior parte dei casi, una volta creato un elemento dati, viene sempre letto. Come cambia il contenuto dell'elemento dati è un'altra questione. Quindi non importa quanti millisecondi ci vogliano per creare un elemento dati, perché le letture sono più veloci (solo qualche millisecondo più veloci), ma le letture avvengono più frequentemente.
Così, ConcurrentDictionary ha vinto la partita.
Gioco 6: Crea oggetti che consumano tempi diversi
Cosa succede se il tempo necessario per creare diversi elementi di dati varia?
Crea più elementi di dati che consumano tempi diversi e aggiungili al dizionario in parallelo. Questo è il punto di forza di ConcurrentDictionary.
ConcurrentDictionary utilizza diversi meccanismi di blocco per permettere l'aggiunta simultanea di elementi dati, ma logiche come decidere quale lock usare, richiedere a un lock di cambiare la dimensione del bucket, ecc., non aiuta. La velocità con cui gli elementi dati vengono inseriti in un bucket è veloce come una macchina. Ciò che davvero rende vincente ConcurrentDictionary è la sua capacità di creare oggetti in parallelo.
Tuttavia, in realtà possiamo fare la stessa cosa. Se non ci interessa se stiamo creando oggetti in parallelo, o se alcuni di essi sono stati scartati, possiamo aggiungere un blocco per rilevare se l'elemento dati esiste già, poi rilasciare il blocco, creare l'elemento dati, premere per ottenere il blocco, controllare di nuovo se l'elemento esiste e, se non esiste, aggiungere l'elemento dati. Il codice potrebbe apparire più o meno così:
* Nota che uso un dizionario di tipo <int, int>.
Nella struttura semplice sopra, Dictionary + Locks funziona quasi altrettanto bene quanto ConcurrentDictionary nella creazione e nell'aggiunta di elementi dati in condizioni parallele. Ma c'è anche lo stesso problema, dove alcuni valori possono essere generati ma mai usati.
conclusione
Quindi, c'è una conclusione?
Al momento, ce ne sono ancora alcuni:
Tutte le classi di dizionario sono molto veloci. Anche se ho creato milioni di dati, è comunque veloce. Normalmente creiamo solo un piccolo numero di elementi dati, e ci sono alcuni intervalli di tempo tra una lettura e l'altra, quindi generalmente non notiamo il sovraccarico temporale della lettura dei dati.
Se lo stesso oggetto non può essere creato due volte, non usare ConcurrentDictionary.
Se sei davvero preoccupato per le prestazioni, Dictionary + Locks potrebbe comunque essere una buona soluzione. Un fattore importante è il numero di elementi dati aggiunti e rimossi. Ma se ci sono molte operazioni di lettura, è più lento di ConcurrentDictionary.
Anche se non l'ho introdotto io, in realtà c'è più libertà nell'usare lo schema Dizionario + Serrature. Ad esempio, puoi bloccare una volta, aggiungere più elementi di dato, eliminare più elementi di dati o interrogare più volte, ecc., e poi rilasciare il blocco.
In generale, evita di usare ReaderWriterLockSlim se ci sono molte più letture che scritture. I tipi di dizionario sono già molto più veloci rispetto a ottenere un blocco di lettura in un blocco di lettura-scrittura. Naturalmente, questo dipende anche dal tempo impiegato per creare un oggetto in una serratura.
Quindi, penso che gli esempi dati siano un po' estremi, ma mostrano che usare ConcurrentDictionary non è sempre la soluzione migliore.
Senti la differenza
Ho scritto questo articolo con l'intenzione di cercare una soluzione migliore.
Sto già cercando di capire meglio come funziona un specifico corso di dizionario (ora sento di essere molto chiaro).
Si potrebbe sostenere che Bucket e Node in ConcurrentDictionary siano molto semplici. Ho fatto qualcosa di simile quando ho provato a creare una classe di dizionario. La classe regolare del Dizionario può sembrare più semplice, ma in realtà è più complessa.
In ConcurrentDictionary, ogni nodo è una classe completa. Nella classe Dizionario, Node viene implementato usando un tipo di valore, e tutti i nodi sono mantenuti in un enorme array, mentre Bucket viene usato per indicizzare nell'array. Viene anche usato al posto del semplice riferimento di un Nodo al suo nodo successivo (dopotutto, come nodo di tipo struct, non può contenere un membro nodo di tipo struct).
Quando si aggiunge e si rimuove un dizionario, la classe Dizionario non può semplicemente creare un nuovo nodo, deve verificare se c'è un indice che segna un nodo eliminato e poi riutilizzarlo. Oppure "Count" viene usato per ottenere la posizione del nuovo nodo nell'array. Infatti, quando l'array è pieno, la classe Dizionario impone un cambiamento di dimensione.
Per ConcurrentDictionary, un Nodo può essere considerato un nuovo oggetto. Rimuovere un nodo significa semplicemente rimuovere il suo riferimento. Aggiungere un nuovo Node può semplicemente creare una nuova istanza di Node. Cambiare la dimensione serve solo a evitare conflitti, ma non è obbligatorio.
Quindi, se la classe Dictionary utilizza volutamente algoritmi più complessi per gestirla, come farà ConcurrentDictionary a garantire che funzioni meglio in un ambiente multithread?
La verità è: mettere tutti i nodi in un unico array è il modo più veloce per allocare e leggere, anche se serve un altro array per tenere traccia di dove trovare quei dati. Quindi sembra che avere lo stesso numero di bucket consumi più memoria, ma i nuovi elementi di dati non devono essere riallocati, non servono nuove sincronizzazioni degli oggetti e non avviene una nuova garbage collection. Perché tutto è già al suo posto.
Tuttavia, sostituire contenuti in un Nodo non è un'operazione atomica, che è uno dei fattori che rendono il suo thread insicuro. Poiché i nodi sono tutti oggetti, inizialmente viene creato un nodo, poi viene aggiornato un riferimento separato per indicarlo (operazione atomica qui). Quindi, il thread di lettura può leggere il contenuto del dizionario senza bloccare, e la lettura deve essere uno dei valori vecchio e nuovo, e non c'è possibilità di leggere un valore incompleto.
Quindi, la verità è: se non hai bisogno di un lock, la classe Dictionary è più veloce nelle letture, perché è il lock che rallenta la lettura.
Questo articolo è tradotto dall'articolo di Paulo Zemek "Dictionary + Locking versus ConcurrentDictionary" su CodeProject, e alcune affermazioni cambieranno per motivi di comprensione.
|
Pubblicato su 13/09/2016 13:33:04
|
|
|
Padrone di casa|
Pubblicato su 13/09/2016 13:33:15
|
