Все больше и больше область применения языка программирования 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 накладок на вызов инструкций со-процессора особо не накладывается из-за возможности оптимизировать его внутри микроархитектуры, то в других процессорах со-процессор зачастую выполняет отдельную последовательность команд и управляется центральным. Таким образом, вызов его команды будет осуществлен по схеме:
Явно больше трех инструкций, которые мы пытаемся сократить. Отсюда логика работы на специфичной аппаратуре состоит в том, что опять же необходимо минимизировать точки соприкосновения скалярной и векторной арифметики, чтобы уменьшить количество пересылок данных и прочих накладок.
Например, описание ARM на википедии:
Усовершенствованный SIMD (NEON)
Расширение усовершенствованного SIMD, также называемое технологией NEON — это комбинированный 64- и 128-битный набор команд SIMD (single instruction multiple data), который обеспечивает стандартизованное ускорение для медиаприложений и приложений обработки сигнала. NEON может выполнять декодирование аудиоформата mp3 на частоте процессора в 10 МГц, и может работать с речевым кодеком GSM AMR (adaptive multi-rate) на частоте более 13МГц. Он обладает внушительным набором команд, отдельными регистровыми файлами, и независимой системой исполнения на аппаратном уровне. NEON поддерживает 8-, 16-, 32-, 64-битную информацию целого типа, одинарной точности и с плавающей запятой, и работает в операциях SIMD по обработке аудио и видео (графика и игры). В NEON SIMD поддерживает до 16 операций единовременно.
Одним из недостатков (или, скажем, особенностью) усовершенствованного SIMD является то, что сопроцессор выполняет команды усовершенствованного SIMD с достаточно значительной задержкой относительно кода основного процессора, задержка достигает двух десятков тактов и более (зависит от архитектуры и конкретных условий). По этой причине при попытке основного процессора воспользоваться результатами вычисления сопроцессора исполнение будет заморожено на значительное время.
Вообще, мы говорим тут об 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 (а с ними и векторов такой же размерности. Математических векторов, а не вычислительлных) 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 как таковых.
К сожалению, не доступен сервер mySQL