Running Java in Node.js with WebAssembly

Hello, everyone. Welcome to my talk on running Java in Node.js with WebAssembly. I'm Brendan. I'm currently a research engineer at Expo, but before that, I worked on developer tools for CloudFloat workers.

So, before we begin, why would you want to do this? Many organisations have a lot of Java code, and as they adopt newer technologies such as Node.js or CloudFloat workers, maintaining interoperability with this existing code becomes important. Additionally, lots of interactive web experiences used to be powered by Java, but modern browsers block Java applets, so lots of sites no longer work. It would be nice if we didn't have to rewrite everything.

Let's start from the basics. This is a simple Java program that prints to the console. You compile it with the Java compiler that produces a class file and you can run it with the Java command. Java here is a runtime, which is slightly different from C and Go programs, where you're compiling for a specific architecture. As I mentioned, this runtime is the Java virtual machine, which takes these class files, which are portable and platform-independent, containing JVM instructions as opposed to architecture-specific instructions, and then runs them. The important thing here is that it doesn't have to be just Java. You can compile other languages like Scala and Kotlin to the same JVM bytecode as well.

The JVM is a stack machine, so let's have a quick look at what that looks like for this simple add program. So, the parameters to the function are stored as locals, and we start the first instruction, which pushes a local onto the stack, we move on to the next instruction, and then this add instruction pops two values off the stack, adds them together, and then pushes the result back onto the stack.

As I mentioned, the JVM provided a very portable runtime. You used to be able to run applets in browser via a plugin. Browsers started to disable applets, they introduced this thing called Java Web Start instead, but we've still got lots of, like, not very nice security warnings here. You still have to install the Java runtime, and it wasn't built into browsers. Nowadays, of course, we do all of this interactive stuff with JavaScript instead, and JavaScript engines are becoming very powerful. So, modern JavaScript engines will use just-in-time compilation. This is a simplified pipeline of Chrome's V8 engine. So, what happens is you first interpret the JavaScript and then you observe what types functions are called with on a frequent basis, and then you generate optimized code as a result of that. With all of these, sort of, efficient JavaScript engines, it becomes possible to potentially run other languages in the browser as well using the same engine.

So, there was this thing called Asm.js, which was designed as a compilation target for other languages. It was an extremely optimizable subset of JavaScript, and browsers that didn't support this Asm.js thing could still treat it as regular JavaScript and run it without, like, additional runtime. And what people found is when, like, you compiled C programs to this optimizable subset, you could usually, sort of, get near native performance with still, sort of, integrating with JavaScript. But there was more that could be done here. So, this is where WebAssembly comes in.

WebAssembly is a stack machine-based thing, like the JVM, but with a different instruction set. So, it's typed, so it's highly optimizable, but it improves over Asm.js with this new binary format, and it also supports streaming compilation as well, and modern CPU features like SIMD and 64-bit integers.

WebAssembly has two interchangeable formats. You've got the binary format on the left and this human-readable text format on the right. And in all future examples, we're just gonna use the text format because it's much easier to read.

So, if we go back to the pipeline, because we now know these types ahead of time, we can go straight to the optimized machine code. So, we don't have to, like, watch the executions and see what's going on first. WebAssembly runs everywhere these days. So, browsers, of course, Node.js, other JavaScript runtimes on the server, like CloudFlow Workers and all that, and embedded runtimes as well, so you can sort of run it within your Rust or Go programs or whatever. Yeah. So, that's what this project is going to be about. We're going to be compiling JVM bytecode to WebAssembly so that Java or any other JVM targeting languages can run Node.js or the browser or anywhere else that supports WebAssembly.

So, now that we've had a quick look at the history, let's look at what these class files actually look like. So, if we go back to the simple compilation example, what does this hello.class file contain? A binary mess. We can see the names of some other class names, but, yeah, that's not very useful. So, class files themselves are packaged into jar files, and each class file looks something a bit like this, where you've got this constant pool, you've got some metadata, you've got some fields, and you've got the actual code itself.

The methods each have a sort of method descriptor which describes the types of the inputs and the outputs. So, we've got this sort of the types of parameters in the brackets and then the return type afterwards. And the primitive Java types map to these little letters, so, like, byte is B, char is C, long is J, of course, and so on.

So, now that we can parse these class files, let's talk about compiling and calling functions with them. So, we've got the method descriptors, we've got the byte code. So, we can start transforming it to WebAssembly. To do this, we can just pattern match on the descriptors that we've parsed earlier and convert them to WebAssembly types, and similarly for instructions, we can just take the JVM instructions and convert them to WebAssembly. This is going to be really easy. And that's kind of all we need for basic compilation. When you've got this, to run it, you can just wrap it with a WebAssembly module, and then you can export it, and then we've got this text format which we can't actually run, so we convert it to the binary format, and we get this Node.js code, which is super nice, because we just have to read the file, we can compile that into a WebAssembly module, instantiate it, and call its exports.

So, we can also call the function from within WebAssembly, which is nice, but hang on a minute, we've got a first problem. Java lets you do method overloads, where you can have the same method, the same name, but just, like, different parameters instead. And we can kind of implement this in WebAssembly. We can just stick the method descriptors on the function names and treat them as separate functions. That works, that's fine. But there's a little subtlety here. In, even though we're adding two of the same things, in the integer example, the second integer is loading from index one, and in the double example, the second double is loading from index two. This is kind of a quirk of how Java's storing these locals. So, Java treats locals as four byte word slots, and ints are one word each, doubles are two words, and the problem is that WebAssembly expects single typed values for locals. So, when you create a local in WebAssembly, you have to define its type ahead of time, and it can only ever be that type. This gets even more complicated, because if we take this, like, example here, the local slots get reused if the variables go out of scope. So, a single word is referenced as an int, and the first half of a double in the same function. This is definitely not allowed in WebAssembly.

This gets even more complicated, because if we take this, like, example here, the local slots get reused if the variables go out of scope. So, a single word is referenced as an int, and the first half of a double in the same function. This is definitely not allowed in WebAssembly.

So, the solution here is that we can remap WebAssembly locals. What we can do is for each unique JVM index and type pair, we can create that pair as its own local instead.

Compiling functions is great, but almost all programs will have some conditional logic to you. This is an example program with an if statement. What we're doing here is returning true if the value is greater than two. Probably wouldn't write something like this, but we can see the corresponding Java byte code on the right-hand side.

So, let's walk through an example execution of this function where the value is three. So, we've got the parameter in local zero, and we've got the result value in local one. So, we've reached this point in the execution where we've hit this if integer compare less than or equal to instruction, and we have to evaluate whether three is less than or equal to two. So, that's not the case, so we're not going to take this jump. Instead, we just continue on to the next instruction, and we store true in the result. If we go back, and instead the value that we pass to the function is one, then we do want to take this branch, so we move forward five instructions and we jump past the if statement.

The problem is that WebAssembly has no gotis, so we can't implement this kind of jumping base branching. Instead, WebAssembly needs structured control flow. So, this basically means just like regular if statements that you'd see in JavaScript. So, in order to take this JVM byte code and convert it to this, we need to recover the if statement somehow.

Let's look at a more interesting example. So, this has some nested if statements and some pretty interesting control flow. So, for analysis, a control flow graph is very useful. A control flow graph is basically each node is an instruction, and you have an edge if one instruction leads to another. We can group instructions with no intermediate control flow into basic blocks. This doesn't affect the results of the analysis, it just makes it more efficient and it's also much easier to see what is going on as well.

So, when we're recovering if statements, what we're interested in is finding the headers of those if statements, where they start, and then the follow nodes where the branches join back together. We want to allow nested statements as well. Let's go through some definitions. Node A dominates B if control must pass through A before reaching B. Node A strictly dominates B if A dominates B and A is not equal to B.

And then node A is the immediate dominator of B if A strictly dominates B, but doesn't dominate any other strict dominator of B. So, that's a bit of a word soup. But basically, immediate dominator is the closest strict dominator. So, in this example, the immediate dominator of node 5 would be 0. To actually recover the follow nodes, we have this algorithm here, which traverses the graph in reverse, depth first post order.

So, nested structures are handled first. We have this set of unresolved nodes, which is the two-way header nodes for which we haven't yet found a follow node, and we say that the follow node is the maximum node with two plus in edges that has a header as the immediate dominator. If we found it, we mark all unresolved nodes with that follow to, and if not, we add it to the unresolved set. And using this algorithm, we end up with enough information to reconstruct the original if statements. The resulting web assembly would look something like this.

As before, the branching instructions, if you hit an if statement, you take the branch if the top of the stack is non-zero. So, that works great for most conditionals, but Java also has these short circuit conditionals as well. You'll see this in JavaScript as well. And B isn't evaluated if A is false. This produces a control flow graph that looks something like this, and what we have here is something called unstructured or irreducible control flow.

If we wanted to apply similar logic to what we just did before, we may need to duplicate block two. Instead, we can look for patterns in these, what these short circuit conditionals produce, and then we can repeatedly apply rewrites to the graph until we have no more changes. And WASM lets us treat if statements as expressions as well. So, you can sort of return values from branches, and then after evaluation, the sort of the stuff I've got on bold here will collapse to a single stack value, and then we can use that for branching on instead. And that will let us produce these short circuit conditionals.

Okay, so in addition to conditionals, most programmers will have loops as well. So, the defining characteristic of a loop in a control flow graph is a back edge. So, this is an edge to the same or an earlier point in the graph. Each back edge corresponds to a loop. We have two different types of loops. We have pre-tested loops, these are like your traditional while loops, and we have post-tested loops, which are like do-while loops.

To recover loops from our control flow graphs, we need this sort of derived sequences of tuples, of graphs and their intervals. So, we say that the nodes of graph I are the intervals of the previous graph, and we add edges to graph I if there exists an edge between intervals of the previous graph. And we keep repeating this until we've got no changes, and this produces the sequence of tuples. So, this is an example sequence that we've got here. 0 is our original graph, 1 is after one iteration, and then 2 is after the second iteration. And we've reached a trivial graph at the end. If we hadn't reached a trivial graph with just a single block, we would say that we have irreducible flow. And again, we've got this algorithm where we can, for each of these tuples in the derived sequence, we can look at each interval, look for the back edge in the same interval, and then we've got, we can work out which is the header and the latching node, and then based on some patterns, we can work out what the type of the loop is, and then we can work out the follow node, based on whether it's a pre or post-tested loop. To actually implement these types of loops, Wasm gives us two other block types. So, block behaves like break statements, loop kind of behaves like continue statements when you branch to them, and then using these two different things, we can implement pre and post-tested loops. Finally, we're missing something important.

So, this is an example sequence that we've got here. 0 is our original graph, 1 is after one iteration, and then 2 is after the second iteration. And we've reached a trivial graph at the end. If we hadn't reached a trivial graph with just a single block, we would say that we have irreducible flow.

And again, we've got this algorithm where we can, for each of these tuples in the derived sequence, we can look at each interval, look for the back edge in the same interval, and then we've got, we can work out which is the header and the latching node, and then based on some patterns, we can work out what the type of the loop is, and then we can work out the follow node, based on whether it's a pre or post-tested loop.

To actually implement these types of loops, Wasm gives us two other block types. So, block behaves like break statements, loop kind of behaves like continue statements when you branch to them, and then using these two different things, we can implement pre and post-tested loops. Finally, we're missing something important. Java is an object-oriented language, so we need objects too. Before we can talk about objects, we need to talk about program memory. So, program memory is usually split up into two sections, the stack made of local variables living for the lifetime of a function call, and the heap, which is an unorganized pile of objects living for the lifetime of the program. The stack contains references to objects on the heap, and so WebAssembly, if we want a heap, we can use the linear memories, and this here creates a memory which is 64 KB in size.

Let's look at a simple class with two fields. We've got integer field and we've got a double field. The integer fields will occupy four bytes and the doubles will occupy eight bytes. The fields are stored continuously in our memory.

When we create a new instance of the object, we allocate space for it, and there are lots of different allocation strategies, but to start with, we can implement a bump allocator. So, this has a global next pointer, and when you allocate a specific size, we add that size to the global next pointer and return the original pointer. There's no garbage collection here, we just keep on allocating, keep on allocating.

We can use this with our adder class, so we know the size of the adder is going to be 12 bytes, so we just create a constant on the stack and then call our allocation. What if we want to add instance methods, though? So, we have this add method here which adds the two fields together, and it produces the following byte code, but what is this, like, a load zero thing? So, this is loading the implicit this parameter, which you might have seen in, like, other languages like Python itself. In Java, you don't actually have to write it, but it's always there.