Логика Java fork / join framework

Это стало "побочным эффектом" к ответу на другой вопрос сегодня. Это скорее любопытство, чем реальная проблема.

Java SE 7 предлагает то, что Oracle называет "Fork / join framework". Это предположительно лучший способ планирования работы для нескольких процессоров. Хотя я понимаю, как это должно работать, я не могу понять ту часть, где это превосходство и претензии, сделанные о краже работы.

Может быть, у кого-то другого есть больше понимания, почему это подход был бы желателен (кроме того, что он имеет причудливое название).

Базовыми примитивами fork/join являются ForkJoinTasks, которые являются Futures, и идея заключается в том, чтобылибо выполнить работу немедленно[sic] (формулировка вводит в заблуждение, поскольку "немедленно" подразумевает, что это происходит синхронно в главном потоке, в действительности это происходит внутри Future) ниже определенного порога, либо разделить работу на две задачи рекурсивно, пока не будет достигнут порог.

Будущее-это концепция инкапсуляции задачи, которая выполняется асинхронно в объект непрозрачным и неопределенным способом. У вас есть функция, которая позволяет проверить, доступен ли результат, и вы получаете функцию, которая позволяет вам (ждать и) получить результат.
Строго говоря, вы даже не знаете, выполняется ли будущее асинхронно, оно может выполняться внутри get(). Теоретически реализация может также породить поток для каждого будущего или использовать пул потоков.
На практике Java реализует фьючерсы как задачи в очереди задач с присоединенным пулом потоков (то же самое верно для всей платформы fork/join).

Документация fork/join дает этот конкретный пример использования:

protected void compute() {
    if (mLength < sThreshold) {
        computeDirectly();
        return;
    }

    int split = mLength / 2;

    invokeAll(new ForkBlur(mSource, mStart, split, mDestination),
              new ForkBlur(mSource, mStart + split, mLength - split,
                           mDestination));
}

Это отправляет задачи в очередь задач базового threadpool способом, не зависящим от того, как Mergesort будет проходить их (благодаря рекурсии).
Скажем, например, что у нас есть массив из 32 "элементов" для обработки и имеет порог 4, и разделить равномерно, он будет производить 8 задания с 4 "предметами" в каждом, и выглядят так:

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
                                               .
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15|16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
                       .                       .                       .
00 01 02 03 04 05 06 07|08 09 10 11 12 13 14 15|16 17 18 19 20 21 22 23|24 25 26 27 28 29 30 31
           .           .           .           .           .           .           .
00 01 02 03|04 05 06 07|08 09 10 11|12 13 14 15|16 17 18 19|20 21 22 23|24 25 26 27|28 29 30 31
------------------------------------------------------------------------------------------------
     1     |     2     |     3     |     4     |     5     |     6     |     7     |     8     | 

На одноядерном процессоре это будет представлять / выполнять (очень сложным способом) группы задач 1-2-3-4-5-6-7-8 по порядку.
На двухъядерном процессоре это отправит / выполнит (1,3)-(2,4)-(5,7)-(6,8) ^[1].
На четырехъядерном процессоре это будет представлять / выполнять (1,3,5,7)-(2,4,6,8).

Для сравнения, наивная реализация без всей высшей магии просто поставила бы задачи 1-2-3-4-5-6-7-8 в очередь задач сразу же. Всегда.

На одноядерном процессоре это будет представлять / выполнять 1-2-3-4-5-6-7-8.
На двухъядерном процессоре это будет представлять / выполнять (1,2)-(3,4)-(5,6)-(7,8).
На четырехъядерном процессоре это будет представлять / выполнять (1,2,3,4)-(5,6,7,8).

Вопросы:

1. Вместо того чтобы просто запихиватьsThreshold последовательные элементы в одну задачу и отправлять одну задачу за другой в очередь задач пула потоков, a создается древовидная рекурсивная иерархия. Это включает в себя построение, обращение и уничтожение N + log2(N) объектов для N подзадач, которые фактически ничего не делают. Почему это превосходство?

2. Ни одна точка отсчета не сохраняется. Ни процессорные кэши, ни виртуальная память не любят, когда с ними так обращаются. Почему это превосходство?

3. За исключением однопроцессорной системы, задачи гарантированно не будут планироваться в порядке, близком к их первоначальному порядку. Это может быть не проблема, если это действительно не имеет значения, но это делает такие вещи, как, например, забор или барьер, в значительной степени неосуществимыми. Единственный способ иметь что-то вроде забора-это ждать завершения корневого объекта и только после этого отправлять новые задачи. Это эквивалентно полной остановке трубопровода (что именно то, чего вы никогда не хотите).

4. Документация Oracle утверждает, что этот подход реализует кражу работы и поэтому лучше, чем поток бассейн . Я не вижу, как это происходит. Все, что я вижу, - это очень сложный способ передачи задач в обычный пул потоков. Как это должно магически реализовывать кражу работы?

---

^[1] давайте не будем делать это слишком сложным и предположим, что рабочие потоки не обгоняют друг друга, а все задачи обрабатываются в одно и то же время. В противном случае исполнение могло бы, конечно, происходить в другом порядке, хотя подчинение было бы тем же самым.