Мне давно хотелось приступить к изучению WebAssembly, но никак не находилось подходящего материала. Однако недавно я просматривал некоторые старые программы и вспомнил, что как-то написал решатель судоку, который отлично подходил для этого эксперимента. И я поставил цель: перенести эту программу в WASM и провести тестирование производительности.
Решатель судоку
Первый шаг — рефакторинг и приведение оригинальной Java-программы в форму, чтобы добиться некоторой базовой производительности. Как обычно, всегда удивительно, насколько плох оказывается ваш код, когда вы возвращаетесь к нему спустя годы. ?
Программа-решатель использует обратный путь для решения головоломки. То есть программа будет использовать грубую силу для исследования всех возможных решений. На конкретном примере: программа поместит 1 в первую доступную ячейку (если при этом нигде не нарушены правила) и перейдет к следующей. По правилам игры еще одну 1 в следующую горизонтальную ячейку поместить уже нельзя, поэтому программа попытается вместо этого поместить в эту ячейку 2. Если программа наткнётся на такую ячейку, в которую нельзя поместить ни одну из девяти цифр, то она вернется назад и исследует другую ветвь решения. Для этого она очищает текущую ячейку и увеличивает значение в предыдущей ячейке на единицу. Этот процесс повторяется до тех пор, пока не будет найдено решение (все ячейки заполнены допустимыми значениями).
Многие обратные алгоритмы реализуются с помощью рекурсии, но в данном случае программа использует простой итеративный подход. И, наконец, бывает, что решение судоку с помощью обратного перебора занимает много времени, особенно для головоломок, подобных этой с Википедии:
| |
| 3 | 8 5
1 | 2 |
---------------------
| 5 7 |
4 | | 1
9 | |
---------------------
5 | | 7 3
2 | 1 |
| 4 | 9
В примере ниже программа должна пройти почти все возможные ветви, чтобы найти решение:
9 8 7 | 6 5 4 | 3 2 1
2 4 6 | 1 7 3 | 9 8 5
3 5 1 | 9 2 8 | 7 4 6
---------------------
1 2 8 | 5 3 7 | 6 9 4
6 3 4 | 8 9 2 | 1 5 7
7 9 5 | 4 6 1 | 8 3 2
---------------------
5 1 9 | 2 8 6 | 4 7 3
4 7 2 | 3 1 9 | 5 6 8
8 6 3 | 7 4 5 | 2 1 9
Чтобы избежать подобной ситуации, в решатель включен подготовительный шаг, на котором программа подсчитает, сколько подсказок доступно в верхней, средней и нижней части доски и временно переупорядочит клетки, чтобы больше подсказок сосредоточилось в верхней части. Как только решение будет найдено, первоначальный порядок восстановится. Можете просмотреть исходный код, если интересно.
Давайте запустим решатель
9 8 7 | 6 5 4 | 3 2 1
2 4 6 | 1 7 3 | 9 8 5
3 5 1 | 9 2 8 | 7 4 6
---------------------
1 2 8 | 5 3 7 | 6 9 4
6 3 4 | 8 9 2 | 1 5 7
7 9 5 | 4 6 1 | 8 3 2
---------------------
5 1 9 | 2 8 6 | 4 7 3
4 7 2 | 3 1 9 | 5 6 8
8 6 3 | 7 4 5 | 2 1 9
Solved in 0.172 seconds
Учитывая, что в основном мы применяем циклы, расчет происходит довольно быстро.
Kotlin/Native
Нам также понадобится JavaScript-версия решателя, чтобы провести сравнение с WASM-версиями. Kotlin/Native позволяет компилировать одну и ту же программу для разных целевых языков, включая JS и WASM, так что с него и начнем. Конвертировать Java в Kotlin с помощью IDEA легко и быстро (по меркам, конечно, такой маленькой программы).
plugins {
id 'org.jetbrains.kotlin.multiplatform' version '1.3.72'
}
repositories {
mavenCentral()
}
kotlin {
js {
browser {
webpackTask {
destinationDirectory = file("$buildDir/bin/js/bundle")
doLast {
copy {
from("$projectDir/src/jsMain/web") {
filesMatching("index.html") {
expand(project.properties)
}
}
into(destinationDirectory)
}
}
}
}
}
wasm32() {
binaries {
executable {
// Измените, чтобы указать полное имя точки входа именно для вашего приложения:
entryPoint = 'main'
}
}
}
sourceSets {
commonMain {
dependencies {
implementation kotlin('stdlib-common')
}
}
wasm32Main {
dependencies {
implementation(kotlin("stdlib-common"))
}
}
jsMain {
dependencies {
implementation(kotlin("stdlib-js"))
}
}
}
}
Как видите, Kotlin/Native, JS и WASM используют различные реализации стандартных библиотек, и в каждой из них у меня применились разные методы для подсчета затраченного времени.
Kotlin/Native — JS
Посмотрим сначала, как выполняется код на JavaScript:
<!DOCTYPE html>
<html lang="en">
<head>
<title>JS Sudoku Solver</title>
</head>
<body>
<h1>JS Sudoku Solver</h1>
<script src="./sudoku_kotlin.js"></script>
</body>
</html>
Chrome
Firefox
JS-версия медленнее нативной, но всё же выполняется довольно быстро, и даёт аналогичные результаты как в Chrome, так и в Firefox.
Kotlin/Native — WASM
HTML-файл, который я использовал для запуска WASM-версии:
<!DOCTYPE html>
<html lang="en">
<head>
<title>WASM Sudoku Solver</title>
</head>
<body>
<h1>WASM Sudoku Solver</h1>
<script wasm="./sudoku_kotlin.wasm" src="./sudoku_kotlin.wasm.js"></script>
</body>
</html>
Я использовал очень простой http-сервер для обслуживания файлов. Если хотите попробовать другой, просто убедитесь, что он поддерживает тип application/wasm
.
import http.server
import socketserver
PORT = 5000
class HttpRequestHandler(http.server.SimpleHTTPRequestHandler):
extensions_map = {
'': 'application/octet-stream',
'.manifest': 'text/cache-manifest',
'.html': 'text/html',
'.png': 'image/png',
'.jpg': 'image/jpg',
'.svg': 'image/svg+xml',
'.css': 'text/css',
'.js':'application/x-javascript',
'.wasm': 'application/wasm',
'.json': 'application/json',
'.xml': 'application/xml',
}
httpd = socketserver.TCPServer(("localhost", PORT), HttpRequestHandler)
try:
print(f"serving at http://localhost:{PORT}")
httpd.serve_forever()
except KeyboardInterrupt:
pass
Взглянем на результат:
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# на решение головоломки:
9 8 7 | 6 5 4 | 3 2 1
2 4 6 | 1 7 3 | 9 8 5
3 5 1 | 9 2 8 | 7 4 6
---------------------
1 2 8 | 5 3 7 | 6 9 4
6 3 4 | 8 9 2 | 1 5 7
7 9 5 | 4 6 1 | 8 3 2
---------------------
5 1 9 | 2 8 6 | 4 7 3
4 7 2 | 3 1 9 | 5 6 8
8 6 3 | 7 4 5 | 2 1 9
Solved 0.295 in seconds
А как Blazor работает с WASM?
Chrome
Firefox
Производительность очень низкая как в Chrome, так и в Firefox, но в этом обсуждении объясняется, что сейчас Blazor использует неоптимизированный интерпретатор и чтобы можно применить компиляцию AOT, чтобы улучшить производительность.
Тестирование в таблицах
Java Native = 0,172 секунды.
C# Native — 0,295 секунды.
Заключение
Основываясь на вариантах, для которых я проводил сравнительную оценку, лучше всего транспилировать с Java на JavaScript, если производительность — главное, что вас беспокоит. Тем не менее, команды разработчиков проделывают с WASM большую работу, и можно надеяться, что в будущем разрыв в производительности сократится. Исходный код доступен здесь. Спасибо, что прочитали!
Читайте также:
- Способы публикации библиотеки JavaScript: CDN, NPM, GitHub
- Замеры производительности на Java с JMH
- Основы программирования UDP-сокетов на Java
Перевод статьи: Roberto Vaccari, Porting a Java Sudoku solver to WebAssembly