LinkedListとConcurrentLinkedQueue

Question

現在、マルチスレッド環境では、LinkedListを使用してデータを保持しています。時にはログに、リンクされたリストをポーリングしているときにNoSuchElementExceptionが返されることがあります。リンクリストからConcurrentLinkedQueue実装に移行すると、パフォーマンスへの影響を理解するのに役立ちます。

おかげで、 サチン

Answer 1

NoSuchElementExceptionを取得した場合は、正しく同期していない可能性があります。 例：it.hasNext()で要素がリスト内にあり、その後にit.next()で取得しようとしている場合は、チェックしています。その間に要素が削除されたときに失敗する可能性があります。これは、Collection APIの同期バージョンを使用するときにも発生します。

ConcurrentLinkedQueueに移動すると問題は解決できません。例外が発生しないかもしれませんが、空でないことを前にチェックしてもnullが返されることを前提としています。これは、同じエラーですが、実装は異なります。これは、SAME同期スコープでの空と要素の取得のチェックを持つコードで、適切な同期がない限り、真です。

NoSuchElementExceptionの後に新しいNullPointerExceptionを持っている可能性があります。

これは、パフォーマンスについてのご質問に直接お答えするものではありませんが、ConcurrentLinkedQueueに移動する理由としてLinkedListにNoSuchElementExceptionがあると少し奇妙に聞こえます。

編集

壊れた実装するためのいくつかの擬似コード：適切な同期のために

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

いくつかの擬似コード：

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

"壊れた" 同期のためのいくつかのコード（し意図したとおりに動作しません）。 これは、自分自身で同期を取り除くためにLinkedListからCLQに直接切り替えた結果かもしれません。

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

いくつかの適切なコード：

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

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

または

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

Answer 2

ConcurrentLinkedQueue無制限、スレッドセーフな、FIFO順序キュー[あります]。それは、スキップリストの基礎としてセクション13.2.2で見たのと同様のリンクされた構造と、ハッシュテーブルオーバーフローチェインのセクション13.1.1で使用されます。リンクされた構造の主な魅力の1つは、ポインタの並び替えによって実装される挿入操作と削除操作が一定の時間内に実行されるということです。これにより、構造の両端にあるセル、つまりリンク構造の低速順次検索を使用して配置する必要のないセルで、これらの操作が常に必要とされるキューの実装として特に便利です。

ConcurrentLinkedQueueは、キューにアクセスする他のスレッドの状態に関係なく、スレッドが常に現在の処理を完了できることを保証するCASベースの待機フリーアルゴリズムを使用します。一定の時間内にキューの挿入と削除操作を実行しますが、sizeを実行するには線形時間が必要です。これは、挿入と削除のためのスレッド間の協調に依存するアルゴリズムがキューのサイズを追跡しないため、必要なときにキューを反復して計算する必要があるためです。

Java Generics and Collectionsから、ch。 14.2。

注ConcurrentLinkedQueueことはListインタフェースを実装していないので、後者はキューとして純粋に使用された場合にのみ、LinkedListの代替として十分です。この場合、明らかにConcurrentLinkedQueueが良い選択です。サイズが頻繁に問い合わせられない限り、大きなパフォーマンス上の問題はありません。ただし、免責条項として、あなた自身の具体的な環境やプログラムの中でそれを測定すれば、パフォーマンスについて確かめることができます。