ForkJoinPool seems to waste a thread

Question

I'm comparing two variations on a test program. Both are operating with a 4-thread ForkJoinPool on a machine with four cores.

In 'mode 1', I use the pool very much like an executor service. I toss a pile of tasks into ExecutorService.invokeAll. I get better performance than from an ordinary fixed thread executor service (even though there are calls to Lucene, that do some I/O, in there).

There is no divide-and-conquer here. Literally, I do

ExecutorService es = new ForkJoinPool(4);
es.invokeAll(collection_of_Callables);

In 'mode 2', I submit a single task to the pool, and in that task call ForkJoinTask.invokeAll to submit the subtasks. So, I have an object that inherits from RecursiveAction, and it is submitted to the pool. In the compute method of that class, I call the invokeAll on a collection of objects from a different class that also inherits from RecursiveAction. For testing purposes, I submit only one-at-a-time of the first objects. What I naively expected to see what all four threads busy, as the thread calling invokeAll would grab one of the subtasks for itself instead of just sitting and blocking. I can think of some reasons why it might not work that way.

Watching in VisualVM, in mode 2, one thread is pretty nearly always waiting. What I expect to see is the thread calling invokeAll immediately going to work on one of the invoked tasks rather than just sitting still. This is certainly better than the deadlocks that would result from trying this scheme with an ordinary thread pool, but still, what up? Is it holding one thread back in case something else gets submitted? And, if so, why not the same problem in mode 1?

So far I've been running this using the jsr166 jar added to java 1.6's boot class path.

Insipience

Are you saying that when you see one thread "nearly always waiting" that it's while the other thread handles most of the work processing the task? Also check out the idlePerActive() function: gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/… – Peduncle

@Insipience can you post the test you are running? – Perineuritis

@JohnVint It's rather a large program. I'll try to create a more limited test case and put it up on github, it will take a while. – Insipience

@Insipience When you say 'What I expect to see is the thread calling invokeAll immediately going to work on one of the invoked tasks rather than just sitting still' Do you mean the thread that is passing the initial task to the thread-pool? And also is mode-1 set up to divide-and-conquer like your mode-2 is/should be? – Perineuritis

@JohnVint see edit in which I attempted to elaborate. – Insipience

@Insipience Did you fix this issue? I have bug with invokeAll method. One task is hangs on externalAwaitDone method – Meda

Did you happen to notice how long ago this was written? Also, I accepted the accepted answer for a reason. – Insipience

Answer 1

ForkJoinTask.invokeAll is forking all tasks, but the first in the list. The first task it runs itself. Then it joins other tasks. It's thread is not released in any way to the pool. So you what you see, it it's thread blocking on other tasks to be complete.

Laflamme

Well, most of the time. Join will not wait if the joined task is on top of the stack, I believe. Then it will execute it. – Laflamme

If a task calls invokeAll on a bunch of tasks, which one does it 'join' first? – Insipience

So 1st task (index 0) it executes itself, the joins 2ns, then 3rd, .... I've checked implementation. – Laflamme

@Laflamme That's not really true. The first task can compute() which can fork sub tasks, each sub task can then fork their own sub task. The first task will not join until its second task finishes (which can be the product of many many fork/joins) – Perineuritis

Answer 2

The classic use of invokeAll for a Fork Join pool is to fork one task and compute another (in that executing thread). The thread that does not fork will join after it computes. The work stealing comes in with both tasks computing. When each task computes it is expected to fork it's own subtasks (until some threshold is met).

I am not sure what invokeAll is being called for your RecursiveAction.compute() but if it is the invokeAll which takes two RecursiveAction it will fork one, compute the other and wait for the forked task to finish.

This is different then a plain executor service because each task of an ExecutorService is simply a Runnable on a queue. There is no need for two tasks of an ExecutorService to know the outcome of another. That is the primary use case of a FJ Pool.

Perineuritis

FWIW, the invokeAll typically passes in about a dozen tasks. – Insipience