5

以下代码会导致ConcurrentModificationException副作用或其他副作用吗?

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

考虑到列表的大小非常大,并且在执行上述代码时另一个线程正在同时修改列表。

4

3 回答 3

9

编辑:

我最初的回答是肯定的,但正如@JohnVint 正确指出的那样,这不会是ConcurrentModificationException因为在幕后ArrayList使用System.arrayCopy(...). 见最后的代码片段。

问题是在您执行此副本时,另一个线程正在对元素数组进行更改。您可能会得到IndexOutOfBoundsException未初始化的数组值,甚至是某种本机内存访问异常,因为System.arraycopy(...)这是在本机代码中完成的。

您将需要在更新和复制期间同步列表以防止这些竞争条件以及建立内存屏障以确保支持的元素数组ArrayList是适当的最新的。


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);
于 2012-06-14T14:02:03.227 回答
1

你需要考虑你在这里做什么。如果list' 的类不是线程安全的,则可以list使用此代码完全销毁,以及newList--a CME 将是您的问题中最少的。(我建议使用不抛出 CME 的类,但在这种情况下,CME 是一件好事。)另请注意:这段代码很难测试。您将在每次失败之间获得零到十亿次无问题运行之间的某个位置,并且失败可能非常微妙,尽管它们更有可能是大规模的并且超出了合理的解释。

最快的解决方法是锁定list. 您要确保在使用它的任何地方都将其锁定;您并没有真正锁定列表,而是锁定了您从中访问它的代码块。您必须锁定所有访问权限。缺点是您将在创建新列表时阻塞另一个线程。这真的是要走的路。但是,如果如您所说,“列表非常庞大”,您可能会担心性能,所以我会继续......

如果newList将其视为不可变的并且您在创建后经常使用它,那么这样做是值得的。newList现在可以毫无问题地同时读取大量代码,并且不必担心不一致。但是最初的创作仍然存在阻碍。

下一步是创建list一个 java.util.ConcurrentLinkedQueue。(如果您需要更高级的东西,可以使用并发映射和设置。)这个东西可以有一堆线程读取它,同时添加和删除更多线程,它总是有效的。它可能不包含认为它包含的内容,但迭代器不会进入无限循环(如果list是 java.util.LinkedList 可能会发生这种情况)。这可以newList让您在一个核心上创建,而您的另一个线程在另一个上工作。

缺点:如果list是 ArrayList,您可能会发现切换到并发类需要做一些工作。并发类使用更多内存并且通常比 ArrayList 慢。更重要的是: 的内容list可能不一致。(实际上,您已经遇到了这个问题。)您可能会在另一个线程中同时添加或删除条目 A 和 B,并期望两者都或都不在 中newList,而实际上只有一个很容易在那里,迭代器在添加或删除一个之后但在另一个之前通过。(单核机器没有这么多的问题。)但是如果list已经被认为处于恒定的、无序的流动中,这可能正是你想要的。

另一个不同的副作用: 您必须小心使用大型数组和使用它们的东西(如 ArrayList 和 HashTable)。当您删除条目时,它们不会使用更少的空间,因此您最终可能会得到一堆包含少量数据的大型数组,从而占用您的大部分内存。

更糟糕的是,当您添加条目时,它们会释放旧数组并分配一个新的更大的数组,这会导致空闲内存碎片化。也就是说,空闲内存大部分变成了旧数组中的废弃块,这些块都不足以用于下一次分配。垃圾收集器会尝试对所有这些进行碎片整理,但工作量很大,而且 GC 倾向于抛出内存不足的异常,而不是花时间重新排列空闲块,以便它可以得到最大的内存块。刚要求。因此,当只有 10% 的内存在使用时,就会出现内存不足错误。

数组是最快的东西,但你需要小心使用大数组。注意每次分配和免费。给他们一个适当的初始大小,这样他们就不会重新分配空间。(假设你是一个 C 程序员。)善待你的 GC。如果您必须创建、释放和调整大列表的大小,请考虑使用链接类:LinkedList、TreeMap、ConcurrentLinkedQueue 等。它们只使用少量内存,GC 喜欢它们。

于 2012-06-14T16:00:04.513 回答
0

我创建了一些代码来测试@Gray 所说的内容。从数组列表中删除时使用复制构造函数会导致创建的列表中出现空元素。您可以在以下代码中看到错误条目的数量不断增加:

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));
    }
}
于 2017-03-19T19:21:55.117 回答