Сам еще учусь…
О пулах потоков и одномерных шахматных досках
История до сих пор
Итак, если вы не отстаете от этой серии, вам действительно нужно больше выходить. Основной упор на данный момент заключается в том, что я хорошо умею считать решения с n-ферзями и получаю удовольствие от решения их медленным способом как можно быстрее! Задача n-ферзей состоит в том, чтобы найти правильные решения для размещения n ферзей на шахматной доске n×n таким образом, чтобы ни один из них не мог атаковать друг друга. Меня интересует подсчет количества решений для различных значений n. Это объясняется в этом замечательном Блоге разработчиков Google с забавными (да, забавными!) комментариями и примерами на разных языках.
В этом блоге
Как всегда, я исследую экспоненциальные решения для подсчета решений с n-фермерами, чтобы показать, что временная сложность не является всем и завершает все: константы и порядки по-прежнему имеют значение, если ваши вычисления занимают много времени. .
- «Объединение» веб-воркеров;
- Представление платы только одним массивом.
Прыгайте, ребята: вода прекрасная и теплая
Например, "прыгнуть в пул потоков". Думаю, шутка не удалась, если мне придется ее объяснять
Первое, что вы заметите из приведенного ниже (если вы читали мой предыдущий блог), это то, что я научился правильно использовать Mocha и теперь предоставляю гораздо более точные сравнения.
Второе, что вы, вероятно, заметите (или первое, если это не важно), — это огромное увеличение производительности (более чем в 10 раз) по сравнению с моими предыдущими веб-воркерами до моих новых, привлекательных объединенных веб-воркеров в верхнем результате n=8, которое уменьшается по мере увеличения n и уменьшения количества повторений.
Использование пула потоков для развлечения и получения прибыли
В обеих строках (веб-воркеры и веб-воркеры в пуле) выполняется одно и то же решение с одинаковым количеством потоков, но один из них выполняется значительно быстрее: это связано с тем, что я создал пул потоков.
TL; DR пулов потоков заключается в том, что вместо создания нового потока всякий раз, когда он вам нужен, ваша программа создает в начале несколько потоков, которые читают работу из очереди, которую вы можете добавлять во время выполнения. На самом деле, мои веб-воркеры уже делают именно это (пингуют очередь для задания), поэтому единственная разница здесь в том, что мы не создаем новый поток каждый раз, когда пытаемся решить для n (например, чтобы решить n=8 100 раз, мой код без пула создал бы четыре потока 100 раз, но мой код из пула создал бы четыре потока один раз и каждый раз использовал их повторно).
Как правило, целью пулов потоков является снижение влияния многократного создания и уничтожения потоков, особенно для небольших задач (как мы делаем здесь). Создание нового потока может быть дорогостоящим, но хотя стоимость высока, она должна быть постоянной. Разница здесь непостоянна: при нахождении одного и того же решения 100 раз сэкономленное время не примерно в два раза больше, чем при нахождении одного и того же решения 50 раз. На самом деле вы заметите, что абсолютная разница (общее количество сэкономленного времени) намного выше (почти пять секунд, а не примерно 1,5), но пропорциональная разница намного ниже (75% от общего количества сэкономленного времени). затраченное время, а не ‹10%). Это улучшение заключается не только в снижении стоимости управления потоками: на самом деле, есть очень конкретная причина, по которой я хотел попробовать пул потоков с JavaScript, языком, который обычно запускается в среде с оптимизирующим JIT-компилятором.
Использование JIT для повышения производительности и привлечения помощника
Я думаю, что значительная доля этого увеличения скорости заключается в том, что JIT полностью прорабатывает функции, из которых он состоит. Эти функции короткие и (в основном) чистые, они почти полностью используют плотные массивы целых чисел, и они вызываются сотни тысяч раз с одним и тем же типом входных данных: они явные кандидаты на компиляцию и оптимизацию. Эти функции становятся очень и очень горячими по мере запуска решения и, следовательно, оптимизируются JIT; поэтому, когда решение завершается, оно, вероятно, работает намного быстрее, чем когда оно начинается. Если мы затем terminate() запустим этот поток и начнем новый, нам придется повторить эту работу, начиная медленно, компилируя и затем оптимизируя по мере продвижения. Пул потоков сохраняет эту оптимизацию во всех решениях, обеспечивая существенное увеличение скорости.
Вот почему мы получаем огромный прирост скорости при многократном использовании низких значений для n: когда n меньше, решение достигается быстрее. быстро, поэтому наши функции вызываются меньше раз, а доля оптимизированных вызовов ниже. Решение оптимизировано, но оптимизированная версия мало используется. С другой стороны, при более высоких значениях n каждое решение вызывает эти функции много-много раз, поэтому оптимизированный код активно используется, даже если мы уничтожаем поток и запускаем его снова. Следовательно, это увеличение производительности снижается по мере увеличения n и, конечно же, имеет значение только для повторяющихся решений: вы заметите, что разница с n=13 меньше, чем точность, которую мы могли разумно ожидать от нашего времени.
Одномерные шахматы
Лучше нулевых штрих-кодов
Еще одно серьезное улучшение, которое я сделал (с некоторыми советами от приятеля, Робин Ким), заключается в представлении доски просто как один массив, а не как массив массивов. Объяснение этому простое: я могу разместить только одну фигуру в каждой строке или столбце, и в каждой строке и столбце должна быть одна (и только одна) фигура. Следовательно, вся необходимая мне информация может быть представлена в виде массива из nчисел, где каждый индекс представляет столбец, а каждое число представляет строку, в которой находится ферзь этого столбца (или наоборот, не имеет особого значения). Мне плевать на любую другую информацию, так зачем мне ее включать?
Я приведу короткий пример. Правильное решение для n=4 с ферзем в [0,0] (вверху слева), [1,2], [2,1] и [3,3] (внизу справа) будет просто быть:
[0, 2, 1, 3]
Конфликты обнаруживаются всякий раз, когда повторяется одно и то же число или когда абсолютная разница между двумя числами равна абсолютной разнице их индексов (диагональный конфликт). Например, при [0, 2, 3, 1] два средних числа имеют абсолютную разность, равную единице, и отличаются на один индекс. Таким образом, на доске будет диагональный конфликт, поскольку они смещены на один столбец и одну строку.
Главный вопрос: это быстрее? Ответ: да, много.
Очевидно, особенностью этих чисел, привлекающих внимание заголовков, является чрезвычайная разница между временем, которое потребовалось для вычисления наивного решения для n=12 (около 14 минут) и использованием этого решения с одним массив (100 мс). Это титульное увеличение скорости в 8000 раз.
Ясно демонстрируя, что мои предыдущие тайминги, вероятно, были собраны нечестно (методы, с помощью которых они были собраны, не были полностью сопоставимы), это настолько близко, насколько мы можем приблизиться к сравнению яблок с яблоками, и это, безусловно, вызывает удивление. повышение.
Почему так быстро?
Использование одного массива существенно быстрее, чем использование двумерного массива, намного превосходя такое решение с пулом потоков и без него. Действительно, это даже быстрее, чем решение с гораздо меньшим количеством операций. Это решение не имеет распространения ограничений, особенности, благодаря которой время моего исходного (непараллельного) решения сократилось с 10–20 минут до примерно 10 секунд.
Как я предположил в своем самом первом блоге на эту тему:
Иногда самое умное решение не является ни лучшим, ни самым быстрым.
Также:
Не заморачивайтесь с медленными операциями.
Последнее — перефразирование, но возиться с кучей массивов даже с некоторыми хитрыми сокращениями было эмпирически медленнее, чем просто перебирать и пробовать все возможные решения с одним массивом.
Например, если бы мы помещали ферзя в столбец 1 и строку 3, мое предыдущее решение помечало это пространство как небезопасное, вычитая 1 (board[1][3]--), тогда как это решение задавало значение столбца 1 равным 3 (board[1] = 3).
Вывод: массивы действительно намного медленнее, чем примитивы.
По возможности избегайте многомерных массивов
Мы по-прежнему тестируем то же количество возможных макетов, что и предыдущее решение, и мы тестируем их, выполняя больше операций записи и значительно больше операций чтения на единицу площади платы. Однако эти операции чтения и записи относятся к примитивам (не менее чем к целым числам) в массиве, а не в другом массиве. Даже с учетом того, что последний явно демонстрирует JIT-оптимизацию и некоторые алгоритмические сокращения, он значительно уступает одномерному массиву для n=13.
В своем последнем блоге я описал три способа ускорить решение проблемы:
- выполнение меньшего количества операций;
- Выполнение более быстрых операций;
- Выполнение большего количества операций одновременно.
Еще раз (как и в моем первом блоге на эту тему) мы обнаружили, что выполнение большего количества более быстрых операций может привести нас к цели быстрее, чем меньшее количество более медленных. Я думал, что, перейдя на более сложное решение, которое просто записывает в дополнительные массивы, а не копирует их значения и создает новые, я сэкономил все дорогостоящие операции, которые мог, но все еще тратил время на индексацию во втором измерении. Не употребляйте наркотики.
Изюминка!
Это MapReduce
Ура! Мы любим MapReduce! Правильно? Самое лучшее в объединении всего в один массив — это то, что мы все ближе и ближе подходим к выражению n-ферзей как одной операции MapReduce.
Очевидно, это был мой эндшпиль с самого начала, но в следующий раз нас ждет очень забавный поворот (он включает в себя несколько компьютеров).
А пока, пожалуйста, наслаждайтесь (и саркастически комментируйте) одним решателем n-Queens, который широко использует map и reduce.
