Why does this blocking queue code not work when I comment out a System.out.println?

Question

The code below doesn't ever print Done. However, if I uncomment System.out.println(list.size()); it finishes. Why does this happen?

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.LinkedBlockingQueue;

public class Test3 {

    static BlockingQueue<String> blockingQueue;
    static List<String> list = new ArrayList<>();

    static void run()  {
        while (true) {
            try {
                String s = blockingQueue.take();
                Thread.sleep(1000);
                list.add(s);
            }catch (InterruptedException e){}
        }
    }

    public static void main(String[] args)  {
        blockingQueue = new LinkedBlockingQueue<>();
        blockingQueue.add("test1");
        blockingQueue.add("test2");
        blockingQueue.add("test3");

        CompletableFuture.runAsync(() -> run());

        while (list.size() < 3) {
            // uncomment the line below to make it finish
            //System.out.println(list.size());
        }

        System.out.println("Done");
    }
}

I don't seem to have any idea.

Answer 1

The compiler is free to optimize

    while (list.size() < 3) {
        // uncomment the line below to make it finish
        //System.out.println(list.size());
    }

to

    if (list.size() < 3) {
        while(1);
    }

Why? Because this just looks like the CPU is reading the list's size from cache, and CPUs are allowed to have caches and read from them.

Note that it's not that the CPU actually has a cache or that anything is actually read from a cache. It's just that CPUs are allowed to have caches and read from them and your code has to take that into account, which you failed to do.

Java provides any number of synchronization primitives that you can use to solve this problem.

This may seem like a weird decision for a language to make. But cross-thread synchronization is only needed in a limited number of cases and the number of optimizations allowed by assuming that cross-thread synchronization is not needed is vast and significant. So the onus is put on code that requires synchronization to request it.

When you hear Java's memory semantics described in terms of flushing caches to main memory, understand that that's an abstraction. The system behaves as if it had caches that needed to be flushed. Synchronization functions behave as if they flushed data to, or read data from, main memory. But what's actually happening under the hood on most systems is entirely different because CPU cache coherence is guaranteed in hardware on most realistic multi-core CPUs you're likely to run Java code on.

It's somewhat amusing, but this mythical caching and flushing allows code to be more efficient even though it does not actually exist in realistic modern hardware! The fact that programmer's are required to act as if such caching existed and such flushing was required permits optimizations to be made in code generation that result in significant performance improvements.

Answer 2

According to: https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html ArrayList are not thread-safe, to quote:

Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be "wrapped" using the Collections.synchronizedList method.

To fix use:

static List<String> list = java.util.Collections.synchronizedList(new ArrayList());