Why Does Parallel Stream with Lambda in Static Initializer Cause a Deadlock

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

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.

Deadlock happens if I use lambda in parallel stream but it doesn't happen if I use anonymous class instead?

The difference is that lambda body is written in the same Test class, i.e. a synthetic method

private static int lambda$static$0(int n, int m) {
    return n + m;
}

In the second case the implementation of the interface resides in a different Test$1 class. So the threads of a parallel stream do not call static methods of Test and thus do not depend on Test initialization.

Why using parallel streams in static initializer leads to not stable deadlock

TL;DR This is a HotSpot bug JDK-8215634

The problem can be reproduced with a simple test case that has no races at all:

public class StaticInit {

    static void staticTarget() {
        System.out.println("Called from " + Thread.currentThread().getName());
    }

    static {
        Runnable r = new Runnable() {
            public void run() {
                staticTarget();
            }
        };

        r.run();

        Thread thread2 = new Thread(r, "Thread-2");
        thread2.start();
        try { thread2.join(); } catch (Exception ignore) {}

        System.out.println("Initialization complete");
    }

    public static void main(String[] args) {
    }
}

This looks like a classic initialization deadlock, but HotSpot JVM does not hang. Instead it prints:

Called from main
Called from Thread-2
Initialization complete

Why this is a bug

JVMS §6.5 requires that upon execution of invokestatic bytecode

the class or interface that declared the resolved method is initialized if that class or interface has not already been initialized

When Thread-2 calls staticTarget, the main class StaticInit is obviously uninitialized (since its static initializer is still running). This means Thread-2 must launch class initialization procedure described in JVMS §5.5. According to this procedure,

2. If the Class object for C indicates that initialization is in progress for C by some other thread, then release LC and block the current thread until informed that the in-progress initialization has completed

However, Thread-2 is not blocked despite the class is in progress of initialization by thread main.

What about other JVMs

I tested OpenJ9 and JET, and they both expectedly deadlock on the above test.

It's interesting that HotSpot also hangs in -Xcomp mode, but not in -Xint or mixed modes.

How it happens

When interpreter first encounters invokestatic bytecode, it calls JVM runtime to resolve the method reference. As a part of this process JVM initializes the class if necessary. After successful resolution the resolved method is saved in the Constant Pool Cache entry. Constant Pool Cache is a HotSpot-specific structure that stores resolved constant pool values.

In the above test invokestatic bytecode that calls staticTarget is first resolved by the main thread. Interpreter runtime skips class initialization, because the class is already being initialized by the same thread. The resolved method is saved in the constant pool cache. The next time when Thread-2 executes the same invokestatic, the interpreter sees that the bytecode is already resolved and uses constant pool cache entry without calling to runtime and thus skips class initialization.

A similar bug for getstatic/putstatic was fixed long ago - JDK-4493560, but the fix did not touch invokestatic. I've submitted the new bug JDK-8215634 to address this issue.

As to the original example,

whether it hangs or not depends on which thread first resolves the static call. If it is main thread, the program completes without a deadlock. If the static call is resolved by one of ForkJoinPool threads, the program hangs.

Update

The bug is confirmed. It is fixed in the upcoming releases: JDK 8u201, JDK 11.0.2 and JDK 12.

Why when I don't use the lambda method reference code style in static block will cause deadlock?

Interesting Question: This question is similar with Class Loading with Static Block Competition Cause Deadlock,

but for this issue, it's caused by when use e -> {System.out.println(e);} after compiling, it will generate an synthetic method: anonymous static private method for this, as:

  // access flags 0x100A
  private static synthetic lambda$init$0(Ljava/lang/Integer;)V
   L0
    LINENUMBER 27 L0
    GETSTATIC java/lang/System.out : Ljava/io/PrintStream;
    ALOAD 0
    INVOKEVIRTUAL java/io/PrintStream.println (Ljava/lang/Object;)V
   L1
    LINENUMBER 28 L1
    RETURN
   L2
    LOCALVARIABLE e Ljava/lang/Integer; L0 L2 0
    MAXSTACK = 2
    MAXLOCALS = 1

this synthetic method: private static method is generated by e -> {System.out.println(e);} compile.

also it's similar equal to:

static {
    init();
}

private static void init() {
    Map<Integer, String> map = new HashMap<>();

    int i = 0;
    map.put(++i, "1");
    ***
    Thread foo = new Thread() {
        @Override
        public void run() {
            print(map.keySet().iterator().next()); //try access the private method, this cause a competition with **Class Initializer** and **static block**
        }
    };

    foo.start();
    try {
        foo.join();
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}
//equal to e -> {System.out.println(e);}
private static void print(int t) {
    System.out.println(t);
}

so as Class Loading with Static Block Competition Cause Deadlock this post explanation: when init class BugSimulate, it will invoke static block firstly, but since it's using parallelStream and try to invoke the generated private anonymous method, this caused an competition with class initializer, so finally it's deadlock.

Lambdas in static initialiser threadlocking

When the class is being staticly initialized the JVM holds a class-level lock. The lock prevents other threads from accessing the class until it is fully initialized.

There is no need to do what you're trying to do, anyways. A new Object[9] array is already initialized to all nulls. Not to mention, even if it did work, parallelism has a ton of overhead. The overhead would vastly outweigh any benefit from splitting up this task across multiple cores. (With 9 elements there is no benefit.)

Program hangs if thread is created in static initializer block

You're not just starting another thread - you're joining on it. That new thread has to wait for StaticInitializer to be fully initialized before it can proceed, because it's trying to set the state field... and initialization is already in progress, so it waits. However, it's going to be waiting forever, because that initialization is waiting for that new thread to terminate. Classic deadlock.

See the Java Language Specification section 12.4.2 for details about what's involved in class initialization. Importantly, the initializing thread will "own" the monitor for StaticInitializer.class, but the new thread will be waiting to acquire that monitor.

In other words, your code is a bit like this non-initializer code (exception handling elided).

final Object foo = new Object();
synchronized (foo)
{
    Thread t1 = new Thread(new Runnable() {
        @Override
        public void run() {
            synchronized (foo) {
                System.out.println("In the new thread!");
            }
        });
    t1.start();
    t1.join();
});

If you can understand why that code would deadlock, it's basically the same for your code.

The moral is not to do much work in static initializers.

Why does a parallel Java Stream with a short-curcuit operation evaluate all elements of the Stream while a sequential Stream does not?

A parallel stream still supports short-circuiting, but there was be no advantage in using a parallel stream, if all threads were deferring their work until the thread(s) processing previous elements acknowledged that the operation has not ended.

Therefore, it is expected behavior that a parallel stream processes an unspecified number of elements more than necessary, as long as the final result is assembled correctly, i.e. dropping excess elements.

It’s just your example, consisting of only two elements, were just processing one element more than necessary can be interpreted as “all elements are processed”.

There’s generally little benefit in parallel processing when the number of elements is small and/or the actual operation is to find something that will predictably be among the first elements of the stream. Things get more interesting, if you do something like

IntStream.range(0, 2000).parallel()
    .map(i -> { LockSupport.parkNanos(TimeUnit.MILLISECONDS.toNanos(50)); return i;})
    .filter(i->i%397==396)
    .findAny();

---

Note that the terminal operation will wait for the completion of all worker threads before returning the final result, so when the evaluation of an element has been already started by the time a result has been found, that element’s processing will be completed. This is by design. It ensures that there will be no concurrent access to a source collection or other data accessed by your lambda expressions when your application code proceeds after the stream operation.

Compare with the package documentation:

In almost all cases, terminal operations are eager, completing their traversal of the data source and processing of the pipeline before returning. Only the terminal operations iterator() and spliterator() are not; …

So a short-circuiting parallel stream does not process all elements, but may still take longer to return the already evaluated result when the other worker threads are still processing obsolete elements.

If you want an early return, accepting potentially still running background threads, the Stream API is not the right thing for you. Consider

private int work(int i) throws InterruptedException {
    System.out.println( "working... " + i );
    Thread.sleep(i * 1000);
    System.out.println( "worked. " + i );
    return i;
}
public void parallel() throws Exception {
    System.out.println( "parallel start." );
    List<Callable<Integer>> jobs = IntStream.range(0, 100)
      .collect(ArrayList::new, (l,i) -> l.add(() -> work(i)), List::addAll);
    ExecutorService pool = Executors.newFixedThreadPool(10);
    Integer result = pool.invokeAny(jobs);
    pool.shutdown();
    System.out.println( "parallel done, result="+result );
}

Note that this not only returns immediately after the first job completed, it also supports cancellation of all already running jobs via interruption.

Why is there a deadlock between two parallel executions of identical transactions?

Instead of diagnosing this one, I would just hit the "easy button", and serialize the transactions with an application lock:

BEGIN TRAN UpdateMediaTables
exec sp_getapplock 'UpdateMediaTables', 'Exclusive'
. . .

Then the second session will be blocked before acquiring any locks until the first is complete.

---

Related Topics