Введение

Недавно я работал над разработкой браузерной 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::<Vec<_>>()[..],
                ))
            })
            .collect::<Vec<_>>(),
    ))
}

И, конечно, приводем к этому же виду использование оригинального алгоритма:

const jsNoise = (x, y, scale) =>
    [...Array(x).keys()].map((x) =>
      [...Array(y).keys()].map((y) => noise.perlin2(x / scale, y / scale))
    )

Реализации 3D-версии показывать, считаю, не имеет смысла — кода больше, а идея та же. Но если вы ценитель эстетики монструозных функциональных однострочников, как я, то держите ссылку.

В итоге, при запуске эксперимента, мы получаем следующие результаты:

Вот, другое дело! Wasm-версия 2D шума отрабатывает быстрее в среднем в 1,78 раз.

И 3D-версия:

Как ни странно, получаем ту же разницу в 1,78 раз. Сомнительно, ну Окэй.

Уверен, если не гнать в выходных данных вложенные друг в друга векторы, то можно добиться прироста производительности еще в несколько раз.

Визуализация шума

Наконец что-то интересное, а не эти ваши куски кода и какие-то графики

Для 2D-версии получаемая величина была нормализирована и отображена как оттенок серого (где 0 - черный, а 1 - белый).

В 3D-версии, напомню, мы получаем не число, а вектор чисел, потому я решил поступить интересным образом: разделить его на 3 части, получить среднее значение каждого, нормализовать, и точно также, как и с 2D-версией, получить значение оттенка, только уже красного, зеленого и синего соответственно для каждой из 3 частей, чтобы получить цветную точку.

Результат можно увидеть у себя в браузере, если перейти по ссылке (да-да, автор в верстку не могет).

Заключение

Подытожить данное приключение хочется тем, что Wasm, как более низкоуровневая технология, безусловно будет быстрее. Главное — правильно ее применять, иначе — можно получить похожий результат и остановиться где-то на первом блине комом.

Репо с кодом проекта