Arraylist throws ConcurrentModificationException when it has a high number of values

Question

So here is my issue, I have an ArrayList, it contains all of the entities that should be rendered to the screen.

It does so like this with a foreach loop.

for (Entity e : entities) {
    g.fillRect(x, y, w, h);
}

This works perfectly fine with no errors when it is populated with a lower numbers of values such as 50. That is, the size of the list is 50. However when it is something like 1,000 it throws a ConcurrentModificationException and crashes the app.

I know that the exception means the list has been modified whilst iterating through it, but in that loop is never actually does anything to the list. The list is accessed elsewhere to update things, but shouldn't the foreach loop finish before something else happens that modifies the list?

The list is modified in an update method which updates entities.

The zombies are enemies in a sense and survivors are AI. When a zombie collides with an AI it removed the survivor and replaces it with a survivor. This is the only place the lists are modified.

This all works perfectly when it is dealing with a small number of entities, however with a larger number it crashes.

public void update(double delta) {
    for (Zombie z : zombies) {
        z.update(delta);
    }
    for (Survivor s : survivors) {
        s.update(delta);
    }

    List<Survivor> toRemove = new ArrayList<Survivor>();
    List<Zombie> toAdd = new ArrayList<Zombie>();

    for (Survivor s : survivors) {
        for (Zombie z : zombies) {
            if (z.collides(s)) {
                toAdd.add(new Zombie(s.position, this, zms));
                toRemove.add(s);
            }
        }
    }

    for (Survivor s : toRemove) {
        survivors.remove(s);
    }

    for (Zombie z : toAdd) {
        zombies.add(z);
    }
}

Answer 1

public void update(double delta)

This method sounds like one that's being called by an engine of some sort, which is almost certainly in another thread.

for (Entity e : entities) {
    g.fillRect(x, y, w, h);
}

This is running in your swing thread, which is separate.

When you have a few number of entities it is likely that this operation may complete atomically. When you have a much larger number of entities, you have a much higher chance of swapping into another thread to do work in the middle of drawing the entities.

The fix(I'm assuming zombies and survivors are entities):

synchronized(entities)
{
    for (Survivor s : toRemove) {
        survivors.remove(s);
    }

    for (Zombie z : toAdd) {
        zombies.add(z);
    }
}

And in your paint:

synchronized(entities)
{
    for (Entity e : entities) {
        g.fillRect(x, y, w, h);
    }
}

This will ensure that only 1 thread can be in one of the synchronized blocks at a time, forcing them to happen separate from eachother

EDIT: This has a possibility of painting a frame after a collision has occurred. If your frame rate is high enough this will be completely unnoticeable. If you do start to notice it, then you may need to do a little bit more work so that once an update starts, a paint will not start until completely done.

Answer 2

To avoid synchronization, you should think about using the list read-only.

That is, in update(), don't remove from the list, but copy survivors to a new list, then add zombies to that new list. Finally, you can replace the reference to the old list with one to the new list. This only requires synchronization on the object that holds this reference. But because the replacement of a reference is really cheap, synchronization wouldn't cause another trhread to wait too long.

// pseudo code
newList = update(entities);    // takes some time
synchronized (this) {
    entities = newList;        // is quasi-immediate
}

Don't forget to make the getter for entities synchronized, too, and access entities only through the getter.