Why does parallel stream with lambda in static initializer cause a deadlock?

Question

I came across a strange situation where using a parallel stream with a lambda in a static initializer takes seemingly forever with no CPU utilization. Here's the code:

class Deadlock {
    static {
        IntStream.range(0, 10000).parallel().map(i -> i).count();
        System.out.println("done");
    }
    public static void main(final String[] args) {}
}

This appears to be a minimum reproducing test case for this behavior. If I:

• put the block in the main method instead of a static initializer,
• remove parallelization, or
• remove the lambda,

the code instantly completes. Can anyone explain this behavior? Is it a bug or is this intended?

I am using OpenJDK version 1.8.0_66-internal.

Answer 1

I found a bug report of a very similar case (JDK-8143380) which was closed as "Not an Issue" by Stuart Marks:

This is a class initialization deadlock. The test program's main thread executes the class static initializer, which sets the initialization in-progress flag for the class; this flag remains set until the static initializer completes. The static initializer executes a parallel stream, which causes lambda expressions to be evaluated in other threads. Those threads block waiting for the class to complete initialization. However, the main thread is blocked waiting for the parallel tasks to complete, resulting in deadlock.

The test program should be changed to move the parallel stream logic outside of the class static initializer. Closing as Not an Issue.

---

I was able to find another bug report of that (JDK-8136753), also closed as "Not an Issue" by Stuart Marks:

This is a deadlock that is occurring because the Fruit enum's static initializer is interacting badly with class initialization.

See the Java Language Specification, section 12.4.2 for details on class initialization.

http://docs.oracle.com/javase/specs/jls/se8/html/jls-12.html#jls-12.4.2

Briefly, what's happening is as follows.

1. The main thread references the Fruit class and starts the initialization process. This sets the initialization in-progress flag and runs the static initializer on the main thread.
2. The static initializer runs some code in another thread and waits for it to finish. This example uses parallel streams, but this has nothing to do with streams per se. Executing code in another thread by any means, and waiting for that code to finish, will have the same effect.
3. The code in the other thread references the Fruit class, which checks the initialization in-progress flag. This causes the other thread to block until the flag is cleared. (See step 2 of JLS 12.4.2.)
4. The main thread is blocked waiting for the other thread to terminate, so the static initializer never completes. Since the initialization in-progress flag isn't cleared until after the static initializer completes, the threads are deadlocked.

To avoid this problem, make sure that a class's static initialization completes quickly, without causing other threads to execute code that requires this class to have completed initialization.

Closing as Not an Issue.

---

Note that FindBugs has an open issue for adding a warning for this situation.

Answer 2

For those who are wondering where are the other threads referencing the Deadlock class itself, Java lambdas behave like you wrote this:

public class Deadlock {
    public static int lambda1(int i) {
        return i;
    }
    static {
        IntStream.range(0, 10000).parallel().map(new IntUnaryOperator() {
            @Override
            public int applyAsInt(int operand) {
                return lambda1(operand);
            }
        }).count();
        System.out.println("done");
    }
    public static void main(final String[] args) {}
}

With regular anonymous classes there is no deadlock:

public class Deadlock {
    static {
        IntStream.range(0, 10000).parallel().map(new IntUnaryOperator() {
            @Override
            public int applyAsInt(int operand) {
                return operand;
            }
        }).count();
        System.out.println("done");
    }
    public static void main(final String[] args) {}
}

Answer 3

There is an excellent explanation of this problem by Andrei Pangin, dated by 07 Apr 2015. It is available here, but it is written in Russian (I suggest to review code samples anyway - they are international). The general problem is a lock during class initialization.

Here are some quotes from the article:

---

According to JLS, every class has a unique initialization lock that is captured during initialization. When other thread tries to access this class during initialization, it will be blocked on the lock until initialization completes. When classes are initialized concurrently, it is possible to get a deadlock.

I wrote a simple program that calculates the sum of integers, what should it print?

public class StreamSum {
    static final int SUM = IntStream.range(0, 100).parallel().reduce((n, m) -> n + m).getAsInt();

    public static void main(String[] args) {
        System.out.println(SUM);
    }
} 

Now remove parallel() or replace lambda with Integer::sum call - what will change?

Here we see deadlock again [there were some examples of deadlocks in class initializers previously in the article]. Because of the parallel() stream operations run in a separate thread pool. These threads try to execute lambda body, which is written in bytecode as a private static method inside StreamSum class. But this method can not be executed before the completion of class static initializer, which waits the results of stream completion.

What is more mindblowing: this code works differently in different environments. It will work correctly on a single CPU machine and will most likely hang on a multi CPU machine. This difference comes from the Fork-Join pool implementation. You can verify it yourself changing the parameter -Djava.util.concurrent.ForkJoinPool.common.parallelism=N