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

Question

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.

Answer 1

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.

Answer 2

As the Author stated: BitSet Javadocs say multi-threaded usages should be synchronized, so this is arguably an artificial example

The JVM makes no guarantees of atomic operations for Bitwise OR: ior, lor.

See: https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-2.html#jvms-2.11.3

The BitSet make not attempt to make atomic changes either.

See: https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/BitSet.java

/**
 * Sets the bit at the specified index to {@code true}.
 *
 * @param  bitIndex a bit index
 * @throws IndexOutOfBoundsException if the specified index is negative
 * @since  1.0
 */
public void set(int bitIndex) {
    if (bitIndex < 0)
        throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    int wordIndex = wordIndex(bitIndex);
    expandTo(wordIndex);

    words[wordIndex] |= (1L << bitIndex); // Restores invariants

    checkInvariants();
}

When the lor is carried can not be determined in a multiprocessor system.

To be more precise:

`lload`  words[wordIndex]
`lor`    (1L << bitIndex)
`lstore` words[wordIndex]

These 3 commands can switch at anytime between the 2 threads.