@alexcrichton

What I have been saying is that the default value I don't believe ever needs a fallible clone in practice, only conceptually.

FWIW, we could diverge from cranelift_entity::SecondaryMap's API here and only allow using Default::default() as the default value and document that Default::default() should never allocate.

@cfallin

non-deterministic latency (despite amortized bound linear with total size of all modules). Maybe that's enough reason to favor HashMaps generally in module metadata.

HashMaps will also have non-deterministic latency if you hit the resize path on insertion. I don't think they will actually change anything about latency determinism (and they potentially make it worse because it isn't just realloc with a potential memcpy if the realloc didn't happen in place, it is redistributing (and potentially rehashing) each entry across the hash map's new buffer).

Also HashMaps don't give us as strong of guarantees around OOM and fallible allocation on insertion. We already use one, but it doesn't seem like a great idea to further entrench more of them here.

The other alternative would be to move towards an OOM-handling BTreeMap, which we will eventually need anyways, but that will move us from $O(1)$ to $O(log(n))$.

But backing up and regarding sparseness in general: I view our struct-of-arrays representation as a strict improvement over the equivalent array-of-structs representation (which is what I would consider the default/baseline way to implement this stuff):

struct Type {
    ty: Arc<WasmSubType>,
    rec_group: RecGroupEntry,
    supertypes: Option<Box<[VMSharedTypeIndex]>>,
    trampoline: Option<VMSharedTypeIndex>,
    gc_layout: Option<GcLayout>,
};

struct TypeRegistryInner {
    hash_consing_map: HashSet<RecGroupEntry>,
    types: Slab<Type>,
    drop_stack: Vec<RecGroupEntry>,
}

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.

(Ignoring OOM handling and the insertion latency discussion for a second) switching to a HashMap or something else sparse would give use a further space-saving optimization for when GC stuff is used but only rarely. That would be nice, but like any other random optimization that we haven't implemented yet, it is a "nice to have" not a hard requirement IMO.

@alexcrichton

I still want to clarify, though, what's the imapct of not having this PR at all? Does this actively block some OOM-handling work for example? My current understanding is that this fixes a footgun with KSecondaryMap, but it's not a footgun that we're currently able to fire. If this actively unblocks something then the situation is different.

There was a bug in the previous implementation of Serialize/Deserialize where it didn't match cranelift_entity::SecondaryMap's behavior (which trims trailing default entries) which was triggering some panics once later PRs that depend on this one were applied.

So it is blocking those others from landing, but we could also make a new PR that just reimplements serialization in order to unblock them.