Optimize `Instance` handling in the `CallStack`

Currently each CallFrame in the CallStack has an Instance to which its state refers. The size_of<Instance> is 8 bytes, so for many recursive calls this is significant memory usage for large call stacks.

The problem with the current design is that it is optimizes for frequent changes of the currently used Instance which is quite rare usually and can only happen when calling imported functions that are hosted by another Wasm Instance. In order to further reduce memory consumption and eventually also boost the performance of call-intense executions we could factor out the Instance as follows:

Instead of

struct CallStack {
    frames: Vec<CallFrame>,
}

struct CallFrame {
    instance: Instance,
    ...
}

We'd have:

struct CallStack {
    frames: Vec<CallFrame>,
    instances: Vec<(usize, Instance)>,
}

struct CallFrame { ... } // no more `instance` field

Where (usize, Instance) in the instances field represents the index: usize at this this Instance got active. Thus the CallStack starts out with the following initial configuration:

CallStack {
    frames: vec![CallFrame { ... }],
    instances: vec![0, Instance(i)],
}

Where 0 denotes that at call height 0 the instance i was used. If a CallFrame gets pushed onto the CallStack that does not change the currently used Instance then nothing gets pushed to instances. If a CallFrame gets pushed onto the CallStack that does change the currently used Instance then instances is pushed with a (index, Instance(x)) pair where index is the current length of frames and x the new Instance to be used from that point onwards.

If a CallFrame is popped from the CallStack we check if the last element of instances shared the index with the popped element and in this case also pop and return the associated Instance, otherwise we do nothing and return None.

Thus the following API for CallStack is implied:

impl CallStack {
    // Note: Even if `instance` is `Some` this only pushes a new element to `instances` if `instance` and the last `Instance` in `instances` are not equal.
    // Returns `Some(instance)` if `instances` had to push a new `Instance` pair and thus the currently operated-on `Instance` has changed with this new `CallFrame`.
    pub fn push(&mut self, frame: CallFrame, instance: Option<Instance>) -> Option<Instance> { ... }

    pub fn pop(&mut self) -> (CallFrame, Option<Instance>) { ... }
}

wasmi-labs / wasmi

Optimize `Instance` handling in the `CallStack` #1049