Rivertrail: параллелизм в JavaScript

Использование возможностей параллелизма в настоящее время стало уже обычной практикой в программировании. Однако все языки можно разделить на два типа: те, в которых параллельность применяется вовсю и активно (например, С) и те, которые не вкусили еще в полной мере радостей многопоточности. К последним, в частности, относится JavaScript. Чтобы восполнить этот досадный пробел и пополнить копилку прогрессивного опыта, предлагаем вашему вниманию перевод сообщения из блога Ника Матсакиса, программиста Mozilla Foundation, в котором он делится первыми личными впечатлениями от использования Rivertrail — инструмента параллелизации в JavaScript, созданным Intel.

Недавно я начал использовать Rivertrail — продукт, предлагаемый Intel в качестве инструмента для распараллеливания по данным в JS. Проект пока оставляет только положительные впечатления. Начальная версия будет завязана на интеловских спецификациях, но я надеюсь, что затем его получится сочетать с другими проектами, создаваемыми в рамках PJs.

Rivertrail для чайников

Вот небольшое интро для тех, кто не слышал об этом продукте раньше: Rivertrail — это спецификация, позволяющая обрабатывать массив параллельно. Основа спецификации — добавление класса ParallelArray. Данные массивы имеют ряд ключевых отличий от массивов JS.

• они неизменны
• не имеют промежутков
• они могут быть многомерны, но многомерны «правильно» (к примеру, в двухмерной матрице число столбцов будет равно числу рядов).

Параллельные массивы поддерживают достаточно большое количество операций высокого уровня, таких как ()map и ()reduce, и не только. Полный список вы сможете найти в спецификации к Rivertrail. Эти методы принимают функции в качестве аргумента, и работают примерно так же, как соответствующие ф-и в обычных массивах JS. Кроме пары важных отличий:

• во-первых, функции, которые берутся в качестве аргумента, всегда должны быть «чистыми» (pure), об этом немного ниже;
• во-вторых, там, где это возможно, движок JS будет стараться выполнять эти функции параллельно.

Чистые функции

Это обычные JS-функции, которые не изменяют разделяемое состояние (shared state). Это не значит, что функции вообще не могут что-то изменять — локальные переменные и объекты, аллоцированные самой функцией, изменяться могут.

К примеру, функция, вычисляющая множество Мандельброта, является чистой:

  function mandelbrot(x, y) {
    var Cr = (x - 256) / scale + 0.407476;
    var Ci = (y - 256) / scale + 0.234204;
    var I = 0, R = 0, I2 = 0, R2 = 0;
    var n = 0;
    while ((R2+I2 < 2.0) && (n < 512)) {
        I = (R+R)*I+Ci;
        R = R2-I2+Cr;
        R2 = R*R;
        I2 = I*I;
        n++;
    }
    return n;
}

mandelbrot() изменяет только локальные переменные. А вот sums() в этом плане поинтереснее — функция вычисляет частичные суммы входного массива X и сохраняет их в выходной массив sums:

function sums(x) {
    var sums = [], sum = 0;
    for (var i = 0; i < x.length; i++) {
        sum += x[i];
        sums[i] = sum;
    }
    return sums;
}

На что стоит обратить внимание — данная функция присваивает значения массиву sums, меняя объект кучи, а не только локальные переменные. Но, поскольку данный объект выделен в самой функции, это все еще чистая функция. На самом деле, конкретный пример не будет исполняться параллельно из-за ряда ограничений, имеющихся в текущей версии Rivertrail, но, надеюсь, скоро это изменится.

А вот пример функции, которая не будет считаться чистой, так как она изменяет X, а X не аллоцирован локально.

x = [1, 2, 3];
function impure() {
    x[0] += 1;
}

Параллельное выполнение

Главное волшебство ParallelArray в том, что по мере возможности, он будет выполнять функции параллельно. При этом параллельность или последовательность выполнения будет зависеть от самой реализации JS. То, что предназначаемые для параллельного выполнения функции — чистые, значит, что концептуально они всегда могут выполняться безопасно. Но это не значит, что сам движок JS будет в состоянии их выполнить.

Движки JS выполняют много скрытой оптимизации, и не все из этих оптимизаций — поточно-безопасные.

Пока что список выполняемых параллельно операций довольно консервативен, но со временем он будет расширяться и, в идеале, разрастется так, что любые чистые функции можно будет выполнять параллельно.

Вам приходится делать много вещей, чтобы убедиться, что ваш код работает быстро. Чтобы обеспечить параллельное выполнение кода, придется делать те же самые вещи. Вот почему.

Пример

a.b = c

Если компилятор JIT проанализирует тип a и определит, к примеру, что свойство b всегда хранится с определенным смещением, то он сможет оптимизировать код в одну ассемблерную инструкцию. Но если компилятору не удастся проанализировать код, в худшем случае будет вызван интерпретатор, работающий над различными хеш-таблицами, деревьями прототипирования, и прочее. Теперь нужно понять, является ли a.b = c поточно-безопасным. Тут все просто – инструкция сохранения безопасна в предположении, что к памяти, в которую сохраняют, имеет доступ лишь один поток. Что и является гарантирует «чистая» функции. Сложнее будет решить это, когда интерпретатор будет затрагивать сотни, если не тысячи, строк кода.

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

Модели параллельного выполнения

Модель использования Rivertrail Mozill`ой немного отличается от разработанного Intel прототипа. Это плагин, компилирующий JS в OpenCL. Нативная же реализация позволяет выполнить код 4 разными способами, но на данный момент доступны только 2 первых.

• Последовательно. Резервный режим. Эквивалентен записи для циклов или использования высокоуровневых методов Array. Данный режим работает в сборках Nightly и, возможно, в Aurora. Попробуйте ввести в консоли var x = new ParallelArray([1, 2, 3]
• Режим Multicore. В этом режиме и работаем по умолчанию. Многоядерный режим распределяет по одному потоку на каждое ядро в системе. Каждый рабочий поток будет работать с выполняемой в параллель копией функции. Более функциональную версию данного режима ожидаем в течение ближайшей пары месяцев.
• Векторизированный режим. Похож на многоядерный, но есть отличия — каждый рабочий поток использует SSE-инструкции для обработки более одного элемента массива одновременно. Это пока в планах после Multicore.
• GPU. Это просто вариант исполнения режима векторизации, но в нем векторизация кода будет работать не на CPU, а на GPU. Технических различий тут много. С одной стороны, векторизацию будет аппаратно обрабатывать GPU, и компилятору не придется задействовать специальные инструкции. С другой стороны, на некоторых платформах придется много поработать над копированием памяти между CPU и GPU.

Из описанных режимов наиболее общим можно считать Последовательный — его можно применять к любой чистой функции. Многоядерный тоже достаточно универсален и может быть использован при работе с чистыми функциями, ограничивающими себя поддерживаемыми в данный момент операциями.

Режимы векторизации и GPU будут более ограниченными. Векторизацию будет иметь смысл использовать только для функций, в которых код можно преобразовать в инструкции SSE без упаковки и распаковки, GPU же наложит определенные ограничения на перемещение данных, и так далее.

Пара слов о производительности

Тут будет немного данных, так как

• я пока не закончил профилирование
• пока нет хороших подробных тестов
• оптимизация вычислений также не проведена

По крайней мере, вот результаты работы при вычислении множества Мандельброта на моем четырехъядерном ноутбуке с Hypertheading.

seq — время выполнения в последовательном режиме
par — время выполнения этого же числа потоков в параллельном режиме
ratio — отношение времени последовательного режима к времени параллельного (seq/par). Чем больше — тем лучше.

Очевидно, что эти значения можно улучшить. Было бы здорово, если бы производительность увеличивалась линейно. И я не думаю, что этого сложно достичь, я оптимистичен.

Кстати, данные по последовательному режиму здесь взяты, используя выполнение JS на основе массивов, а не на последовательном режиме ParallelArray, и код работал некоторое время, дабы убедиться, что использовался JIT. Хотя инструментальной проверки использования JIT не делалось (именно поэтому я и говорю, что «надлежащего профилирования не делалось»

О PJs

Некоторые из вас могли слышать о предыдущих идеях выполнения JavaScript параллельно, они назывались «PJs» (Parallel Java Script). Пока это все в планах, но, быть может, появится возможность использовать некоторые механизмы Rivertrail в PJs API. И пока не видно никаких причин, которые могли бы стать помехой в этом деле. Главное сейчас — расширить набор ф-ий, поддерживаемых многоядерным режимом.

Резюмируя

Совмещение данных (параллелизм) приходит к JS (как минимум, в Firefox). Реализуемые API смогут поставить JS в авангард языков программирования с использованием параллелизма. Это все очень просто использовать и гарантирует переводимое в последовательную форму исполнение. PJs также гарантирует детерминированное исполнение, но Rivertrail этого не делает из за наличия функций типа ()reduce. Немногие языки могут этим похвастаться.

Благодарю vikky13 за помощь в переводе и редактировании.

Автор: Sterhel