Все больше и больше область применения языка программирования 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;
}(Примеры взяты с ресурса liranuna.com)
Первый вариант станет в asm чем-то типа:
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
На что тут нужно обратить внимание? На то, что операция "сложить" (инструкция addps) действительно одна, когда в первом примере их 4, при этом в первом примере так же много сложебных пересылок данных туда-сюда. Действительно, в сухом остатке инструкций стало меньше. Впрочем, в x86 время выполнения (как и в остальных CISC), не ограничено, в теории можно в микрокод даже хоть модель всего мира запихнуть. Считаться он будет бесконечно, но инструкция то одна! Однако, что гораздо важнее для нас именно сейчас, это регистры xmm0-7 (0-15 в 64-разрядной архитектуре. Однако мы сейчас не на схемотехнике и даже не про ассемблер говорим, такие подробности нам не важны). Это специальные регистры из расширения SSE (англ. Streaming SIMD Extensions, потоковое SIMD-расширение процессора) размерностью 128 бит, каждый из которых может содержать 4 значения с плавающей точкой одинарной точности (32-х разрядные float), ну а так же всевозможные комбинации из знаковых и беззнаковых целых чисел разной разрядностью. Именно над ними и происходят все SIMD-инструкции.
Это достаточно важно, покуда любая операция подразумевает, что вы сначала каким-либо образом данные туда загрузите. Тут и кроется главное ограничение этой технологии — загрузка этих данных обходится не очень дешево, поэтому смешанная арифметика (векторные и скалярные операции вперемешку) дадут только большие издержки на перегоне данных туда-сюда, отсюда все алгоритмы для векторных исчислений оптимизируются таким образом, чтобы минимизировать точки соприкосновения, что не всегда просто.
Однако подключить сюда потоковую обработку — производительность еще больше вырастает за счет того, что DDR позволяют получить от 2-х (для ddr3 это аж 8) слов за одно обращение к памяти. Безусловно, процессор и в скалярных вычислениях попытается прибегать к ним, однако если ему сказать об этом явно, ему проще будет понять что и как загружать.
Внутри каждая из инструкций выглядит примерно так:
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
Реальный пример не приведу по двум причинам: во-первых, они все очень объемные, а к делу не относятся, во-вторых — никто из крупных компаний, особенно intel, не особо разогнались им делиться, а знакомых схемотехников оттуда у меня нет (это тонкий намек, к слову). Но это и не важно. Важно другое — подобные строчки кода (точнее, описания аппаратуры) есть где-то в недрах ядра x86 процессора intel, доступного нам через микроархитектуру в виде расширенного набора инструкций sse. Вот только в других архитектурах (да, вроде как, и внутри x86, где-то под микроархитектурой, там, где честный RISC) он является частью со-процессора по арифметике с плавающей точкой. Если же для x86 накладок на вызов инструкций со-процессора особо не накладывается из-за возможности оптимизировать его внутри микроархитектуры, то в других процессорах со-процессор зачастую выполняет отдельную последовательность команд и управляется центральным. Таким образом, вызов его команды будет осуществлен по схеме:
- инициировать параметры сопроцессора
- передать значения, с которыми ему необходимо работать
- установить его внутренний CP (счетчик инструкций) на адрес программы, написанной для него
- запустить его
- дождаться пока он завершит операцию (в это время можно заняться чем-то другим, не менее полезным)
- получить результаты
- остановить сопроцессор
Явно больше трех инструкций, которые мы пытаемся сократить. Отсюда логика работы на специфичной аппаратуре состоит в том, что опять же необходимо минимизировать точки соприкосновения скалярной и векторной арифметики, чтобы уменьшить количество пересылок данных и прочих накладок.
Вообще, мы говорим тут об SIMD в js. Так какого черта? ARM и x86 — это все, что у нас есть, когда java-script-разработчиков волновало то, на какой архитектуре будет выполняться их код? Максимум — какой даже не браузер, а движок.
А вот черта с два. Во-первых, а с какого перепуга вообще потянули SIMD в JS? Во-вторых, спорное решение, но их сейчас как грибов. А раз инструмент есть, то понимать как им пользоваться эффективно все таки нужно.
Практика
Итак, векторные операции скоро появятся в js. Насколько скоро? В данный момент их поддерживает firefox nightly, edge с флагом "экспериментальные возможности" и chrome с флагом при запуске --js-flags="--harmony-simd", т.е. хоть в каком-то виде, но все браузеры. Помимо этого есть полифилл, так что можно использовать уже прямо сейчас.
Небольшой пример как использовать 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. Хочу обратить внимание, что SIMD.Float32x4 не является конструктором и запись new SIMD.Float32x4(0, 0, 0, 0); не является валидной.
Не буду расписывать все возможности по использованию, их не очень много, в целом — арифметика да загрузка с выгрузкой данных, еще немного примеров все на том же MDN, сразу перейду к примерам.
Обозначения, введенные мной для простоты примеров, такие:
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 отдельных команды загрузки, так что потеря не велика.
Оператор Собеля
Википедия. Является примером одной из типовых задач, которые должны хорошо ложиться на SIMD, покуда является внутри сверткой над изображением. Картинок, кода и алгоритма не будет, однако замечу, что в тесте я несколько смухлевал. Дело в том, что оператор Собеля оптимизируется гораздо больше и сильнее при использовании SIMD, однако сначала нужно преобразовать данные к другому виду, да и матан там не простой. Однако даже простое применение дало преимущество. Что касается честного преобразования — хоть jpeg и является дискретно-косинусным преобразованием, внутри он не так далеко ушел от свертки оператором Собеля, а именно за счет SSE (и старших) расширений процессора мы можем смотреть видео в высоком качестве на процессоре (и накладывать гораздо более сложные эффекты используя видеокарту), так что данный алгоритм является прямым назначением SIMD-инструкций в процессоре, в том числе, в js.
Будущее здесь? Производительность
Тест руками можно запустить тут. Не забудьте убедиться, что ваш браузер поддерживает SIMD. Исходный код, не забываем о кнопочке 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,
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. Это позволит движку самому выбрать наиболее оптимальный вариант векторизации, оперировать не только 128-ми битными векторами, да и сделает код платформонезависимым. Можно ли сделать это автоматически во время JIT? Не всегда удается, а возможность указать вручную была бы удобной.
P.S. В прошлой статье вместо технологии все начали обсуждать математику и сложные вычисления на javascript. Подходящий ли язык для этого или нет, хорошо это или плохо, однако все больше и больше задач на js требуют больших математических вычислений, а технология, которая позволяет их ускорить, играет только на руку, нежели вредит. Прошу воздержаться от обсуждения сложных вычислений на js как таковых.
Автор: kahi4
