Hacker News Reader

Comment by boothead | Hacker News Reader

How can anyone program sanely in the presence of this:

currentPos = new Point(currentPos.x+1, currentPos.y+1); does a few things, including writing default values to x and y (0) and then writing their initial values in the constructor. Since your object is not safely published those 4 write operations can be freely reordered by the compiler / JVM.

So from the perspective of the reading thread, it is a legal execution to read x with its new value but y with its default value of 0 for example. By the time you reach the println statement (which by the way is synchronized and therefore does influence the read operations), the variables have their initial values and the program prints the expected values.

I'm not anywhere near smart or careful enough for that... I think I'll stick with Haskell.

View on HN

The One Commandment of multithreaded programming:

1. Thou Shalt Not touch shared data without synchronization.

You must know what data is shared, and you must synchronize all access to shared data (with one exception, when all access is read-only).

People try to find exceptions to this One Commandment. They think, I'm only writing one value, so what's the harm? Well, this is the harm. Follow the One Commandment and you'll be safe(r).

No real argument here, but Haskell does encourage you to use read only data structures unless you truly need writes. That said, there's still a wide variety of clever ways in which you can find your way to multithreading hell.

Read-only data structures are a common idiom in Java as well (the classic example is String), and do indeed help reduce the headaches.

Not sure this is true. There is the concept of final fields, but that doesn't make objects immutable, and thus even when declaring object finals (or arrays) you can pretty easily shoot yourself in the foot by mutating them in-place.

For immutable collections, guava is helpful.

It is -- but you still do have to be aware if the objects in your collection are also immutable... if so, you may end up with an "immutable" list of 5 objects, and down the line it will still have those 5 objects, but the objects themselves may have completely different internal data.

Referring partly to your parent comment... it's instructive to look at the String implementation.

It's immutable, but they have to jump through a few hoops to do it properly... internally, a String has a private char array. An array is not immutable, so the code has to be very careful to never expose that char array externally.

Because of that, calling toCharArray() will copy the internal array and return the copy -- that one's fairly obvious. But less obviously, a String constructed with a char array must also make a copy... otherwise the calling code might then modify the array after creating the String with it.

So sure, immutable objects are possible, and widely encouraged in Java, but they're easy to do wrongly/incompletely.

As Josh Bloch said:

Classes should be immutable unless there's a very good reason to make them mutable

Immutability makes life a LOT easier. A great example is the well designed joda-time vs the disaster that is the the mutable Date and Calendar core language classes.

Yes. Now if only the standard Java collections were immutable...

My exception: If all operations on the shared data are atomic, and always leave it in a valid state, then you can get away without explicit synchronization. Unfortunately, the only way you can really achieve this (without some sort of a synchronization API) is to use assembly code, and take advantage of architecture-specific data access mechanisms.

Absolutely true. I would say that either atomics count as a form of "synchronization", or they're advanced enough that you can disregard the One Commandment once you get to that stage.

Although atomicity helps, it typically doesn't provide any visibility guarantees, so typically some other form of synchronization or memory barrier will be required.

The Atomic* classes in Java give you essentially direct access to these mechanisms.

But you'll need memory barriers. Let's say you have two variables, x and y, satisfying x >= y at all times, and the values of x and y are never allowed to decrease.

    // Thread 1
    atomic_inc(&x);
    atomic_inc(&y);

    // Thread 2
    local_y = atomic_read(&y);
    local_x = atomic_read(&x);

If you go through it logically, it's always in a valid state, right?

No. You need explicit synchronization. If we start at x=1, y=1, then thread 2 can see x=1, y=2, which seems impossible!

Or in short, your exception sucks. (By "sucks" I mean it is not sufficiently detailed enough to prevent errors.)

This is only the case on architectures where atomic operations don't imply memory barriers. On x86, there is a total order on atomic operations, do another CPU will never see the write to "y" before the write to "x". Indeed on x86, there is total order on stores, so if you had two threads like that, where one thread only did reads and the other thread did updates, you can get away with an unlocked increment (x++; y++).

Being atomic is not enough. It's too easy to use two atomics operations and assume they'll be sequentially consistent.

For example, suppose we have:

    A = 0
    B = 0
    Producer:
        while true:
            AtomicIncrement A
            AtomicIncrement B

    Consumer:
        while true:
            postA = AtomicDecrement A
            postB = AtomicDecrement B
            assert postA == postB // wrong

The assertion is wrong, when you're dealing with relaxed atomics. For example, the producer can be optimized into this either by the compiler or by caching layers:

        int savedUpA = 0
        while true:
            savedUpA++
            if (savedUpA == 100)
                AtomicAdd A, 100
            AtomicIncrement B

In which case the consumer will often see that postA != postB.

Thankfully, languages are apparently converging on "every atomic write is a release barrier" and "every atomic read is an acquire barrier", which makes these sorts of optimizations illegal (releasing B's new value requires releasing A's new value).

Heh, my 1st commandment of multithreaded programming is: share as little as possible, isolate data in each thread and hand-off ownership between threads. With this, you will need only very little synchronization (only for queues), and you will not risk deadlock.

I think that's 3 commandments ;-).

.. or 3 ways of saying the same thing, really :)

0. Thou Shalt minimize and reduce shared mutable data as much as possible, in the design stage.

Sometimes just making new copy and passing that around might not cause that much of a performance penalty vs the time spent debugging synchronization problems.

Corollary: don't put in locks blindly just because a datum is shared. You'll just get deadlocks instead of race conditions.

Synchronization is like commas in English. People don't really know the rules, and there is danger in putting in too many as well as too few. You should never put in a lock without understanding the mechanics of the datum you're touching. Some times you won't need synchronization at all.

I would, on the whole, usually rather have a deadlock than a race since they tend to crash rather than silently corrupt state ... and the ones that cause retries rather than crashes tend to show up in the profiler. But that's an "err on the side of" rule of thumb rather than a defence of blindly locking things.

Honestly I don't think Haskell would have helped much here.

That code is terrible from a thread safety perspective. If the author didn't read up on how to write good thread-safe code, it's unlikely he'd read up on Haskell, so he'd probably write bad code there, too.

Haskell has type-safe software transactional memory for this stuff. And it's exponentially harder to get a program that compiles and has error like that.

The author didn't take the time to learn the very basics of thread safety. It's highly unlikely he would take the time to learn Haskell and software transactional memory.

Can you explain what makes it so terrible? At first glance it seems as if it is thread safe, and avoiding synchronization locks can provide a nice speed up.

The notion that currentPos could be set to the new Point before the Point(int x, int y) constructor completed was completely surprising to me.

Is that something that was obvious to you, or do you have other reasons to dislike it?

Yeah, this is very surprising to me. I simply didn't know that java worked that way and I've been programming in java for many years. I assumed that the memory that "currentPos" would eventually be bound to was fully initialized before the assignment operator remapped "currentPos" to the new value. I also assumed that binding a variable name to a new value is atomic across all threads.

currentPos is modified in one thread and read in a different thread, outside of a synchronized block, and without being protected by a mutex.

It's a pretty straightforward recipe for disaster.

I don't program much in java, but I would have thought that the problem was in the assignment of the new Point to currentPost, not the construction of the new Point.

I would have thought that the order of operations would be:

1) Read value from currentPos.x and add 1. Do same for y.

2) Pass values to constructor

3) Construct the new object

   3a) init values with 0

   3b) assign new values to x and y

4) Assign the newly constructed object's pointer to currentPos.

I thought that the problem lay in 4 where you might read a partial update of the pointer, possibly giving weird results. Is he saying that it might get assigned first and then constructed afterwards?

You're assuming that the code is executing in the way you read it, which is false. With the advent of branch prediction and Instruction reordering in CPUS (to gain performance), a CPU have the liberty of reordering operations for efficiency (http://en.wikipedia.org/wiki/Out-of-order_execution) EXCEPT when there are memory barriers (or explicit synchronization instructions). With a multi-core processor things get even more complex, as you have cache locality (a thread reading the point value might be hitting the CPU cache and not main memory). If the thread happens to be executing on a different core than the assigning thread, disaster ensues.

> I thought that the problem lay in 4 where you might read a partial update of the pointer, possibly giving weird results. Is he saying that it might get assigned first and then constructed afterwards?

Yes. In some versions of java the code: x = new X() results in assigning to x a reference to a new uninitialized object X and then a call to the constructor.

Reference assignment in java is always atomic, it is guaranteed by the memory model.

No. x = new X() should not make x assigned such that it is visible inside the constructor of X. The behaviour in the post can only been seen with concurrency.

The issue here is the lack of a write barrier at the point of publishing the reference to the newly constructed object, and the lack of a read barrier at the point of reading the reference to the newly constructed object. You want to stop both writes moving forward in time (the writes in the constructor happening after the write that publishes the object) and reads moving backwards in time (the reads on the other thread reading the old values of the constructed object, rather than the initialized values - may be caused by e.g. satisfying the read from per-CPU cache).

Java's volatile acts both ways; writes are write barriers and reads are read barriers.

In less technical language, "creation of the object is not atomic". You could switch threads in the middle of the creation.

Also, "reading of the data is not atomic" - you can switch threads in the middle of reading the data.

In order to program THREADED CODE sanely with that in mind, you need to minimize the amount of shared data, and be sure to lock / synchronize around the writing AND READING of any shared data.

If you're not writing threaded code then there is no shared data, and you don't care about these rules. Writing threaded code isn't like dusting crops, but it's not impossible.

EDIT: you also said "the println statement [...] is synchronized" but it doesn't look like that's true - there's nothing in the synchronized(this) {} block, and even if there was, all it would do is keep "this" from entering that block twice; it has no effect on other threads in this code.

You misunderstood the part about println. The implementation of println() uses synchronized internally. You can't see it without downloading the Java source code, but it's there.

Ah, thanks. I don't do much Java.

So "println() uses synchronized internally" means two println statements will never overlap each other, but still says nothing about their interaction with other objects, right? Does nothing to prevent switching threads in the middle of the println and getting two different values?

Correct. It synchronizes on the instance of the PrintStream, which has no effect here.

The bottom line is that the Point object should have been immutable, which would have made it safe for publication. That requires its fields to be final (among other things), which was not the case.

In general, you shouldn't assume that tomorrow's implementation behaves like today's, or today's implementation X behaves like today's implementation Y, unless there is documentation that says so. Looking at http://stackoverflow.com/questions/9459657/synchronization-a..., it seems that Java does not guarantee that println will synchronize.

The exception is if you have tight control over your environment, have tests in place to verify that environment upgrades do not break your assumptions, and you desperately need to bend the rules, but even then, you should look really hard for better alternatives.

But the argument to println is evaluated before println is called! Whatever synchronization it's doing internally therefore can't affect what it prints.

Seems to me, either there's something synchronized in Integer.toString (which seems undesirable and therefore unlikely) or, statistically, in the rare cases that the writes don't take effect in time for the 'if' predicate, they do take effect a few nanoseconds later, in time for the conversions involved in the string construction. (Actually p.x is the only one at risk here, statistically speaking; the conversion of its value to a string will take plenty long enough for the write of p.y to take effect. Combine that with the fact that the write of p.x probably still precedes that of p.y, so that the one that's wrong in the 'if' statement is probably p.y, and you see that the odds of the wrong values being printed are vanishingly small.)

The comment about println being synchronized is indeed incorrect. See my reply to Eiwatah4.

You don't have to know the majority of that, though.

These are tricks the compiler/VM can use, because (unless you say otherwise in code) it's assumed that there's no sharing data between threads.

Most programmers (regardless of the language) just learn the rules about programming with threads -- they don't care why exactly following the rules is important.

Sure those programmers learn the rules... then they promptly forget them because they seem too complicated and "it works on my machine with only one client"..

I agree with you, one must know why rules are important.. but in large systems, it's better if the system/language enforces this separation of data (praise Erlang).

insert "dumb code in any language" rant here

Get real

Reply on news.ycombinator.com