I’ve been wanting to explore WASM for a while, but I couldn’t find a good candidate to do it. However, I was recently going through some old programs and remembered that I once coded a Sudoku solver that might be a decent option for this experiment. So the objective was to port the program to WASM and do some performance testing.

Sudoku solver

The first step was refactoring and getting the original Java program in shape in order to have a performance baseline. As usual, it’s always surprising how bad your code is when you come back years later. 😉

The solver uses backtracking to solve the puzzle. This means that the program will use brute force to explore all branches of the solution space. Basically, it will place a 1 in the first available cell (if there are no rule violations) and move to the next one. Trying to place another 1 on the next horizontal cell will trigger a violation so the program will attempt to place a 2 in that cell instead. If a cell is found where none of the 9 digits can be placed, then it has to go back and explore another candidate solution branch. To go back, it clears the current cell and increments the previous cell by one. This process is repeated until a solution is found (all cells have valid values).

Many backtracking algorithms are implemented using recursion, but in this case the program uses a simple iterative approach.

Finally, there are some cases in which solving Sudoku using backtracking can take a long time, especially for puzzles such as this one found on Wikipedia:

      |       |      
      |     3 |   8 5
    1 |   2   |      
---------------------
      | 5   7 |      
    4 |       | 1    
  9   |       |      
---------------------
5     |       |   7 3
    2 |   1   |      
      |   4   |     9

As you can see in the solution below, the program has to go through almost all possible branches to find a solution (the first row is 9, 8, 7, 6, 5, 4, 3, 2, 1).

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

In order to avoid this situation, the solver includes a preliminary step in which it will count how many hints are available in the upper, middle and bottom part of the board and it will temporarily reorder it to have the most hints in the upper part. Once the solution is found the original order is restored.

You can check the source code if you are interested.

Let’s run it

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

Considering that we are mostly doing loops it looks reasonably fast.

Kotlin/Native

We also need a JavaScript version of the solver in order to make comparisons with the WASM versions. Kotlin/Native allows you to compile the same program to different targets including JS and WASM, so it seemed like a good option to start the journey. It’s quite easy to convert Java to Kotlin using IDEA and this step was quite fast (for such a small program of course).

Kotlin MPP

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 {
                // Change to specify fully qualified name of your application's entry point:
                entryPoint = 'main'
            }
        }
    }

    sourceSets {
        commonMain {
            dependencies {
                implementation kotlin('stdlib-common')
            }
        }

        wasm32Main {
            dependencies {
                implementation(kotlin("stdlib-common"))
            }
        }

        jsMain {
            dependencies {
                implementation(kotlin("stdlib-js"))
            }
        }
    }
}

As you can see in Kotlin/Native, JS and WASM use different standard library implementations. Surprisingly, for my specific case, the methods for getting the elapsed milliseconds were different in each standard library.

Kotlin/Native - JS

Let’s see how the JS version performs first.

<!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 chrome_js

Firefox firefox_js

The JS version is slower than the native version, but it’s still quite fast and both Chrome and Firefox provide similar results.

Kotlin/Native - WASM

This is the HTML file I used to run the WASM version.

<!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>

I also used a very simple http server to serve the files. If you want to try another web server, just make sure that it supports the application/wasm mime type.

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

Let’s take a look at the results.

Chrome chrome_js

Firefox firefox_js

As you can see, WASM’s performance is quite bad compared to the JS version. Interestingly enough, Firefox seems to have a much better implementation than Chrome for this particular scenario. In any case, it’s clear that a lot of time, effort and money has been invested into making JavaScript fast in the browser. On the other hand, WASM is newer technology and correctness and feasibility might have been prioritized over performance so far.

I’m not sure why, but the WASM binary produced in Release mode crashed, so keep in mind that the results above are for the Debug version.

Finally, the Kotlin/Native team is working on a new WASM compiler backend. Performance at runtime is not mentioned explicitly, but there might be some improvements.

JWebAssembly

I managed to setup and compile their HelloWorld sample. According to the documentation, the compiler output uses these features:

  • bigint
  • mutableGlobals (most important)
  • referenceTypes (most important)
  • saturatedFloatToInt
  • signExtensions

At this moment Chrome does not support all of them even if you enable Experimental WebAssembly in chrome://flags/. Firefox stable does not support all of them either. So I had to test the program using Firefox Nightly, which according to this tester has the necessary features:

Firefox Nighly

Unfortunately, the HelloWorld crashed at runtime with the following error:

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

I didn’t spend much time investigating the issue because after all it’s a binary produced by a compiler in alpha stage and running on a nightly browser.

TeaVM

TeaVM’s WebAssembly implementation is still experimental and not documented. However, let’s see at least if the JS compiler works.

Chrome TeaVM

Firefox TeaVM

Not as fast as Kotlin/Native’s JS but still good. The positive part is that I didn’t need to translate my Java code to anything else. The fact that they provide a Maven archetype to setup the project was also useful (I used the first one listed here).

While researching, I found this 2019 comment from a TeaVM developer and it’s quite interesing regarding the challenges that Java poses for WebAssembly.

Blazor

This is clearly not Java related, but another option that came to mind for this experiment was Blazor. Converting a Java program to C# is not difficult, so let’s see how much time it takes for the native C# port to solve the puzzle.

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

And now let’s see how Blazor performs using the WASM option.

Chrome chrome_js

Firefox firefox_js

The performance is very bad both in Chrome and Firefox, but this thread explains that at the moment Blazor is using an unoptimized interpreter and that performance should increase significantly once AOT gets implemented.

Summary

Java Native = 0.172 seconds

VersionChrome (seconds)Firefox (seconds)
Kotlin/Native JS0.3700.361
TeaVM JS0.5320.571
Kotlin/Native WASM10.7152.932
Smaller is better

C# native = 0.295 seconds

VersionChrome (seconds)Firefox (seconds)
Blazor WASM15.52412.004
Smaller is better

Final thoughts

Based on the options I’ve evaluated, transpiling from Java to JavaScript is the best option if your main concern is performance. However, there is work been done on WASM by different teams and hopefully the performance gap will be reduced in the future.

If you are interested, the source code is available here.

Thanks for reading!