Attempt at Compiling OR-Tools To WASM

[akevinge]

Why

• Would enable us to use the Maxflow algorithm in TS/JS
• Would allow for 0-latency validation in the browser

Issues

• OR-Tool maintainers won't add WASM for a long time (see: Add Wasm32 as target for cross compiling google/or-tools#2404)
• C++ dependency management might just be the devil himself

If there is a PR, why not just use the fork?

Trust me... I tried. For some reason, the fork only compiled the host tools such as Google's protoc to WASM.
This is what I tried:

export TARGET=wasm32 
export PROJECT=or-tools
./tools/cross_compil.sh build 

This only produced binaries (such as tests, samples, and host tools as mentioned before, in build/bin). The OR-Tools library itself gets compiled to a library file (.so or .a, see: static vs dynamic libraries). I'm not entirely sure why it does this, but you could try looking into how the fork uses emcmake and how emcmake works with CMake projects.

Ok fine, since it only produces WASM binaries, why not expose the bindings via sample files? If you're planning on attempting this, I would highly recommend trying this as a last resort. This method is quite janky and feels like a workaround (if it even works).

One thing that threw me way off is a Medium post, Kjartan - the creator of the fork, made.
See it here: https://12ft.io/medium.com/swlh/a-suduko-solving-serverless-endpoint-using-webassembly-and-or-tools-df9f7bb10044

This lead me to a PoC he made compiling OR-Tools to WASM: https://github.com/kjartanm/sudoku-solver
Awsome!! A working example!

Not so fast D:

How did he get the header files for OR-Tool dependencies in deps/include? OR-Tools does not produce these. How did he get the library files in deps/lib? He must have copied/manually downloaded them. If his fork should work, why did he do this?

We could also do this - manually build OR-Tools, copy the library files over, and download header files from its dependencies, but this would be terrible for maintainability. It would ruin the code transparency of Planner because OR-Tools would need to be built separately. You could write a script to manually copy them over, but that's even more jank.

It is definitely possible to output header files during the build. But whether it is worth a graph-only fork, understanding and modifying OR-Tools cmake files, and potentially destroying the maintainability of the validator is a question to stop and think on.

Summary

I tried

• The fork
• Importing and building OR-Tools from a different project to expose wasm bindings
• Getting OR-Tools to output dependency headers :/

If you're going to try this. I would highly recommend reexamining the fork.

Useful links:

• How to install dependencies during build: https://discourse.cmake.org/t/whats-the-best-way-to-include-headers-from-fetchcontent-deps/7047/2
• What is the fork? https://github.com/google/or-tools/pull/2404/files
• WASM support discussion: Feature request: A browser-friendly version of or-tools (emscripten) google/or-tools#2997
• Consuming OR-Tools from a different project: cmake support in the binary distribution google/or-tools#1440
• My graph-only fork: https://github.com/thekevinge/wasm-or-tools-max-flow/tree/graph-only

My findings after 14 hours. Forgive me for the typos. Gn ya'll 💤

[ZzRanger]

Thanks for looking into this! I think it was worthwhile to look into, but due to the difficulties you mentioned it might be best to revisit at a later point. If we ever look into trying to compile OR-Tools to WASM again, this will be a really helpful resource to start with. Please get some well deserved rest!

[akevinge]

DO NOT DO THIS. COMPILING OR-TOOLS TO WASM IS INSANELY DIFFICULT AND WILL BE IMPOSSIBLE TO MAINTAIN.

PLEASE USE Rust and rs-graph. Create wasm bindings on a library that uses rs-graph as a dependency. Compiling rs-graph to wasm directly does not work.

[akevinge]

(Accidentally put this comment on a different discussion previously)

I got the algo to compile to wasm but after talking to Eric and @ZzRanger today, I think the consensus was to keep it in Python.

Issues with using wasm

• What if there is a bug/patch that breaks the wasm build.
• The main selling point of our app is the mere existence of a degree planning tool. The validation is a bonus. Wasm is an unnecessary optimization
• it takes ~0.8s for current validation to run (excluding latency). This is acceptable
  if we wanted 0 latency, we could compile python to wasm. Again, ~0.8s validation is acceptable
• adding wasm means adding Rust to the code base - Rust that we don’t write but need to know how to maintain (keeping up to date w rs-graph and deleting everything except max flow)

If you think about the pros and cons, the debt we’d take in heavily outweighs the benefits.

[WillieCubed]

Just chiming in since I led the project in the beginning. I would slightly disagree that the main selling point of the app is the mere existence of a degree planning tool (since a spreadsheet with the templates for course breakdown by semester provided by each school can accomplish that) and would say the main selling point is having a tool that keeps track of edge cases and tell a student when they're not on a path to timely graduation. When the project was originally conceived, degree plan validation was something core to the experience.

To agree with you, as cool as Rust is, I would caution against adding a new programming language to the project's stack as it would be more difficult for Nebula Labs as a whole to maintain. As Donald Knuth once said, premature optimization is the root of all evil!

[akevinge]

Hi Willie, this is not a point of contention. While that previously may have been the theoretical selling point of the app, we realized that people appreciate the convenience of our drag and drop over all else. Just to clarify, our priority is user experience - not the validator. The validator is essential to the user experience but does not define it. The original intention of the project is irrelevant to creating the best product that we can.

[akevinge]

I also ended up looking at node-gyp thanks to Pelumi. The issue with that is we'd have to write a wrapper using NodeJS's addon API (which is in C++). It's not bad, but it's definitely harder to make and maintain than getting wasm to build.

I looked into rs-graph again in my free time and got it to work.

Bindings/Build: https://github.com/thekevinge/maxflow-wasm
Example: https://github.com/thekevinge/maxflow-wasm-example

Usage:

import { SimpleMaxFlow } from "./pkg/maxflow_wasm";

const smf = new SimpleMaxFlow();
const [SOURCE, SINK] = smf.add_nodes(2);

const [C1, C2] = smf.add_nodes(2);
const [R1, R2] = smf.add_nodes(2);

const test_arc = smf.add_arc_with_capacity(SOURCE, C1, 3);
smf.add_arc_with_capacity(SOURCE, C2, 3);

smf.add_arc_with_capacity(C1, R1, 1000);
smf.add_arc_with_capacity(C1, R2, 1000);
smf.add_arc_with_capacity(C2, R2, 1000);

smf.add_arc_with_capacity(R1, SINK, 3);
smf.add_arc_with_capacity(R2, SINK, 3);

const { max_flow, flow } = smf.solve_maxflow(SOURCE, SINK);
console.log(max_flow); // 6
console.log(smf.tail(test_arc)); // 0
console.log(smf.head(test_arc)); // 2