Concurrency

Java Gaming Wiki
#1

Here is a good tutorial on Java concurrency : Concurrency

The most common way of way of handling concurrent modifications is by using the synchronized key word, but that is not the only way to do it. There is also methods based on message passing like the actor model and there is atomic variable.

The 5 levels of thread safety. It defines objects that are the best/easiest to use in a multi-threaded environment to the worst/hardest.

  1. Immutable : The object can’t be modified once created. This is the most safe level. No matter how many threads access this object you won’t run into any problems.
  2. Thread-safe : The object contains enough internal synchronization (synchronized method) to be used without problems by multiple threads.
  3. Conditionally thread-safe : Same as thread-safe except that under some circumstances, you will need to provide external synchronization (outside of that object)
  4. Thread-Compatible : Can be used in multi-threaded environment but it is up to the programmer to do the synchronization
  5. Thread-hostile : Can’t be used in multi-threaded envrionment (Ex.: Thread.stop() - That method was deprecated because it releases the lock when it is called. Hence it could leave an object into an invalid state)

People usually think that the method Collections.synchronizedList(new ArrayList()) will return a thread-safe collection. But that is not true. It is conditionnaly thread-safe. That is true for almost all Java default ‘‘synchronized’’ collections. Here is a list of collections that are Thread-safe : Concurrent Collections

Vectors are conditionally thread-safe. That means that most of the time you don’t need to provide external synchronization but in some cases you might. One case where you need external synchronization is when iterating over the Vector and modifying it.
Collection.getSynchronizedCollection() - (or something like that) are also conditionnally thread-safe : meaning that you have to provide external synchronization for some operation.
ArrayList is thread compatible : meaning that if you want to use it in a multi-threaded environment you have to provide all the synchronization

The Best Advice On Using Concurrency
(ROQUEN: All of this is so wrong it should be axed)

… is to avoid using concurrency at all if you can help it. Threads are extremely difficult to debug, behaving and interacting in very complex ways that are often counterintuitive or seemingly completely indeterministic. They are also not nearly as effective as you’d like to hope in a typical SMP desktop system: two threads does not equal twice the computation, typically. You’ll be lucky to achieve a fraction of an increase, for a great deal of extra complexity.

this is junk…brain dumpish

Blocking vs. Non-Blocking

Classic concurrent methods are built using locks (wikipedia) and mutual exclusions (wikipedia). In these methods a single thread acquires a lock, performs some task and then releases the lock. Any other running thread which attempts to access the structure at the same time is “blocked” until the first releases the lock.

(wikipedia)

(wikipedia)

Progress Guarantees

A given concurrent data structure will provide some type of progress guarantee which describes how it behaves under contention. Non-blocking data structures can be described as one of the following:

[tr][td]Obstruction Free[/td][td]a thread running exclusively will make a progress[/td][/tr]
[tr][td]Lock Free[/td][td]at least one of the running threads will make a progress[/td][/tr]
[tr][td]Wait Free[/td][td]every thread that gets the CPU will make a progress[/td][/tr]

More complete descriptions can be found on the non-blocking wikipedia link above.

#2

Immutable objects aren’t really useful for concurrency in Java (that I can see). Using explicit locks IMHO (like the synchronized keyword) should be avoided and lock-free data structures used instead of the older stuff.

#3

Immutable object can be used by has many thread as you want without creating any inconsistency. It’s kind of useful. Any constants that you declared (public static int SOME_VALUE = 2) is an immutable object.

I’m not really familiar with lock-free data structures. :frowning:

#4

It could be said that mutable objects can be used in the same way as well, provided you don’t call any mutating methods on them. What would be the important feature of immutable objects in this scenario is mutating methods that return new copies of the object. You may end up creating as many problems as you solve though because you’ve then got references to both the new and the old objects and the old object isn’t really “valid” any more.

Cas :slight_smile:

#5

Java immutables aren’t really immutable and that doesn’t magically deal with the reference…we’re not a functional language.

This is a topic that will need a lot of discussion I think.

  1. single-producer single-consumer = easy
  2. mutiple-producer single-consumer/single-producer multiple-consumer = pretty easy
  3. mutiple-producer multiple-consumer = requires thinking

Most stuff should be 1, some 2 and rarely (if ever) 3.

#6

Also you might conceptually think that creating loads of immutable objects solves your concurrency worries … only to discover you end up spending 30% of your time in GC, as all you’ve really done is pushed the problem under the covers and forcing a generic solution to deal with it.

Cas :slight_smile:

#7

A mutable object you don’t mutate is for all intents and purposes immutable. It would be nice if Java had the concept built in, since it would make a lot more optimizations available, but that’s not where we are. It does still have the const keyword reserved and unused, but I’ll be damned if I want to see Java descending into C++'s insane positional-language notion of how const works, so I’d rather they kept it in reserve til they can be sure it’s used wisely.

You can always run to the GC as a counter-argument to any kind of abstraction; FSM knows that smug C programmers like to beat java programmers over the head with it every day. Everything you do has a cost, and either you’re paying it directly, or the runtime will do it on your behalf. Personally I find the runtime’s gc far more efficient than my clumsy tinkering.

If garbage is really a problem, you can still use localized state where it doesn’t affect referential transparency. Memoizing is one example of that: one typically uses a mutable hashmap to cache the inputs and outputs of a memoized function. Also, since functional code tends to not rely on object identity, you can get away with pooling almost anything (but that does have the same drawbacks pooling always has).

Another cool thing about fully deterministic code is that it can be run in any order and you get the same result, meaning it’s trivial to parallelize any chunk of it.

#8

Yes I was referring to (currently) the backend can’t do anything special with immutables. This might change in the future, but still I think that we can agree that in plain-old-java immutable objects aren’t useful for concurrency. Unless someone can come up with an example.

WRT: lock-free. In the context of java, the primary operation is a compare-and-swap. java.util.Random core generation is an example as are the “new” stuff in the concurrency package. The general rule of thumb (which means it ain’t always true) is that under very heavy contention you a lock and otherwise use lock-free. But really you want to avoid heavy contention anyway.

#9

For real immutable I’d probably go with specifying with an annotation which locks the field. Requires some minor tweaks to reflection API … go go jigsaw.

#10

Is there a place to post references to books and articles for learning some of the standard patterns for dealing with concurrency.

Great article by Bill Venners I recommend as a starting point:
http://www.artima.com/insidejvm/ed2/threadsynch.html

“Java Concurrency in Practice” by Goetz (most practical)
“Concurrent Programming in Java, 2nd Ed.” by Lea (more theoretical)

I have been studying this because working with audio by definition requires some concurrency:
(1) the audio is happening at the same time as the game in its own thread
(2) if game state is going to affect audio, there has to be efficient ways to bridge game state threads and the audio producing threads.

A simpler situation in game programming that comes up is the decision whether to use a Timer to control game loop timing. There are two main Timers, the Swing timer and the Util timer. The Swing timer avoids concurrency by acting exclusively on the EDT, and has terrible performance.

However, the Util timer launches concurrent threads and has been shown to have comparable performance to programmed game loops. For this assertion I can cite “Killer Game Programming in Java” (Davison).

But fears of concurrent threads tend to lead to the avoidance of this very useful construct. I think these fears overblown, and continue to use Timer for my animations.

#11

Btw, this is a pretty good book. Have it here in some bookshelf right beside me too. He discusses some intresting parts of game development. But IMO you can forget the 3D part of the book, because it is so outdated (2005)

#12

Am I being dense? How do you avoid multithreading in an OpenGL application? For example lets say you have a data visualization app that has a swing GUI and charting built with OpenGL. The GUI and the GL code are separate threads sharing a data structure. You can keep it sane in that case by only giving the GL code read access to the model. In all but the simplest cases, advice to avoid threading is just unfeasible.

#13

That depends where the data is coming from. If the data is coming from some external source, eg. streamed from an InputStream in some other thread, then you’re going to occasionally have to protect things. If however your data model is interacted with in the UI then there’s absolutely no reason not to have painting and UI handling in the same thread, as is traditional. In fact OpenGL UIs work basically exactly the same way as Swing UIs and if you want to do heavy lifting in the UI thread you’ve got to farm out computation to threads and then integrate the results later.

Cas :slight_smile:

#14

In libgdx, for LwjglCanvas and friends that are designed for mixed use with Swing, I do the GL work on the Swing thread. The amount of headache this saves is immense.

#15

I started to edit this but I’m not sure where to start. I added some minor stuff after the ‘-----’. The remainder seems to be either not useful or completely incorrect. Thoughts anyone?

#16

Wow, I was debugging something about threads, and found out about concurrency, by getting a ConcurrentModification exception. I read up on it, and I was modifying an arraylist in 2 threads at the same time. So I changed it to a CopyOnWriteArrayList (feel free to call any fault…). I never heard about atomic variables though. Thanks WikiDuke!

#17

I started to edit this but I’m not sure where to start. I added some minor stuff after the ‘-----’. The remainder seems to be either not useful or completely incorrect. Thoughts anyone?

#18

Wow, I was debugging something about threads, and found out about concurrency, by getting a ConcurrentModification exception. I read up on it, and I was modifying an arraylist in 2 threads at the same time. So I changed it to a CopyOnWriteArrayList (feel free to call any fault…). I never heard about atomic variables though. Thanks WikiDuke!

#19

You should probably take a step back and read up a bit on concurrency before proceeding, or you’ll end up with lots of bugs that are extremely hard to debug. :frowning:

#20

I did. Took a look at the java tutorials on concurrency. Very good read.