Ускоряем браузерные вычисления на коленке с помощью WebAssembly на примере генерации шума
Введение
Недавно я работал над разработкой браузерной 3D-игры в качестве очередного pet-проекта с помощью движка BabylonJS. И в какой-то момент встал вопрос о необходимости процедурной генерации террейна — уверен, у каждого, кому приходилось сталкиваться с созданием естественных локаций в играх, возникала такая проблема. Вопрос состоит в подборе подходящего алгоритма генерации шума, который затем можно будет использовать в качестве карты глубины, нормалей и/или чего-нибудь еще. Да даже генерация движения воды, ветра и так далее — обычно производятся теми же алгоритмами!
Стоит сказать, что чаще всего используется один из нескольких популярных алгоритмов, вроде Шума Перлина, Симплекса, их кастомных модификаций и так далее. BabylonJS в примерах с генерацией террейна предлагает воспользоваться реализацией Шума Перлина, написанной на JavaScript. Зная то, что этот язык не лучший кандидат для таких низкоуровневых CPU-bound операций, я решил попробовать реализовать Шум Перлина с помощью WebAssembly и затем определить, удалось ли ускорить процесс генерации и если да, то насколько?
Немного о WebAssembly
Официальный сайт позиционирует технологию следующим образом:
WebAssembly (сокращенно Wasm) — это формат двоичных инструкций для стековой виртуальной машины. Wasm разработан как кроссплатформенный таргет компиляции для языков программирования, позволяющий развертывать в интернете клиентские и серверные приложения.
По своей сути, данный формат одновременно является уже скомпилированным набором инструкций в бинарном виде, что позволяет миновать стадии подготовки кода, интерпретации и JIT-компиляции, которые производят браузерные JS-движки, такие как V8 и SpiderMonkey (подробно об этом можно почитать, например, здесь).
Wasm появился не вчера и не год назад, так что уже на сегодняшний момент существуют игровые движки, платформы и редакторы, позволяющие компилировать проект, созданный в них, под Wasm для портирования его в браузеры. Но мы с вами попробуем написать программу и скомпилировать ее под Wasm вручную, без пап, мам и готовых движков. Это не сколько сложнее, сколько более чище и нагляднее в плане эксперимента.
В данном ридми представлен список языков программирования, которые могут быть скомпилированы в Wasm. Для удобства, они разделены на те, что уже активно используются в продакшене, стабильные для использования, нестабильные, в разработке и неподдерживаемые.
В качестве языка был выбран самый простой язык программирования в мире Rust. Он является type and memory safe и не требует Runtime-мусора вроде GC, хотя т.к. наша цель — ускорить процесс как можно сильнее, то , при должной уверенности в том, что код не упадет и выполнится корретко без UB, можно получить такой же результат и на C/C++/Zig.
Данная статья не о тонкостях реализации конкретного алгоритма на конкретном языке. Так что опустим ревью каждой строчки кода и того, что в них происходит и перейдем сразу к самому интересному — циклу разработки:
Цикл разработки
Итак, приступим
Не мудрствуя лукаво, было решено просто переписать алгоритм с той самой версии, предлагаемой BabylonJS в вышеупомянутом примере. Тем более, таким образом мы сможем получить лучшее сравнение, чем если бы одна реализация была основана на одном алгоритме, а другая — на слегка измененном или вообще ином, что явно повлияло бы на результаты, исказив их!
Пример предлагал как Шум Перлина 2D, так и 3D. И, ради более показательных результатов, были переписаны оба алгоритма.
Оригинальная реализация алгоритма была сделана с соответствующими верхнеуровневыми функциями для генерации шумов так, что каждая из них принимает на вход координаты точки (x, y для 2D и x, y, z для 3D-версии) и возвращает число с плавающей точкой в случае 2D, и вектор (массив) таких чисел — для 3D-версии.
Первый блин — комом
Переписав оба алгоритма точь-в-точь, я принялся замерять время их выполнения. Для полной сходимости результатов, они оба были загружены на веб-страницу и испытаны в идентичных условиях: 2D-версия была испытана путем вложения алгоритма в двойной цикл, а 3D — в тройной, чтобы те получали все возможные координаты точек плоскости/пространства. Сам файл бенчмарков выглядел следующим образом:
import init, { Perlin } from './wasm-perlin-pkg/wasm_perlin.js'
await init()
const seed = Math.random()
noise.seed(seed)
const noiseWasm = new Perlin(seed)
const experiments = [
['perlinjs', noise],
['webperlin', noiseWasm],
]
experiments.forEach(([id, noise]) => {
const totalStart = Date.now()
for (let x = 0; x < 1e3; x++) {
for (let y = 0; y < 1e3; y++) {
noise.perlin2(x / 100, y / 100)
}
}
const totalEnd = Date.now()
console.log(`[${id}] Rendered in ` + (totalEnd - totalStart) + ' ms')
})Стоит заметить, что рекомендуется использовать console.time вместо Date.now в случае попыток в профилирование! В нашем случае нужно не просто вывести результат в консоль, и по перфомансу разницы никакой
Код написан, остается лишь открыть веб-страницу и посмотреть в консольку. И что мы видим?
Первый эксперимент
Похоже на ошибку! Разница в 3.5 раза и не в пользу Wasm-версии! Нужно запустить алгоритм, скажем, сотню раз, чтобы получить статистическую точность. Слегка меняем наш код запуска экспериментов:
experiments.forEach(([id, noise]) => {
const result = [...Array(100).keys()].map((i) => {
const totalStart = Date.now()
for (let x = 0; x < 1e3; x++) {
for (let y = 0; y < 1e3; y++) {
noise.perlin2(x / 100, y / 100)
}
}
const totalEnd = Date.now()
return totalEnd - totalStart
})
console.log(id, result)
})И получаем результаты:
Результаты первого эксперимента, запущенного сотню раз
И если вы не всматривались в цифры, и вас не хватил инфаркт, то вот вам те же данные, но уже в виде графика:
Графическое представление. Цвета не в честь хэллоуна, а в цвет соотстветсвующих иконок языков!
Средние значения: 3.55 и 25.16, разница в 7 раз!
Выходит, никакой ошибки нет. Все ясно, результаты говорят сами за себя! JS превосходит Wasm даже в CPU-bound задачах, другого и быть не может!
Или все-таки может?
Рефлексия
Давайте на время отложим идею о том, что мы сравниваем 2 реализации алгоритма, и попытаемся проанализировать сам эксперимент. Нам кажется, что мы сравниваем их в чистом виде. Однако так ли это на самом деле?
Уверен, самые смышленные заметили подвох еще на моменте примеров кода самого эксперимента, но давайте всё же разберем, в чем причина подобных провальных результатов:
Итак мы имеем JS-версию и Wasm-версию алгоритма, написанного на Rust, так что в сборку Wasm-файла не должен попасть всякий рантайм-мусор вроде garbage collector, каких-то платформенных утилит и т.д. И там, и там код чисто алгоритма. Идем дальше.
Стоит вернуться к тому, что данные реализации представляют из себя на уровне их интерфейса функцию, принимающую координаты и возвращающую число. Обе реализации мы испытываем в JS-среде. Получается, при запуске JS-версии алгоритма в JS-среде функция получает JS values, с ними же работает и их же возвращает. А Wasm-версия, кроме самого алгоритма, должна сначала принять данные через WebAssembly ABI, а потом отправить выходные данные через него же. Также происходит вызов Wasm-функции, который, предположительно, происходит также весьма не бесплатно.
В общем-то похоже на выяснение того, кто сильнее: медведь или рыба-клоун, если сравнение мы будем производить в толще морской воды, в которой медведь не то, что не сможет нормально двигаться или дышать, а скорее всего сразу же погибнет из-за огромного давления.
Мем, чудом подошедший по смыслу
К сожалению, мне не удалось найти достаточного кол-ва информации на просторах интернета, чтобы накидать ссылок в статью, поясняющих за подобные даунсайды при работе с Wasm. Надеюсь, среди читателей найдутся те, кто разбирается в данном вопросе и смогут разъяснить данный момент в комментариях, буду очень признателен.
Дубль два или попытка в great comeback
Чтож, наше предположение состоит в том, что код работает медленно из-за того, что мы вызываем Wasm-функцию, пихаем туда пару-тройку чисел и получаем оттуда одно число. И так много-много раз. И просадка происходит именно в моменте запуска функции + при пробрасывании входных данных и получении выходных.
Тогда, как вариант, можно просто передовать в функцию координаты, с которых начинать генерацию нашей матрицы (в случае 2D алгоритма) или 3D-матрицы (в случае 3D алгоритма), производить генерацию на стороне Wasm и возвращать уже готовые массивы данных. И все это единовременно!
Что же, для этого добавим функцию для генерации матрицы шума в нашу реализацию. Говорил, что не будет примеров кода Rust, а тут:
/// 2D Perlin Noise Matrix
#[wasm_bindgen(js_name = "perlin2Matrix")]
pub fn perlin2_matrix(&self, x: Float, y: Float, scale: Float) -> js_sys::Array {
js_sys::Array::from(&JsValue::from(
(0..(x as usize))
.map(|x| {
JsValue::from(js_sys::Float64Array::from(
&(0..(y as usize))
.map(|y| self.perlin2((x as Float) / scale, (y as Float) / scale))
.collect::>()[..],
))
})
.collect::>(),
))
} И, конечно, приводем к этому же виду использование оригинального алгоритма:
const jsNoise = (x, y, scale) =>
[...Array(x).keys()].map((x) =>
[...Array(y).keys()].map((y) => noise.perlin2(x / scale, y / scale))
)Реализации 3D-версии показывать, считаю, не имеет смысла — кода больше, а идея та же. Но если вы ценитель эстетики монструозных функциональных однострочников, как я, то держите ссылку.
В итоге, при запуске эксперимента, мы получаем следующие результаты:
Раунд 2, 2D шум
Вот, другое дело! Wasm-версия 2D шума отрабатывает быстрее в среднем в 1,78 раз.
И 3D-версия:
Раунд 2, 3D шум
Как ни странно, получаем ту же разницу в 1,78 раз. Сомнительно, ну Окэй.
Уверен, если не гнать в выходных данных вложенные друг в друга векторы, то можно добиться прироста производительности еще в несколько раз.
Визуализация шума
Наконец что-то интересное, а не эти ваши куски кода и какие-то графики
Для 2D-версии получаемая величина была нормализирована и отображена как оттенок серого (где 0 — черный, а 1 — белый).
В 3D-версии, напомню, мы получаем не число, а вектор чисел, потому я решил поступить интересным образом: разделить его на 3 части, получить среднее значение каждого, нормализовать, и точно также, как и с 2D-версией, получить значение оттенка, только уже красного, зеленого и синего соответственно для каждой из 3 частей, чтобы получить цветную точку.
Результат можно увидеть у себя в браузере, если перейти по ссылке (да-да, автор в верстку не могет).
Заключение
Подытожить данное приключение хочется тем, что Wasm, как более низкоуровневая технология, безусловно будет быстрее. Главное — правильно ее применять, иначе — можно получить похожий результат и остановиться где-то на первом блине комом.
Репо с кодом проекта
