Concurrency.. ^^

[Regenuluz]

'ello folks,

So I'm storing a LinkedList of entities that does stuff every tick, however this list is modified in a different thread than the thread that loops through it and ticks the entities it holds.

Now as you might've guessed, this is causing ConcurrentModificationExceptions to be thrown left and right! Now, I'd really like to know how the heck I can avoid this problem?

[teletubo]

well just don't access it from different Threads!
You will not only avoid this exception but as well as many other concurrency problems you might face.

But if you really insist on multi threading, take a look at ConcurrentLinkedQueue class.

[Mads]

Vectors could help you, because they're syncronized. The rest of the Collections are not.
Also, the volatile keyword makes sure the field is never stored Thread locally, and access is always as if it's through a syncronized block.

This should make it Thread-safe.

Edit: Proven wrong. 

Games published by our own members! Check 'em out!

[cylab]

This should make it Thread-safe.

Nope http://stackoverflow.com/questions/9059266/does-volatile-mean-it-is-thread-safe

[Regenuluz]

@Teletubo That's a little hard, since one thread is the one handling all my input(That would be the swing one, I suppose) and the other is the one handling the game loop. I might end up using that ConcurrentLinkedQueue, though I don't like that the size() function runs in O(n) instead of constant time.

@Mads According to the javadocs, then vectors aren't going to help me. They'll throw ConcurrentModificationExceptions too, if I try to edit them while iteration through them.

[Orangy Tang]

Vectors could help you, because they're syncronized. The rest of the Collections are not.

The proper way to do it is to use Collections.synchronizedList (or synchronizedMap, etc.) rather than using Vector. Or as teletubo mentions use the collections in java.util.concurrent.*

[cylab]

@Regenuluz
I usually solve this by stuffing Events/Actions/Whatever on non-gameloop-threads into a ConcurrentLinkedQueue and retrieve them for processing in the gameloop-thread. This way you can use whatever collections you want in the gameloop and schedule thread safe modifications from outside.

[princec]

synchronized won't fix concurrent modification problems which are what happens when one thread is iterating and one thread starts changing stuff in the list.

Do this:

1. Stop using LinkedLists anyway. Use ArrayLists.
2. Stop using two threads. Do everything in one thread that needs to be done to that list.

Cas

[Regenuluz]

Well, this:

1	public List<Entity> entitiesToTick = Collections.synchronizedList(new LinkedList<Entity>());

plus this:

1   2   3   4   5

synchronized (entitiesToTick) {    for (Entity e : entitiesToTick) {       e.tick();    } }

fixed it, or at least I haven't gotten a single ConcurrentModificationException yet, after using that.

Thanks for the help guys!


P.S.:
And now that I know all you clever people are around, go answer my other question! I still haven't solved that one! (This one: http://www.java-gaming.org/topics/making-stuff-work-between-windows-and-osx/26132/view.html )

[Regenuluz]

Actually, on a side node:

1. Stop using LinkedLists anyway. Use ArrayLists.

Why?

Games published by our own members! Check 'em out!

[sproingie]

ArrayLists are faster for most uses.  Even ones where LinkedList has a better complexity, ArrayList tends to outrun it for small lists simply because the array operations are so much faster than chasing pointers.  If you need to do a lot of insertion and removal at the ends, ArrayDeque is a good choice.

Doubtful you'll see much difference though until you start pressuring the gc, at which point you will appreciate the difference.

[pitbuller]

Well, this:

1	public List<Entity> entitiesToTick = Collections.synchronizedList(new LinkedList<Entity>());

plus this:

1   2   3   4   5

synchronized (entitiesToTick) {    for (Entity e : entitiesToTick) {       e.tick();    } }

fixed it, or at least I haven't gotten a single ConcurrentModificationException yet, after using that.

Thats not how you design against concurrency. You just can't test it a while and say its solved. You need to analyze it a bit more than do a couple test run.

[sproingie]

The design looks sound to me.  It'll run through the whole list, and any threads spawned that try to modify entitiesToTick will block until the loop is done telling everything in the list to tick.  As long as tick() methods don't block, it looks reasonable.

[princec]

Indeed that will work but effectively single threading the use of the list rather looks like it defeats the purpose of having another thread manipulating it I think.

Cas

[loom_weaver]

Another question to ask yourself is why exactly are you using threads?

Newbie and concurrency do not go together.  I guess this can be a learning experience but dang...

[sproingie]

Indeed that will work but effectively single threading the use of the list rather looks like it defeats the purpose of having another thread manipulating it I think.

Naw, it will fire off all the tick() events quickly then finish.  As long as tick() is cheap, the loop shouldn't block anything else for too long.  Personally, I wouldn't share the list at all, thus obviating the need to lock it, but locking it just long enough to fire off a bunch of tick events seems reasonable.

I would agree you should have a strong justification for using threads before pulling them out though, or your concurrency constructs should make them invisible to you.

[Regenuluz]

You need to analyze it a bit more than do a couple test run.

^ I did give it a couple of test runs.


Well, what I'm doing in my constructor is:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

public MapEditor() {    this.mainWindow = new MainWindow(this);    this.setFocusable(true);    this.requestFocus();    // Show loading screen   this.screen = new LoadingScreen(this);    // Fire up under the painting!   new Thread(this).start();    // Initialize map data   init();    // Add controllers   this.addKeyListener(new KeyController(this));    MouseController mc = new MouseController(this);    this.addMouseListener(mc);    this.addMouseMotionListener(mc); }

I've tried shuffling it around a bit, but I have no idea how to avoid the exception, except for doing it like I posted a little earlier. So how would I go on about making this single threaded..?

[sproingie]

You need to analyze it a bit more than do a couple test run.

^ I did give it a couple of test runs.

You need to read that more closely.  He said you need to do more than a couple test runs, and his point was that you need to understand what it's doing, and why it works.  For example, synchronizing on the list reference itself will only protect you from CME if everything else synchronizes on the same thing.  Are you sure that's what the list's own methods synchronize on?  Not everything in the standard library uses synchronized(this), some things create an internal lock and synchronize on that.

Your code happens to work, but if you don't know why, it's bound to break with the slightest change.

[Regenuluz]

Arh right. Well, as far as I've understood from the java docs, then the linked list doesn't do any synch'ing, in which case it shouldn't pose a problem as long as I remember to sync it myself.

Or am I entirely off the mark here? (If that's the case, please do explain ^^)

[sproingie]

If you synchronize all access to it yourself, you're perfectly ok.  It's just when you use concurrent collections and mix the internally-synchronized methods with your own synchronization where you can screw the pooch.  I speak from experience, poor pooch.

[Mads]

What if you just use a for loop instead, and check for null objects? Would that not (although while being a cheap solution), stop throwing you those exceptions? 

[Regenuluz]

@sproingie
Arh, well, I am synch'ing it myself But I'll make a note to remember to not mix concurrent collections and internally-synch'ed methods.

@Mads
It's not null pointers that's causing that exception. It's because elements are being added or removed from the list while it's being iterated through. ^_^

[cylab]

@Mads
It's not null pointers that's causing that exception. It's because elements are being added or removed from the list while it's being iterated through. ^_^

He means a for-loop with an index and a getter. The CME is only thrown when using for(x:y) loops or Iterators. So his suggestion is

1   2   3   4   5

for(int i=0; i<entitiesToTick.size(); i++) {     Entity e=entitiesToTick.get(i);     if(e!=null) e.tick(); }

unfortunately that won't work either, because of:

public Object get(int index)

    Returns the element at the specified position in this list.

    Parameters:
        index - index of element to return.
    Returns:
        the element at the specified position in this list.
    Throws:
        IndexOutOfBoundsException - if the index is out of range (index < 0 || index >= size()).

so if an element gets removed while iterating over it, an IOOBE is thrown. Other than that, this loop could lead to missed entities or double calls to tick() on the same entity.