Java fork/join framework logic

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

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

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

Подчиненными примитивами fork/join являются ForkJoinTask s, которые являются Future s, и идея либо выполняет работу немедленно [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).

Вопросы:

Вместо того, чтобы просто перебивать sпороговые последовательные элементы в одну задачу и отправлять одну задачу за другой в очередь задач пула потоков, генерируется иерархическая иерархия рекурсии. Это включает в себя построение, привязку и уничтожение объектов N + log2 (N) для N подзадач, которые фактически ничего не делают. Почему этот начальник?
Никакая местность ссылки не сохраняется. Ни кеширование процессоров, ни виртуальная память не обрабатываются. Почему этот начальник?
За исключением однопроцессорной системы, задачи гарантированно не планируются в порядке, близком к их первоначальному порядку. Это может быть проблемой, если это действительно не имеет значения, но это делает такие вещи, как например. забор или барьер в значительной степени неосуществимы. Единственный способ иметь что-то вроде забора - ждать завершения корневого объекта и только после этого отправлять новые задачи. Это эквивалентно полному конвейеру (это именно то, чего вы никогда не хотите делать).
Документация Oracle утверждает, что этот подход реализует кражу работы и поэтому лучше, чем пул потоков. Я этого не вижу. Все, что я вижу, это очень сложный способ отправки задач в обычный обычный пул потоков. Как это должно магически выполнять кражу работы?

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

Ответ 1

При использовании ExecutorService вы определите, сколько потоков будет в пуле потоков, и не существует никакого различия между запланированными вами задачами и подзадачами, которые создают эти задачи.
ForkJoinPool вместо этого управляет потоками на основе 1) доступных процессоров и 2) задачи. В этом случае подзадачи, созданные активными задачами, планируются разными способами, чем внешние задачи.
Обычно у нас есть один пул fork-join для всего приложения (в отличие от использования ExecutorService, где типично иметь более одного в любом нетривиальном приложении), и нет необходимости в shutdown.
Я не рассмотрел внутренности, чтобы дать вам более низкое объяснение, но если вы видите здесь, то есть презентация и контрольный показатель, показывающий измерения, показывающие parallelism, что обещано.

Update:
В этой структуре рассматриваются конкретные проблемы (ExecutorService работает лучше для задач, которые имеют сочетание активности ЦП и ввода/вывода).
Основное мышление здесь состоит в том, чтобы использовать подход рекурсивный/разделяй и завоевывать, чтобы постоянно поддерживать процессор. Идея состоит в том, чтобы создавать новые задачи (forking) и приостанавливать текущую задачу до тех пор, пока новые задачи не будут завершены (join), а без, создавая новые потоки и без, имеющих общую рабочую очередь.
Таким образом, структура Fork-join реализуется с помощью кражи работы путем создания ограниченного числа рабочих потоков (столько, сколько ядер). Каждый рабочий поток поддерживает частную двухстороннюю рабочую очередь.
Во время разворота рабочий ставит новую задачу во главе своего дека. При ожидании или бездействии работник вытаскивает задачу из головы своего дека и выполняет ее вместо сна.
Если рабочие deque пуст, он крадет элемент с хвоста дека другого случайно выбранного работника.
Я бы рекомендовал прочитать Data parallelism в Java, а также сделать некоторые тесты сами, чтобы убедиться. Теория хороша только до определенной степени. После этого сделайте свои измерения, чтобы увидеть, есть ли значительное преимущество производительности или нет.

Ответ 2

Позвольте мне начать с статьи [да, я ее написал], которая критикует структуру. Явление вилки-виртуализации Java

Теперь на ваши вопросы:

Это не так. Рамка хочет обработать DAG. Это структура дизайна.
Это не так. Как упоминается в статье, приложения Java ничего не знают о кэшах, памяти и т.д., Поэтому допущения ошибочны.
Да. Это именно то, что происходит. Стенды настолько распространены, что инфраструктуре необходимо создать "продолжения потоков" для продолжения движения. В статье упоминается вопрос, где нужно более 700 потоков продолжения.
Я, конечно, согласен, что код сложный. Scatter-gather работает намного лучше, чем кража работы для приложений. Что касается документации, какая документация? Информация от Oracle отсутствует. Его все нажимают на использование рамки.

Существуют альтернативы.