TypeRegistry internal data structures

[fitzgen]

A place to continue the discussion from #12621

[alexcrichton]

Carrying over from here

Our struct-of-arrays implementation today is an optimization over that baseline because it allows us to avoid the memory overhead of supertypes, trampolines, and GC layouts when GC stuff isn't used at all. That's already a win.

To try to quantify this, our current struct-of-arrays is here where the arrays are:

• types - a pointer-per-element (of WasmSubType) which all types will push to
• type_to_rec_group, type_to_supertypes, type_to_gc_layout - not present for "vanilla" function types but GC types will insert into this.
• type_to_trampoline - possible to show up for some function types using GC types and such

The theoretical wins here is that WasmSubType is smaller because it doesn't need to contain rec groups, supertypes, gc layouts, and trampolines. WasmSubType, however, is pretty inefficient where its hierarchy is:

• WasmSubType = (bool, Option<EngineOrModuleTypeIndex>, WasmCompositeType)
• EngineOrModuleTypeIndex = (tag, u32)
• WasmCompositeType = (WasmCompositeInnerType, bool)
• WasmCompositeInnerType = WasmArrayType | WasmFuncType | WasmStructType | WasmContType | WasmExnType
• ...

Basically I'd say that WasmSubType is already quite far away from its optimal representation, and we're allocating that per-type in the Engine. Given that are we really gaining much by moving a few extra things out to secondary maps?

For example one thing we could do is bundle all the SecondaryMaps into some sort of TypeAuxiliary thing which is stored in WasmSubType under an Option<Box<...>>. That's a single word of extra storage per type which compared to the current weight of WasmSubType I would suspect is relatively small. Even if we were to optimize the representation of WasmSubType an extra word probably wouldn't break the bank.

So my current read on this -- are we benefitting from the secondary maps? My impression is that struct-of-arrays are really good for (a) allocating a ton of a type which has lots of internal padding or (b) algorithms that frequently access just a single field of many structs. For (a) I don't think we've optimized WasmSubType to actually get any gains, and for (b) I don't think we're using the struct-of-arrays approach for cache locality currently.

I could very well be missing things though, @fitzgen you wouldn't happen to recall any measurements or specific situations you were thinking of struct-of-arrays for would you?