A Suduko Solving Serverless Endpoint Using WebAssembly and OR-Tools
In this article I will go through the process of
- Building an existing C++ library as WebAssembly
- Creating a WebAssembly application that links to this library
- Deploying the WebAssembly application as part of a serverless endpoint
The example I use is a Sudoku solver using Google OR-Tools for the solving part. There is an online demo of the result here: https://sudoku-solver.krmuller.workers.dev/. To be clear: Creating a Sudoku solver is not really the end goal here. Puzzles like Sudoku is kind of a “Hello World” in this context. It exemplify the use of powerful C++-based libraries being leveraged within a serveless setting. The GitHub-repo for the Sudoko solver can be found at https://github.com/kjartanm/sudoku-solver.
First a bit of background. Using WebAssembly can have different motivations: Speed is obviously one, consistent speed across environments another — since WebAssembly may not always be faster. But access to tools, applications, libraries and functionality that else would be hard to use is another important motivation. Also, WebAssembly has different usecases: on browser, on serverless, or even in gateways. Here I focus on access to otherwise hard to implement functionality in combination with serverless. That is a natural combination. When compiling stuff that was not at all meant for a browser, you risk getting filesizes that is huge — even compared to todays React-based js-bundles. Pushing that as part of your js-app could create unacceptable download times. Enabling that same functionality on serverless could then make sense.
Building OR-Tools as WebAssembly
I became aware of Google OR-Tools while researching technology for dealing with task management. OR-Tools is an extensive library for handling problems that falls within the discipline that is called “Operations Research”:
Operations research (OR) is a discipline that deals with the application of advanced analytical methods to help make better decisions (…) operations research arrives at optimal or near-optimal solutions to complex decision-making problems. (Wikipedia)
Typical OR-problems is scheduling, routing, work flows, critical paths etc. Problems with a lot of variables, hard and soft constraints, and potentially a range of possible solutions that needs to be prioritized.
The problems can be dealt with in a myriad of ways, using different techniques, methods and technologies. OR-Tools supports several of these by a mixture of own components and third party libraries. In addition OR-Tools include wrappers for Java, Python and C#. All in all it is a complex setup with a lot of dependencies.
I was looking for something I could use on the web. Since I also was looking into WebAssembly at the time, I thought I could see if it was possible to compile OR-Tools into Wasm. Being a novice of WebAssembly, having only rudimentary knowledge of C++, and being borderline clueless about OR, that sounded like a good idea :) Fortunately it turned out well!
But the start was bumpy. The usual way to compile existing libraries — as I gathered from the examples — would be to use Emscripten and its ‘make’-commands: emmake, emconfigure. The make process for OR-Tools has two steps, building the third-party dependencies first. Using emmake for the dependencies didn’t work well at all, and the main make process for OR-Tools is a very all-or-nothing for creating libraries, binaries, wrappers for Java and Python, examples, tests, etc. This is great for those who want to jump into it, but is hard to adapt for something else — at least for me with limited experience creating make-files.
The breakthrough was after reading this article about cross compiling (http://marcelbraghetto.github.io/a-simple-triangle/2019/03/10/part-06/), with a setup for using Emscripten.cmake. OR-Tools has an experimental cmake support, so I could adapt the Emscripten.cmake setup from the article for my own purpose. The first run(s) failed, but even so gave better feedback and showed lot more promise than using emmake directly. So I iterated on that, and in the end, I didn’t really have to change that much. Some small changes within the OR-Tools process, mostly turning things off that I didn’t really need, and some changes with two of the dependencies.
The OR-Tools cmake-process adapt the dependencies for its own purposes doing a patch after fetching them. So to do the needed changes, I used standalone versions of the dependencies in question, iterated on them until I got a Wasm-build, then created patches with the differences. The patches were added back into the OR-Tools repo for its cmake-process. The resulting build took a lot of time, but it actually worked! I compiled some of the examples using Emscriptens emcc, linking the output of the OR-Tools build, and they behaved as the should.
The changes I did was of the quick and dirty kind, so for now building OR-Tools as Wasm is just part of this fork (https://github.com/kjartanm/wasm-or-tools). But with that little changes, it should be totally possible to adapt the OR-Tools cmake process to add Wasm as an option in a proper way. But that is for someone more experienced with cmake than myself at the moment.
Update: The repo have been cleaned up a bit, making it less hacky.
Creating an WebAssembly application using OR-Tools
OR-Tools comes with a lot examples illustrating different methods and techniques. This Sudoku solver is based on a Java example in the contributor section of the examples. But ported to C++ and adapted for integration with JavaScript. The solver uses something called Constraint Programming, where “ users declaratively state the constraints on the feasible solutions for a set of decision variables”. In the Sudoku solver this is done in just a few steps. First the solver sets up the variables:
std::vector<std::vector<IntVar *>> grid = {
{}, {}, {}, {}, {}, {}, {}, {}, {}};
std::vector<IntVar *> grid_flat;for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
std::ostringstream varname;
varname << "grid[ " << i << "," << j << "]";
IntVar *nr = solver.MakeIntVar(1, 9, varname.str());
grid[i].push_back(nr);
grid_flat.push_back(nr);
}
}
This is the well known 81 variables with numbers from 1–9 arranged in a grid (the solver use both a flat and a 2d version of the grid for convenience ).
Then we add the constraints:
for (int i = 0; i < n; i++)
{
std::vector<IntVar *> row;
for (int j = 0; j < n; j++)
{
if (sudoku_flat[i * n + j] > 0)
{
solver.AddConstraint(solver.MakeEquality(grid[i][j], sudoku_flat[i * n + j]));
}
row.push_back(grid[i][j]);
}
solver.AddConstraint(solver.MakeAllDifferent(row));
}Here we add constraints for the rows. The first AddConstraint says that if we already have a value from the original problem, the variable should be equal to this value. The other says all variables in a row should be different. Constraints for columns and the 3x3 cells is declared in the same way.
After defining variables and setting the constraints, we initiate a solver and execute a search for solutions:
DecisionBuilder *db = solver.MakePhase(
grid_flat,
solver.INT_VAR_SIMPLE,
solver.INT_VALUE_SIMPLE
);
solver.NewSearch(db);
if (solver.NextSolution())
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
sudoku_flat[i * n + j] = (int)grid[i][j]->Value();
}
}
}
solver.EndSearch();In this case we write the solution back into the orginal array which is already referenced by the JavaScript integration.
The application is compiled using the following script:
docker run --rm -v $(pwd):/src emscripten/emsdk \
emcc \
-O3 \
--bind \
--no-entry \
-s EXTRA_EXPORTED_RUNTIME_METHODS='["getValue"]' \
-s ALLOW_MEMORY_GROWTH=1 \
-s DYNAMIC_EXECUTION=0 \
-s TEXTDECODER=0 \
-s MODULARIZE=1 \
-s ENVIRONMENT='web' \
-s EXPORT_NAME='emscripten' \
--pre-js './pre.js' \
-lm \
-s ERROR_ON_UNDEFINED_SYMBOLS=0 \
-I deps/include \
-L deps/lib \
-lglog \
# Rest of libs removed from the example, ca 90 in total
-o ./build/module.js \
./src/sudoku.ccI will not go into details here. Most of these settings comes from the Cloudflare Emscripten-template. See here https://emscripten.org/docs/tools_reference/emcc.html#emccdoc and here https://github.com/emscripten-core/emscripten/blob/master/src/settings.js for added details. What I have changed/added is emscripten/emsdk as docker image instead of the deprecated trzeci/emscripten that most examples usually references. I also added —-bind since I’m using Emscripten’s Embind for integrating WebAssembly with JavaScript. —-no-entry says that the module doesn’t have any main() that can be called, and -I deps/include and -L deps/lib is where to find the dependencies. I haven’t included every or-tool library here, since there is around 90 of them. But the repo has the full script.
Integrating with JavaScript on serverless endpoint
The setup for the serverless endpoint is as following:
- First it receives the Sudoko problem as a flat array in JSON as a POST request
- It sets up a Wasm-instance with the Sudoku solver
- It loads the problem-array into instance’s memory
- Then it calls instance.solve with the pointer for the array
- Finally it reads back the solution from the instance’s memory into an array that it returns as JSON to the client.
I wanted to use Cloudflare Workers for this example. They seems to emphasize the possibilities with WebAssmbly, and I wanted to test the experience. That has mostly been positive, even if they need to update their template for emscripten. But it should be very easy to adapt this example to other serverless platforms as well (or add it to a SPA). The main work is done in a single method that is called by the function handling the request:
let instance = null;
const solve = async sudokuArray => {
if(!instance) {
instance = await emscripten_module;
}
const I32_SIZE = 4;
const sudokuPtr = instance._malloc(sudokuArray.length * I32_SIZE);
instance.HEAP32.set(sudokuArray, sudokuPtr / I32_SIZE);
instance.solve(sudokuPtr); for (let v = 0; v < sudokuArray.length * I32_SIZE; v += I32_SIZE) {
sudokuArray[v/I32_SIZE] = instance.getValue(sudokuPtr + v, 'i32')
}
instance._free(sudokuPtr);
return new Response(JSON.stringify(sudokuArray), { 'status': 200, 'content-type': 'application/json' });
}
When passing arrays to a Wasm-function you will have to load it into the memory for the Wasm-instance and pass the pointer in the function call. In the same way you can’t return an array, but must pass a pointer. Since the Wasm-solver writes the result back to the same memory space, we can just use the same pointer here.
Emscripten has a lot of helpful functionality for dealing with stuff like this. The most important thing is to remember that the memory is one single ArrayBuffer, and it is easy to overwrite stuff by accident. For example, instance.HEAP32 and instance.HEAPF64 is just two views of the same array buffer, so it is important to keep track of nr of bytes with the different types when addressing and allocating memory, and keep within the allocated space. See https://becominghuman.ai/passing-and-returning-webassembly-array-parameters-a0f572c65d97 for a more thorough discussion about passing/receiving arrays with Wasm.
For the integration to work this way, two methods needs to be added to the Emscripten instance: getValue is added by the EXTRA_EXPORTED_RUNTIME_METHODS setting in the build script (see above). solve is added by using Embind to bind the C++ function to its JavaScript counter part:
int solve(int sudoko_ptr)
{
int *sudoku_flat = (int *)sudoko_ptr;
operations_research::solve(sudoku_flat);
return EXIT_SUCCESS;
}EMSCRIPTEN_BINDINGS(module)
{
function("solve", &solve);
}
Since we can’t pass the pointer directly as a pointer in Embind at the moment, I pass it as int and cast it as pointer before processing it further. When the call to Wasm returns, the JavaScript-part can read back the solution array from memory.
One concern with using OR-Tools on serverless is that processing time can grow real fast with increased complexity of the problems. Cloudflare has a 10 ms CPU time capping on a request on their free plan, and 50 ms on their bundled plan. 50 ms is more than enough to solve tough Sudoko problems, but not for more advanced OR-problems. But they are now testing a new Unbound plan in a beta-program that are without this capping, and hopefully the pricing will be acceptable also for complex OR-Tools-applications. On other platforms, this will count against general timeout settings — like 10 seconds on Vercel.
Concluding remarks
The possibility of leveraging complex functionality in serverless through WebAssembly and libraries like OR-Tools represent a huge opportunity, I think. It is early days yet, but I see promise in this area with companies like Cloudflare, and for example Fastly who are putting Wasm directly on endpoints without the need of being instantiated by JavaScript (https://www.fastly.com/blog/announcing-lucet-fastly-native-webassembly-compiler-runtime). Experiments like this Sudoku solver have been very encouraging so far, and this is absolutely something I look forward to explore further.
