1-byte small `local.get` would save significant bundle size in real-world code

[dead-claudia]

Massive chunks of uncompressed binaries are just local.get with small indices. To use Tensorflow's SIMD WebAssembly bundle (424594 B) as an example:

Index	Bundle size %	local.get %
0	2.7%	9.8%
0-1	4.9%	18.0%
0-3	9.1%	33.2%
0-7	15.4%	56.2%
0-15	22.8%	83.4%
All	27.3%	100%

Here's similar stats for local.set and local.tee:

local.set index	Bundle size %	local.set %
0	0.36%	5.9%
0-1	0.73%	12.2%
0-3	1.6%	25.9%
0-7	2.8%	47.1%
0-15	4.5%	72.2%
All	6.2%	100%

local.tee index	Bundle size %	local.tee %
0	0.38%	7.8%
0-1	0.73%	15.1%
0-3	1.5%	30.4%
0-7	2.6%	53.1%
0-15	4.1%	83.5%
All	5.0%	100%

I checked savings from
multiple possibilities:

• 1-byte local.get 0-15 only: about 11.4%
• 1-byte local.get 0-7 only: about 7.7%
• 1-byte local.get 0-3 only: about 4.6%
• 1-byte local.get 0-7 + local.set/tee 0-3: about 9.3%
• 1-byte local.get 0-3 + local.set/tee 0-1: about 5.4%

I checked Tensorflow's non-SIMD bundle and saw similar ratios.

Each of these, to my knowledge, are possible in the 0xE0-0xEF space (unless there's extensions I don't know about), so I propose putting 1-byte local.get 0-15 there.

[dead-claudia]

Caught this while putting together a reply for #1559.

[kmiller68]

I’m open to exploration of this space but I think I’d prefer something along the lines reserving some set of opcodes and providing them via an alias/macro custom section describing what they should map to. The simplest version could be just one instruction+immediates but I could imagine extending it to full blocks (maybe with some limitations). That seems at least as powerful as this proposal while also being more flexible as wasm/toolchains evolve.

It seems like the group most with potential difficulties under such a proposal would be in-place interpreters. Even then, I don’t know how bad it would be for them.

[dead-claudia]

@kmiller68 I was trying to avoid any level of indirection, specifically to help boost direct interpreters and latency-sensitive JIT compilers. And that's basically just a poor man's Huffman/entropy coding - I was very actively not proposing any sort of compression.

And macro-like constructs would significantly slow down bytecode dispatch, and it's long been well-documented that bytecode dispatch is among the most perf-sensitive components of interpreters. (I remember many years ago reading about the heated debates and ancient flame wars on stuff like indirect threading vs direct threading vs subroutine threading. Performance was one of the biggest bludgeons people used to assert their side in them.)

---

Worth noting RISC-V took a similar approach with its compressed instructions, citing similar reductions in code size. Its compressed move instructions can index the low 15 of its 31 registers, with most of its other compressed instructions only able to index registers 8-15. RISC-V's generally focused on ISA simplicity at the expense of decoder complexity (promoting opcode fusion) in high-performance implementations, and it's always had soft FPGA core and software core implementors in mind (it's already found significant use as a simple sandbox VM base in both embedded and high-assurance smart contracts), so it's somewhat valid as a data point here.

[rossberg]

FWIW, this has been discussed extensively in the initial design discussions for Wasm (for which we don't have records, unfortunately), including the suggestions to introduce specialised instructions for low-index locals. At the time we concluded that code size concerns are best addressed by a more flexible and systematic solution, in the form of a macro-like encoding layer like @kmiller68 mentions. For most part, standard zip compression turned out to be good enough that this never became a pressing point, though. But it keeps coming up, and eventually we should reevaluate.

Wasm was explicitly designed for jit compilation, so interpreters have not been a concern initially. However, that has changed a bit more recently. Yet compilation still is the expected approach where maximum performance matters, so Wasm probably wouldn't need to go out of its way to avoid all overhead for interpreting macros, as long as it doesn't affect anything else.

[fgmccabe]

@dead-claudia Opcodes 0xe0-0xe5 are being used for wasmfx/core stack switching.

[dead-claudia]

@dead-claudia Opcodes 0xe0-0xe5 are being used for wasmfx/core stack switching.

Okay, then do you have a map of what first-byte opcode ranges that aren't in use by proposals?

And is F0-F7 clear? (I'm not tied to any particular range, to be clear.)

[fgmccabe]

F0-F7 Seem to be clear at the moment. At least, they are not being using in V8.
This is not a comment on the viability of the suggestion itself.

[dead-claudia]

Wasm was explicitly designed for jit compilation, so interpreters have not been a concern initially. However, that has changed a bit more recently. Yet compilation still is the expected approach where maximum performance matters, so Wasm probably wouldn't need to go out of its way to avoid all overhead for interpreting macros, as long as it doesn't affect anything else.

To be fair, RISC-V also is in a similar boat: it was explicitly designed for CPUs and just aware of interpreters. Now, interpreters are starting to crop up, first with untrusted VMs for constrained environments and now with Polkadot actively switching to RISC-V and Vitalik recently proposing such a switch for Ethereum for other reasons.

This is part of why I cited it as precedent.

[rossberg]

Yes, but a CPU is more or less an interpreter in hardware, so close enough. Compilation otoh leads to very different and sometimes contrary design decisions, like the use of LEBs or structured control.