Optimization: Use compact encoding of bytecode about wasmi HOT 8 CLOSED

I got this working with a crude encoding scheme. Each isa::Instruction is identified with a single u8, followed by any operands (usually u32). As of now, I'm seeing a 10-15% performance improvement in cargo bench results.

The savings aren't as large as I had hoped. A napkin-math analysis over the test suite gives me a thought:

Most of the u32 operands are slots or offsets or similar small integers. Maybe a variable length encoding scheme is worth a go?

from wasmi.

10-15% is a very good figure actually!

This is basically a trade-off and we can easily get more overhead than we save by compacting the bytecode. What we might want to explore is introduction of a special narrow versions of opcodes that takes, say, u16 instead of u32 immediates.

from wasmi.

Well… then I started thinking about how WebAssembly is already a compact bytecode format with variable-length encoding of operands. FunctionReader::read_instruction() swizzles around flow control, but many more instructions are validated then emitted 1:1. Maybe it's better not to produce a second bytecode, but to instead produce a mix of new/enriched flow control instructions along with references to the original bytecode.

from wasmi.

Maybe it's better not to produce a second bytecode, but to instead produce a mix of new/enriched flow control instructions along with references to the original bytecode.

Can you expand a little on this? I'm not sure I follow.

from wasmi.

This issue proposes decoding instructions for validation, re-encoding them to a new bytecode, and decoding that bytecode in the interpreter.

I'm now thinking about decoding instructions for validation, building &[u8]s of which instructions do not require special handling, and then decoding those instructions from the original bytecode again in the interpreter. Something like:

mod isa {
  pub enum Operation {   // formerly Instruction
    GetLocal(u32),
    SetLocal(u32),
    TeeLocal(u32),

    Br(Target),
    BrIfEqz(Target),
    BrIfNez(Target),
    BrTable(Box<[Target]>),
    Return(DropKeep),

    /// WebAssembly bytecode, guaranteed not to contain:
    ///
    ///  * `Nop`
    ///  * `Block`
    ///  * `Loop`
    ///  * `If`, `Else`, `End`
    ///  * `Br`, `BrIf`, `BrTable`
    ///  * `Return`
    ///  * `GetLocal`, `SetLocal`, `TeeLocal`
    ///
    /// All other instructions are permissible and have valid operands.
    ValidatedWasmBytecode(&[u8]),
  }
}

The existing bytecode format is equivalent for most instructions, and wasmi already knows how to decode it. It's denser than my u32 immediate format and thus ought to make better use of memory bandwidth. I intend to experiment in this direction :-)

from wasmi.

Related:

• paritytech/parity-wasm#135
• paritytech/parity-wasm#154
• https://github.com/yurydelendik/wasmparser.rs/pull/45

from wasmi.

I am going to implement a more compact encoding of wasmi bytecode for the v1 implementation introduced in #287.

from wasmi.

The mentioned PR (#287) shrank the size of the enum bytecode from 24 bytes to 16 bytes by disentangling BrTable variant. The BrCode operand now only hosts the number of targets excluding the default target and is followed by Branch and Return operands by construction of the wasmi bytecode.

Closing this issue now since we probably won't get way lower than that given that we embed constant values into the bytecode since indirectly accessing constants (that must be 64-bits) would create too much overhead.

from wasmi.