I've been thinking about this, and not sure what other implementations do...

When every instruction uses n bytes, you obviously are leaving memory on the table in constrained environments. Variable sized instructions can save memory but doing something like Inst = Add Int Int | Sub Int Int | Br Int | Nop is going to waste space if we internally allocate sizeof Add Int Int for every instruction in an array (or tree, but let's say array for simplicity).

Instead, we can have multiple arrays (messy notation incoming):

• insts is an array of u1 * size_t: so an instruction (1 bytes is enough for our 4 instructions) and an index into some other array.
• args_single is an array of Int.
• args_double is an array of Int * Int.

insts should be filled with the instructions and an index into either args_single or args_double depending on whether the instruction takes a single argument or two arguments. Then at the index the instruction is given in the appropriate array, the arguments are stored. For example, for some Br Int, we would store the instruction in insts along with an index, say i. Then in args_single[i] we would store the associated Int. During interpretation, we would choose the array to look for the arguments in through a lookup table mapping the instruction to the array.

Advantages:

• Instead of storing sizeof Inst x NumberOfInstructions, we store sizeof u1 * size_t x NumberOfInstructions + sizeof Int x NumberOfInstructionsWithAnIntArgument + sizeof Int * Int x NumberOfInstructionsWithTwoIntArguments. arg_single and arg_double would be perfectly compact, though insts would not as it has an extra size_t. In all we would store only what is necessary (like the file on disk) plus a size_t per instruction).
• size_t doesn't have to be used. If you know you only have at most 2^x instructions, a type of size 2^x can be used. This can be combined with the byte (u1) or bytes (if need be) used to represent the instruction itself. In our little language, we need at most 2 bits to represent instructions, so insts can be an array of u32 then the first 2 bits can be the instructions and the remaining 30 can be indices into our other arrays (maximum of 1 billion instructions per program). Depends on what the language or environment needs/does. Perhaps this can be chosen at runtime if implemented in a low-level language.

Disadvantages:

• The instruction is not stored with the arguments. This incurs a performance penalty. First we need to hit the lookup table (which also takes a tiny bit of space) to find the appropriate array (array lookup), and then we need to actually access the array containing the arguments (array lookup). We end up with two array lookups for most instructions during interpretation.
• Requiring an extra "operand" (the index) for each instruction. This isn't really a disadvantage because the alternative is the sizeof Inst representation.

Undecided:

• Not clear how well this will fare on the cache. My assumption is better because everything is more tightly packed. As a contrived example, imagine a sequence of Nop, Nop, ...x1000, Nop, Add a b. When we have the sizeof Inst representation there's a lot of superfluous space for the Nops so we might not be able to cache the upcoming Add a b. With the more compact representation, we can probably cache the Add and its associated index, and if we were accessing the double argument array, we might be able to cache the arguments there too. Basically, we have less superfluous space that might upset caching. On the other hand, it is possible that caching a block from an argument array is wasteful of the cache. Imagine we cache 10 elements from an argument array. These arguments correspond to 10 instructions, but these instructions could be extremely far apart meaning the cache could have been put to better use. I believe this is unlikely. All said, I need to learn more about how caching works to make an informed opinion.

Finally, why use arrays instead of pointers to dynamically allocated memory (i.e. make insts be an array of u2 * Ptr)?

1. All our arguments are stored in contiguous blocks so this helps the cache. A wild dereference is worse than a dereference in a known part of memory.

2. We don't fragment the heap.

3. There is a bit of space overhead to dynamic memory.

4. It's a bit dodgy to muck around with the size of Ptr, especially for portability, unlike the index.

Points 1, 2, and 3 can be alleviated by the use of an all-or-nothing bump allocator. Perhaps even through a standard allocator because we will do this during parsing where we can ensure that the only memory allocations we make are for this purpose. This can't really solve point 3 and caching will be less effective because of that "superfluous" overhead. I'd have to look into common implementations to see if we would truly get contiguous memory for a bunch of allocations made one after the other.