Логика фреймворка Java / соединения
Это стало побочным эффектом ответа на другой вопрос сегодня. Это больше о любопытстве, чем о реальной проблеме.
Java SE 7 предлагает то, что Oracle называет "инфраструктурой fork/join". Это, по-видимому, лучший способ планирования работы с несколькими процессорами. Хотя я понимаю, как это должно работать, я не могу понять, в чем его преимущество, и какие требования предъявляются к краже работы.
Может быть, кто-то еще лучше понимает, почему этот подход был бы желательным (кроме того, что у него есть причудливое имя).
Основными примитивами fork/join являются ForkJoinTask с, которые 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));
}
Это отправляет задачи в очередь задач базового пула потоков способом, идентичным тому, как 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).
Вопросы:
Вместо простого объединения последовательных элементов sThreshold в одну задачу и отправки одной задачи за другой в очередь задач пула потоков создается древовидная иерархия рекурсии. Это включает в себя создание, обращение и уничтожение N+log2(N) объектов для N подзадач, которые фактически ничего не делают. Почему это лучше?
Ссылка не сохраняется. Ни кэш-память процессора, ни виртуальная память не воспринимаются так. Почему это лучше?
За исключением однопроцессорной системы, задачи гарантированно не планируются в порядке, близком к их первоначальному порядку. Это может не иметь значения, если это действительно не имеет значения, но делает такие вещи, как, например, забор или барьер, практически неосуществимым. Единственный способ получить что-то вроде ограждения - это дождаться завершения корневого объекта и только после этого отправлять новые задачи. Это эквивалентно полной остановке конвейера (а это именно то, чего вы никогда не хотите).
Документация Oracle утверждает, что этот подход реализует кражу работы и поэтому лучше, чем пул потоков. Я не вижу, что это происходит. Все, что я вижу, - это очень сложный способ отправки задач в обычный обычный пул потоков. Как это должно волшебным образом осуществить кражу работы?
[1] Давайте не будем усложнять ситуацию и предположим, что рабочие потоки не опережают друг друга, а выполнение всех задач занимает одно и то же время. В противном случае выполнение может, конечно, происходить в другом порядке, хотя отправка будет такой же.
2 ответа
Когда вы используете ExecutorService вы решите, сколько потоков будет в пуле потоков, и нет никакого различия между запланированными задачами и подзадачами, которые эти задачи создают. ForkJoinPool вместо этого класс управляет потоками на основе 1) доступных процессоров и 2) задач.
В этом случае подзадачи, созданные активными задачами, планируются другими методами, чем внешние задачи.
У нас обычно есть один пул разветвления для всего приложения (в отличие от использования ExecutorService где обычно более 1 в любом нетривиальном приложении) и нет необходимости shutdown,
Я не проверял внутренности, чтобы дать вам более низкое объяснение уровня, но если вы видите здесь, есть презентация и тест, показывающий измерения, показывающие обещанный параллелизм.
Обновить:
Эта структура решает конкретные проблемы (ExecutorService лучше работает для задач, которые имеют сочетание процессора и ввода / вывода).
Основное мышление здесь - использовать рекурсивный / разделяй и властвуй подход, чтобы постоянно загружать процессоры. Идея состоит в том, чтобы создавать новые задачи (разветвление) и приостанавливать текущую задачу до тех пор, пока новые задачи не будут завершены (объединиться), но без создания новых потоков и без общей рабочей очереди.
Таким образом, инфраструктура Fork-join реализована с использованием кражи рабочих данных путем создания ограниченного числа рабочих потоков (до числа ядер). Каждый рабочий поток поддерживает частную двустороннюю рабочую очередь.
Разветвляясь, рабочий выдвигает новую задачу во главе своей очереди. В ожидании или в режиме ожидания рабочий вытаскивает задачу из головы своей очереди и выполняет ее вместо сна.
Если рабочий список пуст, украдет элемент у хвоста рабочего стола другого случайно выбранного рабочего.
Я бы рекомендовал прочитать параллелизм данных в Java, а также сделать некоторые тесты самостоятельно, чтобы убедиться. Теория хороша только до определенного момента. После этого сделайте ваши измерения, чтобы увидеть, есть ли существенное снижение производительности или нет
Позвольте мне начать со статьи [да, я написал это], которая критикует рамки. Бедствие Java Fork-Join
Теперь на ваши вопросы:
Это не. Фреймворк хочет обработать DAG. Это структура дизайна.
Это не. Как упоминается в статье, приложения Java ничего не знают о кешах, памяти и т. Д., Поэтому предположения ошибочны.
Да. Именно так и происходит. Стойлы настолько распространены, что фреймворк должен создавать "потоки продолжения", чтобы продолжать движение Статья ссылается на вопрос, где было необходимо более 700 продолжений.
Я, конечно, согласен, что код является сложным. Scatter-collect работает намного лучше, чем похищение работ для приложений. Что касается документации, что документация? Нет подробностей от Oracle. Это все толчок, чтобы использовать рамки.
Есть альтернативы.