First synchronization issue

[Mark Hedge]

I've never come up against this before, but for all things there is a first time.

I'm trying to code up a Java version of the olde game of Asteroids. I have an ArrayList called gameobjects which holds all the objects in the game, asteroids, bullets, the players ship, etc. Objects have a public boolean called 'nuke' which if set to true is the signal to remove that object from the list.

Right in the heart of it all, in the game loop, is this :-

Iterator<GameObject> it = gameobjects.iterator();

while(it.hasNext()) {
GameObject currentObject = it.next();
if (currentObject.nuke == false) {
currentObject.updatePosition();
currentObject.paint(bufferGraphics);
} else {
it.remove();
}
}

This works up to a point, but sling more than a couple of objects in the arraylist and I get this :-

Exception in thread "Thread-2" java.util.ConcurrentModificationException
at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at java.util.AbstractList$Itr.next(AbstractList.java:343)
at asteroids.Screen.render(Screen.java:82)
at asteroids.Screen.run(Screen.java:129)
at java.lang.Thread.run(Thread.java:619)

asteroids.Screen.render line 82 is this one in the above :-

GameObject currentObject = it.next()



Now, I'm sure this is due to a synchronization problem with accessing that collection, and I figure its probably not too hard to fix for someone who knows how it works. I've tried liberal scattering of synchronized keywords but it ain't working, and clearly I don't understand it enough to sort it out on my own despite some reading.

...one thing that does puzzle me a bit is theres only one thread of execution in this program using that Screen class. So what is trying to access it concurrently?

Any help on this one would be greatly appreciately!
[ May 06, 2007: Message edited by: Bear Bibeault ]

[Nicholas Jordan]

Originally posted by Someone Else:
...This works up to a point, but sling more than a couple of objects in the arraylist and I get this .....

So what is slinging the other whateveritises ?

Other threads ? If so, they could reasonably drive concurrent modification exceptions.

You would synchronize(this) if the method calls are non-static.

Because we have:

Exception in thread "Thread-2" java.util.ConcurrentModificationException

we see obviously that there is a second thread.

// N:\src\java\util\ArrayList.java
 
 * Note that this implementation is not synchronized. If
 * multiple threads access an ArrayList instance concurrently, and at
 * least one of the threads modifies the list structurally, it must be
 * synchronized externally.  (A structural modification is any operation that
 * adds or deletes one or more elements, or explicitly resizes the backing
 * array; merely setting the value of an element is not a structural
 * modification.)  This is typically accomplished by synchronizing on some
 * object that naturally encapsulates the list.  If no such object exists, the
 * list should be "wrapped" using the Collections.synchronizedList
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:

thus:

synchronized(currentObject){
 
// .... your code block supplied goes here, after comment by others.
 
}

I find it is better to use the bare keyword synchronized directly, rather than relying on implementations you did not write yourself. The question arises of what exactly to synchronize on, the answer to which is best determined by the do as little as possible approach.
[ May 06, 2007: Message edited by: Nicholas Jordan ]

[Bear Bibeault]

"Someone Else",

There aren't many rules that you need to worry about here on the Ranch, but one that we take very seriously regards the use of proper names. Please take a look at the JavaRanch Naming Policy and adjust your display name to match it.

In particular, your display name must be a first and a last name separated by a space character, and must not be obviously fictitious.

Thanks!
bear
JavaRanch Sheriff

[Mark Hedge]

Alright, I got it working!

its a little different from the post above, though.

I had to do this first (gameobjects is of type List) :-

gameobjects = Collections.synchronizedList(new ArrayList());


and then later on, the synchronized had to go on the collection not the object being drawn from the collection, so,

synchronized(gameobjects) {
Iterator<GameObject> it = gameobjects.iterator();

while(it.hasNext()) {
GameObject currentObject;
currentObject = it.next();
if (currentObject.nuke == false) {
currentObject.updatePosition();
currentObject.paint(bufferGraphics);
} else {
it.remove();
}

}
}

[Nicholas Jordan]

Originally posted by Mark Hedge:
Alright, I got it working! - its a little different from the post above, though.

You mean you ran a few tests, in the form of test runs,..... and it appears to work. I am not being critical, it's just in the nature of Thread'ing not to jump to the conclusion you did. You should be encouraged, not wrap it up and ship it.

Trust me, I know.
:roll:

I had to do this first (gameobjects is of type List)

Looks like type of gameobjects is ArrayList.

gameobjects = Collections.synchronizedList(new ArrayList());

If you use Collections.synchronizedList(); you shouldn't need the synchronized(gameobjects)

the synchronized had to go on the collection not the object being drawn from the collection

Correct.

See the way Dr. Ernest Friedman-Hill does it in http://www.coderanch.com/t/233779/threads/java/Any-Solution-Deadlock

public static void go2(){  
synchronized (ThreadResource1.class) {    
synchronized (ThreadResource2.class) {        
System.out.println("Entered in resource 2");        
System.out.println(Thread.currentThread().getName());

Also be aware of: deadlock detection utility which has been added to the Java HotSpot VM. The utility is invoked by a Ctrl+\ on the command line while an application is running. The utility detects Java-platform-level deadlocks, including locking done from the Java Native Interface (JNI), the Java Virtual Machine Profiler Interface (JVMPI), and Java Virtual Machine Debug Interface (JVMDI).

Deadlock, which I call cross-lock, can go undetected for quite awhile ~ then occur sporadically. It's just normal part of Threading issues .... note Dr. Friedman-Hill's use of the keyword synchronized directly. Normal approach should be to synchronize(this){/*your code goes here*/} because that seems to me to eliminate a lot of complexity.


Also,see what JY has to say in:java.util.Collections

I would note that it's pretty rare in my experience that the alleged "thread safety" you get from Collections.synchronizedXXX(), or from Vector and Hashmap, is good enough to actually make your code thread-safe. Typically there are places where you need to prevent other threads from cutting in in between two different synchoronized method invocations - this means you need additional synchronization outside the methods themselves. And if you're going to do that, why bother using synchronizedXXX() at all? It just confuses the issue by putting some synchronization inside the XXX class, while other synchronization is in the class that uses the XXX. Just put it all in the class that uses it. Many, many bugs have been committed by people relying on the false promise of "thread safety" from synchronizedXXX() etc.

[ May 06, 2007: Message edited by: Nicholas Jordan ]
[ May 13, 2007: Message edited by: Nicholas Jordan ]

[Jim Yingst]

[Nicholas]: Looks like type of gameobjects is ArrayList.

No, it's List. Look at the return type of the synchronizedList() method. There is an ArrayList involved, but that's not the class that gameobjects is directly referencing. Even if it were a plain ArrayList, it's entirely possible (and generally good practice) to declare the variable with a more general type, like List or Collection.

[Nicholas]: If you use Collections.synchronizedList(); you shouldn't need the synchronized(gameobjects)

Considering my old comment that you quoted later in this post, I think the opposite is true. He does need the synchronized(gameobjects), because that's the only way to prevent another thread from cutting in while the iteration is going on. However since he's using synchronized(gameobjects), the synchronizedList() method appears redundant. Except I'm pretty sure that there's still some other code that accesses gameobjects (e.g. to add() something, as you noted earlier). The synchronizedList() call could be removed - but whatever other code is accessing gameobjects would need to use a synchronized block instead. Using synchronizedList() may be an acceptable way to achieve the same effect, assuming the other code is not trying to do anything overly complex (like, say, iterating).

My main complaint about methods like synchronizedList() is that many people think it automatically means their code is "thread-safe", and they neglect to check more carefully. Mark has at least discovered one extra place where he needed more synchronization, so that's good - he seems to have avoided the trap that many people fall into. It's hard to say if he has completely avoided such traps, because we haven't seen the other code that accesses gameobjects. It would probably be a good idea for him to study that code carefully and see if there's any additional synchronization that needs to be added.

[Nicholas]: See the way Dr. Ernest Friedman-Hill does it

Mmm, EFH's example is addressing a somewhat different problem, so it may be misleading here. EFH was showing how to acquire two different sync locks and hold them at the same time - and the locks were both class-level. It's not at all clear that Mark needs two locks; he could well be fine with just the one lock on the gameobjects list. And he's also not using class-level locks here. Referring him to EFH's example may just confuse the issue, since right now it looks like his needs are different than the problem EFH was addressing.
[ May 06, 2007: Message edited by: Jim Yingst ]

[Mark Hedge]

gameobjects is declared as type List, it is actually implemented as an ArrayList though, yes.

The code for the synchronization I got from the API :-

public static <T> List<T> synchronizedList(List<T> list)

Returns a synchronized (thread-safe) list backed by the specified list. In order to guarantee serial access, it is critical that all access to the backing list is accomplished through the returned list.

It is imperative that the user manually synchronize on the returned list when iterating over it:

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


Failure to follow this advice may result in non-deterministic behavior.

The returned list will be serializable if the specified list is serializable.

Parameters:
list - the list to be "wrapped" in a synchronized list.
Returns:
a synchronized view of the specified list.

The only other place where gameobjects is being used at the moment after initialisation is here, in part of a case statement :-

case ' ':
Bullet newBullet = playerShip.fire();
gameobjects.add(newBullet);
break;

Am I right in assuming that as that is not iterating through the collection I dont need to use a synchronized codeblock there for gameobjects? Certainly it seems to work, anyway... not that that necessarily proves anything.

[Jim Yingst]

[Mark]: Am I right in assuming that as that is not iterating through the collection I dont need to use a synchronized codeblock there for gameobjects? Certainly it seems to work, anyway... not that that necessarily proves anything.

Yes. Or more precisely, the reason you can rely on the synchronizedList() to protect you in this case is because you only need a single method call (at a time) to gameobjects. Additional protection is needed when there are two or more method calls and you need to make sure that there is no interference from another thread in between those calls. That happens when iterating (you're using hasNext() and next(), and looping) but it can also happen with other code. For example:

if (!gameobjects.isEmpty()) {
    Object obj = gameobjects.remove(0);
    doSomething(obj);
}

or

for (int i = 0; i < gameobjects.size(); i++) {
    doSomething(gameobjects.get(i));
}

In each of these, bad things could happen if gameobjects changed in between one call and another (e.g. if there was just one element in the List, but then it got removed). These would also require external synchronization, just like iteration did. My experience is that stuff like this is often overlooked, and that's why I discourage people from relying on synchronizedList() to take care of their problems. However it is possible to use synchronizedList() in a safe fashion, and it looks like that's what you've done here.

[Nicholas Jordan]

[Jim Yingst]: No, it's List. Look at the return type of the synchronizedList() method.

Noted:

ArrayList.java(55): *List list = Collections.synchronizedList(new ArrayList(...));

But then: (N:\src\java\util\ArrayList.java)

/**
* Resizable-array implementation of the <tt>List</tt> interface. Implements
* all optional list operations, and permits all elements, including
* <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
* this class provides methods to manipulate the size of the array that is
* used internally to store the list. (This class is roughly equivalent to
* <tt>Vector</tt>, except that it is unsynchronized.)<p>
*/
So why not use Vector directly ? Sounds to me like it would solve a lot of issues someone coding a game would want solved for K.I.S.S

[Jim Yingst]: (and generally good practice) to declare the variable with a more general type, like List or Collection.

List is an ordered collection, which degrades game performance (slightly) because of it's need to maintain order to fulfill this contract of Ordering.

/*
* Collection is typically used to pass collections around and
* manipulate them where maximum generality is desired.
*/

Poster states GameObject holds all the objects in the game, therefore a class could be written called GameObject which implements interface Collection, having member variables of type Vector - for fast removal and addition - upon which the scope of the keyword synchronized could be restricted to the scope of asteroids, bullets, players prefs, player's ship, ships fuel load and time remaining ... and the unforseen that could Sidewinder the program design later.

[Jim Yingst]: It's hard to say if he has completely avoided such traps, because we haven't seen the other code that accesses gameobjects

Factual avoidance of all threading issues (in the form of cross-locks and data-tampering) requires detailed inspection of sources for JVM, knowledge of the compiler upon which a given JVM was built and adroit tools to spot those dead-locked code paths. Generally, for game enthusiasts, time-cost robustness precedes reliability issues. For the New Team Lead, this can be difficult unlesss the transition of Gamers to OO Team style coding is capable of insuring whatever other code is accessing data (anywhere in the process) would use a synchronized block on the Collection, Vector, or individual data item. That would become hell on a decent sized project that was not coded for fun on the weekends by one person, and somewhere in all this you state other func()'s accessing a data item must also sync() on the same data item,.... ooooh, baby ! here we go ! the OO camp would win that one every time on a decent sized project.

How would you define acceptable risk / decent reliability such as a situation where a fine package running in a class 5 data center had a table erased due a 'business error' which there was no means to recover by technological means.

This is one thing in consumer-grade operating systems, and especially in game coding is not considered a design constraint, but in that you express:

[Jim Yingst]: complaint about methods like synchronizedList() is that many people think it automatically means their code is "thread-safe", and they neglect to check more carefully.

I have some comments, but they would be considered Meaningless Drivel by observers. I note from your profile that you have reason to give these greater inspection and invite discussion of this by you and I by pm.

[Jim Yingst]: Mmm, EFH's example is addressing a somewhat different problem,....(and remainder)

I had intended for Mark Hedge to observe the use of synchronized keyword directly, and realized it may be somewhat confusing, but consdered the risk productive in that the following sentences steer ( ! )  the reader to the use of synchronized(this), but your comments lead me to examine the idea that the entire body of code for any large project would have to be examined rigorously on any non-trivial project, and it is glaring to me that much of OO's basis derives from difficulties the New Team Lead has on large projects - I am sure you have been on many of them.

Use of synchronized(this) will have known issues and reasons to favor the style in recognizable ways.

Nick
[ May 13, 2007: Message edited by: Nicholas Jordan ]

[Nicholas Jordan]

Originally posted by Mark Hedge:
Am I right in assuming that as that is not iterating through the collection I dont need to use a synchronized codeblock there for gameobjects?

No - see discussion. Any, I mean any, access - no matter how derived or accomplished invokes the entire discussion of threading issues .... there is no close is close enough. There are optomization in the screen drawing algorithim that have more than one thread going, it is either that or you have two or more threads running. You may have done this inadvertently by copy-pasting sample code from somewhere. gameobjects.add(newBullet);is a structrual modification of the ArrayList, List, or Collection ~ not allowed ~ but you could modifiy a varable that was already in the list (without synchronization barriers and monitors) but that would involve a design decision that a ice look and feel on a campfire would be acceptable in some limited time slices.

Jim states:

Using synchronizedList() may be an acceptable way to achieve the same effect, assuming the other code is not trying to do anything overly complex (like, say, iterating).

Jim's pretty sharp about these things, I have contramanded and there's gotta be a reason - can you state program design goals ? If if is just write a game to learn how to write a game, the program may run reliably. It all resolves on program complexity, robustness and relaiblity needs.

You got Exception in thread "Thread-2" java.util.ConcurrentModificationException at GameObject currentObject = it.next(); so the exception was thrown while iterating the collection.

Doesn't sound to me like your screen did this.

Screen class should involve matters having to do with graphics, and is a common simplification for beginners to put the spaceships in the screen class. I suggest a re-work of fundamental program design, placing drawing in the Screen class, GameObjects in the game object class.

The only other place where gameobjects is being used at the moment after initialisation is here, in part of a case statement:

case ' ':{
                Bullet newBullet = playerShip.fire();
                gameobjects.add(newBullet);
                break;
}

That's the game in full-tilt-boogie and your gameobjects.add(newBullet); is exactly what we are talking about. If there is only, and only one, thread driving the entire game, then it is impossible to code a ConcurrentModificationException scenario - no matter how many fuction calls are scattered around. If there are multiple threads driving the game, then any access to either a collection or an isolated data item becomes a candidate for inspection of threading issues. Note also that the assignment operator (single equals sign) makes a code statment non-atomic. With knowledge of how a compiler is written and the details of a paticular platform, and invocation of what is called critical sections can effectively emulate threading safety, but it (this technique) does not eliminate dead-locks ~ it just makes avalable to the coder tools for avoiding concurrent modification.

I have tested the waters, and no one here seems to mind large posts when and where the post involves a good size code chunk that members can poke around in,.... in fact they seem to enjoy it - look at the post times.


[ps: getting all this straightend out resembles fifteen ways to stack a cat]
[ May 13, 2007: Message edited by: Nicholas Jordan ]