On the principle this looks good. From an organization point of view, I would put everything in the side table (which represents pre-computed information on the wasm bytecode). This side table would contain information about how to take branches/jumps, where to find functions, etc. It needs to be serializable with easy random access.

Regarding the other type of accessors, it's probably enough to store their position in the wasm bytecode and deserialize them on demand. This is still O(1). We can probably avoid storing the "end" parser position by always using the end of the wasm bytecode. For functions, we could also store only one position, which would be right before the u32 encoded size, meaning we need to parse_u32 and split_at for each access, but we save 50% storage, so it's some tradeoff.

@ia0 Could you take another look at the design? Thanks.

metadata := parser:(u32 u32) type:u16 branch-table (if 32-bits aligned)
| type:u16 parser:(u32 u32) branch-table (otherwise)

Could you elaborate on the two cases here? By "otherwise", do you mean 16 bits aligned?

@ia0 Please take a look at the generalized SideTable. Let's first agree on the design, and I'll add unit tests later. Thanks.

metadata := parser:(u32 u32) type:u16 branch-table (if 32-bits aligned)
| type:u16 parser:(u32 u32) branch-table (otherwise)

Could you elaborate on the two cases here? By "otherwise", do you mean 16 bits aligned?

Yes. Every "item" is at least 16 bits aligned. metadata may either be at least 32-bits aligned in which case the parser comes first, or exactly 16-bits aligned (in which case the type index comes first).

metadata := parser:(u32 u32) type:u16 branch-table (if 32-bits aligned)
| type:u16 parser:(u32 u32) branch-table (otherwise)

Could you elaborate on the two cases here? By "otherwise", do you mean 16 bits aligned?

Yes. Every "item" is at least 16 bits aligned. metadata may either be at least 32-bits aligned in which case the parser comes first, or exactly 16-bits aligned (in which case the type index comes first).

Why does the order matter? We can read exactly based on how we write, and the alignment is known by design when we write.

metadata := parser:(u32 u32) type:u16 branch-table (if 32-bits aligned)
| type:u16 parser:(u32 u32) branch-table (otherwise)

Could you elaborate on the two cases here? By "otherwise", do you mean 16 bits aligned?

Yes. Every "item" is at least 16 bits aligned. metadata may either be at least 32-bits aligned in which case the parser comes first, or exactly 16-bits aligned (in which case the type index comes first).

Why does the order matter? We can read exactly based on how we write, and the alignment is known by design when we write.

For the CPUs we use it probably doesn't matter because they are quite simple. But Rust which supports much more, makes a distinction between aligned and unaligned accesses. But maybe the solution is to just use &[u8] everywhere and use {to,from}_ne_bytes() functions. The code will probably be optimized as expected.

Regarding the order, every metadata has an odd amount of u16 because parser and branch-table have both an even amount of u16. So metadata are alternating between 32-bit aligned or only 16-bit aligned. If we want the u32 to be 32-bit aligned then the order matter (and the order is alternating).

There's the same problem for writing. We need to write with the proper alignment. It is not known, it depends how many branches are in each function before the current function. We could add a u16 padding after some functions to make sure all metadata start 32-bit aligned, so that even indices and odd indices can be used to tell the alignment.

But I think at this point, it's probably better to just not rely on alignment and read all values as &[u8]. All flash controllers we use so far support reading at byte granularity directly from linear memory. So it's just a matter of unaligned reads having the same performance as aligned reads for the CPU we consider.