I keep getting this problem… no matter what I try it always fails.
I’ve tried:
Synchronizing the method
Synchronizing the access (synchronized(MUTEX))
Using an Iterator<>
Using the normal for ( ; ; ) loop
Using foreach version of the for loop
^^ All the above methods fail… any advice?
You cannot / should not modify a collection while iterating over it.
Unless you use myIterator.remove()
what if I HAVE to modify it, for example its removing the monster from the map but the panel is still iterating through the paint method…?
Create a copy of the collection and iterate over the copy. Maybe use CopyOnWriteArrayList. Although it is not the most efficient way.
Will that cause memory leaks coping it every 20 millseconds?
I got the same problem recently and I fix it by making a copy of my ArrayList.
But I have a question regarding the synchronization.
I was accessing my ArrayList with a method getList() and I was clearing the list with clearList() in the same class as getList(). I was also iterating through the list I got from getList() and that cause problem when clearList() was call at the same time.
If I had synchronize both getList() and clearList() would it have fix my problem? Or getList() just return a pointer to my ArrayList then the method terminate.
You can create an empty ArrayList (called removeList) before you start iterating that collection. Once you see a item you want to remove, you add it to the removeList. Once you’re done, you can iterate the removeList and remove those items from the collection.
Here’s an example of what I’m using to update a set of entities, and remove dead entities (like killed units, expired bullets):
public void update(int delta) {
for(Entity entity : entities) {
if(entity.isActive()) {
entity.update(delta);
} else {
entitiesInactive.add(entity);
}
}
for(Entity entity : entitiesInactive) {
entities.remove(entity);
}
entitiesInactive.clear();
}
Ahh I see. Thanks for the help.
Unfortunately, that will become extremely slow when your lists get bigger. Every item you remove, will have to be searched throughout the whole list, and on average located in the center of the list. Every remove will also be very slow in an ArrayList (it has to shift all references after the index, to the left - a LinkedList is much faster, but slower to build).
When you’re removing lots of items, or removing few items on a large list, it will become a serious performance bottleneck.
The alternative it so copy everything into a list that you keep, as apposed to remove. Adding to an ArrayList is very fast, and you never have to remove an item.
List items = new ArrayList();
List retain = new ArrayList();
for(Object item: items)
{
if(needed(item))
{
retain.add(item);
}
}
items.clear();
items.addAll(retain);
Doesn’t seem to be any performance bottleneck in my game using ArrayList in my games, I have hundreds of bullets flying around and expiring every few seconds. I’ll take a look at the LinkedList idea though, seems like a logical choice of data structure!
However…
I don’t agree with your code example. This requires creating a new ArrayList every time there is an update() call. So, for a game running at 100 FPS this means creating 100 ArrayList’s every 1 second. I can just see the garbage collector going into overdrive and hogging the system.
ArrayList.addAll(): Appends all of the elements in the specified Collection to the end of this list
ArrayList.clear(): Iterates all items in the collection and sets them to null.
Worst case scenario you’re iterating the list THREE TIMES if you’re retaining all the items, which is mostly the case in every game loop.
By modifying my idea to use LinkedList you’ll get O(2n) (removing all objects which is never the case), but in your idea is O(3n) (when keeping all objects which is almost always the case)
That was what I used to do, and it created 1 linkedlist every 20 millseconds therefore lagging the game out.
First, if you’re worried about GC, you can always hang on to the old ArrayList and clear it instead of making a new one.
But there’s no point: 100 ArrayLists every second is never ever ever EVER going to bottleneck your program if you’re running on the desktop, unless you’re either writing literally the most tightly optimized code I’ve ever seen in my life or working with some fantastically large lists.
I ran a quick test, doing a manual filtered ArrayList copy (pretty much exactly as Riven suggested): I started with a 1000 element ArrayList filled with random values between 0 and 1; for each iteration I created a new ArrayList (pre-allocated to the size of the old one so I don’t waste time growing it), and copied elements over unless their values were less than 0.1, in which case I randomly generated new ones. After each iteration I copied the old list into the new one after a clear.
Clearly there’s a lot of inefficient stuff in there, the random calls and the autoboxing; I know this, the point is, you should at least be able to achieve this performance.
I got 17,500 iterations per second on my Macbook Pro using the client JVM. A small GC happened about every 100 iterations, usually taking about .0002 seconds (garbage came from autoboxing).
I tried the same test actually creating new ArrayLists each time, and got very similar results, FWIW.
100 vs. 17,500: That’s not even worth thinking about, let alone optimizing for, unless you’re working on a platform that can’t handle any amount of GC (Android or J2ME, for instance), in which case you’re designing from day one to work around issues like this.
Also, just so we’re being complete, if you really want to alter an ArrayList while you’re iterating over it and don’t want to deal with iterators, it’s easy:
ArrayList<Float> floats = new ArrayList<Float>();
for (int i=0; i < 1000; ++i) {
floats.add(i*1.0f);
}
int i = 0; //handle iteration ourselves, quite manually
while (i < floats.size()) {
if (floats.get(i) % 3 == 0) { //this "evil" comparison actually works, somehow
floats.remove(i);
continue;
}
++i;
}
System.out.println("Not multiples of 3: ");
for (i=0; i<floats.size(); ++i) {
System.out.println(floats.get(i));
}
However, as Riven mentioned, remove calls on ArrayLists are expensive, since they arraycopy the whole tail of the array, and further, floats.size() is not constant so it must be evaluated every time you loop. I’m pretty sure the JVM can optimize away most of those tests as well as most of the bounds checks if you don’t alter the list while iterating.
I didn’t speed test this because it’s bad form anyhow.
3 times, yes.
But, if you remove 6 items from the list (with average position at half), you’re also at 3 times.
Once you remove more than 6 items from the list, my worst case scenario is always faster…
Power of datastructures 
removing 50% of list with 16 items, using KEEP list: 0ms removing 50% of list with 16 items, using REMOVE list: 1ms removing 50% of list with 64 items, using KEEP list: 0ms removing 50% of list with 64 items, using REMOVE list: 1ms removing 50% of list with 256 items, using KEEP list: 0ms removing 50% of list with 256 items, using REMOVE list: 1ms removing 50% of list with 1024 items, using KEEP list: 0ms removing 50% of list with 1024 items, using REMOVE list: 5ms removing 50% of list with 4096 items, using KEEP list: 0ms removing 50% of list with 4096 items, using REMOVE list: 66ms removing 50% of list with 16384 items, using KEEP list: 2ms removing 50% of list with 16384 items, using REMOVE list: 835ms removing 50% of list with 65536 items, using KEEP list: 6ms removing 50% of list with 65536 items, using REMOVE list: 12397ms
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Random;
/*
* Created on Apr 10, 2009
*/
public class ListBench
{
public static void main(String[] args)
{
for (int i = 16; i < 1000000; i *= 2)
{
// create list
Random r = new Random(1234567890L);
int max = 100;
List<Integer> list = new ArrayList<Integer>();
for (int k = 0; k < i; k++)
list.add(Integer.valueOf(r.nextInt(max)));
list = Collections.unmodifiableList(list);
List<Integer> testList1 = new ArrayList<Integer>();
testList1.addAll(list);
List<Integer> testList2 = new ArrayList<Integer>();
testList2.addAll(list);
long t1 = System.currentTimeMillis();
removeAbove_usingKeepList(testList1, max / 2); // remove half
long t2 = System.currentTimeMillis();
removeAbove_usingRemoveList(testList2, max / 2); // remove half
long t3 = System.currentTimeMillis();
System.out.println("removing 50% of list with " + i + " items, using KEEP list: " + (t2 - t1) + "ms");
System.out.println("removing 50% of list with " + i + " items, using REMOVE list: " + (t3 - t2) + "ms");
if (testList1.size() != testList2.size())
throw new IllegalStateException();
}
}
public static void removeAbove_usingRemoveList(List<Integer> list, int max)
{
List<Integer> remove = new ArrayList<Integer>();
for (Integer val : list)
{
if (val.intValue() >= max)
{
remove.add(val);
}
}
list.removeAll(remove);
}
public static void removeAbove_usingKeepList(List<Integer> list, int max)
{
List<Integer> keep = new ArrayList<Integer>();
for (Integer val : list)
{
if (val.intValue() < max)
{
keep.add(val);
}
}
list.clear();
list.addAll(keep);
}
}
Needless to say it’s best to work with Sets when your data is highly dynamic. :-X :persecutioncomplex:
Read up on the 3 things you have to care about with concurrent/parallel programming: Ordering Visibility and Atomicity - Don’t go decorating your whole code with synchronised or some other random language construct.
As for handling removals just leave it to the implementation. If you want to aggregate the removal to reap some performance gains then I guess so - but I’d advice first building a game that actually needs it. Use ravens first suggestion until.
I know this might come across as motherhood and apple pie but yeah.