Java 8 Parallel Streams Deadlocking

The Java 8 parallel streams api supports parallel processing of operators and parallel foreach loops. However, it appears as if the backend executor framework, the fork/join pool, has a problem with nested parallel loops: If you use nested parallel streams, e.g. like
IntStream.range(0,24).parallel().forEach(i -> {
  // do some heavy work here
  IntStream.range(0,100).parallel().forEach(j -> {
    // do some work here
  });
});
you may observe very poor performance at high CPU usage. For example, runnning the test program at NestedParallelForEachBenchmark.java I get the following results:

Timing for test cases (parallelism set to 2):
inner loop parallel             = 41,18 +/- 2,99 (min: 33,14 , max: 45,59) [CPU Time: 106,00] (number of threads in F/J pool: 8)
inner loop sequential           = 27,61 +/- 0,50 (min: 26,62 , max: 28,61) [CPU Time: 76,91] (number of threads in F/J pool: 2)
inner loop parallel with bugfix = 26,99 +/- 0,81 (min: 25,75 , max: 28,77) [CPU Time: 77,73] (number of threads in F/J pool: 2)
(test cases were run independent with 20 warm up runs and 20 test runs on an Intel i7@2.6 GHz).

In addition, using synchronization may lead to (unexpected) deadlocks. For example, the following code will result in a deadlock:
IntStream.range(0,24).parallel().forEach(i -> {
  // do some heavy work here
  synchronized(this) {
    IntStream.range(0,100).parallel().forEach(j -> {
      // do some work here
    });
  }
});
In this test case we generate 24 parallel tasks to make some calculation. At one point we need to synchronize (assume we need to access some state). There is only one thread entering the synchronized() part. Inside the synchronized part we evaluate some function in parallel (why not, all the other threads are waiting anyway), but that is fine (there is no nested locking). Some might suspect that - given that all tasks are submitted to a common thread pool - there are no more threads to calculate the inner loop in parallel. However, even if there are no more free workers, there is at least one active thread, namely that one which entered the synchronized {} block, and we expect that parallel execution defaults to in-line sequential execution if there are no additional threads available.
The parallel streams use a common ForkJoinPool as a backend, and this behavior is implemented in the ForkJoinTask: it distinguishes between a ForkJoinWorkerThread and the main Thread and all tasks which cannot be completed by a ForkJoinWorkerThread can run (sequentially) on the main Thread.
Also note, that the documentation of the backend ForkJoinPool states that

"The pool attempts to maintain enough active (or available) threads by dynamically adding, suspending, or resuming internal worker threads, even if some tasks are stalled waiting to join others. However, no such adjustments are guaranteed in the face of blocked IO or other unmanaged synchronization."

- but a deadlock would only be expected if the number of available threads is exhausted (and we are far below that number). So while synchonize should be avoided, the documentation of the ForkJoinPool does not forbit synchronization.
Even without the synchronize the bug will lead to performance issues (see a corresponding post on stackoverflow).

The Bug

The test whether a task is running on a main thread (the creator of that loop) or running on a worker is performed via the line (401 in ForkJoinTask of 1.8u5 (Java 8))
((t = Thread.currentThread()) instanceof ForkJoinWorkerThread)
so it just tests if the currentThread is of type ForkJoinWorkerThread. But for a nested loop, the calling thread (the creator) could itself be of type ForkJoinWorkerThread, because it is a worker of the outer loop. In that case the inner loops task is joined with another outer loop task (which is currently waiting for the synchronized lock) and this results in a deadlock.

Reproducing the bug

To reproduce the bug and check the claim:

1. Run the program NestedParallelForEachAndSynchronization.java (see below) in a debugger. It will hang in a deadlock in the last test case (a simple nested loop with inner synchonization).
2. In the debugger suspend all threads and check where theses threads are waiting.
3. You will find out that all threads wait for the synchronize lock inside the outer loop and that lock is owned by one of the threads, lets call that thread ForkJoinPool.commonPool-worker-7.
4. If you check ForkJoinPool.commonPool-worker-7 then you see that he waits of the synchronize lock too, but he is already inside the inner loop. Now, lets check why a pice of code inside the synchronize waits for the lock: You see that the wait() is issued by the awaitJoin() in line 402 of ForkJoinTask. This is wrong, instead that task should have done an externalWaitDone(). Explanation: That task is the main task of the inner loop, i.e., a task of the outer loop that created the inner loop, but (due to a bug) that tasks considers itself as a forked worker (of the inner loop) and creates a join - effectively joining with the outer loop’s task. The problem is that if the inner loop is running on a forked worked of the outer loop, we cannot distinguish forked (inner loop’s) worker from main threads because line 401 is always true.
5. Double Checking: If the explanation in 4 would be correct, the problem would go away if we fix line 401 (and also all other corresponding tests). To fix this we change the type of the thread containing the inner loop from ForkJoinWorkerThread to Thread (by creating a wrapper). Indeed: this fixed that deadlock and greatly improved performance. The second test case in NestedParallelForEachAndSynchronization.java does this.

For a complete test demonstrating the deadlock and the workaround see: NestedParallelForEachAndSynchronization.java

Perfomance Problem induced by the Bug

The faulty join may lead to performance problems. For a complete test demonstrating the performance issue see NestedParallelForEachBenchmark.java or NestedParallelForEachTest.java.

Epilog

Nested parallelism may occure quite natural: Consider
IntUnaryOperator func = (i) -> IntStream.range(0,100).parallel().map(j -> i*j).sum();
- a definition of a function i -> func(i), which is defined as a sum of i*j and which is internally calculated in parallel. and then do
IntStream.range(0,100).parallel().map(func).sum();
(a discrete approximation of a two dimensional integral). Of course, this code (and other such problems) can be reformulated into a non-nested version, but assuming that you like to encapsulate the internal definition of func, the nesting is a consequence of abstraction.

I first encountered that bug via a deadlock introduced by using a Semaphore inside the outer loop (e.g. like a blocking IO). I have posted this to stackoverflow (and, following a suggestion on SO, to the concurrency-interest mailing list). The discussion started by that post then focussed on the question whether using a Semaphore and/or nested parallel loops would be a good design practice.
So far my conclusion is:

• Currently, nesting of parallel streams should be avoided since it has a performance issues.
• Nesting of parallel streams with inner synchronized has to be avoided, because a real risk of (otherwise unexpected) deadlocks.
• Currently the use of dedicated Executor frameworks is best to implement nested parallelism. However, using dedicated Executors has the disadvantage that is is much harder to maintain a global level of parallelism.

Tags:java, software

A new version of Obba has been released: Obba Version 3.1.5.

New in version 3.1: Support for creating objects dynamically from source code, see Class to Object Demo (movie).

Obbaprovides a bridge between spreadsheets and Java classes. With Obba, you can use spreadsheets as GUIs (Graphical User Interfaces) for your Java libraries. Compatible with Excel/Windows, OpenOffice/Win/Mac/Linux, LibreOffice/Win/Mac/Linux, NeoOffice/Mac.

Obba's main features are:

• Stateful access to almost all objects and methods running in a Java virtual machine via a fixed set of spread sheet functions.
• Client/server support: The Java virtual machine providing the add-in may run on the same computer or a remote computer - without any change to the spreadsheet.
• Loading of arbitrary jar or class files at runtime through a spreadsheet function.
• Instantiation of Java objects, storing the object reference under a given object label.
• Invocation of methods on objects referenced by their object handle, storing the handle to the result under a given object label.
• Asynchronous method invocation and tools for synchronization, turning your spreadsheet into a multi-threaded calculation tool.
• Allows arbitrary number of arguments for constructors or methods (avoids the limitation of the number of arguments for Excel worksheet functions).
• Serialization and de-serialization (save Serializable objects to a file, restore them any time later).
• All this through spreadsheet functions, without any additional line of code (no VBA needed, no additional Java code needed).

Use cases:

• For Spreadsheet Users: Creating powerful spreadsheet calculations using external libraries, running calculations in Java.
• For Java Developers: Testing, debugging and analyzing Java libraries with spreadsheets. Setting up unit test in spreadsheets. Using spreadsheets as GUI to your object while debugging.

Advanced Features:

• Run Obba server (and its JVM) on one machine, while the spreadsheet (with Obba add-in) runs on another machine.
• Obba allows to create an object from Java source code (dynamically compile source to java.lang.Class, re-load the class definition and instantiate an object from it), see Class to Object Demo (movie).

For tutorials see Obba tutorials. For a more detailed introduction see Obba documentation.

Tags:software, java, excel, openoffice

A new version of Obba has been released: Obba Version 3.0.6.

Obba provides a bridge between spreadsheets and Java classes. With Obba, you can use spreadsheets as GUIs for your Java libraries; turning your Java library to platform independent spreadsheet add-ins. Compatible with Excel/Windows, OpenOffice/Win/Mac/Linux, LibreOffice/Win/Mac/Linux, NeoOffice/Mac.

Its main features are:

• 
  
• Stateful access to almost all objects and methods running in a Java virtual machine via a fixed set of spread sheet functions.
• 
  
• Client/server support: The Java virtual machine providing the add-in may run on the same computer or a remote computer - without any change to the spreadsheet.
• 
  
• Loading of arbitrary jar or class files at runtime through a spreadsheet function.
• 
  
• Instantiation of Java objects, storing the object reference under a given object label.
• 
  
• Invocation of methods on objects referenced by their object handle, storing the handle to the result under a given object label.
• 
  
• Asynchronous method invocation and tools for synchronization, turning your spreadsheet into a multi-threaded calculation tool.
• 
  
• Allows arbitrary number of arguments for constructors or methods (avoids the limitation of the number of arguments for Excel worksheet functions).
• 
  
• Serialization and de-serialization (save Serializable objects to a file, restore them any time later).
• 
  
• All this through spreadsheet functions, without any additional line of code (no VBA needed, no additional Java code needed).
• 
  

For a tutorial see Obba tutorial. In this tutorial you create a Java class and a spreadsheet to fetch Stock quotes from finance.yahoo.com.

For a more detailed introduction see Obba documentation and Obba home page.

Version 3.0.6 of Obba is a major revision. It brings support for running the Java virtual machine on a different machine, i.e. via Obba, the spreadsheet may perform its Java calculations on a remote machine.

For more information see Obba's homepage.

Tags:software, java, excel, openoffice

A new version of Obba has been released: Obba Version 2.2.15.

Obba provides a bridge from spreadsheets (Excel or OpenOffice) to Java classes via worksheet functions (UDFs), without the need to write a single line of code. With Obba, you can easily build spreadsheet GUIs to Java classes. Obba is available for Excel and OpenOffice and Obba sheets may be migrated from Excel to OpenOffice or vice versa.

For more information see Obba's homepage.

Tags:software, java, excel, openoffice

A new version of Obba has been released: Obba Version 1.9.34.

Obba provides a bridge from spreadsheets (Excel or OpenOffice) to Java classes via worksheet functions (UDFs), without the need to write a single line of code. With Obba, you can easily build spreadsheet GUIs to Java classes. Obba is available for Excel and OpenOffice and Obba sheets may be migrated from Excel to OpenOffice or vice versa.

For more information see Obba's homepage.

Release Notes

Version 1.9.34 of Obba brings the following changes:

• Fixed a problem which prevented loading of some classes. The current thread's context class loader was null. This appears to be a problem with the Java plugin. A workaround was created. Note: This problem resulted in the XMLDecoder not working.
• Fixed a problem which prevented installation of Obba for OpenOffice.
• More improvements for OpenOffice
• Arrays of objects can be created using obMake with a class name of ClassName[] where ClassName is the component type (see documentation for an example).
• Added a demo sheet showing how to access data from finance.yahoo.com. Include the Java source code for the class handling the web access.

Tags:software, java, excel, openoffice

I wrote a small tutorial on how to use Obba and a small Java class to load Yahoo stock quotes into Excel / OpenOffice. It is just an example and could easily extended to other data / web sites.

Java code and spreadsheets are included.

Tags:java, obba, openoffice, excel, marketdata

A new version of Obba has been released: Obba Version 1.9.13.

Obba provides a bridge from spreadsheets (Excel or OpenOffice) to Java classes via worksheet functions (UDFs), without the need to write a single line of code. With Obba, you can easily build spreadsheet GUIs to Java classes. Obba is available for Excel and OpenOffice and Obba sheets may be migrated from Excel to OpenOffice or vice versa.

For more information see Obba's homepage.

Release Notes

Version 1.9.13 of Obba brings the following changes:

• Added a window to the Obba Control Panel which visualizes the objects and their dependencies in a graph. The dependencies are determined by the objects used during construction an object.
• Improved the handling of transient object handles.

Tags:software, java, excel, openoffice

A new version of Obba has been released: Obba Version 1.8.21.

Obba provides a bridge from spreadsheets (Excel or OpenOffice) to Java classes via worksheet functions (UDFs), without the need to write a single line of code. With Obba, you can easily build spreadsheet GUIs to Java classes. Obba is available for Excel and OpenOffice and Obba sheets may be migrated from Excel to OpenOffice or vice versa.

For more information see Obba's homepage.

Release Notes

Version 1.8.21 of Obba brings the following changes:

• Access fields of an object directly through a spreadsheet function call using 'obCall'. In this case the method name has to be dot + fieldname (e.g '.myMember').
• Access elements of an array through a spreadsheet function call using 'obCall'. In this case the method name has to be '[]' and the argument of the call is integer specifying the index. Element of multi-dimensional arrays can be accessed likewise.
• Vector arguments can be passed as arbitrary ranges (columns, rows or two dimensional ranges which are then flattened using row major).

Tags:software, java, excel, openoffice

A new version of Obba has been released: Obba Version 1.7.29.

Obba provides a bridge from spreadsheets (Excel or OpenOffice) to Java classes via worksheet functions (UDFs), without the need to write a single line of code. With Obba, you can easily build spreadsheet GUIs to Java classes. Obba is available for Excel and OpenOffice and Obba sheets may be migrated from Excel to OpenOffice or vice versa.

For more information see Obba's homepage.

Release Notes

This release fixes two small bugs in connection with the software registration: For OpenOffice the location where the registration is stored changed (you have to reenter registration data).

Tags:software, java, excel, openoffice