Sửa đổi đồng thời danh sách khi sử dụng hàm tạo bản sao

Question

Mã sau đây có gây ra ConcurrentModificationException hoặc các tác dụng phụ khác không?

ArrayList<String> newList = new ArrayList<String>(list); 

Xét rằng kích thước của danh sách là rất lớn và một sợi là đồng thời sửa đổi danh sách khi trên đang nhận được thực hiện.

Answer 1

Edit:

phản ứng ban đầu của tôi là có, nhưng như @JohnVint một cách chính xác chỉ ra, nó sẽ không được một ConcurrentModificationException từ dưới lớp chăn ArrayList được sao chép mảng sử dụng System.arrayCopy(...). Xem đoạn mã ở cuối.

Vấn đề là một chuỗi khác đang thực hiện thay đổi đối với mảng phần tử khi bạn thực hiện bản sao này. Bạn có thể nhận được IndexOutOfBoundsException, giá trị mảng chưa được khởi tạo hoặc thậm chí một số loại ngoại lệ truy cập bộ nhớ riêng từ System.arraycopy(...) được thực hiện bằng mã gốc.

Bạn sẽ cần phải đồng bộ hóa trên danh sách trong cả bản cập nhật và bản sao để bảo vệ khỏi các điều kiện chủng tộc này cũng như thiết lập hàng rào bộ nhớ để đảm bảo mảng phần tử sao lưu ArrayList được cập nhật một cách thích hợp.

---

public ArrayList(Collection<? extends E> c) { 
    elementData = c.toArray(); 
    ... 
} 

// ArrayList 
public Object[] toArray() { 
     return Arrays.copyOf(elementData, size); 
} 

// Arrays 
public static <T,U> T[] copyOf(U[] original, int newLength, 
    Class<? extends T[]> newType) { 
    ... 
    System.arraycopy(original, 0, copy, 0, 
     Math.min(original.length, newLength)); 
} 

// System 
public static native void arraycopy(Object src, int srcPos, 
    Object dest, int destPos, int length); 

Answer 2

Bạn cần phải suy nghĩ về những gì bạn đang làm gì ở đây. Nếu lớp học của list không an toàn cho luồng, bạn có thể hủy hoàn toàn list bằng mã này, cùng với newList --a CME sẽ là vấn đề ít nhất của bạn. (Tôi muốn đề nghị một lớp học không ném CME, nhưng trong trường hợp này, CME là một điều kiện tốt.) Cũng lưu ý: mã này khó kiểm tra. Bạn sẽ nhận được một nơi nào đó giữa số không và một tỷ vấn đề không có vấn đề giữa mọi thất bại, và thất bại có thể rất tinh tế, mặc dù chúng có nhiều khả năng là lớn hơn và vượt ra ngoài lời giải thích hợp lý.

Khắc phục nhanh nhất là khóa list. Bạn muốn chắc chắn để khóa nó ở khắp mọi nơi nó được sử dụng; bạn không thực sự khóa danh sách , bạn đang khóa chặn mã bạn đang truy cập. Bạn phải khóa tất cả các quyền truy cập. Nhược điểm là bạn sẽ chặn các thread khác trong khi danh sách mới đang được tạo ra. Đây thực sự là con đường để đi. Tuy nhiên, nếu, như bạn nói, "danh sách rất lớn", bạn có thể quan tâm đến hiệu suất, vì vậy tôi sẽ tiếp tục ...

Có thể thực hiện điều này nếu newList được coi là không thay đổi và bạn thực hiện thường xuyên sử dụng nó một khi được tạo ra. Rất nhiều mã bây giờ có thể đọc newList đồng thời mà không gặp sự cố và mà không sợ sự mâu thuẫn. Nhưng vẫn có sự giữ vững với sự sáng tạo ban đầu.

Bước tiếp theo là tạo list một java.util.ConcurrentLinkedQueue. (Có một bản đồ đồng thời và thiết lập nếu bạn cần một cái gì đó fancier.) Điều này có thể có một loạt các chủ đề đọc nó trong khi một bó thêm được thêm vào và xóa nó, và nó luôn luôn hoạt động. Nó có thể không chứa những gì bạn nghĩ rằng nó có chứa, nhưng một iterator sẽ không đi vào một vòng lặp vô hạn (như có thể xảy ra nếu list là một java.util.LinkedList). Điều này cho phép newList được tạo trên một lõi trong khi luồng khác của bạn hoạt động trên một lõi khác.

Nhược điểm: nếu list là một ArrayList, bạn có thể tìm thấy nó một chút công việc để chuyển sang một lớp đồng thời. Các lớp đồng thời sử dụng nhiều bộ nhớ hơn và thường chậm hơn ArrayList. Quan trọng hơn nhiều: nội dung của list có thể không phù hợp. (Trên thực tế, bạn đã có vấn đề này.) Bạn có thể thêm hoặc xóa các mục A và B cùng một lúc trong chuỗi khác và hy vọng rằng cả hai hoặc cả hai sẽ không nằm trong newList, khi thực tế nó chỉ đơn giản là một ở đó, trình lặp đi qua sau khi một người được thêm vào hoặc gỡ bỏ nhưng trước khi người kia có. (Máy đơn lõi không có vấn đề này nhiều). Nhưng nếu list đã được nghĩ đến như là một hằng số, rối loạn thông lượng, điều này có thể chỉ là những gì bạn muốn.

Một, khác nhau, tác dụng phụ: bạn phải cẩn thận với mảng lớn và những thứ sử dụng chúng (như ArrayList và HashTable). Họ không sử dụng ít không gian hơn khi bạn xóa các mục, vì vậy bạn có thể kết thúc với một loạt các mảng lớn với ít dữ liệu trong đó chiếm hầu hết bộ nhớ của bạn.

Tệ hơn nữa, khi bạn thêm mục nhập, chúng sẽ giải phóng mảng cũ của chúng và phân bổ mảng mới, lớn hơn, dẫn đến việc phân mảnh bộ nhớ trống. Đó là, bộ nhớ miễn phí trở thành phần lớn các ký tự đại diện từ các mảng cũ, không có bộ nhớ nào đủ lớn để sử dụng cho lần phân bổ tiếp theo. Garbage Collector sẽ cố gắng chống phân mảnh tất cả điều này, nhưng nó có rất nhiều công việc và GC có khuynh hướng ném ra các bộ nhớ ngoài thay vì dành thời gian sắp xếp lại các khối miễn phí để nó có thể chặn khối bộ nhớ lớn nhất mà bạn vừa được yêu cầu. Vì vậy, bạn nhận được một lỗi out-of-bộ nhớ khi chỉ có 10% bộ nhớ của bạn đang được sử dụng.

Mảng là điều nhanh nhất, nhưng bạn cần phải sử dụng những cái lớn cẩn thận. Hãy nhận biết của mỗi phân bổ và miễn phí. Cung cấp cho họ một kích thước ban đầu thích hợp để họ sẽ không tái phân bổ không gian. (Giả sử bạn là một lập trình viên C.) Hãy tử tế với GC của bạn. Nếu bạn phải tạo và miễn phí và thay đổi kích thước các danh sách lớn, hãy cân nhắc sử dụng lớp được liên kết: LinkedList, TreeMap, ConcurrentLinkedQueue, v.v. Chúng chỉ sử dụng một chút bộ nhớ và GC yêu chúng.

Answer 3

Tôi đã tạo một số mã để kiểm tra xem @Gray đã nói gì. Việc sử dụng hàm tạo bản sao trong khi loại bỏ khỏi danh sách mảng dẫn đến các phần tử null trong danh sách được tạo. Bạn có thể thấy điều này vì số lượng mục nhập sai tăng liên tục trong đoạn mã sau đây:

public static void main(String[] args) { 

    final int n = 1000000; 
    final int m = 100000; 
    final ArrayList<String> strings = new ArrayList<String>(n); 

    for(int i=0; i<n; i++) { 
     strings.add(new String("abc")); 
    } 


    Thread creatorThread = new Thread(new Runnable() { 
     @Override 
     public void run() { 
      ArrayList<String> stringsCme = new ArrayList<String>(strings); 
      int wrongEntries = 0; 
      for(int i=0; i<m; i++) { 
       stringsCme = new ArrayList<String>(strings); 

       for(String s : stringsCme) { 
        if(s == null || !s.equals("abc")) { 
         //System.out.println("Wrong entry: " + s); 
         wrongEntries++; 
        } 
       } 

       if(i % 100 == 0) 
        System.out.println("i = " + i + "\t list: " + stringsCme.size() + ", #wrong entries: " + wrongEntries); 
      } 

      System.out.println("#Wrong entries: " + wrongEntries); 
     } 
    }); 
    creatorThread.start(); 

    for(int i=0; i<m; i++) { 
     strings.remove(MathUtils.random(strings.size()-1)); 
    } 
}