Java

Мне давно хотелось приступить к изучению 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 большую работу, и можно надеяться, что в будущем разрыв в производительности сократится. Исходный код доступен здесь. Спасибо, что прочитали!

Читайте также:

Перевод статьи: Roberto Vaccari, Porting a Java Sudoku solver to WebAssembly

Предыдущая статьяPython: 5 ошибок в применении охвата списка
Следующая статьяScrum мёртв. Восславим нового короля - Kanban!