Memilih daftar konkurensi terbaik di Java [ditutup]

98

Kumpulan utas saya memiliki jumlah utas tetap. Untaian ini perlu sering-sering menulis dan membaca dari daftar bersama.

Jadi, struktur data mana (sebaiknya Daftar, harus bebas monitor) dalam java.util.concurrentpaket yang terbaik dalam kasus ini?

java concurrency 象 嘉 道
sumber
5
Itu tergantung apa yang ingin Anda lakukan dengan koleksinya. Lihat posting blog saya (meskipun tentang .Net, konsepnya sama). Anda tidak mungkin dapat menulis kode aman utas yang benar dengan List.
SLaks
1
Sekarang, saya menggunakan CopyOnWriteArrayList , tetapi pengecualian ConcurrentModificationException masih muncul sesekali.
象 嘉 道
2
Harap sertakan lebih banyak informasi tentang apa yang Anda lakukan dengan koleksi sehingga orang dapat menjawab lebih baik, jika tidak, ini hanya tebakan.
mattsh
2
The ConcurrentModificationExceptionmungkin tidak berasal dari masalah sinkronisasi; itu juga muncul misalnya dalam perulangan-ke atas koleksi di mana Anda mencoba untuk menghapus elemen dari koleksi.
toto2
1
Saya tahu ini bukan bagian dari paket, tetapi apakah seseorang sudah mencobanya Vector?
WesternGun

Jawaban:

97

lebih baik List

Satu- satunya List implementasi di java.util.concurrentadalah CopyOnWriteArrayList . Ada juga opsi daftar yang disinkronkan seperti yang disebutkan Travis Webb.

Yang mengatakan, apakah Anda yakin Anda membutuhkannya List? Ada lebih banyak opsi untuk konkuren Queuedan Maps (dan Anda dapat membuatnya Setdari Maps), dan struktur tersebut cenderung paling sesuai untuk banyak jenis hal yang ingin Anda lakukan dengan struktur data bersama.

Untuk antrian, Anda memiliki banyak sekali opsi dan mana yang paling sesuai bergantung pada bagaimana Anda perlu menggunakannya:

ColinD
sumber
14
CopyOnWriteArrayListmemiliki kerugian menjadi sangat mahal untuk menulis (tetapi murah untuk membaca) Jika Anda melakukan banyak penulisan, lebih baik Anda menggunakan Daftar tersinkronisasi atau antrian.
Peter Lawrey
67

Koleksi Java apa pun dapat dibuat agar aman untuk Thread seperti:

List newList = Collections.synchronizedList(oldList);

Atau untuk membuat daftar thread-safe baru:

List newList = Collections.synchronizedList(new ArrayList());

http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#synchronizedList(java.util.List)

Travis Webb
sumber
7
Untuk alasan ini, Anda tidak akan menemukan implementasi daftar di java.util.concurrent - Uhm, ConcurrentHashMapmeskipun ada Collections.synchronizedMapmetode.
aioobe
7
Baca Javadocs di ConcurrentHashMap. Detail implementasi sinkronisasi berbeda. menggunakan synchronizedmetode pada Collectionsdasarnya hanya membungkus kelas dalam monitor Java. ConcurrentHashMapmenggunakan fitur konkurensi yang lebih pintar.
Travis Webb
1
Ya. Namun, itu membuat kalimat terakhir Anda tidak valid.
aioobe
1
Jika menggunakan monitor, kinerja program sangat buruk :-(
象 嘉 道
5
Sebagai tambahan, iterasi pada newList tidak aman untuk thread. !!
bluelurker
9

Jika ukuran daftar tetap, maka Anda dapat menggunakan AtomicReferenceArray . Ini akan memungkinkan Anda untuk melakukan pembaruan yang diindeks ke slot. Anda dapat menulis tampilan Daftar jika diperlukan.

Ben Manes
sumber
6

Anda mungkin ingin melihat ConcurrentDoublyLinkedList ditulis oleh Doug Lea berdasarkan "A Practical Lock-Free Doubly-Linked List" dari Paul Martin. Itu tidak mengimplementasikan antarmuka java.util.List, tetapi menawarkan sebagian besar metode yang akan Anda gunakan dalam Daftar.

Menurut javadoc:

Implementasi daftar tertaut serentak dari Deque (antrean berujung ganda). Operasi penyisipan, penghapusan, dan akses bersamaan dijalankan dengan aman di beberapa utas. Iterator kurang konsisten , mengembalikan elemen yang mencerminkan status deque di beberapa titik atau sejak iterator dibuat. Mereka tidak menampilkan ConcurrentModificationException, dan dapat melanjutkan operasi lain secara bersamaan.

palsu
sumber
5

ConcurrentLinkedQueuemenggunakan antrian bebas kunci (berdasarkan instruksi CAS yang lebih baru ).

eSniff
sumber
7
... yang tidak mengimplementasikan Listantarmuka.
aioobe
1
eSniff, bagaimana Anda akan menerapkan List.set(int index, Object element)dengan ConcurrentLinkedQueue?
John Vint
4
Sebagian besar Listmetode -spesifik tidak akan dapat diterapkan menggunakan Queue(tambahkan / setel pada indeks tertentu, misalnya) atau dapat diimplementasikan tetapi tidak efisien (dapatkan dari indeks). Jadi saya tidak berpikir Anda benar-benar bisa membungkusnya. Meski begitu, menurut saya saran a Queueboleh saja karena OP belum benar-benar menjelaskan kenapa mereka membutuhkan a List.
ColinD
1
@ ColinD itulah jawaban yang saya tuju. Ada alasan bagus mengapa CLQ tidak bisa dimasukkan ke dalam Daftar. Meskipun saya setuju, tidak dapat mengesampingkan antarmuka Antrian.
John Vint
1
❗️ Perlu diperhatikan bahwa: "Berhati-hatilah bahwa, tidak seperti di kebanyakan koleksi, metode ukuran BUKAN merupakan operasi waktu-konstan. Karena sifat asinkron dari antrean ini, menentukan jumlah elemen saat ini memerlukan penjelajahan elemen."
Behrang Saeedzadeh
3

Jika set sudah cukup, ConcurrentSkipListSet mungkin digunakan. (Implementasinya didasarkan pada ConcurrentSkipListMap yang mengimplementasikan daftar lewati .)

Biaya waktu rata-rata yang diharapkan adalah log (n) untuk operasi berisi, menambah, dan menghapus; metode ukuran bukanlah operasi waktu-konstan.

anre
sumber