Stream: git-wasmtime

Topic: wasmtime / PR #12621 Implement our OOM-handling `Secondar...

view this post on Zulip Wasmtime GitHub notifications bot (Feb 18 2026 at 21:03):

fitzgen opened PR #12621 from fitzgen:impl-oom-handling-secondary-map-from-scratch to bytecodealliance:main:

I realized we need to adjust its V: Clone bound into V: TryClone which means
that we can no longer actually just wrap an inner
cranelift_entity::SecondaryMap<K, V> and need to instead implement our
own. This also made me realize that we need remove to be fallible because,
when the entry being removed is in bounds, it overwrites the entry with the
default value, but that default value needs to be TryCloned now which is, of
course, a fallible operation.

Depends on

view this post on Zulip Wasmtime GitHub notifications bot (Feb 18 2026 at 21:03):

fitzgen requested alexcrichton for a review on PR #12621.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 18 2026 at 21:03):

fitzgen requested wasmtime-fuzz-reviewers for a review on PR #12621.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 18 2026 at 21:03):

fitzgen requested wasmtime-compiler-reviewers for a review on PR #12621.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 18 2026 at 21:03):

fitzgen requested wasmtime-core-reviewers for a review on PR #12621.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 18 2026 at 21:26):

fitzgen edited PR #12621:

I realized we need to adjust its V: Clone bound into V: TryClone which means
that we can no longer actually just wrap an inner
cranelift_entity::SecondaryMap<K, V> and need to instead implement our
own. This also made me realize that we need remove to be fallible because,
when the entry being removed is in bounds, it overwrites the entry with the
default value, but that default value needs to be TryCloned now which is, of
course, a fallible operation.

Depends on

view this post on Zulip Wasmtime GitHub notifications bot (Feb 18 2026 at 22:26):

alexcrichton commented on PR #12621:

I'll be honest in that I continue to not really understand SecondaryMap as a data structure as it seems so niche to almost never be applicable... Do we actually have any usages of the map which need this TryClone bound? Could we, for example, switch this a Copy bound on the key?

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 02:33):

github-actions[bot] added the label fuzzing on PR #12621.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 02:33):

github-actions[bot] added the label wasmtime:ref-types on PR #12621.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 02:33):

github-actions[bot] added the label cranelift on PR #12621.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 02:33):

github-actions[bot] added the label wasmtime:api on PR #12621.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 02:33):

github-actions[bot] commented on PR #12621:

Subscribe to Label Action

cc @fitzgen

<details>
This issue or pull request has been labeled: "cranelift", "fuzzing", "wasmtime:api", "wasmtime:ref-types"

Thus the following users have been cc'd because of the following labels:

To subscribe or unsubscribe from this label, edit the <code>.github/subscribe-to-label.json</code> configuration file.

Learn more.
</details>

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 16:28):

fitzgen commented on PR #12621:

I'll be honest in that I continue to not really understand SecondaryMap as a data structure as it seems so niche to almost never be applicable...

It is for whenever you want to associate extra data with a PrimaryMap's key on the side (sort of struct-of-arrays style), and it also supports use cases where potentially not every key has extra data / there is a default value for the extra data.

For example, in the TypeRegistry we (morally) have a PrimaryMap<VMSharedTypeIndex, Arc<WasmSubType>> but we also want to be able to map from a type to its GC layout, if any, so we have a SecondaryMap<VMSharedTypeIndex, Option<GcLayout>> on the side as well.

Do we actually have any usages of the map which need this TryClone bound? Could we, for example, switch this a Copy bound on the key?

The key is already bounded by EntityRef, which implies Copy. The TryClone bound is for values. And yes, we do have non-Copy values in SecondaryMaps that need to be try_cloned (such as GcLayout in the previous example).

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 16:34):

cfallin commented on PR #12621:

It is for whenever you want to associate extra data with a PrimaryMap's key on the side (sort of struct-of-arrays style), and it also supports use cases where potentially not every key has extra data / there is a default value for the extra data.

To say it another way that may also help (I've had this question too in the past):

So in Cranelift we tend to use them where we know most IDs will have an entry. Using a PrimaryMap would be incorrect as it would allocate different IDs.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 19:11):

fitzgen updated PR #12621.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 19:28):

alexcrichton commented on PR #12621:

Setting aside my reservations about SecondaryMap for a second, my main concern here is duplication of data structures. I think it's fine and reasonable to have API duplication as we do today but implementation duplication feels a step too far. One possible way to resolve this is to implement today's SecondaryMap in terms of KSecondaryMap (assuming we go with K*), but I realize that this wouldn't be trivial given the lack of relationship between Clone and TryClone.

Bringing back my reservations about SecondaryMap, the main thing I find weird about it is that it's sort of trying to be a HashMap<K, V> without exposing the fact that it's actually a dense map under the hood. The API surface area is focused around insert/remove/etc which gives it a feeling, in my opinion at least, of being more efficient than it actually is. I would personally prefer to see Wasmtime's SecondaryMaps modeled as a PrimaryMap instead with perhaps methods on PrimaryMap to do helper-like things such as (fill with N values of T then push this other value of T at the specified index). That, to me, would appropriately model the runtime behavior here where insert is O(N), not O(1).

The reason I also bring this up is that I don't feel this extra data structure implementation is necessarily justified. In practice the default value for V is always None or PackedOption::none() for all SecondaryMaps in the TypeRegistry. That means that while I agree conceptually the bounds on KSecondaryMap should be TryClone we wouldn't actually benefit from such a generalization anywhere. Or did you run in to a case preexisting in Wasmtime where V: TryClone was needed since an allocation could fail? My assumption would be that if we modeled things as PrimaryMap it would more naturally lend itself where the secondary-map-like-helper-methods would take V: TryClone and work appropriately.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 19:44):

cfallin commented on PR #12621:

Bringing back my reservations about SecondaryMap, the main thing I find weird about it is that it's sort of trying to be a HashMap<K, V> without exposing the fact that it's actually a dense map under the hood. The API surface area is focused around insert/remove/etc which gives it a feeling, in my opinion at least, of being more efficient than it actually is.

It might be good to understand whether this is the case or not more objectively. Picking one use-site in the type interner, for example, here (ModuleTypes::trampoline_types), it appears that there are entries for function types but not other (GC-related) types, is that right? If so we expect this to be dense-ish for core modules and non-GC-using components, but maybe not otherwise? Can we measure this? What other use-sites are there and how do they fare? (cc @fitzgen on this I guess)

More broadly: I'm somewhat concerned that we're discussing the existential fate of SecondaryMap alongside and intertwined with questions of implementation strategy. It exists for good reason in Cranelift; the places where it's used, it is dense in practice (e.g.: a map of result value-lists for every Inst; every instruction has one of those, but the map is not in charge of ID allocation), and I would hope it's used for similar reasons in wasmtime-environ.

And we should be clear about both asymptotic and implementation efficiency: (i) the Vec is much more efficient than a HashMap at such use-cases because it doesn't need to store the explicit keys, and access patterns are less random and involve less logic; (ii) the statement "That, to me, would appropriately model the runtime behavior here where insert is O(N), not O(1)." is incorrect for any key space whose size is linear in the input program: there can only be at most O(#keys) pushes onto the end of the Vec; new-key inserts are thus amortized O(1) and existing-key updates are deterministic O(1).

I think we should satisfy ourselves that we do need the data structure, get everyone on that page, and then move discussion on toward only how to implement it.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 19:48):

cfallin commented on PR #12621:

Also: @alexcrichton in addition to thoughts on the above, could you clarify what you mean by "model things as PrimaryMap"? A SecondaryMap is fundamentally different in that it associates values with existing IDs, while a PrimaryMap allocates new IDs for values that are inserted, so one can't be replaced with the other.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 21:28):

alexcrichton commented on PR #12621:

Sorry I'm doing my best to disentangle my bias against SecondaryMap from my concerns here, and I'm not doing a great job. At a base level my main concern is this is (a) duplicating a data structure that (b) I don't think is necessary. Specifically the V: TryClone while semantically correct I don't think is ever exercised in practice because the default for these maps is always None or something where Clone at runtime is just shuffling bytes and doing no allocation. I don't think it's worth having an entire duplicate implementation of this data structure for a feature that's not actually used, personally.

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.

Orthogonally it's probably most productive for me to just keep my concerns about SecondaryMap to myself. I understand its theoretical use as a data structure and I'm not advocating for its removal from Cranelift. I'd like to minimize/remove its usage from Wasmtime personally, but that's orthogonal to this PR itself.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 21:33):

cfallin commented on PR #12621:

I'd like to minimize/remove its usage from Wasmtime personally, but that's orthogonal to this PR itself.

Well, I guess that's why I'm asking about value-presence density for the specific use-cases in Wasmtime above. The one that I linked for func-type trampolines should be dense for most modules today, so using a HashMap would be a performance regression (and PrimaryMap is not an option; it's semantically different). So I guess that's what I'm trying to understand: we want to remove it from Wasmtime because of some subjective feeling, or because we believe other uses of it are actually less efficient at runtime?

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 22:02):

alexcrichton commented on PR #12621:

I'm not actaully sure what the best data structure for Wasmtime is, but my assumption is that we'd replace it with PrimaryMap. My understanding is that a SecondaryMap<K, V> is actually a PrimaryMap<K, V> where V has some sort of sentinel meaning "none" (e.g. Option<T> or PackedOption<I>). Given that I don't understand why PrimaryMap is not an option, because that's already more-or-less the implementation details of SecondaryMap. If I'm not misunderstanding, this is why I find SecondaryMap confusing, it's a PrimaryMap in a thin veil.

As for the best data structure, we can construct things every which way: modules with the SecondaryMap empty, modules with SecondaryMap being dense, and modules with SecondaryMap having a huge gap followed by a single entry. The rough saving grace today is that most SecondaryMaps (I think) are only needed for GC-related which is still off-by-default meaning most of this isn't used, so it doesn't end up mattering in practice currently as it's rarely used. In all of these situations though I don't think there's an obvious answer -- hash maps would excel in some use cases and fall down in others. SecondaryMap shines in some use caes and falls down in others too. Without changing the algorithmic constraints of lookup (e.g. going to O(log(n))) I don't think we have great options.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 19 2026 at 22:07):

cfallin commented on PR #12621:

but my assumption is that we'd replace it with PrimaryMap. My understanding is that a SecondaryMap<K, V> is actually a PrimaryMap<K, V> where V has some sort of sentinel meaning "none" (e.g. Option<T> or PackedOption<I>). Given that I don't understand why PrimaryMap is not an option, because that's already more-or-less the implementation details of SecondaryMap. If I'm not misunderstanding, this is why I find SecondaryMap confusing, it's a PrimaryMap in a thin veil.

OK, so there's the root of the misunderstanding: the above is not true; a SecondaryMap is not a PrimaryMap with presence. The difference is in the API: as described above, a SecondaryMap does not allocate keys. You use a PrimaryMap when you want to create a collection of things and have the container give you IDs as handles. You use a SecondaryMap when you already have IDs (handles) and want to associate some other data with them. Using a PrimaryMap in that case makes no sense, because all you can do is add a new V, and the map will allocate some other arbitrary K for you.

Given all that, a SecondaryMap can be compared to a HashMap. This is the difference between a map and a vector, basically, at the abstract datatype API level.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 20 2026 at 19:39):

alexcrichton commented on PR #12621:

To avoid getting sidetracked too much, I do want to say again that my primary concern above I've tried to disentangle from my thoughts on SecondaryMap -- specifically this is duplicating a data structure for a feature that I don't believe we use. I understand the "close the footgun" motivation but I don't think that alone is enough to motivate the duplication.

Otherwise personally I'm not really sure how the detail of allocating IDs or not leads to a misunderstanding here. There's nothing stopping us from adding APIs to PrimaryMap which make it operate like a SecondaryMap in some situations. That IDs are allocated feels to be but a side effect of an operation already happening. To me the underlying data structure implementation and big-O of methods is way more important than the conceptual operation happening. For example I don't think it makes sense to say PrimaryMap is entirely unsuitable for doing SecondaryMap's job when it's 1-2 methods away from being able to do that.

My overall point is that SecondaryMap runs the risk of being a very bad HashMap. It operates reasonably enough as a HashMap in specific situations and can spectacularly fall down in others. Papering over this, in my opinion very important, detail is doing the collection a disservice. For example a more apt name would be something like DenseMap which emphasizes that it is only really intended when the key space is particularly dense.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 20 2026 at 21:09):

cfallin commented on PR #12621:

A few thoughts:

view this post on Zulip Wasmtime GitHub notifications bot (Feb 23 2026 at 18:37):

alexcrichton commented on PR #12621:

I understand, yeah, that V: Copy isn't possible, but my point is that the reason for reimplementing the collection is because the default value is cloned and that's what needs to be fallible. What I have been saying is that the default value I don't believe ever needs a fallible clone in practice, only conceptually.

Also, yeah, I understand the consequences of sparse-ness, and the point I was making is that we are not equipped to say whether something is sparse or not ahead of time. An engine could register hundreds of modules that don't use GC types, and then all of a sudden registering a GC one takes a nontrivial amount of time because it's got to grow a bunch of secondary maps a very large amount before it's done. Alternatively an engine could entirely have GC modules and the key space could be super dense and have no real cost at all. My point is Wasmtime as an engine cannot assume dense or not, we just simply don't know ahead of time.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 23 2026 at 19:56):

cfallin commented on PR #12621:

OK, yeah, that's a good point regarding the 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.

I suppose that should be done in a separate PR if so. @fitzgen, what do you think?

view this post on Zulip Wasmtime GitHub notifications bot (Feb 23 2026 at 21:24):

fitzgen commented on PR #12621:

@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.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 23 2026 at 23:25):

alexcrichton commented on PR #12621:

How about this:

  1. Update this PR (or a sibling one) to fixing the Serialize/Deserialize bug
  2. Have a separate issue discussing possible data structure changes to TypeRegistry
  3. For now documenting the default value in a wasmtime_environ::collections::SecondaryMap shouldn't allocate-on-clone.
  4. Determine the final fate of OOM-capable SecondaryMap depending on the outcome of (2)

Last updated: Feb 24 2026 at 04:36 UTC