Do you want a sequential consistent Java?

A lot of developers still think that Java is sequential consistent, but what does it mean? When code is executed by multiple threads, only results of all possible interleavings following the order of instructions in the sourcecode, are allowed and the most recently written variable will be visible when a read is done.

Example:

class Foo{
	int a,b;

	void init(){
		a=1;
		b=1;
	}

	void print(){
		println(format("a=%s b=%s"),a,b);
	}
}

If init and print are called by different threads, according to sequential consistency you can expect the following output:

a=0 b=0
a=1 b=0
a=1 b=1

The problem is that ‘a=0 and b=1’ also is possible because Java is not sequential consistent. This strange behaviour can be attributed to certain compiler optimizations:

  1. reordering: a=1 and b=1 could be reordened (maybe the compiler thinks it improves the chance of a cache hit, or the cpu stalls the execution of a=1 and starts with the execution of b=1 or just executes them in parallel but b=1 instruction finishes before a=1)
  2. visibility: it could happen that the write of a=1 is later visible in the thread that calls print than b=1 (a visibility problem could also be seen as a reordering problem).

When I explain this to developers they start to look funny at me at best or they shout that I’m nuts and Java is broken. Well.. although sequential consistency is very intuitive, it also is very expensive because it prevents a lot of optimizations. So it would be nice experiment to see if we can make the JVM sequential consistent and compare the performance to a standard JVM.

I think this can be largely done by changing all normal reads/writes into volatile read/writes because volatile reads and writes prevent reordering and visibility problems. Changing them to volatile read/writes also doesn’t influence the behavior of the application (apart from the reduced performance). Modifying the normal read/writes would not be that difficult, it can be done writing a custom JVMTI agent that modifies the bytecode. If I have time, I’m going to give it a try this weekend. I’ll keep you posted.

Advertisements

11 Responses to Do you want a sequential consistent Java?

  1. Hey Peter,

    Interesting experiment. Curious to see the results!

  2. I don’t think you’re nuts, but I don’t think sequential consistency is very useful either. But then I generally don’t like threading, and if I do use threading I will minimize access to shared state and guard any and all access to shared state with synchronization primitives like mutexes, so I’ve _never_ come across any cases where sequential consistency would make any difference.

    I think that’s the case for most programmers. After all, even with sequential consistency it’s far too trivial to mess up unsynchronized access to shared state for it to be something for you to rely on without _very_ careful consideration.

    In fact, I almost think the more unreliable the results are between threads, the better, as it makes problems far more likely to surface early during testing, and might teach people to be more careful about managing shared state…

  3. Jude says:

    Dude , isn’t the synchronized keyword suppose to take care of inconsistencies across threads . I thought the Java Memory Model was designed that way .

  4. Andy Key says:

    Actually, your example is a little bit misleading, and you need to look at the bytecode to see why — it’s a shame that too many java programmers have never looked at the internal workings of the JVM. This in fact has nothing to do with sequential consistency, but is a plain-Jane old-fashioned race condition.

    Here’s an excerpt from the call to Foo.print():
    13: iconst_0
    14: aload_0
    15: getfield #18; //Field a:I
    18: invokestatic #31; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
    21: aastore
    22: dup
    23: iconst_1
    24: aload_0
    25: getfield #20; //Field b:I
    28: invokestatic #31; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
    31: aastore
    32: invokevirtual #37; //Method java/io/PrintStream.format:(Ljava/lang/String;[Ljava/lang/Object;)Ljava/io/PrintStream;

    Notice that it’s pushing the VALUE of i onto the stack and then autoboxing it to an Integer — the format method requires objects as its arguments, not primitives. It does the same with b as well. So the value of i used is its immediate value at the TIME OF EXECUTION. If a separate thread has called init(), and manages to set b=1 before the first thread resumes, then and Integer with the value 1 will be left on the stack.

    It’s just a simple race condition. Nothing fancy or even complicated.

  5. pveentjer says:

    Thanks for your reply, but can you elaborate on it?

    Each thread has its own stack, so there are no race problems between the stacks. So I don’t understand ‘value 1 will be left on the stack’.

    And can you elaborate on the effects of the race problem?

    >> So the value of i used is its immediate value at the TIME OF EXECUTION. If a
    >> separate thread has called init(), and manages to set b=1 before the first thread
    >> resumes, then and Integer with the value 1 will be left on the stack.

    This is the part where I’m loosing you.

  6. Andy Key says:

    Each thread does indeed have it’s own stack. The problem is in how and when objects are placed onto the stack. Let me break down what’s happening with the individual instructions:
    13:iconst_0 // pushes a constant integer 0 on the stack
    14:aload_0 // pushes the “this” object onto the stack
    15:getfield #18 // consumes the (0,this) on the stack, reads the value of i and leaves it on the stack
    18:invokestatic #31 // consumes the int on the stack, autoboxes as an Integer, and leaves it on the stack
    21:aastore // stores the Integer into the variable args array

    The same code is duplicated for the b property as well. Simply put, you’re not storing a reference to i in the variable args, but its value at the time the bytecode is executed. Once the value of i has been pushed onto stack, it doesn’t matter if the property is changed in another thread, since it’s just a value and not a reference to the property.

  7. pveentjer says:

    So the consequence of this race problem could be that a=0 and b=0 is shown, but the a already has changed to 1. Am I correct?

    I don’t think this is a serious issue because this output is still valid.

    But can you explain the a=0 and b=1 using your race problem? I don’t think that is possible. Reordering/visibility is the only possible cause as far as I know.. but please enlighten me!

  8. Andy Key says:

    The only problem here is in fact the race condition. You’re missing the point about how threads in Java work. Although a thread may be “executing”, if you only have one CPU, then only one thread will be actually executing on the CPU at any one given time. The JVM doesn’t execute java, but bytecode, so a call to format(“…”) is not atomic — in fact it is compiled into a series of bytecode, and the JVM may choose to pause the executing thread at any point. The timing looks like this:

    1. Thread one calls print. It reads the value of a (0 at this point) and pushes it on to the stack. The JVM at this point “pauses” execution of this thread and switches to another thread.
    2. Thread two calls init(). The JVM allows init() to complete, and now both a and b have been set to 1.
    3. The JVM resumes thread one. It reads the value of b (which is now 1) and pushes it on to the stack.
    4. Thread one invokes the format method with the arguments on the stack, where the first argument is 0 and the second is 1.

    The key here is that the JVM has stored the value of the property at the time the individual opcodes were executed, not references to the properties.

  9. pveentjer says:

    Cool to see that there is a race problem that can cause the a=0 b=1 problem!

    But I don’t agree with your conclusion that it is the only cause. Visibility and reordering also could cause an out of order execution or a value not being visible. This is clearly specified in the JMM.

  10. Abhirama says:

    Is code within a try block guaranteed not to be reordered? I know that code within synchronized block is not reordered but I am a bit hazy on the try block part.

  11. The canonical example of a slightly surprising result of instruction reordering, I think is the following:

    Initial state: x = y = 0

    Thread 1:
    r1 := x
    y := r1

    Thread 2:
    r2 := y
    x := 1

    In this case, all possible interleavings would result in a state where r2 = 0. (Whenever the first instruction of thread 2 is executed, it will assign 0 to r2 and never overwrite that value.)

    However, due to the possibility of instruction reordering mentioned in the blog entry, the two instructions of thread 2 could actually be executed in the “wrong” order, resulting in a state where r2 = 1.

    // Andreas

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: