13,9 тыс подписчиков

Портируем решатель судоку с Java на WebAssembly

29 октября 202029 окт 2020

5 мин

Оглавление

Решатель судоку
Давайте запустим решатель
Kotlin/Native

Мне давно хотелось приступить к изучению WebAssembly, но никак не находилось подходящего материала. Однако недавно я просматривал некоторые старые программы и вспомнил, что как-то написал решатель судоку, который отлично подходил для этого эксперимента. И я поставил цель: перенести эту программу в WASM и провести тестирование производительности.

Решатель судоку

Первый шаг — рефакторинг и приведение оригинальной Java-программы в форму, чтобы добиться некоторой базовой производительности. Как обычно, всегда удивительно, насколько плох оказывается ваш код, когда вы возвращаетесь к нему спустя годы. ?

Программа-решатель использует обратный путь для решения головоломки. То есть программа будет использовать грубую силу для исследования всех возможных решений. На конкретном примере: программа поместит 1 в первую доступную ячейку (если при этом нигде не нарушены правила) и перейдет к следующей. По правилам игры еще одну 1 в следующую горизонтальную ячейку поместить уже нельзя, поэтому программа попытается вместо этого поместить в эту ячейку 2. Если программа наткнётся на такую ячейку, в которую нельзя поместить ни одну из девяти цифр, то она вернется назад и исследует другую ветвь решения. Для этого она очищает текущую ячейку и увеличивает значение в предыдущей ячейке на единицу. Этот процесс повторяется до тех пор, пока не будет найдено решение (все ячейки заполнены допустимыми значениями).

Многие обратные алгоритмы реализуются с помощью рекурсии, но в данном случае программа использует простой итеративный подход. И, наконец, бывает, что решение судоку с помощью обратного перебора занимает много времени, особенно для головоломок, подобных этой с Википедии:

В примере ниже программа должна пройти почти все возможные ветви, чтобы найти решение:

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

Давайте запустим решатель

Учитывая, что в основном мы применяем циклы, расчет происходит довольно быстро.

Kotlin/Native

Нам также понадобится JavaScript-версия решателя, чтобы провести сравнение с WASM-версиями. Kotlin/Native позволяет компилировать одну и ту же программу для разных целевых языков, включая JS и WASM, так что с него и начнем. Конвертировать Java в Kotlin с помощью IDEA легко и быстро (по меркам, конечно, такой маленькой программы).

Как видите, Kotlin/Native, JS и WASM используют различные реализации стандартных библиотек, и в каждой из них у меня применились разные методы для подсчета затраченного времени.

Kotlin/Native — JS

Посмотрим сначала, как выполняется код на JavaScript:

Chrome

Firefox

JS-версия медленнее нативной, но всё же выполняется довольно быстро, и даёт аналогичные результаты как в Chrome, так и в Firefox.

Kotlin/Native — WASM

HTML-файл, который я использовал для запуска WASM-версии:

Я использовал очень простой http-сервер для обслуживания файлов. Если хотите попробовать другой, просто убедитесь, что он поддерживает тип application/wasm.

Взглянем на результат:

Chrome

Firefox

Производительность WASM довольно низкая по сравнению с JS-версией. Любопытно, что реализация этого сценария для Firefox намного превосходит реализацию для Chrome. В любом случае, очевидно, что в то, чтобы ускорить JavaScript внутри браузеров, было вложено много времени, усилий и денег. WASM — более современная технология, поэтому, возможно, в приоритете пока стоят корректность и возможность реализации, а не производительность.

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

На данный момент команда Kotlin/Native работает над новым бэкендом для компилятора WASM. Производительность во время выполнения не упоминается, но некоторые улучшения возможно внесут.

JWebAssembly

Я настроил и скомпилировал их образец HelloWorld. Согласно документации, выходные данные компилятора используют следующие функции:

bigint
mutableGlobals (самое важное)
referenceTypes (самое важное)
saturatedFloatToInt
signExtensions

На данный момент Chrome поддерживает не все из них, даже если включить экспериментальную веб-сборку в chrome://flags/. Стабильная версия Firefox поддерживает так же не все, поэтому мне пришлось тестировать программу в Firefox Nightly, который, согласно этим тестам, имеет необходимые функции:

К сожалению, во время выполнения HelloWorld упал со следующей ошибкой:

CompileError: wasm validation error: at offset 2219: bad type

Изучать проблему подробно я не стал, потому что, в конце концов, это двоичный файл, созданный компилятором в альфа-стадии и работающий в “ночной” сборке браузера.

TeaVM

Реализация WebAssembly TeaVM все еще экспериментальна и не имеет документации, однако давайте посмотрим, по крайней мере, работает ли JS-компилятор:

Chrome

Firefox

Не так быстро, как JS Kotlin/Native, но все равно неплохо. Мне не пришлось переводить свой Java-код ни в какой другой. Также, что очень полезно, для настройки проекта предоставляется архетип Maven. Я использовал этот:

mvn -DarchetypeCatalog=local \
-DarchetypeGroupId=org.teavm \
-DarchetypeArtifactId=teavm-maven-webapp \
-DarchetypeVersion=0.6.1 archetype:generate

Архетипы перечислены здесь.

Изучая вопрос, я нашел этот комментарий 2019 года от разработчика TeaVM, и он довольно интересен в отношении проблем, которые Java ставит перед WebAssembly.

Blazor

Еще один вариант для этого эксперимента, не связанный с Java, но всё же пришедший мне на ум — Blazor. Можно легко преобразовать Java-программу на C. Давайте посмотрим, сколько времени потребуется нативному порту C# на решение головоломки:

А как Blazor работает с WASM?

Chrome

Firefox

Производительность очень низкая как в Chrome, так и в Firefox, но в этом обсуждении объясняется, что сейчас Blazor использует неоптимизированный интерпретатор и чтобы можно применить компиляцию AOT, чтобы улучшить производительность.

Тестирование в таблицах

Java Native = 0,172 секунды.

C# Native — 0,295 секунды.

Заключение

Основываясь на вариантах, для которых я проводил сравнительную оценку, лучше всего транспилировать с Java на JavaScript, если производительность — главное, что вас беспокоит. Тем не менее, команды разработчиков проделывают с WASM большую работу, и можно надеяться, что в будущем разрыв в производительности сократится. Исходный код доступен здесь. Спасибо, что прочитали!