ConcurrentModificationException when removing an item from an arraylist

Newbie & Debugging Questions
#1

Hey guys, in my game I keep track of entities such as the player and items in an arraylist


  public static ArrayList<Entity> entities = new ArrayList <Entity>();
  
  //this method adds entities to the "entities" arraylist
  public static void entityAdder(){
    entities.add(new Player(100, 100));
    entities.add(0, new ItemEntity (200, 200, 0, 1));
    entities.add(0, new ItemEntity (50,50, 1, 1));}

I have enhanced for loops in my program that draw each entity and keep track of their locations.

Right now I’m trying to work out how to pick up items and place them into my inventory, I figured to do this when I pick up the item i’ll need to remove it from my arraylist of entities so that my enhanced for loops dont draw them or keep track of their location anymore. Only thing is now when I go to pick the item up I get this exception.


Exception in thread "Thread2" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(UnknownSource)
at java.util.ArrayList$Itr.next(Unknown Source)

Any ideas on how I could work around this?

#2

Using multiple threads that try to modify the same object at the same time, OR
doing


for(Entity entity:entities) {
entities.remove(entity);
}
#3

either do


for(Iterator<E> i = entities.iterator(); i.hasNext();)
{
  E e = i.next();
  if(...) i.remove();
}

or


for(int i=entities.size()-1; i>=0; i--)
{
  E e = entities.get(i);
  if(...) entities.remove(i);
}
#4

If I read your question correctly, the animation loop is continually cycling through the entity list and drawing objects. If you try to remove something during one of these rendering iterations, the concurrent modification exception occurs.

Instead of an ArrayList, you might be able to get the functionality you need by using an CopyOnWriteArrayList.
http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/CopyOnWriteArrayList.html

This is a reasonable collection to use if the iterations are frequent (as they would be with game loop rendering) and the modifications to the array are relatively infrequent. I’m not sure exactly how it is implemented, but once an iteration starts it goes through to completion with the collection as it existed at the start of the iteration, even if you make a modification to the collection during this iteration. On the next iteration, the updated collection will be used. Thus, in terms of game loop rendering, you will never be more than a single frame off.

The other alternatives that I can think of are to use synchronization, or include a pause between iterations to manage the array state. But with the CopyOnWriteArrayList, you can probably retain most of the code you already have without writing any of the additional management or synchronization. Just swap it in for the ArrayList.

#5

Or create your own synchronised list, which is harder than it sounds.

I believe libgdx Array is thread safe, might be wrong.

#6

There is one synchronized list: Collections.synchronizedList()

 List list = Collections.synchronizedList(new ArrayList());
      ...
  synchronized (list) {
      Iterator i = list.iterator(); // Must be in synchronized block
      while (i.hasNext())
          foo(i.next());
  }
#7

The best way is to use two [icode]ArrayList[/icode] objects - one contains the actual objects and the other one to store the objects that are marked for removal. Remove at the end of the iteration.


ArrayList objects = ...
ArrayList removed = ...

for (int i=0; i<objects.size(); i++)
{
    if (...)
        removed.add(objects.get(i));
}

objects.removeAll(removed);
removed.clear();

Hope this helps.

#8

Here is the method I always use ATM.


for(int i=0;i<entities.size();i++){
     Enitity entity=entities.get(i);
     entity.update();
     if(entity.removed) {
          entities.remove(entity);
          i--;
     }
}
#9

No!
don’t do a remove all, this is a very expansive operation. Just double-buffer your entity list.

  • use 2 lists
  • each iteration move all still living entities to the next list
  • clear the first list
  • swap the two lists, so the second(which you just filled with the live entities is now the first)
  • render the first list and repeat
#10

@Danny02

You were right! I did a quick google and found this. http://stackoverflow.com/a/7032144/1026805

#11

[quote]No!
don’t do a remove all, this is a very expansive operation. Just double-buffer your entity list.

use 2 lists
each iteration move all still living entities to the next list
clear the first list
swap the two lists, so the second(which you just filled with the live entities is now the first)
render the first list and repeat

[/quote]
If you are copying the array every iteration, why not use the CopyOnWriteArrayList? It should be much less costly, as the copies are only made when something is added or deleted to the collection (and done so automatically by core Java programmers who really do understand the architecture–no need to code and debug it yourself).

How often does someone pick up or discard an object, in game frame iterations? If you do this once every 5 or 10 seconds, at 60 fps, that’s like one copy of the array for every 300 to 600 iterations, instead of doing it every time.

Is there some drawback to CopyOnWriteArrayList that I don’t know about? ??? I mean, besides the really long and strange name?

#12

CopyOnWriteArrayList is really not fit for this problem. CopyOnWriteArrayList main advantage over a normal ArrayList is that it’s thread safe since every time you modify the list it creates a brand new internal array, allowing all old Iterator objects to keep using the previous array of the ArrayList. They solve a completely different problem.

Double buffering using two ArrayLists has many advantages in our case.

  • The only functions we’ll ever use is add(Object object), get(int index) and clear(), so we can avoid the slow remove(int index) or the even worse remove(Object object).
  • We generate no garbage since the two lists are reused forever (except for when the list needs to be resized).

The whole point is that we copy all objects between the two lists during each update. This allows us to mark an element for deletion and then simply not copy it to the other list during the next update, giving us a new compacted list. If we remove something from a CopyOnWriteArrayList using remove(), it would first of all generate a new internal array and copy all elements to it but skipping the removed object. This happens for every single remove. If we remove all objects in a 1000 from CopyOnWriteArrayList, we’re generating 1000 new arrays and copying around 500 000 elements. If we “remove” 1000 objects from a double buffered ArrayList, we simply loop through the list, notice that the elements are all dead and copy none of them to the other list.

#13

If the order is not important, you can write your own list class that avoids all the overloads. Every time an element is deleted, you can overwrite the deleted item with the last item in the list, then decrease the list size counter. That way you can remove items without speed penalty and you don’t need two lists, and all the copies that can be worse than the deletes. I have use this in my Retroships game and it works like a charm.

#14

[quote]CopyOnWriteArrayList is really not fit for this problem. CopyOnWriteArrayList main advantage over a normal ArrayList is that it’s thread safe since every time you modify the list it creates a brand new internal array, allowing all old Iterator objects to keep using the previous array of the ArrayList. They solve a completely different problem.
[/quote]
But it seems to me that that is actually a very good description of the problem. The inventory list, if used for display purposes, and is being iterated every draw. (If I have this wrong, never mind!) Thus, we have a situation where traversals vastly outnumber mutations. And the exception that occurs is due to the ArrayList not being thread safe for the occasional concurrent modifications (during iteration), a situation that is safe with CopyOnWriteArrayList.

Why code the copying an array’s contents 600 times (if 60fps, that’s 10 seconds between picking up a new item or dropping an item, on average), when a CopyOnWriteArray only copies the array once in that same use case, and does it for you, behind the scenes? And, we are only dropping one item, probably, out of several dozens at most (I’m guessing), and not dealing with a list of 500,000 elements. Again, I could be wrong if I misunderstood what the OP is trying to do.

I’m surprised to hear that an isolated single, occasional delete from a supposedly optimized-for-random-access array would be so exorbitantly costly.

In your method, how do you “mark” an object in a array for deletion? Are you doing searches or tests to match items in one array with another? All this costs cpu too.

I guess the main thing is to test the two methods and see. I’ve been surprised many times by the results of profiling. And it could very well be that the number of objects involved are low enough that efficiency isn’t even really much of an issue, in which case swapping in one type of thread safe array for another surely beats writing a bunch of additional code.

#15

#16

CopyOnWriteArrayList solves nothing in this case. Just using a (single) ArrayList is sufficient in this case. CopyOnWriteArrayList will always copy all objects in the list on each write, while ArrayList only needs to compact its array by shifting elements to fill the gap of the removed object, which on average is half the objects. In addition it generates a significant amount of garbage due to the arrays being created. From a performance view CopyOnWriteArrayList is worse in all cases. However, for something as simple as a few items that aren’t even being updated each frame any performance wins are insignificant, so this whole argument is meaningless.

My interpretation of the original post was that he was talking about his game entities, e.g. objects that are updated each frame. In that case we already have a loop over the objects in place. This is a perfect fit for a double buffered ArrayList, since the additional overhead per frame will be very low.

Original code using only one ArrayList:


ArrayList<Entity> entities = ...;

for(int i = 0; i < entities.size(); i++){
    Entity e = entities.get(i);
    e.update();
    if(!e.isAlive()){
        entities.remove(i--);
    }
}

Double buffered ArrayList:


ArrayList<Entity> entities1 = ...;
ArrayList<Entity> entities2 = ...;

for(int i = 0; i < entities1.size(); i++){
    Entity e = entities1.get(i);
    e.update();
    if(e.isAlive()){
        entities2.add(e);
    }
}
entities1.clear();
ArrayList<Entity> temp = entities1;
entites1 = entities2;
entities2 = temp;

This has several performance advantages. The biggest performance related win isn’t peak performance since adding the objects to a second list isn’t free (although it is cheap). The win here lies in predictable performance. Often you’ll get to a point where many objects die simultaneously. Maybe there was an explosion, maybe all the pellets fired from a shotgun hit a wall at almost the same time, maybe a parent object died so all child objects automatically died as well, etc etc etc. In addition, such events generally are slow to compute in the first place (expensive collision detection, having to update all child objects, etc), so we already have a smaller time budget than usual. Let’s say that we use the single ArrayList approach and we have 1000 objects and 100 die within a single frame, the average list size will be 950 and we need to on average move half those objects each update. That’s 47 500 moves in a single frame. A CopyOnWriteArrayList would in this case have to copy all objects, not just the following ones, so we’d be copying the full 95 000 object in a single frame. The result is a horrible performance spike where we’re potentially freezing up the game for several milliseconds for no good reason. Using a double buffered ArrayList we only suffer a small predictable performance hit to be able to get rid of all remove()s for that list, elimination copy “bursts” consisting of tens of thousands of copies for a static 1 000 copies per frame.

What exactly is CopyOnWriteArrayList supposed to solve here? It’s only advantage over a normal ArrayList is that it’s thread safe. Nowhere does OP say that he’s using multiple threads. ConcurrentModificationExceptions are generally caused by people removing stuff from within a for-each loop which have a hidden Iterator object.

#17

Yeah I am working with in-game objects such as items and enemies and such. I think your method with the double buffered arraylist is the way i’m going to go with, I do have a couple of questions though, when I originally add entities to my game, do I add them using the entities1 arraylist? like


entities1.add( new ItemEntity (200, 200, 1, 1, false));
entities1.add( new ItemEntity (50,50, 0, 1, false));
entities1.add(new Player(100, 100));

I am also using for loops to draw the sprites of each Entity with this loop


 for(Entity p : GamePlayState.entities){
     Image img =p.getSprite();
     if (img!=null)
     g.drawImage(img,p.getX(),p.getY(),this);
 }

my last question is the isAlive method on line 7, I assume i’ll be adding this method to my entities interface, iv tried somthing similar before, but whenever called it would remove all the entities, so any help with that method would be really helpful too (:

#18

You’re correct about adding entities to the first entity list (entities1). The first list always contains the current list of objects (except during updates while we’re copying).

isAlive() could be as simple as [icode]return health > 0;[/icode] or it could be read from a variable that is set by the update() code.


public void update(){
    move();
    if(this.hitsWall()){
        alive = false;
    }
}

public boolean isAlive(){
    return alive;
}

This idea is to instead of immediately deleting the object from the list, we simply mark it for deletion so that it’s automatically removed later.

Your rendering loop will work fine and should only loop over entities1 without doing any copying.

#19

Would it be better to use a temporary byte to store which list is the main list, instead of creating a 3rd list?

#20

There’s no 3rd list being created. Those are all just references.


ArrayList<Entity> entities1 = new ArrayList();
ArrayList<Entity> entities2 = new ArrayList();
ArrayList<Entity> temp = null;

entities1 = ArrayList instance 1
entities2 = ArrayList instance 2
temp = null

ArrayList<Entity> temp = entities1;

entities1 = ArrayList instance 1
entities2 = ArrayList instance 2
temp = ArrayList instance 1 <—

entites1 = entities2;

entities1 = ArrayList instance 2 <—
entities2 = ArrayList instance 2
temp = ArrayList instance 1

entites2 = temp;

entities1 = ArrayList instance 2
entities2 = ArrayList instance 1 <—
temp = ArrayList instance 1

We have 3 different references; entities1, entities2 and temp, but only 2 actual objects/instances.