2005-06-20

Java Threads

Tim Bray wrote a long post called On Threads, which touches on whether mainstream programmers are up to writing correct concurrent programs. Here's an excerpt that caught my attention:

Problem: Java Mutexes The standard APIs that came with the first few versions of Java were thread safe; some might say fanatically, obsessively, thread-safe. Stories abound of I/O calls that plunge down through six layers of stack, with each layer posting a mutex on the way; and venerable standbys like StringBuffer and Vector are mutexed-to-the-max. That means if your app is running on next year’s hot chip with a couple of dozen threads, if you’ve got a routine that’s doing a lot of string-appending or vector-loading, only one thread is gonna be in there at a time.

One thing the Java people need to do is put big loud blinking messages in all that Javadoc saying Using this class may impair performance in multi-threaded environments! You can drop in ArrayList for Vector and StringBuilder for StringBuffer. Hey, I just noted that the StringBuffer Javadoc does have such a warning; good stuff, but we need to be doing more evangelism on this front.

On the other hand, those mutexes were there for a reason. Nobody’s saying “Ignore thread-safety” but rather “Thread-safety is expensive, don’t do it unless you need to.”

To my mind, this is one of the biggest concurrency fallacies. Those mutexes may have been there (in classes such as Vector) for a reason, but not the reason many people naively expect.

I'm not saying "ignore thread safety", but the trouble is that you can't usually push all your concurrency concerns all the way down into the library where they're cured by the library pixies. (The best of those library pixies can do some pretty cool stuff for you, an example of which you'll see later.)

Compare these two snippets:

// Traditional code, using Vector.
// Unsafe.
public void scan(Vector<String> strings) {
for (int i = 0; i < strings.size(); ++i) {
String s = strings.get(i);
doSomething(s);
}
}

// Modern code, using ArrayList.
// Unsafe.
public void scan(ArrayList<String> strings) {
for (String s : strings) {
doSomething(s);
}
}

If you buy the "those mutexes are there for a reason" argument, you might think that the former is more safe in a concurrent situation. After all, ArrayList isn't synchronized, but Vector is.

The trouble is, Vector's synchronization isn't at a useful level. You know that any individual call sees a consistent internal state (which isn't necessarily true with ArrayList), but you have no such guarantee across calls. So you can have checked that your index is less than the current size, for example, but when you come to get that item, the size has changed. Both size and get saw consistent states, but they saw different consistent states. And what you really meant was probably:

// Safe.
public void scan(Vector<String> strings) {
synchronized (strings) {
for (int i = 0; i < strings.size(); ++i) {
String s = strings.get(i);
doSomething(s);
}
}
}

In fact, of the original two alternatives, the ArrayList version was better. It wasn't any more correct, but it was still to be preferred to the other incorrect code. Why? Because the new-style for loop was implicitly invoking iterator on the ArrayList, and that gives you an instance of AbstractList.Itr, and that throws ConcurrentModificationException if it notices that you keep using it after the collection has been mutated.

It does this by keeping a sequence number inside the collection. This number is incremented on each mutation that changes the collection's structure [see the documentation for more details]. Each iterator remembers the sequence number that was current when the iterator was created. If you're in an iterator method and the container's number doesn't match the iterator's... boom!

Some people belittle Java and its contributions to the state of the art, but I think that's a mistake born of snobbery. The individual contributions may be small, but that doesn't stop them being significant. The fail-fast iterators, even if I don't much like their name, are one such small but significant contribution. (Remember: they don't make your code correct, but they can help prove to you that it isn't.)

You can rewrite the original Vector code to use the new-style for loop instead of the old-style counted for loop, and it'll then have the same property, because Vector is also a subclass of AbstractList. It still won't be correct, though.

This is the big point that people miss. The synchronization in Vector is at too low a level to ensure that your application is thread-safe. It's ensuring that the collection itself is. This kind of correctness is almost never what's important to you as an application developer, and is usually made irrelevant by the protection you have to put in at a higher level.

The same is true if you use Collections.synchronizedCollection, and the library pixies explain this in the method's documentation.

The C++ STL collection classes, for example, have no protection. And anyone who suggested it would be laughed at. "Those mutexes are there for a [good] reason" just isn't true. If you had Smalltalk-like internal iteration, where (in Java terms) you give the collection an object to invoke a method on for each contained item, then the collection could usually give you the protection you need, but that's not what we have in Java. Because of that, you almost always need a mutex around any iteration.

The SGI STL implementors say as much in SGI STL Thread-Safety. They explicitly use std::vector as an example of where the naive "synchronize all the methods" approach doesn't work. They do use synchronization where they need to, though, despite the pain it must have caused because Standard C++ has no notions of threads or locks, so it's not like they were simply ignoring the issue, or ignorant of it.

Why do the library pixies care? They care because:

  • it makes them less likely to get blamed for users' bugs (true of both fail-fast iterators and all-synchronized classes, though a failed iteration gives a clear "your code blows goats; I have proof" that all-synchronized classes don't).

  • even inadequate protection will catch (for fail-fast iterators) or avoid (for all-synchronized classes) some problems; see the above point about not being blamed.

  • all-synchronized classes simplify a class' behavior in that (since being synchronized is part of the interface) some of the behavior is made less dependent on the implementation; a synchronized interface gives you some minimal guarantee.


The (strictly correct, but practically not very useful) "thread safety" of classes like Vector can be a danger in itself, because programmers unused to concurrency think they've done enough by using these classes, rather than asking for help from someone more experienced. And with a class like Hashtable, assuming they don't iterate over the keys or values, they'll get away with it. An associative container is substantially less likely to be iterated over, so you can still mostly ignore concurrency. But only "mostly".

I really don't like seeing classes with lots of synchronized methods, because it often means the problem hasn't really been thought about. "If I just sprinkle my magic thread-safety dust around, everything will be lovely." A class with just a couple, though, often means that the problem has been thought about, and carefully contained in just a couple of points, and those points have then been protected.

For classes as low-level as ArrayList and Vector, I think having no synchronized methods is always the right choice. There's almost a parallel with exceptions where, for lack of the ability to do the right thing at some low level, you pass the problem on up until you're at a level where it can be handled (preferably with some way to make sure it's obvious when the situation hasn't been properly handled).

[Though they shouldn't be blamed for any remaining problems, thanks to Olivier Lefevre for his repeated (correct) insistence that what I'd written was unclear, to Ed Porter for his succinct distillation of what I wanted to say (rather than what I did say), and Martin Dorey for his additions relating to the STL and the library pixies' motivation.]