Рассказ о C, фракталах и совместимости JavaScript и Wasm

Я копался в WebAssembly уже несколько недель, и мне было трудно понять один аспект, как распределяется и распределяется память между JavaScript и сгенерированным Wasm. Есть несколько ответов, разбросанных по Интернету, и простые примеры, но я хотел создать что-то более всеобъемлющее. Итак, я вернулся к своим корням и занялся вековой Игры Хаоса.

Я могу сказать вам точный момент, когда я узнал о хаосе и фракталах. Я был в отпуске в конце 80-х, и наша семья остановилась в кемпинге где-то в Северной Каролине. Шел проливной дождь, поэтому мы застряли в салоне. В главном домике были две видеоигры (Donkey Kong и Tempest). Мне было скучно играть, поэтому я решил просмотреть крошечную библиотеку. Одна книга выскочила на меня под названием Хаос: создание новой науки. Я прочитал его от корки до корки несколько раз, и мне не терпелось вернуться домой и реализовать фракталы на моем графическом калькуляторе Texas Instruments.

Следующей моей покупкой была книга Фрактальное программирование на языке Си. Через несколько часов я рисовал свои первые фракталы. Для меня фракталы были отличным способом изучать новые языки. Они основаны на алгоритмах, поэтому их можно переводить на несколько языков, они требуют манипуляции с массивами и буферами для рендеринга графики и обеспечивают почти немедленную обратную связь и визуальное удовлетворение. Один из самых простых в реализации фракталов - это игра в хаос. Игра в хаос принимает матрицу значений и вероятностей, затем бросает кости и применяет преобразование к точке на основе столбца преобразований. Результаты могут быть ошеломляющими.

Игра в хаос - идеальный способ проверить производительность WebAssembly и одновременно узнать об управлении памятью.

🔗 Исходный код: https://github.com/JeremyLikness/wasm-trees
👀 Живая демонстрация: https://jlikme.z13.web.core.windows.net/wasm/wasm-trees/

Соревнование

Для этой задачи я хотел узнать об управлении памятью и передаче буферов между JavaScript и Wasm. Мои требования:

  1. Двунаправленный: показать, что я могу передавать буфер в WebAssembly, а также получать его из WebAssembly.
  2. Несколько типов и размеров: понять, как получить доступ к памяти, содержащей различные типы, например байты или десятичные значения с плавающей запятой.
  3. Производительность: измерьте производительность рендеринга в Wasm и посмотрите, практично ли, например, запускать примеры в браузере телефона.

Вооружившись своими старыми книгами, своими знаниями фракталов и WebAssembly и, конечно же, мощью поисковых систем, я приступил к реализации игры в хаос.

Теперь я ясно могу "C"

Игра в хаос работает с использованием матрицы преобразований, каждая из которых с вероятностью будет применена. На основании этих преобразований точка случайным образом прыгает по игровому полю. Следующий код устанавливает преобразования и вероятности для рендеринга фрактального дерева.

Значения p представляют собой шкалу вероятности. Если я брошу 32768-гранный кубик, он упадет под одну из колонок, и это то, что я использую для преобразования.

Развитие целого числа. Моя первая попытка адаптировать старый код C к WebAssembly ужасно провалилась. Любая моя попытка принесет только несколько очков. Тогда я понял, что использую int и вызываю rand() для генерации значения. Вероятности расположены в шахматном порядке от 0 до 32767, которые являются положительными значениями для 16-разрядного целого числа со знаком. В 1989 году это было нормально, но сегодня целые числа по умолчанию 32-битные и допускают на порядок больше значений. Итак, мне пришлось изменить вероятность, используя rand() % 32768.

Основной алгоритм игры просто повторяется (в моем случае 99 999 раз) и отображает точку в любом месте. Это код для игры.

Этот простой объем кода - засеянные значения и итератор - это все, что нужно для создания графики, изображенной ранее. Довольно мощно! Масштаб и смещения - это значения, с которыми я экспериментирую, чтобы правильно отображать графику внутри порта просмотра. Я написал код таким образом, чтобы в него передавался байтовый буфер без знака (это позволяет мне предварительно визуализировать линии сетки в JavaScript и показать, что я могу передать массив в WebAssembly) вместе с шириной и высотой «игрового поля», и два флага. Один флаг инициализирует модель с одной из предустановленных матриц: дерево, папоротник, треугольник, лабиринт и кривая Коха. Другой флаг, называемый «искажение», просто подталкивает случайное преобразование в одном направлении. Используя этот флаг, я могу анимировать изменения, которые происходят при изменении значений.

Это объявление метода и код для «подталкивания» матрицы.

Обратите внимание, что передается указатель на буфер. Этот указатель также передается обратно в JavaScript в конце с помощью return &buffer[0];. Оператор printf сопоставляется с console.log. Я также отслеживаю границы для нанесенных точек, фиксируя минимальное и максимальное переданные значения, даже если они выходят за пределы окна просмотра. Это помогло мне настроить соответствующие масштабы и смещения для целей рендеринга.

Метод plot просто выполняет некоторую проверку границ и, если точка находится в границах, отображает ее, устанавливая байт в буфер:

buffer[x * height + y] = color;

Поскольку код изменяет матрицу значений, мне нужен способ передать эти значения обратно в JavaScript для отображения на экране (таким образом, если у вас получится новый потрясающий фрактал, вы можете заморозить кадр и сохранить значения на потом). Матрица представляет собой набор массивов:

float a[4], b[4], c[4], d[4], e[4], f[4];

Адреса этих массивов могут храниться в массиве указателей:

float *addresses[6];

Метод getAddresses устанавливает указатели, а затем возвращает массив адресов памяти. Обратите внимание, что он использует формат ** «указатель на указатель».

Весь код доступен онлайн в этом репозитории GitHub.



JeremyLikness / wasm-tree
Пример управления памятью / передачи буферов между WebAssembly и JavaScript - JeremyLikness / wasm-tree github.com



Следующим шагом является компиляция кода C в WebAssembly.

Компиляция C в Wasm

Emscripten - это набор инструментов, созданный специально для компиляции проектов C / C ++ в WebAssembly. Помимо генерации байтового кода Wasm, он предоставляет другие услуги, такие как отображение стандартного вывода на консоль JavaScript и преобразование типов JavaScript при передаче в качестве параметров функциям C и C ++. В SDK есть инструменты для его установки и / или сборки на нескольких платформах, но я предпочитаю использовать предварительно созданный контейнер Docker. Это позволяет мне использовать инструменты, ничего не устанавливая локально.

В проект включены два «вспомогательных» сценария в папке tools для создания WebAssembly. Их следует запускать из каталога src, например: ..\tools\compile.bat или ../tools/compile.sh. Основная команда для Windows выглядит так:

docker run -it --rm -v %cd%:/src trzeci/emscripten emcc trees.c -O2 -s WASM=1 -s EXPORTED_FUNCTIONS="['_renderTree', '_getAddresses']" -s EXTRA_EXPORTED_RUNTIME_METHODS="['ccall','cwrap']" -o trees.js -s ALLOW_MEMORY_GROWTH=1

Версия оболочки bash практически идентична, за исключением соглашения о получении текущего рабочего каталога. Это разбивка по параметрам:

  • run - указывает Docker запустить указанный образ. Он загрузит его, если он еще не доступен локально.
  • -it - работает в интерактивном режиме в «терминальном» режиме, поэтому вы видите результат выполненных команд.
  • --rm - автоматически удаляет контейнер Docker после завершения работы.
  • -v - монтирует хранилище для контейнера. Соглашение после сопоставляет текущий рабочий каталог на главном компьютере с папкой src в контейнере. Это позволяет инструментам Emscripten «видеть» текущий рабочий каталог.
  • trzeci/emscripten - указывает на этот предварительно настроенный контейнер Docker с SDK и инструментами.
  • emcc - запускает компилятор Emscripten. trees.c передается как файл для компиляции.
  • -O2 - оптимизирует вывод. Есть несколько вариантов оптимизации, и это самый эффективный, сохраняющий утилиты для управления памятью.
  • -s WASM=1 - информирует компилятор о выводе WebAssembly. Вместо этого используйте 0 для вывода asm.js.
  • -s EXPORTED_FUNCTIONS— предоставляет функции из кода C создаваемому модулю JavaScript. Если функции не указаны, компилятор не знает, что они будут вызваны, и они будут оптимизированы на основе сгенерированного Wasm.
  • -s EXTRA_EXPORTED_RUNTIME_METHODS - указывает, какие «вспомогательные» функции, предоставляемые Emscripten, включены. Перечисленные функции помогают преобразовывать параметры при вызове из JavaScript в Wasm и наоборот. Подробнее об этом позже.
  • -s ALLOW_MEMORY_GROWTH=1 - генерирует код управления памятью для выделения байтов из JavaScript, которые могут быть переданы в WebAssembly.
  • -o trees.js - указывает, что должен быть сгенерирован файл JavaScript-оболочки для загрузки и предоставления WebAssembly.

Выполнение этой команды должно создать два файла размером около 20 килобайт каждый: trees.js и trees.wasm. Скрипты также скопируют их в каталог web.

Передача данных и функций вызова из JavaScript

Основной код JavaScript (написанный, а не сгенерированный) находится в index.js. Там вы найдете набор переменных для отслеживания состояния, ссылки на холст и несколько функций, которые вызываются с интервалами или на основе событий. Первый фрагмент кода, связанный с Wasm, выглядит так:

Вызов cwrap назван удачно: он превращает вызов функции C в функцию JavaScript. Это не является обязательным требованием (вместо этого вы можете использовать Module._renderTree напрямую), но такой подход обеспечивает правильное преобразование типов. Что еще более важно, он также позволяет передавать массивы в WebAssembly. Параметры, по порядку, - это имя функции, возвращаемое значение и типы переданных параметров. Давайте на мгновение рассмотрим renderTree более внимательно. Обратите внимание, что первый параметр имеет тип «массив».

В этом сценарии в JavaScript создается буфер, который передается в Wasm и используется как «холст» для построения точек. Чтобы показать, что передача прошла успешно, в JavaScript «рисуется» набор линий сетки. Этот код создает массив и заполняет линии сетки.

Чтобы передать массив, необходимо выполнить два шага. Во-первых, для приема буфера в WebAssembly необходимо выделить память. Во-вторых, буфер необходимо скопировать в Wasm. Для удобства WebAssembly предоставляет свою память на основе непрерывных блоков или куч типизированных данных. Например, Module.HEAPU8 отображает кучу байтов без знака. Module.HEAPF32 предоставляет блок памяти, содержащий 32-разрядные числа с плавающей запятой. Буфер, который мы будем использовать, указанный как unsigned char * в коде C, представляет собой беззнаковые байты, и поэтому мы используем беззнаковую байтовую кучу.

Следующий код выделяет память и копирует массив JavaScript в память. Затем он передает массив напрямую, используя обернутый вызов функции, который, в свою очередь, находит указатель на массив в куче и передает его в функцию C. После анализа возвращенного значения выделенная память освобождается.

Ключевым моментом здесь является отметить, что даже несмотря на то, что typedArray передается функции, это обернутый вызов. На самом деле в код C передается указатель на HEAPU8, который был создан в предыдущей операции set.

Обратите внимание, что важно выделить правильный размер памяти и передать правильный указатель. В этом случае математика немного избыточна, потому что на каждый элемент приходится ровно один байт. Помня об этой формуле и последовательно используя встроенные константы для размеров элементов, вы всегда будете правильно выделять и устанавливать память. Вы умножаете на байты для каждого элемента (например, 16-битное целое число будет иметь два байта на элемент), чтобы выделить память, и делите на байты для каждого элемента, чтобы установить указатель памяти.

На этом этапе вы можете наблюдать несколько интересных вариантов поведения:

  • Любые манипуляции с памятью не отражаются в исходном typedArray экземпляре. Вы можете проверить массив после вызова и убедиться, что он не изменился. Он используется для передачи данных в кучу Wasm.
  • Смещение, созданное путем выделения памяти, не совпадает с смещением, которое передается обратно. Память, предоставленная C, является отдельной и должна быть возвращена для доступа. Следовательно, смещение buffer не используется для чтения измененных байтов; вместо этого новый указатель передается обратно в переменную offset.

Затем давайте прочитаем немного памяти из WebAssembly.

Чтение памяти WebAssembly из JavaScript

Самый простой способ прочитать память Wasm - использовать беззнаковую байтовую кучу. Следующий код успешно анализирует буфер, которым управляет WebAssembly, и использует его для создания данных изображения, которые рисуются на холсте. Обратите внимание, что он просто перебирает кучу, начиная со смещения, которое было передано обратно из кода C (см. Строку 3).

Это здорово, но как насчет других типов памяти? Если вы помните, код C содержит несколько массивов данных с плавающей запятой, используемых для преобразований. Метод getAddresses возвращает указатель на массив указателей, каждый из которых указывает на массивы чисел с плавающей запятой.

Какие?!

Давайте разберем это, посмотрев на функцию getValues.

Данные, переданные обратно, представляют собой массив указателей. Указатели представляют собой 32-разрядные целые числа без знака, поэтому куча анализируется путем вычисления смещения в HEAPU32 с использованием указателя, переданного обратно вызовом loadValues (сопоставлен с getAddresses):

const varOffset = Module.HEAPU32[ptr / Uint32Array.BYTES_PER_ELEMENT + idx];

Обратите внимание, что перед индексированием указатель делится на размер элементов массива.

Типы HEAPxx накладываются на одну и ту же память. Это просто разные типизированные представления в одном ArrayBuffer.

Каждый полученный указатель является указателем на массив с плавающей запятой. Следовательно, значение второго указателя используется для ссылки на память в HEAPF32. Мы знаем, что каждый массив с плавающей запятой состоит из четырех элементов, поэтому внутренний цикл выполняет итерацию по этим значениям. Ключ, опять же, состоит в том, чтобы разделить указатель на размер элементов для индексации фактического смещения в памяти.

const value = Module.HEAPF32[varOffset / Float32Array.BYTES_PER_ELEMENT + i];

Логически макет выглядит так:

Предположим, вы хотите сослаться на массив из двух беззнаковых 16-битных целых чисел, начиная с ячейки памяти 4. Указатель всегда является выровненным по байтам указателем, поэтому «4» на самом деле означает позицию «2» в HEAPU16 (4/2 = 2 ). Вот этот код поможет:
const ptr = Module.getOffset(); // assume this passes the mem addr (4)
const jsArray = new Uint16Array(Module.HEAP16, ptr/Uint16Array.BYTES_PER_ELEMENT, 2);

После захвата значений из памяти функция затем выдает эти значения, чтобы вы могли записать их для дальнейшего использования.

Заключение

Этот проект фокусируется на том, как WebAssembly и JavaScript работают вместе для управления памятью и доступа к ней. Надеюсь, это дает четкое представление о модели памяти Wasm, о том, как оборачивать функции для вызовов и как правильно обращаться к памяти из JavaScript. Прежде чем я закончу, я не хочу терять из виду происходящее волшебство.

🔗 Исходный код: https://github.com/JeremyLikness/wasm-trees
👀 Живая демонстрация: https://jlikme.z13.web.core.windows.net/wasm/wasm-trees/

Когда вы запускаете приложение, вы можете открыть консоль отладки браузера и просмотреть некоторую статистику, выдаваемую кодом. Например, показано смещение буфера, переданное в дерево рендеринга, вместе с переданным указателем. Обратите внимание, насколько они разные! Но что еще важнее, посмотрите, сколько времени требуется для рендеринга графики. Каждый «кадр» выполняет 99 999 итераций преобразования матрицы с плавающей запятой, а на моей машине он выполняется менее чем за 10 миллисекунд. Кроме того, при рендеринге на моем телефоне он не пропускает ни одной доли. На мой взгляд, это свидетельствует не только о том, насколько далеко зашли вычислительные мощности, но и о том, насколько практично запускать код сегодня в глобальной стандартной безопасной операционной системе, известной как ваш веб-браузер.

С уважением,