4 ms·

WASM is not quite a stack machine

183 points by signa11 6mo ago

stevefan1999 6mo ago
I'm trying to implement a WASM to C compiler, and because of that not-quite-so-stack behavior, I can actually guarantee that it will always build an expression and I don't have to discard or reset stack value! Everything stays within that function, which is very neat, and I think it is one of the reason WAT, the textual format is so neat, that you can represent it with a S-Expression.
- jedisct1 6mo ago
  Compiling WASM to C is a really good option: https://00f.net/2023/12/11/webassembly-compilation-to-c/ https://00f.net/2023/12/11/webassembly-compilation-to-c/
  - ncruces 6mo ago
    Shameless plug… compiling it to Go is a great option too: https://github.com/ncruces/wasm2go https://github.com/ncruces/wasm2go I've used it to translate SQLite (with a few extensions) and, that I know of, it's been used (to varying degrees of success) to translate the MARISA trie library (C++), libghostty (Zig), zlib, Perl, and QuickJS. More on-topic, I use a mix of an unevaluated expression stack and a stack-to-locals approach to translate Wasm.
    - lukevp 6mo ago
      Does that mean you could compile a wasm program to go, then run it with wazero? How many levels deep can it go?? Might be a fun blog topic :)
      - ncruces 6mo ago
        Not very deep. Go generates large Wasm modules, because it bundles its goroutine scheduler, garbage collector and standard library into the module. Translating that back to Go will give you a pretty big Go file. Go is "known" for being fast to compile, but that huge Go file will take (at least?) as long to compile as compiling the Go toolchain does. wasm2go is best used on moderately sized modules (like SQLite). Last I heard, the person who tried to translate Perl got a 80MB Go file that was taking them 20min to compile. https://github.com/ncruces/wasm2go/discussions/15 https://github.com/ncruces/wasm2go/discussions/15
    - nu11ptr 6mo ago
      Interesting. I started working on this same idea a couple of years ago as a way to bypass CGo. Eventually I moved on to something else. Glad someone else is working on this. How does the generated Go performance compare to the original WASM performance?
      - ncruces 6mo ago
        That's going to depend on what you mean for "original Wasm performance". What were you using to run Wasm instead of this? I can compare with wazero, which I was previously using, and say performance stayed mostly in the same ballpark. Things that crossed the Go-to-Wasm boundary very often became much faster, things that stayed mostly in Wasm became slightly slower, as the wazero compiler is pretty good. wasm2go also does not support SIMD, so if your Wasm module uses/benefits from SIMD, you'll notice.
- bsder 6mo ago
  But how do you handle arguments or loop index variables? Your liveness is the entire function? You have to compile all the WASM chunks together in order to do any optimization? That seems ... problematic. Edit: Yep. In article referenced from the original: http://troubles.md/posts/wasm-is-not-a-stack-machine/ http://troubles.md/posts/wasm-is-not-a-stack-machine/ Double edit: Some of this has already been fixed in WASM: https://github.com/WebAssembly/multi-value https://github.com/WebAssembly/multi-value
- rogerbinns 6mo ago
  Check out wastrel https://codeberg.org/andywingo/wastrel https://codeberg.org/andywingo/wastrel Of note WASM 3 has garbage collection (GC), multi-memory, exception handling, tail calls and more which can be challenging to implement.
kg 6mo ago
The lack of a dup opcode in Wasm as mentioned in the post is quite annoying when trying to generate compact code. I wish something like it had made it into the spec.
- thomasmg 6mo ago
  You could use "local.tee". It is kind of is "store" + "duplicate".
  - asibahi 6mo ago
    `local.tee` doesn't duplicate. it just doesn't remove the value from the stack. (so it is "just" `local.set` followed by `local.get`)
    - thomasmg 6mo ago
      Sure. But it does save you one instruction: "tee", "get" instead of "set", "get", "get".
ufo 6mo ago
The author seems to complain about a lack of stack manip expressions like dup and rot, but at least for me that's what I would expect from an average programming language stack machine. Even Java, which does have those instructions, doesn't use them --- reuse happens via local variables. The way I see it, the difference between register and stack vms is all about the instruction encoding. Register VMs have fatter instructions in exchange for needing fewer LOAD and STORE operations. Despite the name, register VMs also have a stack.
- U1F984 6mo ago
  Java does use dup in some cases, e.g. public static void test() { new Object(); } 0: new #2 // class java/lang/Object 3: dup 4: invokespecial #1 // Method java/lang/Object."<init>":()V 7: pop 8: return
  - asibahi 6mo ago
    This `dup` seems entirely useless it actually supports the case for omitting it fron the instruction set.
    - layer8 6mo ago
      The only reason it is useless in this (arguably ill-chosen) example is because the result of “new Object()” is not used (hence the pop), which is an uncommon case. If test() instead returned the new object, or would use it in some other way after the initialization, then the dup would be needed. Invokespecial consumes the object reference on the stack, hence if you want to use it after invokespecial, you have to copy or duplicate it before.
- pjjpo 6mo ago
  > Despite the name, register VMs also have a stack. Out of curiosity what do you think about this - in spite of the name, stack machines also have yet another stack. Ok I don't like that wording, but locals are basically the stack frames people know of from their computer arch class I think. It doesn't change the fact that Wasm operations have to have the execution stack as one or more of the operands. Seems like a stack machines to me too, though I don't know more details on why the specific design of Wasm would make optimizing compilers harder to write than JVM as the article suggests (I think?).
Hendrikto 6mo ago
The series of articles linked at the end (troubles.md/posts/wasm-is-not-a-stack-machine/) is even more interesting, imo. Very well articulated and concise critique by somebody who seems to have a great amount of knowledge and experience with the topics.
asibahi 6mo ago
I dont really disagree with the main premise of the article, which is that WASM is not really a stack language, but this part just gave me pause: > In textual Wasm, for example, they are instead represented in a LISP-like notation – not any less or more efficient The Text format, at least when it comes to instructions, it 1 to 1 with the binary format. The LISP-like syntax is mainly just syntax sugar[1]. ‘(’ plaininstr instrs ‘)’ ≡ instrs plaininstr So (in theory, as far as I understand it) you can just do `(local.get 2 local.get 0 local.get 1)` to mean `local.get 0 local.get 1 local.get 2`, and it works for (almost) any instruction. Unfortunately, in my limited testing, tools like `wat2wasm` and Binaryen's `wasm-as` don't seem to adhere to (my perhaps faulty understanding of) the spec, and demand all instructions in a folded block be folded and have the "correct" amount of arguments, which makes Binaryen do weird things like (return (tuple.make ;; Binaryen only pseudoinstruction (local.get 0) ;; or w/e expression (local.get 1) ;; or w/e expression ) ) when this is perfectly valid local.get 0 local.get 1 return tl;dr: the LISP syntax is just syntax sugar. The textual format is as "stack-like" as the binary format. Edit: An example that is easily done with the stack syntax and not with lisp syntax is the following: call function_that_returns_multivalue local.set 2 ;; last return local.set 1 ;; local.set 0 ;; first return In LISP syntax this would be (local.set 0 (local.set 1 (local.set 2 (call function_that_returns_multivalue ( ;; whatever input paramters ))))) I have not yet tried this with Binaryen but I doubt it flies. [1]: https://webassembly.github.io/spec/core/text/instructions.html#folded-instructions https://webassembly.github.io/spec/core/text/instructions.ht...
- soegaard 6mo ago
  FWIW if you are looking for examples of WebAssembly written in the textual format, take a look at: https://raw.githubusercontent.com/soegaard/webracket/refs/heads/main/runtime-wasm.rkt https://raw.githubusercontent.com/soegaard/webracket/refs/he... As a small example, here is a definition of `$car` which extracts the first value from a pair. (func $car (type $Prim1) (param $v (ref eq)) (result (ref eq)) (if (result (ref eq)) (ref.test (ref $Pair) (local.get $v)) (then (struct.get $Pair $a (ref.cast (ref $Pair) (local.get $v)))) (else (call $raise-pair-expected (local.get $v)) (unreachable))))
shevy-java 6mo ago
I am sad about WASM. It was a promise for epic greatness. It has failed to deliver that - so much is clear now. You rarely see any awesome success story shown with regard to WASM nowadays. What happened to the old promises? "Electron will be SUPER fast thanks to WASM" or "use any language, WASM unifies it all for the larger browser ecosystem". It feels as if WASM is on a step towards exctinction. Sure, it is mentioned, it is used, but let's be honest - only few people really use it. And that won't change either.
- thomasmg 6mo ago
  Well there is Google Sheets, Microsoft Office, Figma, and some other heavier web apps.
- purplesyringa 6mo ago
  There used to be hype about Wasm, now it's a technology as any other. It's still used, and used a lot; it just doesn't get focused on as much.
- sippeangelo 6mo ago
  Just recently I've compiled my side-project Rust game engine to WASM and it runs beautifully in the browser, as well as SSH2 to have a fully featured SSH implementation in the browser over a websocket transport. It can obviously do amazing things, but the expectation for it to do replace webdev frontend code was always a huge misconception. Though recent developments have made DOM access without a JavaScript translation layer possible, so that might change! I'd say the hype is still very much alive.
- bbkane 6mo ago
  Looks like you're getting down voted, but the folks at Mozilla seem like they agree and are working towards making WASM more first class in the browser: https://hacks.mozilla.org/2026/02/making-webassembly-a-first-class-language-on-the-web/ https://hacks.mozilla.org/2026/02/making-webassembly-a-first...
  - flohofwoe 6mo ago
ronin_niron 6mo ago
One thing nobody's named in the thread yet: WASM's validator is linear-time, single-pass, with no dataflow joins. That constraint is what gives the operand stack its weird shape. Every block, loop, and if carries a function-type signature. The operand stack at block entry has to match the parameter type, and at exit has to match the result type. Inside a block the validator only sees pushes and pops within that frame; it never has to merge stacks from sibling control-flow paths, because each path's exit type is independently checked against the same expected signature. JVM went the other way: arbitrary control flow plus a verifier that does dataflow with type merges across joins. That's expensive enough that JVMs do it once at class load and cache the verified state. WASM specifically didn't want that bill; fast startup was a hard requirement. So the prefix/postfix debate elsewhere in the thread is downstream of this. The encoded form is postfix because that's what trivially admits a linear validator; the textual LISP form is sugar for the same expression trees inside a typed frame. dup isn't missing for aesthetic reasons either: local.tee n followed by local.get n already gives you dup-equivalence through typed locals, and any stack op that didn't reduce to typed locals would either duplicate what locals already do, or break the validator's linearity guarantee.
- zozbot234 6mo ago
  The whole point of having a type system is to endow program syntax with verifiable annotations that make validation easier. So if you wished to allow for otherwise "expensive" validation without overly impacting startup speed, the natural way of doing that is to extend the type system itself, in a way that offloads burden from the verifier to the producer. Arguably, this is exactly what WASM did when it implemented SSA phi-nodes via block return values and then extended those to multiple-value returns.
  - ronin_niron 6mo ago
    Yes, this generalizes well. The same producer-side annotation pattern shows up in every type-system extension WASM has shipped: typed function references encode signatures into the reference type, so indirect calls through them don't need runtime signature dispatch; the GC proposal uses declared subtyping via explicit (sub $X $Y) clauses, so subtype checks are chain walks instead of structural equivalence; exception handling uses nominal tag identity, so try/catch dispatch matches by name instead of structurally. Each extension grows the type system and the producer's job, and the verifier stays linear. JVM made the equivalent move retroactively when StackMapTable became mandatory in Java 7, explicit type annotations at branch targets so the verifier doesn't compute joins via fixpoint. WASM was designed with that lesson built in from day one.
Validark 6mo ago
I like to read assembly a lot, and I don't really see the point in WASM trying to be a stack machine. None of our computers are stack machines. Not to mention that compiler backends are missing tons of optimizations even on mainstream targets on real hardware, I just don't think WASM makes sense economically. They should have just picked RISC-V and called it a day.
wabstractions 6mo ago
Calling Wasm a stack machine is misleading. It’s closer to a structured IR that uses a stack encoding, not a machine where the stack is the primary state. The absence of real stack operations (dup, swap, etc.) is not accidental — it shows the stack isn’t meant to be observable. If you build even a tiny real stack CPU (simulator + assembler + traces), the difference becomes obvious very quickly: the stack stops being syntax and starts being semantics. So the real question isn’t “is Wasm a stack machine?” but “why does it avoid being one?” My take: because it’s designed for validation and compilation, not execution as a first-class machine model. And that’s fine — but then we should call it what it is.

183 points by signa11 6mo ago

stevefan1999 6mo ago

I'm trying to implement a WASM to C compiler, and because of that not-quite-so-stack behavior, I can actually guarantee that it will always build an expression and I don't have to discard or reset stack value! Everything stays within that function, which is very neat, and I think it is one of the reason WAT, the textual format is so neat, that you can represent it with a S-Expression.

jedisct1 6mo ago
Compiling WASM to C is a really good option: https://00f.net/2023/12/11/webassembly-compilation-to-c/ https://00f.net/2023/12/11/webassembly-compilation-to-c/
- ncruces 6mo ago
  Shameless plug… compiling it to Go is a great option too: https://github.com/ncruces/wasm2go https://github.com/ncruces/wasm2go I've used it to translate SQLite (with a few extensions) and, that I know of, it's been used (to varying degrees of success) to translate the MARISA trie library (C++), libghostty (Zig), zlib, Perl, and QuickJS. More on-topic, I use a mix of an unevaluated expression stack and a stack-to-locals approach to translate Wasm.
  - lukevp 6mo ago
    Does that mean you could compile a wasm program to go, then run it with wazero? How many levels deep can it go?? Might be a fun blog topic :)
    - ncruces 6mo ago
      Not very deep. Go generates large Wasm modules, because it bundles its goroutine scheduler, garbage collector and standard library into the module. Translating that back to Go will give you a pretty big Go file. Go is "known" for being fast to compile, but that huge Go file will take (at least?) as long to compile as compiling the Go toolchain does. wasm2go is best used on moderately sized modules (like SQLite). Last I heard, the person who tried to translate Perl got a 80MB Go file that was taking them 20min to compile. https://github.com/ncruces/wasm2go/discussions/15 https://github.com/ncruces/wasm2go/discussions/15
  - nu11ptr 6mo ago
    Interesting. I started working on this same idea a couple of years ago as a way to bypass CGo. Eventually I moved on to something else. Glad someone else is working on this. How does the generated Go performance compare to the original WASM performance?
    - ncruces 6mo ago
      That's going to depend on what you mean for "original Wasm performance". What were you using to run Wasm instead of this? I can compare with wazero, which I was previously using, and say performance stayed mostly in the same ballpark. Things that crossed the Go-to-Wasm boundary very often became much faster, things that stayed mostly in Wasm became slightly slower, as the wazero compiler is pretty good. wasm2go also does not support SIMD, so if your Wasm module uses/benefits from SIMD, you'll notice.
bsder 6mo ago
But how do you handle arguments or loop index variables? Your liveness is the entire function? You have to compile all the WASM chunks together in order to do any optimization? That seems ... problematic. Edit: Yep. In article referenced from the original: http://troubles.md/posts/wasm-is-not-a-stack-machine/ http://troubles.md/posts/wasm-is-not-a-stack-machine/ Double edit: Some of this has already been fixed in WASM: https://github.com/WebAssembly/multi-value https://github.com/WebAssembly/multi-value
rogerbinns 6mo ago
Check out wastrel https://codeberg.org/andywingo/wastrel https://codeberg.org/andywingo/wastrel Of note WASM 3 has garbage collection (GC), multi-memory, exception handling, tail calls and more which can be challenging to implement.

kg 6mo ago

The lack of a dup opcode in Wasm as mentioned in the post is quite annoying when trying to generate compact code. I wish something like it had made it into the spec.

thomasmg 6mo ago
You could use "local.tee". It is kind of is "store" + "duplicate".
- asibahi 6mo ago
  `local.tee` doesn't duplicate. it just doesn't remove the value from the stack. (so it is "just" `local.set` followed by `local.get`)
  - thomasmg 6mo ago
    Sure. But it does save you one instruction: "tee", "get" instead of "set", "get", "get".

ufo 6mo ago

The author seems to complain about a lack of stack manip expressions like dup and rot, but at least for me that's what I would expect from an average programming language stack machine. Even Java, which does have those instructions, doesn't use them --- reuse happens via local variables. The way I see it, the difference between register and stack vms is all about the instruction encoding. Register VMs have fatter instructions in exchange for needing fewer LOAD and STORE operations. Despite the name, register VMs also have a stack.

U1F984 6mo ago
Java does use dup in some cases, e.g. public static void test() { new Object(); } 0: new #2 // class java/lang/Object 3: dup 4: invokespecial #1 // Method java/lang/Object."<init>":()V 7: pop 8: return
- asibahi 6mo ago
  This `dup` seems entirely useless it actually supports the case for omitting it fron the instruction set.
  - layer8 6mo ago
    The only reason it is useless in this (arguably ill-chosen) example is because the result of “new Object()” is not used (hence the pop), which is an uncommon case. If test() instead returned the new object, or would use it in some other way after the initialization, then the dup would be needed. Invokespecial consumes the object reference on the stack, hence if you want to use it after invokespecial, you have to copy or duplicate it before.
pjjpo 6mo ago
> Despite the name, register VMs also have a stack. Out of curiosity what do you think about this - in spite of the name, stack machines also have yet another stack. Ok I don't like that wording, but locals are basically the stack frames people know of from their computer arch class I think. It doesn't change the fact that Wasm operations have to have the execution stack as one or more of the operands. Seems like a stack machines to me too, though I don't know more details on why the specific design of Wasm would make optimizing compilers harder to write than JVM as the article suggests (I think?).

Hendrikto 6mo ago

The series of articles linked at the end (troubles.md/posts/wasm-is-not-a-stack-machine/) is even more interesting, imo. Very well articulated and concise critique by somebody who seems to have a great amount of knowledge and experience with the topics.

asibahi 6mo ago

I dont really disagree with the main premise of the article, which is that WASM is not really a stack language, but this part just gave me pause: > In textual Wasm, for example, they are instead represented in a LISP-like notation – not any less or more efficient The Text format, at least when it comes to instructions, it 1 to 1 with the binary format. The LISP-like syntax is mainly just syntax sugar[1]. ‘(’ plaininstr instrs ‘)’ ≡ instrs plaininstr So (in theory, as far as I understand it) you can just do `(local.get 2 local.get 0 local.get 1)` to mean `local.get 0 local.get 1 local.get 2`, and it works for (almost) any instruction. Unfortunately, in my limited testing, tools like `wat2wasm` and Binaryen's `wasm-as` don't seem to adhere to (my perhaps faulty understanding of) the spec, and demand all instructions in a folded block be folded and have the "correct" amount of arguments, which makes Binaryen do weird things like (return (tuple.make ;; Binaryen only pseudoinstruction (local.get 0) ;; or w/e expression (local.get 1) ;; or w/e expression ) ) when this is perfectly valid local.get 0 local.get 1 return tl;dr: the LISP syntax is just syntax sugar. The textual format is as "stack-like" as the binary format. Edit: An example that is easily done with the stack syntax and not with lisp syntax is the following: call function_that_returns_multivalue local.set 2 ;; last return local.set 1 ;; local.set 0 ;; first return In LISP syntax this would be (local.set 0 (local.set 1 (local.set 2 (call function_that_returns_multivalue ( ;; whatever input paramters ))))) I have not yet tried this with Binaryen but I doubt it flies. [1]: https://webassembly.github.io/spec/core/text/instructions.html#folded-instructions https://webassembly.github.io/spec/core/text/instructions.ht...

soegaard 6mo ago
FWIW if you are looking for examples of WebAssembly written in the textual format, take a look at: https://raw.githubusercontent.com/soegaard/webracket/refs/heads/main/runtime-wasm.rkt https://raw.githubusercontent.com/soegaard/webracket/refs/he... As a small example, here is a definition of `$car` which extracts the first value from a pair. (func $car (type $Prim1) (param $v (ref eq)) (result (ref eq)) (if (result (ref eq)) (ref.test (ref $Pair) (local.get $v)) (then (struct.get $Pair $a (ref.cast (ref $Pair) (local.get $v)))) (else (call $raise-pair-expected (local.get $v)) (unreachable))))

shevy-java 6mo ago

I am sad about WASM. It was a promise for epic greatness. It has failed to deliver that - so much is clear now. You rarely see any awesome success story shown with regard to WASM nowadays. What happened to the old promises? "Electron will be SUPER fast thanks to WASM" or "use any language, WASM unifies it all for the larger browser ecosystem". It feels as if WASM is on a step towards exctinction. Sure, it is mentioned, it is used, but let's be honest - only few people really use it. And that won't change either.

thomasmg 6mo ago
Well there is Google Sheets, Microsoft Office, Figma, and some other heavier web apps.
purplesyringa 6mo ago
There used to be hype about Wasm, now it's a technology as any other. It's still used, and used a lot; it just doesn't get focused on as much.
sippeangelo 6mo ago
Just recently I've compiled my side-project Rust game engine to WASM and it runs beautifully in the browser, as well as SSH2 to have a fully featured SSH implementation in the browser over a websocket transport. It can obviously do amazing things, but the expectation for it to do replace webdev frontend code was always a huge misconception. Though recent developments have made DOM access without a JavaScript translation layer possible, so that might change! I'd say the hype is still very much alive.
bbkane 6mo ago
Looks like you're getting down voted, but the folks at Mozilla seem like they agree and are working towards making WASM more first class in the browser: https://hacks.mozilla.org/2026/02/making-webassembly-a-first-class-language-on-the-web/ https://hacks.mozilla.org/2026/02/making-webassembly-a-first...
- flohofwoe 6mo ago

ronin_niron 6mo ago

One thing nobody's named in the thread yet: WASM's validator is linear-time, single-pass, with no dataflow joins. That constraint is what gives the operand stack its weird shape. Every block, loop, and if carries a function-type signature. The operand stack at block entry has to match the parameter type, and at exit has to match the result type. Inside a block the validator only sees pushes and pops within that frame; it never has to merge stacks from sibling control-flow paths, because each path's exit type is independently checked against the same expected signature. JVM went the other way: arbitrary control flow plus a verifier that does dataflow with type merges across joins. That's expensive enough that JVMs do it once at class load and cache the verified state. WASM specifically didn't want that bill; fast startup was a hard requirement. So the prefix/postfix debate elsewhere in the thread is downstream of this. The encoded form is postfix because that's what trivially admits a linear validator; the textual LISP form is sugar for the same expression trees inside a typed frame. dup isn't missing for aesthetic reasons either: local.tee n followed by local.get n already gives you dup-equivalence through typed locals, and any stack op that didn't reduce to typed locals would either duplicate what locals already do, or break the validator's linearity guarantee.

zozbot234 6mo ago
The whole point of having a type system is to endow program syntax with verifiable annotations that make validation easier. So if you wished to allow for otherwise "expensive" validation without overly impacting startup speed, the natural way of doing that is to extend the type system itself, in a way that offloads burden from the verifier to the producer. Arguably, this is exactly what WASM did when it implemented SSA phi-nodes via block return values and then extended those to multiple-value returns.
- ronin_niron 6mo ago
  Yes, this generalizes well. The same producer-side annotation pattern shows up in every type-system extension WASM has shipped: typed function references encode signatures into the reference type, so indirect calls through them don't need runtime signature dispatch; the GC proposal uses declared subtyping via explicit (sub $X $Y) clauses, so subtype checks are chain walks instead of structural equivalence; exception handling uses nominal tag identity, so try/catch dispatch matches by name instead of structurally. Each extension grows the type system and the producer's job, and the verifier stays linear. JVM made the equivalent move retroactively when StackMapTable became mandatory in Java 7, explicit type annotations at branch targets so the verifier doesn't compute joins via fixpoint. WASM was designed with that lesson built in from day one.

Validark 6mo ago

I like to read assembly a lot, and I don't really see the point in WASM trying to be a stack machine. None of our computers are stack machines. Not to mention that compiler backends are missing tons of optimizations even on mainstream targets on real hardware, I just don't think WASM makes sense economically. They should have just picked RISC-V and called it a day.

wabstractions 6mo ago

Calling Wasm a stack machine is misleading. It’s closer to a structured IR that uses a stack encoding, not a machine where the stack is the primary state. The absence of real stack operations (dup, swap, etc.) is not accidental — it shows the stack isn’t meant to be observable. If you build even a tiny real stack CPU (simulator + assembler + traces), the difference becomes obvious very quickly: the stack stops being syntax and starts being semantics. So the real question isn’t “is Wasm a stack machine?” but “why does it avoid being one?” My take: because it’s designed for validation and compilation, not execution as a first-class machine model. And that’s fine — but then we should call it what it is.