Replace enum usage in Brillig VM memory

[vezenovm]

Problem

In the Brillig VM, we currently represent memory as a flat list of memory values.

These memory values are represented by an enum. In Rust, an enum is as large as its largest variant. For a field size of 254 bits, this means all memory value's will take up 254 bits. The largest integer type in Brillig is u128 and there are many Brillig programs in which we are only working with types of u64 and smaller. Thus, this means we are allocating an unnecessary amount of memory when executing Brillig.

Happy Case

The main goal is to have no padding due to the usage of enums.

I think the simplest solution would be representing memory as a flat list of bytes:

pub struct Memory {
    inner: Vec<u8>
}

The main work would then be the encoding/decoding of the MemoryValue enum to our new unified memory of bytes.

With full control over the encoding/decoding of a type, it will be easier to further optimize Brillig VM memory in the future as well (e.g. packing fields, variable length encoding).

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

Nice-to-have

Blocker Context

This could possibly be counted as blocker for some projects that perform heavy Brillig operations. We do not want to see projects bottlenecked by our ACVM/BrilligVM simulation.

Would you like to submit a PR for this Issue?

None

Support Needs

No response

[TomAFrench]

One concern here is on whether we'd lose a lot of performance back and forth between byte decompositions. I've spoken about this issue before (with @michaeljklein I think?) and one option is changing from the current array of enums to a struct of arrays (to take advantage of the fact we know all of the possible types upfront where we just have separate memory for each data type. We would then need a mapping from the brillig VM's memory representation to the rust representation however.

For some ultra low hanging fruit, we should be able to just Box any FieldElements which would reduce the size of this enum from ~256bits to ~64 at the expense of a little bit of performance when operating on field elements (something we'd experience with the Vec<u8> solution anyway.

[vezenovm]

one option is changing from the current array of enums to a struct of arrays (to take advantage of the fact we know all of the possible types upfront where we just have separate memory for each data type. We would then need a mapping from the brillig VM's memory representation to the rust representation however.

I agree, it would be good to have multiple memory layouts in the manner you described. I feel this is essentially an optimization of the OP (differentiating the flat memory and optimizing its layout). I felt as a first step to move away from the enum, it would be simplest to start with a single unified memory of bytes.

We should of course consider any performance hits while working on a solution that moves away from the enum being used by memory. It very well could happen that the simple list of bytes is not sufficient of a solution on its own due to the encoding/decoding cost. Once we have an idea of the new costs with a unified list of bytes, we can then work on reducing the encoding/decoding cost.

[TomAFrench]

I tried the boxing method in #6925 but it doesn't seem to make a dent in the memory usage strangely.