0

As far as I understand, a ForkJoinPool uses the 'Last-in-First-Out principle (LiFo)'. Perhaps the best explanation I could find is this link. However, the invokeall() method in ForkJoinPool.java seems to join (quietlyjoin() ?) the tasks in the order where they were submitted (FiFo), see the code below. Doesn't it make more sense to do it the other way around since all processing is LiFo?

Wouldn't this lead to fewer 'compensation threads' ? I am thinking of rewriting my code to submit tasks, rather than using invokeall(), and join them on the LiFo basis because of this. See also:

ForkJoinPool stalls during invokeAll/join

ForkJoinPool seems to waste a thread

EDIT: there is a difference whether a task is submitted to the external que or the deque of a worker. I am refering to the deque of the worker. I assume that invokeall() can lead to threadstalling here.

public <T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks) {
        // In previous versions of this class, this method constructed
        // a task to run ForkJoinTask.invokeAll, but now external
        // invocation of multiple tasks is at least as efficient.
        ArrayList<Future<T>> futures = new ArrayList<>(tasks.size());

        try {
            for (Callable<T> t : tasks) {
                ForkJoinTask<T> f = new ForkJoinTask.AdaptedCallable<T>(t);
                futures.add(f);
                externalSubmit(f);
            }
            for (int i = 0, size = futures.size(); i < size; i++)
                ((ForkJoinTask<?>)futures.get(i)).quietlyJoin();
            return futures;
        } catch (Throwable t) {
            for (int i = 0, size = futures.size(); i < size; i++)
                futures.get(i).cancel(false);
            throw t;
        }
    }
simon
  • 77
  • 7
  • I think the 'Last-in-First-Out principle (LiFo)' holds only for `ForkJoinTask`s and subtasks submitted through `ForkJoinTask.invokeAll()` (because this is where the recursive split (aka fork/join) takes place, leading to the LIFO behaviour). When using `ForkJoinPool.invokeAll()` there are no dependencies between the tasks, so joining the in order doens't make a big difference compared to joining them in reverser order – Thomas Kläger Apr 06 '20 at 09:31
  • What if your mainthread does a invokeall on 5 tasks, and all create 3 subtasks. The first task processed is the last subtask of the last (5th) maintask. Correct? However, since the first join() in the mainthread is linked to the 1st 'task' due to the invokeall() code above, the thread is stalled.... leading to overhead because a 'compensation thread' needs to be initiated. Although, this is my interpretation of the theory I read so far. – simon Apr 06 '20 at 09:48
  • One thing is the mainthread: it is not one of the `ForkJoinPool`s threads, so it will stall until all 5 tasks are completed, no matter in which order they complete. The 5 tasks are running in parallel in worker threads from the `ForkJoinPool`, spawning 3 subtasks each. Upon trying to join the subtasks, the worker threads will not stall, but do other work from their work queues (which each contains the 3 subtasks). – Thomas Kläger Apr 06 '20 at 13:44
  • You are right there is a que and a deque. What if the workers of the ForkJoinPool initiate the 3 subtasks with invokeall(), though? In this case the 3 new task are put onto the deque, where the worker will start with the last subtask. The thread (not worker) is stalled, thereafter, because invoke all() waits to join the first task. fliping this order of 'joiing' might allow for the worker to do all computations on 1 thread. Is that correct? – simon Apr 06 '20 at 14:00
  • Even then the thread is not stalled, because `invokeAll()` does **not** a `Thread.join()` (which would stall). Instead it decides: if the running thread is an "external" thread (like the main thread) it waits for completion. If the running thread is a `ForkJoinWorkerThread` it will try to do other work (either from it's own work queue or by stealing work from other queues). – Thomas Kläger Apr 06 '20 at 14:14

0 Answers0