Векторные вычисления в JS, есть ли смысл, когда и как можно использовать SIMD в браузере

Все больше и больше область применения языка программирования javascript отходит от движения кнопочками в браузере да перекраски фона в сторону сложных и объемных веб-приложений. Уже во всю по миру шагает технология WebGL, позволяющая отображать трехмерные сцены в браузере прямо на языке js, а вместе с ней и усложняются задачи.

Производительность пользовательских машин продолжает расти, а вместе с ней и язык обзаводится новыми выразительными средствами, позволяющими ускорять вычисления. И пока WebAssembly где-то там в далеком и светлом будущем, asm.js застрял в болоте и свернул с пути, в ближайшее время изначально как часть es2015, ныне как отдельный стандарт выходит поддержка векторных операций в JS.

Все, кому интересно, что такое SIMD и векторные исчисления, как ими пользоваться в js, а так же что дает их использование — прошу под кат.

Отступление от автора: у вас не дежавю, эта статья действительно является перезаливом предыдущей. К сожалению, тогда я не приложил достаточно усилий, чтобы получить качественную статью, а тесты не годились ни для чего, как следствие — я получил в корне неверные выводы, на что справедливо получил критику. "Хабр торт и всякое потребье тут не прокатит" обрадовался я, прикинул, что моя статья пока одна из немногих, которые всплывают по запросы "SIMD JS" и было бы неправильно распространять неверную информацию, да еще и низкого качества. В данной статье пытаюсь исправить, ту беспощадно скрыл и удалил как страшный сон и поучительный урок об соотношении времени, затраченного на статью, к её качеству.

Теория

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

int arr[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
const c = 5;
for (int i = 0; i < 16; i++) {
  arr[i] = arr[i] + c;
}

Догадливые люди могут попытаться немного оптимизировать этот пример, написав что-то вроде:

int arr[16] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
const c = 5;
for (int i = 0; i < 16; i += 4) {
  arr[i] = arr[i] + c;
  arr[i + 1] = arr[i + 1] + c;
  arr[i + 2] = arr[i + 2] + c
  arr[i + 3] = arr[i + 3] + c;
}

Оптимизация сомнительная, но, на самом деле, сработает. Причиной этого является не то, что мы гораздо реже делаем операцию i = i + 1; (ведь она все равно происходит при взятии индекса), а то, что процессор в этом случае может загружать и выполнять операции с большим захлестыванием друг на друга в конвеере, покуда операции не зависят друг от друга, что позволяет ему производить внутренние операции, вплоть до выполнения этих операций одновременно и пакетной загрузке следующей части массива.

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

Примерно так подумали много лет назад (в 70-х годах) где-то в недрах Texas Instruments и CDC, сделав первые векторные супер-компьютеры. Однако до них некий Майкл Флинн предложил свою таксономию (классификацию) компьютеров, одной из которых были SIMD. К сожалению, на этом нить истории теряется, но мы тут не для этого собрались.

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

Графически классическая архитектура выглядит следующим образом:

Нам нужно сложить 4 пары чисел, поэтому мы вынуждены 4 раза вызвать инструкцию add в процессоре.

Векторная операция же выглядит следующим образом:

Когда нам нужно сложить 4 пары чисел, мы просто вызываем одну инструкцию, которая складывает их за один такт.

Небольшая ремарка по поводу "векторная операция" и SIMD-операция. Дело в том, что SIMD — более общее понятие, подразумевающее под собой выполнение в один и тот же момент времени одной или нескольких одинаковых операций над разными данными. В CUDA в каждый момент времени нити выполняют одну и ту же операцию над разными данными, но этих операций выполняется столько, сколько доступно потоков в видеокарте. Векторная арифметика подразумевает то, что выполняется именно одна операция, причем, фактически, она выполняется просто над двумя расширенными данными, составляющими из себя упорядоченно лежащие несколько чисел в одной ячейке. Таким образом, векторные операции входят как подмножество в SIMD-операции, однако в ES2017 говорится именно о векторной арифметике, не знаю, почему они решили так обобщить, далее мы будем считать эти два понятия одним и тем же в рамках этой статьи.

Так что, получается, мы можем увеличить производительность своих js приложений в 4 раза? (Протяженно)Нууу не совсем. Но сперва взглянем, как это делается на C (gcc)

void main() {
 int a[4] = { 1, 3, 5, 7 };
 int b = 3;
 int c[4];

 c[0] = a[0] + b;
 c[1] = a[1] + b;
 c[2] = a[2] + b;
 c[3] = a[3] + b;
}

#include <xmmintrin.h>

extern void printv(__m128 m);

int main()
{
    __m128 m = _mm_set_ps(-4, -3, -2, -1);
    __m128 one = _mm_set1_ps(1.0f);

    printv(_mm_add_ps(m, one)); // Multiply by one (nop)

    return 0;
}

main:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        subq    $64, %rsp
        movq    %fs:40, %rax
        movq    %rax, -8(%rbp)
        xorl    %eax, %eax
        movl    $1, -48(%rbp)
        movl    $3, -44(%rbp)
        movl    $5, -40(%rbp)
        movl    $7, -36(%rbp)
        movl    $3, -52(%rbp)
        movl    -48(%rbp), %edx
        movl    -52(%rbp), %eax
        addl    %edx, %eax
        movl    %eax, -32(%rbp)
        movl    -44(%rbp), %edx
        movl    -52(%rbp), %eax
        addl    %edx, %eax
        movl    %eax, -28(%rbp)
        movl    -40(%rbp), %edx
        movl    -52(%rbp), %eax
        addl    %edx, %eax
        movl    %eax, -24(%rbp)
        movl    -36(%rbp), %edx
        movl    -52(%rbp), %eax
        addl    %edx, %eax
        movl    %eax, -20(%rbp)
        nop
        movq    -8(%rbp), %rax
        xorq    %fs:40, %rax
        je      .L2
        call    __stack_chk_fail

       movss    xmm0, DWORD PTR __real@c0800000
    movss   xmm2, DWORD PTR __real@c0400000
    movss   xmm3, DWORD PTR __real@c0000000
    movss   xmm1, DWORD PTR __real@bf800000
    unpcklps xmm3, xmm0
    xorps   xmm0, xmm0
    unpcklps xmm1, xmm2
    unpcklps xmm1, xmm3
    movaps  XMMWORD PTR tv129[esp+32], xmm0
    movaps  XMMWORD PTR _m$[esp+32], xmm1
    addps   xmm0, xmm1

module adds(
   input wire[0:31] a,
   input wire[0:31] b,
   input wire[0] size, // 8 bit or 16 bit
   output reg[0:31] c,

  input wire clk
);

always @ (posedge clk)
begin
   case (size)
      1'b0: begin
         c[0:7] <= a[0:7] + b[0:7];
         c[8:15] <= a[8:15] + b[8:15];
         c[16:23] <= a[16:23] + b[16:23];
         c[24:31] <= a[24:31] + b[24:31];
       end
      1'b1: begin
         c[0:15] <= a[0:15] + b[0:15];
         c[16:31] <= a[16:31] + b[16:31];
      end
end

endmodule

Практика

Итак, векторные операции скоро появятся в js. Насколько скоро? В данный момент их поддерживает firefox nightly, edge с флагом "экспериментальные возможности" и chrome с флагом при запуске --js-flags="--harmony-simd", т.е. хоть в каком-то виде, но все браузеры. Помимо этого есть полифилл ^[3], так что можно использовать уже прямо сейчас.

Небольшой пример как использовать SIMD в js-коде:

const someValue = SIMD.Float32x4(1,0,0,0);
const otherValue = SIMD.Float32x4(0,1,0,0);

const summ = SIMD.Float32x4.add(someValue, otherValue);

Полный список доступных функций смотрите на MDN ^[4]. Хочу обратить внимание, что SIMD.Float32x4 не является конструктором и запись new SIMD.Float32x4(0, 0, 0, 0); не является валидной.

Не буду расписывать все возможности по использованию, их не очень много, в целом — арифметика да загрузка с выгрузкой данных, еще немного примеров все на том же MDN ^[5], сразу перейду к примерам.

Обозначения, введенные мной для простоты примеров, такие:

const sload = SIMD.Float32x4.load;
const sadd = SIMD.Float32x4.add;
const smul = SIMD.Float32x4.mul;
const ssqrt = SIMD.Float32x4.sqrt;
const sstore = SIMD.Float32x4.store;

Свертка

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

Скалярный вариант:

Векторный:

Тут и далее: по вертикальной оси данные, по горизонтальной — время. Оранжевый блок — данные, над которыми происходит операция.

В коде это пример сверху в явном виде, на js примерно так (часть из алгоритма рассчета дисперсии):

const arr = new Float32Array(someBuffer);

for (let i = 0; i < arr.length; i += 4) { // пример подразумевает, что размер массива кратен 4, будьте осторожны с этим!
   sstore(arr, i, smul(
       sadd(
           sload(arr, i),
           expected // мат. ожидание
       ),
      sadd(
          sload(arr, i),
          expected // мат. ожидание
      )
   ));
}

Сумма элементов массива

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

Расскажу многонитьевой алгоритм, который не сложно адаптировать под векторный: сперва каждый четный (включая нулевой) суммируется с нечетным, следующим за ним. Затем нулевой (в котором теперь лежит сумма a[0] + a[1]) суммируется с вторым четным (a[2], который равен a[2] + a[3]) и так далее. На следующем шаге суммируются 0, 4, 8, ..., затем 0, 8, 16 и так далее по степеням двойки, пока массив не закончится.

В случае с векторными операциями можно суммировать первые 4 значения со вторыми 4-мя значениями, в остальном — все так же, т.е.

a[0-3] = a[0-3] + a[4-7];

a[8-11] = a[8-11] + a[12-15];

Графически:

Скалярный вариант

Векторный:

Прирост скорости ожидается достаточно большой. Мой вариант на js:

    const length = a.length;
    let i = 0;
    let k = 4;
    while (k < size) {
        for (i = 0; i < size; i += k * 2) {
            SIMD.Float32x4.store(a, i, 
                SIMD.Float32x4.add(
                    SIMD.Float32x4.load(a, i),
                    SIMD.Float32x4.load(a, i + k)
                ));
        }
        k = k << 1;
    }

Данный пример имеет ограничение: размер массива должен быть одновременно степенью двойки и кратен 4. В принципе, это не так сложно исправить, но оставим на домашнее задание.

Матричное перемножение 4х4

Есть смысл полагать, что матричные операции для квадратных матриц размера 4 (а с ними и векторов такой же размерности. Математических векторов, а не вычислительлных) SIMD дадут заметный прирост. Что такое перемножение и как выглядит классический вариант, а так же графически — я не покажу (графически выглядит ненаглядно, классический вариант — использование математического определения перемножения матриц в лоб, его можно посмотреть на википедии), векторный код на js у меня вышел такой:

let j = 0;
    let row1, row2, row3, row4;
    let brod1, brod2, brod3, brod4, row;
    for (let i = 0; i < 10000; i++) {
        c = new Float32Array(32);
                row1 = SIMD.Float32x4.load(a, 0);
        row2 = SIMD.Float32x4.load(a, 4);
        row3 = SIMD.Float32x4.load(a, 8);
        row4 = SIMD.Float32x4.load(a, 12);
        for (j = 0; j < 4; j++) {
            d = b[4 * j + 0];
            brod1 = SIMD.Float32x4(d, d, d, d); // у нас нет аналога команды _mm_set1_ps
            d = b[4 * j + 1];
            brod2 = SIMD.Float32x4(d, d, d, d); // у нас нет аналога команды _mm_set1_ps
            d = b[4 * j + 2];
            brod3 = SIMD.Float32x4(d, d, d, d); // у нас нет аналога команды _mm_set1_ps
            d = b[4 * j + 3];
            brod4 = SIMD.Float32x4(d, d, d, d); // у нас нет аналога команды _mm_set1_ps
            row = SIMD.Float32x4.add(
                SIMD.Float32x4.add(
                    SIMD.Float32x4.mul(brod1, row1),
                    SIMD.Float32x4.mul(brod2, row2)
                ),
                SIMD.Float32x4.add(
                    SIMD.Float32x4.mul(brod3, row4),
                    SIMD.Float32x4.mul(brod3, row4)
                )
            );
            SIMD.Float32x4.store(c, j * 4, row);
        }
    }

Сложновато. Замечу, что после просмотра кода, в который компилируется c-шный вариант, не сильно расстроился недостатком _mm_set1_ps, покуда внутри оно компилируется в 4 отдельных команды загрузки, так что потеря не велика.

Оператор Собеля

Википедия ^[6]. Является примером одной из типовых задач, которые должны хорошо ложиться на SIMD, покуда является внутри сверткой над изображением. Картинок, кода и алгоритма не будет, однако замечу, что в тесте я несколько смухлевал. Дело в том, что оператор Собеля оптимизируется гораздо больше и сильнее при использовании SIMD, однако сначала нужно преобразовать данные к другому виду, да и матан там не простой. Однако даже простое применение дало преимущество. Что касается честного преобразования — хоть jpeg и является дискретно-косинусным преобразованием, внутри он не так далеко ушел от свертки оператором Собеля, а именно за счет SSE (и старших) расширений процессора мы можем смотреть видео в высоком качестве на процессоре (и накладывать гораздо более сложные эффекты используя видеокарту), так что данный алгоритм является прямым назначением SIMD-инструкций в процессоре, в том числе, в js.

Будущее здесь? Производительность

Тест руками можно запустить тут ^[7]. Не забудьте убедиться, что ваш браузер поддерживает SIMD. Исходный код ^[8], не забываем о кнопочке fork, если есть идеи, как улучшить и оптимизировать.

К тестам подошел серьезно: каждый тест группируется в 4 запуска, один из которых "холостой", предназначенный на прогрев кеша и чтобы браузер смог скомпилировать то, что он считает нужным, в бинарный код. Три учитываются при рассчете. Затем каждая из этих групп запускается по n раз, порядок выбирается случайным образом, затем считается математическое ожидание и дисперсия (черная полоска на каждом из графиков).

У себя я запускал 500 раз каждую из групп, что позволило исключить такие факторы как сборку мусора, переключение поток, задумавшегося касперского и прочие обновления windows 10, и отражает близкие к действительности числа. К сожалению, на js получить более точные выводы невозможно по той причине, что мы никак не можем заставить планировщик задач системы не переключать задачи и прочие вещи, а получить количество тиков, отведенных исключительно под js, так же нет инструментов (есть в виде профайлера, но он из без того слишком адский. Перепроверить в нем — ссылка на тесты вверху есть, можете проинспектировать).

Результаты на моем компьютере (core i5 6400m, firefox nightly 51.0a):

Выводы

Как видно из импровизированного сравнения на производительность, при хоть чуть более-менее грамотном использовании технологии она дает преимущество в 20-40%. В специфичных задачах можно выжать и гораздо большую производительность, как следствие — технология стоит того, чтобы начинать задумываться об её использовании. К сожалению, векторное программирование достаточно сложное, специалистов по нему мало, тем более в мире js, поэтому все и каждый не ринется. Однако если ваш проект включает в себя сложные вычисления — чувствительный прирост скорости лишним не будет и может сэкономить много ресурсов и времени на решение других задач.

Сейчас доступен полифилл и нет причин думать, что API для работы с SIMD инструкциями в js поменяется, покуда стандарт завершен на 90%, а оставшиеся 10%, по секрету, это размышления о том, как бы переопределить операнды типа "+" и "*". В js перегрузки операндов нет и не вижу причин тащить их сюда, так что, скорее всего, в прямом виде войдет в стандарт, который после принятия в ближайшем же релизе будет доступен в firefox и edge, google в Chrome с ним не спешат по какой-то причине, таким образом, если вы сейчас (на момент написания статьи, в августе 2016 года) начинаете свое новое приложение на JS, в котором будет множество вычислений, стоит сразу иметь эту библиотеку ввиду и писать код если не сразу на ней (с полифиллом), то, по крайней мере, с оглядкой на вероятную миграцию и предусмотреть возможность переписывания, чтобы в будущем не потерять много времени на это.

Стоит ли игра свеч или мои мысли в свободной форме

Конечно рост производительности наблюдается, однако мне не очень понятен выбор технологии и реализация стандарта. Она чуть более, чем полностью оптимизирована только под x86, на любой другой архитектуре и размер вектора может отличаться, и набор инструкций (очень распространена инструкция вида a + b * c, особенно в всевозможных ДСП). Понятное дело, что какой-нибудь 66AK2x от TI (цифровой сигнальный процессор) никто в здравом уме не будет программировать на javascript, однако в супер-высокоуровневом платформонезависимом языке странно видеть платформозависимые инструкции. (Об этом говорил Akon32 ^[9],

SIMD-инструкции? Зачем? JS как бы считается языком высокого уровня, независимым от железа. А тут прямо в исходном тексте программы предполагается, что именно 4-компонентные вектора есть в инструкциях процессора. А если только 3, или 5, или 8 компонентов? Неизвестно, на чём код будет запускаться.
Имхо, более дальновидными (но не простыми) решениями выглядят автоматическая векторизация в JIT (или прямо в суперскалярном процессоре), или OpenCL/CUDA-подобное API.

Не знал, что комментарии при переносе в черновики так же трутся).

Мое лично мнение: гораздо дальновиднее, при этом позволяющее компилятору делать тоже самое, что и в данном стандарте, является MPi (ну или OpenMP). Как бы, к примеру, это выглядело:

function summ(a, b, N) {
  const c = Float32Array(N);
  let i;
  /// #pragma omp parallel for shared(a, b, c) private(i)
  for (i = 0; i < N; i++)
     c[i] = a[i] + b[i];
  }
}

Собственно, плагиат с готового стандарта OpenMP ^[10]. Это позволит движку самому выбрать наиболее оптимальный вариант векторизации, оперировать не только 128-ми битными векторами, да и сделает код платформонезависимым. Можно ли сделать это автоматически во время JIT? Не всегда удается, а возможность указать вручную была бы удобной.

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

Автор: kahi4

Источник ^[11]