LinkedList Vs ConcurrentLinkedQueue

Question

Hiện tại trong môi trường đa luồng, chúng tôi đang sử dụng LinkedList để giữ dữ liệu. Đôi khi trong các bản ghi chúng tôi nhận được NoSuchElementException trong khi nó đang bỏ phiếu danh sách liên kết. Vui lòng trợ giúp trong việc hiểu tác động hiệu suất nếu chúng tôi chuyển từ danh sách liên kết sang triển khai ConcurrentLinkedQueue.

Cảm ơn, Sachin

Answer 1

Khi bạn nhận được NoSuchElementException thì điều này có thể do không đồng bộ hóa đúng cách. Ví dụ: Bạn đang kiểm tra với it.hasNext() nếu một phần tử có trong danh sách và sau đó cố gắng tìm nạp nó với it.next(). Điều này có thể không thành công khi phần tử đã bị xóa ở giữa và điều đó cũng có thể xảy ra khi bạn sử dụng các phiên bản đồng bộ của API thu thập.

Vì vậy, vấn đề của bạn không thể thực sự được giải quyết bằng cách di chuyển đến ConcurrentLinkedQueue. Bạn có thể không nhận được ngoại lệ nhưng bạn phải chuẩn bị rằng null được trả lại ngay cả khi bạn đã kiểm tra trước khi nó không trống. (Đây vẫn là lỗi tương tự nhưng thực hiện khác.) Điều này đúng với điều kiện là không có đồng bộ hóa thích hợp trong mã CỦA BẠN có kiểm tra tính trống rỗng và phần tử truy lục trong phạm vi đồng bộ SAME.

Có một cơ hội tốt để bạn giao dịch NoSuchElementException để có số mới NullPointerException sau đó.

Đây có thể không phải là câu trả lời trực tiếp giải quyết câu hỏi của bạn về hiệu suất, nhưng có NoSuchElementException trong LinkedList là lý do để di chuyển đến ConcurrentLinkedQueue có vẻ hơi lạ.

Sửa

Một số giả mã cho việc triển khai bị hỏng:

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

Một số giả mã cho đồng bộ thích hợp:

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

Một số mã cho đồng bộ "vỡ" (không không hoạt động như dự định). Đây có thể là kết quả của việc chuyển đổi trực tiếp từ LinkedList sang CLQ với hy vọng loại bỏ đồng bộ hóa của riêng bạn.

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

Một số mã đúng:

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

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

hoặc

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

Answer 2

ConcurrentLinkedQueue [là] một vô biên, thread-safe, FIFO theo lệnh hàng đợi. Nó sử dụng một cấu trúc liên kết, tương tự như những gì chúng ta đã thấy trong Phần 13.2.2 làm cơ sở cho các danh sách bỏ qua, và trong Phần 13.1.1 cho chuỗi tràn bảng băm. Chúng tôi nhận thấy rằng một trong những điểm thu hút chính của các cấu trúc liên kết là các hoạt động chèn và loại bỏ được thực hiện bởi các sắp xếp con trỏ thực hiện trong thời gian không đổi. Điều này làm cho chúng đặc biệt hữu ích khi triển khai hàng đợi, nơi các hoạt động này luôn được yêu cầu trên các ô ở cuối của cấu trúc, tức là các ô không cần phải được định vị bằng cách sử dụng tìm kiếm tuần tự chậm của các cấu trúc liên kết.

ConcurrentLinkedQueue sử dụng thuật toán miễn phí dựa trên CAS, đảm bảo rằng bất kỳ luồng nào cũng có thể hoàn thành hoạt động hiện tại của nó, bất kể trạng thái của các chuỗi khác truy cập hàng đợi. Nó thực hiện chèn hàng và loại bỏ các hoạt động trong thời gian không đổi, nhưng yêu cầu thời gian tuyến tính để thực hiện size. Điều này là do thuật toán, dựa trên sự hợp tác giữa các luồng để chèn và loại bỏ, không theo dõi kích thước hàng đợi và phải lặp qua hàng đợi để tính toán nó khi nó được yêu cầu.

Từ Java Generics and Collections, ch. 14.2.

Lưu ý rằng ConcurrentLinkedQueue không triển khai giao diện List, vì vậy, nó chỉ thay thế cho LinkedList nếu sau này chỉ được sử dụng làm hàng đợi. Trong trường hợp này, ConcurrentLinkedQueue rõ ràng là một lựa chọn tốt hơn. Không nên có vấn đề hiệu suất lớn trừ khi kích thước của nó thường xuyên được truy vấn. Nhưng với tư cách là một tuyên bố từ chối trách nhiệm, bạn chỉ có thể chắc chắn về hiệu suất nếu bạn đo lường nó trong môi trường và chương trình cụ thể của riêng bạn.