How can this BitSet example print (false,true) or (true, false)?

I am trying to understand the JMM by following the blog post by Aleksey Shipilëv

The above example is breaking my mind.

Explanation: There are 3 threads the first 2 threads (the 1st and 2nd column) run set() without any locking and the 3rd thread (3rd column) waits for the previous threads to terminate and then tries to read the values written by the previous threads.

If 2 threads run bs.set(1) and bs.set(2) respectively without any locking how can they give inconsistent results?

According to the internals the BitSet is implemented using long[] and bitshifts.

Bit shifting is a constant time operation, right? I simply cannot work out how this is even possible.

Suppose bits are stored inside a long variable v.

• When just bit 1 is set, v would equal 2.
• When just bit 2 is set, v would equal 4.
• When both bits are set, v would equal 6 (i.e. 2|4).

If you set them sequentially, you get something like this:

• v starts at 0.
• bs.set(1)
  • Read v (0)
  • Add 2 to indicate that bit 1 is on
  • Update v (2)
• bs.set(2)
  • Read v (2)
  • Add 4 to indicate that bit 2 is on
  • Update v (6)

Now v is 6, so both bits are on.

If you set them simultaneously, you can get something like this:

• v starts at 0
• Thread 1: bs.set(1)
• Thread 2: bs.set(2)
• Thread 1: Read v (0)
• Thread 2: Read v (0)
• Thread 1: Set v to 2 (i.e. 0|2)
• Thread 2: Set v to 4 (i.e. 0|4)

Now v is set to 4, so bit 2 is on and bit 1 is off.