Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (526)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (593)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  java.util.ConcurrentModificationException  (Read 2530 times)
0 Members and 1 Guest are viewing this topic.
Offline Renoria

Junior Devvie




...


« Posted 2009-04-10 15:47:41 »

I keep getting this problem.. no matter what I try it always fails.

I've tried:

1) Synchronizing the method

2) Synchronizing the access (synchronized(MUTEX))

3) Using an Iterator<>

4) Using the normal for ( ; ; ) loop

5) Using foreach version of the for loop

^^ All the above methods fail.. any advice?
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2009-04-10 16:02:05 »

You cannot / should not modify a collection while iterating over it.

Unless you use myIterator.remove()

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Renoria

Junior Devvie




...


« Reply #2 - Posted 2009-04-10 16:06:26 »

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..?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline tom
« Reply #3 - Posted 2009-04-10 16:23:32 »

Create a copy of the collection and iterate over the copy. Maybe use CopyOnWriteArrayList. Although it is not the most efficient way.

Offline Renoria

Junior Devvie




...


« Reply #4 - Posted 2009-04-10 16:30:40 »

Will that cause memory leaks coping it every 20 millseconds?
Offline Gudradain
« Reply #5 - Posted 2009-04-10 16:34:42 »

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.
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #6 - Posted 2009-04-10 16:46:55 »

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):

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
   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();
   }

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline Renoria

Junior Devvie




...


« Reply #7 - Posted 2009-04-10 16:57:43 »

Ahh I see. Thanks for the help.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2009-04-10 16:58:25 »

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.


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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
List items = new ArrayList();
List retain = new ArrayList();

for(Object item: items)
{
    if(needed(item))
    {
        retain.add(item);
    }
}

items.clear();
items.addAll(retain);

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #9 - Posted 2009-04-10 17:25:11 »


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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
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(2*n) (removing all objects which is never the case), but in your idea is O(3*n) (when keeping all objects which is almost always the case)


Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Renoria

Junior Devvie




...


« Reply #10 - Posted 2009-04-10 17:45:55 »


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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
List items = new ArrayList();
List retain = new ArrayList();

for(Object item: items)
{
    if(needed(item))
    {
        retain.add(item);
    }
}

items.clear();
items.addAll(retain);


That was what I used to do, and it created 1 linkedlist every 20 millseconds therefore lagging the game out.
Offline ewjordan

Junior Devvie





« Reply #11 - Posted 2009-04-10 20:31:17 »

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.
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<Float> 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:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
      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.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #12 - Posted 2009-04-10 21:05:25 »

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.

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 Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2009-04-10 21:20:40 »


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


1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
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);
   }
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #14 - Posted 2009-04-10 21:27:17 »

Needless to say it's best to work with Sets when your data is highly dynamic. Lips Sealed persecutioncomplex

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Mr_Light

Senior Devvie


Medals: 1


shiny.


« Reply #15 - Posted 2009-04-10 21:33:07 »

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.

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

toopeicgaming1999 (71 views)
2014-11-26 15:22:04

toopeicgaming1999 (60 views)
2014-11-26 15:20:36

toopeicgaming1999 (14 views)
2014-11-26 15:20:08

SHC (27 views)
2014-11-25 12:00:59

SHC (25 views)
2014-11-25 11:53:45

Norakomi (31 views)
2014-11-25 11:26:43

Gibbo3771 (25 views)
2014-11-24 19:59:16

trollwarrior1 (38 views)
2014-11-22 12:13:56

xFryIx (77 views)
2014-11-13 12:34:49

digdugdiggy (55 views)
2014-11-12 21:11:50
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!