LinkedList Vs ConcurrentLinkedQueue

Question

Attualmente in un ambiente con multithreading, viene utilizzata una LinkedList per contenere i dati. A volte nei registri otteniamo NoSuchElementException mentre esegue il polling della lista collegata. Aiutateci a comprendere l'impatto sulle prestazioni se passiamo dall'implementazione della lista collegata a ConcurrentLinkedQueue.

Grazie, Sachin

Answer 1

quando si ottiene un NoSuchElementException allora questo forse a causa di non sincronizzare correttamente. Ad esempio: stai verificando con it.hasNext() se un elemento è presente nell'elenco e successivamente prova a recuperarlo con it.next(). Ciò potrebbe non riuscire quando l'elemento è stato rimosso in mezzo e ciò può anche accadere quando si utilizzano versioni sincronizzate dell'API di raccolta.

Quindi il problema non può realmente essere risolto con lo spostamento a ConcurrentLinkedQueue. Non è possibile ottenere un'eccezione, ma è necessario essere pronti a restituire null anche se si è verificato che non è vuoto. (Questo è ancora lo stesso errore ma l'implementazione è diversa.) Questo è vero finché non c'è una sincronizzazione corretta nel TUO codice che ha i controlli per la vacuità e il recupero degli elementi nell'ambito SAME sincronizzato.

C'è una buona probabilità che si scambi NoSuchElementException per avere nuovo NullPointerException in seguito.

Questa potrebbe non essere una risposta indirizzata direttamente alla tua domanda sulle prestazioni, ma avere NoSuchElementException in LinkedList come motivo per passare a ConcurrentLinkedQueue suona un po 'strano.

Modifica

Alcuni pseudo-codice per le implementazioni di rotte:

//list is a LinkedList 
if(!list.isEmpty()) { 
    ... list.getFirst() 
} 

Alcuni pseudo-codice per una corretta sincronizzazione:

//list is a LinkedList 
synchronized(list) { 
    if(!list.isEmpty()) { 
     ... list.getFirst() 
    } 
} 

del codice per la sincronizzazione "rotto" (fa non funziona come previsto). Questo potrebbe essere il risultato del passaggio diretto da LinkedList a CLQ nella speranza di eliminare la sincronizzazione da solo.

//queue is instance of CLQ 
if(!queue.isEmpty()) { // Does not really make sense, because ... 
    ... queue.poll() //May return null! Good chance for NPE here! 
} 

Alcuni codice appropriato:

//queue is instance of CLQ 
element = queue.poll(); 

if(element != null) { 
    ... 
} 

o

//queue is instance of CLQ 
synchronized(queue) { 
    if(!queue.isEmpty()) { 
     ... queue.poll() //is not null 
    } 
} 

Answer 2

ConcurrentLinkedQueue [è] un,, coda FIFO ordinata illimitata thread-safe. Utilizza una struttura collegata, simile a quelli che abbiamo visto nella Sezione 13.2.2 come base per gli elenchi di salto, e nella Sezione 13.1.1 per il concatenamento di overflow della tabella hash. Abbiamo notato che una delle principali attrazioni delle strutture collegate è che le operazioni di inserimento e rimozione implementate dai riarrangiamenti dei puntatori vengono eseguite in un tempo costante. Ciò li rende particolarmente utili come implementazioni di code, in cui queste operazioni sono sempre richieste su celle all'estremità della struttura, ovvero celle che non devono essere localizzate utilizzando la ricerca sequenziale lenta di strutture collegate.

ConcurrentLinkedQueue utilizza un algoritmo di attesa senza CAS che garantisce che qualsiasi thread possa sempre completare l'operazione corrente, indipendentemente dallo stato degli altri thread che accedono alla coda. Esegue operazioni di inserimento e rimozione della coda in tempo costante, ma richiede un tempo lineare per l'esecuzione di size. Questo perché l'algoritmo, che fa affidamento sulla cooperazione tra i thread per l'inserimento e la rimozione, non tiene traccia delle dimensioni della coda e deve eseguire un'iterazione sulla coda per calcolarlo quando richiesto.

Da Java Generics and Collections, ch. 14.2.

noti che ConcurrentLinkedQueue non implementa l'interfaccia List, quindi è sufficiente per sostituire LinkedList soltanto se quest'ultimo è stato usato solo come una coda. In questo caso, ConcurrentLinkedQueue è ovviamente una scelta migliore. Non ci dovrebbero essere grandi problemi di prestazioni a meno che la sua dimensione non venga frequentemente interrogata. Ma in quanto disclaimer, puoi essere sicuro delle prestazioni solo se lo misuri all'interno del tuo ambiente e programma concreto.