WebAssembly & Сложности SIMD-арифметики

[Alikberov]

Кaк некогда работающий непосредственно с низким уровнем (Си/Ассемблер) и знакомый с технологией SIMD, попытался я средствами JavaScript реализовать некоторые из инструкций прямо в браузере, начав разрабатывать некоторую оболочку (ссылка). Однако, споткнулся на вопросе производительности.

Если при открытии ссылки подождать несколько секунд и кликнуть пунтк меню «View» и отметить галочкой опцию «Pseudo Code», можно увидеть некий сгенерированный листинг, который будет завёрнут в «new Function("_", Pseudo_Code)»…
Мною ожидалось, что если вместо многократных циклов с «switch-case» и эмуляцией исполнения инструкций процессора всё перенести внутрь «new Function», то браузер сообразит, что нужно произвести хотя бы минимальную компиляцию кода…

Однако, если мышкой порисовать несколько линий на Canvas'е окошка «Graphics Display», то можно заметить жуткое подвисание браузера на момент исполнения той «Функции» с текстом из окошка «Pseudo Code»…
Очевидно, нужно всё оптимизировать и переносить на уровень WebAssembly!

То есть, как можно видеть из «Pseudo Code», выбросить все getter'ы и setter'ы в первую очередь!
А без них всё усложняется на порядки, так как если глянуть на реализацию одной операции сложения…

BigInt.prototype.PADD = function(n, mask) { // Packed Add
	return (((this & mask) + (n & mask))) ^ ((this ^ n) & ~mask);
}

…котор ая проще операции вычитания…

BigInt.prototype.PSUB = function(n, mask) { // Packed Subtract
	return (((this | ~mask) - (n & mask)) & mask) | ((this - n) & ~mask);
}

…стан овится очевиднее факт, что без прототипов и прочего сахара то самый «Pseudo Code» не будет уже таким изящным, как на данном этапе реализации оболочки…

Ясно, что WebAssembly не создавался для эстетики и служит своеобразным промежутком между JavaScript и псевдо-кодом, годным для трансляции на язык ассемблера конкретного процессора.

Но меня в первую очередь интересует вопрос: Неужели так всё плохо с производительностью getter'ов и setter'ов?
Нельзя ли частично ускорить код, поместив «"use asm"» внутрь многочисленных getter'ов и setter'ов?
Например, вот так:

BigInt.prototype.PADD = function(n, mask) {
	var _this = BigInt(this);
	'use asm';
	_this = _this|0n;
	n = n|0n;
	mask = mask|0n;
	return ((((_this & mask) + (n & mask))) ^ ((_this ^ n) & ~mask))|0n;
}

BigInt.prototype.PSUB = function(n, mask) {
	var _this = BigInt(this);
	'use asm';
	_this = _this|0n;
	n = n|0n;
	mask = mask|0n;
	return (((_this | ~mask) - (n & mask)) & mask) | ((_this - n) & ~mask)|0n;
}

Или нужно идти напролом без всякого сахара?
Может есть иные способы форсировать оптимизатор браузера?

[Aetae]

1. У меня на машине ничего не тормозит.
2. Это не геттеры - это просто расширения прототипа. (добавления методов в интерфейс родтельского класса, если вам так привычнее) Геттры - это неявно вычисляемые свойства. Вызов таких методов практически никак не отличается от вызова обычных функций, накладные расходы на поиск по цепочке наследования вверх пренебрежимо малы.
3. BigInt - может быть медленным, т.к. это не int64 или там int128, а длинная арифметика условно бесконечной длины. Для производительности стоит использовать ArrayBuffer и производные.
4. Скорее всего проблемы с производительностью и вовсе не в вызовах или математике, а во взаимодействии с браузерным api - тем же canvas например, но не поручусь - включите профалер в инструментах браузера и найдите что именно вызывает у вас тормоза, туда и смотрите.

[voraa]

Вам уже не раз писали, что BigInt не имеет никакого отношения к 64 разрядным целым числам. Это вообще многобайтное (столько, сколько нужно) представление числа. Там может быть и 16 бит, и 64, и 128, и 1024...
Javascript вообще не умеет работать с 64 разрядными целыми числами. Точно представляются только целые числа меньше 2^53-1. Все, что больше представляются как Float64.

Операция вила n = n|0n для BigInt вообще не имеет никакого смысла. Число никак не изменяется.
Обычная операция для Number n = n|0 переводит в число в целое, отбрасывая дробную часть, и ограничивает целую часть 32 разрядами. Но BigInt и так целые, и разряды у них не ограничиваются.

Для производительности стоит использовать ArrayBuffer и производные.

Вроде нет, условно говоря Int64Array.

[Alikberov]

1. У меня на машине ничего не тормозит.

Очeнь интересный момент!
У меня в Chromium под Raspbian 600MHz (лето: частоту занизил до плинтуса) линия на весь Canvas подвешивает браузер на 15-25 секунд и периодически выскакивает окошко с вопросом о принудительном завершении сценария!
(Скрипт отлаживать в таких жарких и тормозных условиях чудовищно сложно.)

4. Скорее всего проблемы с производительностью и вовсе не в вызовах или математике, а во взаимодействии с браузерным api - тем же canvas например, но не поручусь - включите профалер в инструментах браузера и найдите что именно вызывает у вас тормоза, туда и смотрите.

Мой промах: Вы правы!
Стоило в листинге даже закомментировать «.canvas rax» - всё залетало!
Ещё притормаживает функция записи в журнал каждого снимка состояния регистров, которая к тому же безобразно написана: Два цикла с push'ами строк в массив. Но не так сильно, как ожидалось…
Всё же Canvas.toDataURL чудовищно просаживает всю производительность!
Буду искать другой метод: Не делать снимки всего Canvas, а просто сохранять координаты, куда ставить точки. Но это усложнит верхний уровень - реакция на «ползунок времени», где вместо простого вывода спрайта нужно будет пиксели стирать-ставить…

Вам уже не раз писали, что BigInt не имеет никакого отношения к 64 разрядным целым числам. Это вообще многобайтное (столько, сколько нужно) представление числа. Там может быть и 16 бит, и 64, и 128, и 1024...

Да, я это уже понял, когда потрудился не действовать методом интуитивного тыка, а вчитаться в спецификацию.
Хорошая фишка этот BigInt!

Для AVX нужно уметь работать с 512 битным словом, да ещё и упакованным.
Если сложение/вычитание ещё работает с упакованными данными по описанному мною трюку с масками выше, то сравнение и сложение/вычитание с насыщением (аналог Uint8ClampedArray) - очень сложная тема и как там с масками трюкачить - пока не понятно.

Операция вила n = n|0n для BigInt вообще не имеет никакого смысла. Число никак не изменяется.
Обычная операция для Number n = n|0 переводит в число в целое, отбрасывая дробную часть, и ограничивает целую часть 32 разрядами. Но BigInt и так целые, и разряды у них не ограничиваются.

Придётся мне непосредственно методом тыка действовать и изучать реакцию браузера!

[Alikberov]

Чтoбы понять все сложности и подводные камни технологии эмуляции SIMD-расчётов, рассмотрим несколько простейших операций.

Сутью SIMD-механизма является т.н. горизонтальное вычисление, когда одной операцией обрабатывается несколько данных, упакованных в одно слово.

Например, сравним две функции сложения упакованных данных.
Так как несущее слово имеет разрядность в 64 бита, то и дробление всех действий кратно длине упакованных данных в нём соответственно.
Если данные - 8-битные слова, то в общем 64-битном умещается их восемь и функция выходит довольно длинной и скучной:

// Сложение восьми 8-битных слов, упакованных в одно 64-битное слово
BigInt.prototype.PADDB = function(n) {
	//	Packed Add for Bytes
	var	d1 = 0xFFn & this;			// Распаковываем из 64-битного слова
	var	d2 = 0xFFn & (this >> 8n);		// восемь отдельных 8-битных
	var	d3 = 0xFFn & (this >> 16n);
	var	d4 = 0xFFn & (this >> 24n);
	var	d5 = 0xFFn & (this >> 32n);
	var	d6 = 0xFFn & (this >> 40n);
	var	d7 = 0xFFn & (this >> 48n);
	var	d8 = 0xFFn & (this >> 56n);
	var	n1 = 0xFFn & n;				// Распаковываем из 64-битного слова
	var	n2 = 0xFFn & (n >> 8n);			// восемь отдельных 8-битных
	var	n3 = 0xFFn & (n >> 16n);
	var	n4 = 0xFFn & (n >> 24n);
	var	n5 = 0xFFn & (n >> 32n);
	var	n6 = 0xFFn & (n >> 40n);
	var	n7 = 0xFFn & (n >> 48n);
	var	n8 = 0xFFn & (n >> 56n);
	var	r1 = ((d1 + n1) & 0xFFn);		// Складываем все восемь 8-битных слов
	var	r2 = ((d2 + n2) & 0xFFn) << 8n;
	var	r3 = ((d3 + n3) & 0xFFn) << 16n;
	var	r4 = ((d4 + n4) & 0xFFn) << 24n;
	var	r5 = ((d5 + n5) & 0xFFn) << 32n;
	var	r6 = ((d6 + n6) & 0xFFn) << 40n;
	var	r7 = ((d7 + n7) & 0xFFn) << 48n;
	var	r8 = ((d8 + n8) & 0xFFn) << 56n;
	return	r8 | r7 | r6 | r5 | r4 | r3 | r2 | r1;	// Упаковываем всё обратно в 64-битное
}

Если же данные - 16-битные слова, то в 64-битном уместится их уже вдвое меньше, соответственно и функция сократится:

// Сложение четырёх 16-битных слов, упакованных в одно 64-битное слово
BigInt.prototype.PADDW = function(n) {
	//	Packed Add for Words
	var	d1 = 0xFFFFn & this;			// Распаковываем из 64-битного слова
	var	d2 = 0xFFFFn & (this >> 16n);		// четыре отдельных 16-битных
	var	d3 = 0xFFFFn & (this >> 32n);
	var	d4 = 0xFFFFn & (this >> 48n);
	var	n1 = 0xFFFFn & n;			// Распаковываем из 64-битного слова
	var	n2 = 0xFFFFn & (n >> 16n);		// четыре отдельных 16-битных
	var	n3 = 0xFFFFn & (n >> 32n);
	var	n4 = 0xFFFFn & (n >> 48n);
	var	r1 = ((d1 + n1) & 0xFFFFn);		// Складываем все четыре 8-битных слов
	var	r2 = ((d2 + n2) & 0xFFFFn) << 16n;
	var	r3 = ((d3 + n3) & 0xFFFFn) << 32n;
	var	r4 = ((d4 + n4) & 0xFFFFn) << 48n;
	return	r4 | r3 | r2 | r1;			// Упаковываем всё обратно в 64-битное
}

Но, как-то всё уныло и скучно получается. Да ещё и циклы применять крайне не желательно. Из-за чего исходный текст программы симуляции растёт как на дрожжах!

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

BigInt.prototype.PADDB = function(n) {
	return (((this & 0x7F7F7F7F7F7F7F7Fn) + (n & 0x7F7F7F7F7F7F7F7Fn))) ^ ((this ^ n) & 0x8080808080808080n);
}

И для 16-битных

BigInt.prototype.PADDW = function(n) {
	return (((this & 0x7FFF7FFF7FFF7FFFn) + (n & 0x7FFF7FFF7FFF7FFFn))) ^ ((this ^ n) & 0x8000800080008000n);
}

К тому же, всё это хозяйство можно унифицировать до:

BigInt.prototype.PADD = function(n, mask) {
	return (((this & mask) + (n & mask))) ^ ((this ^ n) & ~mask);
}

Только маску подставляй нужную и можно работать с упакованностью любой кратности!

С вычитанием выходит немножечко посложнее, так как там не перенос подавить нужно, а предотвратить займ:

BigInt.prototype.PSUB = function(n, mask) {
	return (((this | ~mask) - (n & mask)) & mask) | ((this - n) & ~mask);
}

Ну, здесь можно добавить сахарку и передавать маску в функцию неявным способом - (мой позорный вопрос №189 посвящён задаче маскировки маски), хотя там тоже свои нюансы.

Если с нормальным сложением/вычитанием упакованных данных как бы всё очевидно, просто и изящно, то с операциями сравнения всё намного хуже!

// Сравниваем восемь 8-битных слов и формируем восемь независимых масок в зависимости от результата сравнения
BigInt.prototype.PCMPEQB = function(n) {
	var	d1 = 0xFFn & this;			// Распаковываем из 64-битного слова
	var	d2 = 0xFFn & (this >> 8n);		// восемь отдельных 8-битных
	var	d3 = 0xFFn & (this >> 16n);
	var	d4 = 0xFFn & (this >> 24n);
	var	d5 = 0xFFn & (this >> 32n);
	var	d6 = 0xFFn & (this >> 40n);
	var	d7 = 0xFFn & (this >> 48n);
	var	d8 = 0xFFn & (this >> 56n);
	var	n1 = 0xFFn & n;				// Распаковываем из 64-битного слова
	var	n2 = 0xFFn & (n >> 8n);			// восемь отдельных 8-битных
	var	n3 = 0xFFn & (n >> 16n);
	var	n4 = 0xFFn & (n >> 24n);
	var	n5 = 0xFFn & (n >> 32n);
	var	n6 = 0xFFn & (n >> 40n);
	var	n7 = 0xFFn & (n >> 48n);
	var	n8 = 0xFFn & (n >> 56n);
	var	r1 = (d1 == n1 ? 0xFFn : 0x00n);	// Сравниваем все восемь 8-битных слов
	var	r2 = (d2 == n2 ? 0xFFn : 0x00n) << 8n;
	var	r3 = (d3 == n3 ? 0xFFn : 0x00n) << 16n;
	var	r4 = (d4 == n4 ? 0xFFn : 0x00n) << 24n;
	var	r5 = (d5 == n5 ? 0xFFn : 0x00n) << 32n;
	var	r6 = (d6 == n6 ? 0xFFn : 0x00n) << 40n;
	var	r7 = (d7 == n7 ? 0xFFn : 0x00n) << 48n;
	var	r8 = (d8 == n8 ? 0xFFn : 0x00n) << 56n;
	return	r8 | r7 | r6 | r5 | r4 | r3 | r2 | r1;	// Упаковываем всё обратно в 64-битное
}

Это просто тихий ужас! Как всё это оптимизировать - ума не приложу…
А ведь это сравнение только 8-битных и только на эквивалентность!

Из-за чего вся моя разработка затягивается на недели или откладывается.

А учитывая, сколько всего команд уста ревшей технологии MMX желательно поддержать в симуляторе, да поглядывая ещё на SSE и 3DNow!, не говоря уж о AVX, то вопрос полной поддержки всего этого не стоит особняком, так как симулятор я разрабатывать начал для личных нужд и поддержку команд ввожу по мере надобности в них.
И меня пока не привлекает тот факт, что BigInt поддерживает и 128, и 256, и 512 бит, так как даже представить весь тот ужас описания AVX-512 операций на нём невозможно!
(Придётся халтурить и написать генератор дрожжевого кода в самом симуляторе при загрузке страницы, чтобы все громоздкие функции генериловались автоматически, не засоряя основной листинг симулятора…)

Да, в интернете очень много профессиональных отладчиков, среди которых самый простой и удобный - бразильский: Шустро загружается, интерфейс без излишеств, легко запустить отладку.
Но ни в каких отладчиках я не видел функции отката во времени: Если инструкция выполнилась, нельзя узнать про состояния регистров до её выполнения, иначе как перезапустить весь процесс с самого начала!
Так и родилась идея данного симулятора, который журналирует исполнение каждой инструкции на каждой строчке и во множестве итераций цикла.

[voraa]

Да ещё и циклы применять крайне не желательно.

Почему?

Мне кажется, проще перейти от BigInt к ArrayBufer и TypedArray.
Да, там придется устраивать циклы.
А вы думаете действия с BigInt работают напрямую? Там тоже циклы, только скрыты во внутренних библиотеках поддержки этих данных.
Наверняка каждая операция - это цикл по атомарным единицам хранения этих чисел.

[voraa]

который журналирует исполнение каждой инструкции на каждой строчке и во множестве итераций цикла.

А память симулируемой машины? Ее же тоже надо журналировать для отката.
Как быстро переполнится память на машине симуляторе?

[Aetae]

Ну очевидно тут что надо релизовать единый интерфейс n-битного числа, со всеми нужными методами операций как битовых, так и математических, после чего реализовать его для каждого нужного, неважно как: на bigint или arraybuffer, а то и в webassebly закодить.
А потом просто использовать прозрачно в вычислениях не заморачиваясь, что там под капотом, пока это не станет узким местом.

Что-то типа такого, только и для всех больших битностей: https://github.com/dcodeIO/long.js#readme

[Alikberov]

А вы думаете действия с BigInt работают напрямую? Там тоже циклы, только скрыты во внутренних библиотеках поддержки этих данных.

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

А память симулируемой машины? Ее же тоже надо журналировать для отката.
Как быстро переполнится память на машине симуляторе?

Вот поэтому у меня операции с памятью никак не поддерживаются, но частично симулируется через графику в Canvas как видеобуфер.
Журналировать каждый доступ к памяти - дело крайне не благодарное. Но для работы со стеком я думаю на минимальном уровне как-то это обеспечить.

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

Ну очевидно тут что надо релизовать единый интерфейс n-битного числа, со всеми нужными методами операций как битовых, так и математических, после чего реализовать его для каждого нужного, неважно как: на bigint или arraybuffer, а то и в webassebly закодить.
А потом просто использовать прозрачно в вычислениях не заморачиваясь, что там под капотом, пока это не станет узким местом.

Вот потому нужно разработать некий генератор функций развёрнутых циклов.
(Когда-то я уже делал подобное здесь: Там в «<textarea id=Pattern» псево-языком описывается шаблон генерирования сотен функций…)

При эмуляции работы некоего процессора всегда чего-то не хватает из всего набора языка, так как процессор всегда работает немного иначе, чем можно выразить синтаксисом ЯВУ.
Вот, например, операция Деления над массивом в JS отсутствует и её приходится реализовывать в цикле явно, хотя на уровне процессора такая инструкция есть и выполняется на порядок быстрее.

Проблема в том, что авторы JS не предусматрели подобные матричные операции на базовом уровне. Что говорить, если процессор может одной командой переставить нужные члены массива, а в ЯВУ нужно явно самому их переставлять.

Так, в процессоре с поддержкой AVX-512 одно машинное слово может представляться как Uint8Array(64), Uint16Array(32), Uint32Array(16), Uint64Array(8) и т.д. То есть, здесь слово выступает как микромассив фиксированной длины и с гарантией, что над всеми членами этого массива практически любая операция будет выполняться параллельно. Сам синтаксис языка не поддерживает такой операции, хотя аппаратно она существует.

Что-то типа такого, только и для всех больших битностей: https://github.com/dcodeIO/long.js#readme

Спасибо за ссылку, но там несколько иная тематика.

Сейчас, как говорил выше, очень не хватает набора из Uint16ClampedArray, Int16ClampedArray, Uint32ClampedArray, Int32ClampedArray, Uint64ClampedArray, Int64ClampedArray и т.п. (сабж)
Всё это есть в архитектурах с поддержкой SIMD, но языки как-то не поспевают в след за процессорами!
Получается, будто объектная модель процессорного машинного кода в узких местах даже богаче, чем у JavaScript. К сожалению.

[voraa]

Проблема в том, что авторы JS не предусматрели подобные матричные операции на базовом уровне.

Толку от них в интерпретируемом языке?

Так, в процессоре с поддержкой AVX-512

Js не зависит от процессора. Код должен выполняться везде, даже в кофеварке.