ConcurrentModificationException when removing an item from an arraylist

[GoToLoop]

@Endos

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.

Loved your tip, Endos. I wish I’d known about that technique before! Although I didn’t need to write my own List class at all.
A regular ArrayList is capable to pull that out. Check it out:

static final int BULLETS = 100;
final List<Bullet> bullets = new ArrayList<>(BULLETS);

public void displaySpritesRegular() {
  stroke(Bullet.COLOUR);
  for (int b = bullets.size(); b-- != 0;)
    if (bullets.get(b).script()) {
      bullets.remove(b);
      System.out.println("A bullet has strayed too far from view!");
    }
}

public void displaySpritesOptimized() {
  stroke(Bullet.COLOUR);
  for (int b = bullets.size(), len = b; b-- != 0;)
    if (bullets.get(b).script()) {
      final Bullet u = bullets.remove(--len);
      if (b != len)  bullets.set(b, u);
      System.out.println("A bullet has strayed too far from view!");
    }
}

[Endos]

@GoToLoop

@Endos

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.

Loved your tip, Endos. I wish I’d known about that technique before! Although I didn’t need to write my own List class at all.
A regular ArrayList is capable to pull that out. Check it out:

static final int BULLETS = 100;
final List<Bullet> bullets = new ArrayList<>(BULLETS);

public void displaySpritesRegular() {
  stroke(Bullet.COLOUR);
  for (int b = bullets.size(); b-- != 0;)
    if (bullets.get(b).script()) {
      bullets.remove(b);
      System.out.println("A bullet has strayed too far from view!");
    }
}

public void displaySpritesOptimized() {
  stroke(Bullet.COLOUR);
  for (int b = bullets.size(), len = b; b-- != 0;)
    if (bullets.get(b).script()) {
      final Bullet u = bullets.remove(--len);
      if (b != len)  bullets.set(b, u);
      System.out.println("A bullet has strayed too far from view!");
    }
}

Yes, this will work, but as the source code is available, IMO, is better to write your own class based on that source and just call remove without any check and additional work.

And for your concrete example, you could make a variation, as for sure if you remove any bullet, you will need to add new bullets again. Instead of overwriting the removed item with the last one, you can exchange both values. That way you can have in one list an “in use” and “unused” list of bullets. When you needs a new bullet, the only thing you needs is increase the size counter and return the last element to reuse it, if there is one of course.

[philfrei]

@theagentd Thanks for the explanation, and the code posted. Duh, I’ve been thinking too much on the surface (more involved with other work) to recall the exact details of this technique which I have used before. I can see where CopyOnWriteArrayList could make a single iteration spike in length relative to the others, especially if we are talking about a huge number of missiles flying around, many of which require updating. The more updating happening, the less useful CopyOnWriteArrayList is.

I’m used to working with multiple threads, have only created this error myself in a concurrent use situation. It is hard for me to imagine this error coming up otherwise. If this is happening in a single-thread scenario, that implies code embedded within the render iteration would be altering the array contents, and that raises all sorts of red flags! Render and game state updating should be better isolated from each other.

I’d still like to see a use case that demonstrates the performance differences. Maybe I can find some time to write a short example like the 1000 missiles scenario and test this both ways. And, add a chart that looks at how big a percentage of the units are born or die each iteration and how this impacts the performance. Clearly, though, if there are entity updates every render cycle, it is not a good solution. But if entity updates are rare, relative to rendering (e.g., a hundred renders between updates) then I would want to test the alternatives.

I don’t know enough about the internals of CopyOnWriteArrayList to know how it impacts GC.

P.S., the idea of having pools of Bullets and swapping used ones in and out seems interesting as well. I’ve used something similar in managing notes for a polyphonic synth, where the total number of notes playing at one time has a fixed limit, and we only want to process active notes in the audio loop.

[philfrei]

Thread is going old, and OP has found an acceptable answer.

I’m only posting to say I wrote out a test case, trying both the double buffer array method and just using a single CopyOnWriteArrayList. With 300 entities, I can find no difference in timing between the two methods. I basically am setting a nanoTimer at the beginning of a render and ending it at the end, and accumulating render periods over the test time. The maximum (since our biggest worry is spikes not throughput) render period over the test period is reported.

The variability I get between each test run is much greater than any discernible difference between the two methods. Maybe it becomes relevant with higher numbers of entities. Or maybe a better designed test could tease out the actual difference in performance.

If someone cares enough to ask, I’ll post the test code I wrote. It’s just a bunch of circles moving around–if you click in them they disappear, if you click on a blank part of the screen, an new one appears. Thus we have some adding and deleting to the entity array concurrent with the rendering. The render times are tracked while the mouse is over the JPanel, and results reported when the mouse leaves.