Stream: git-wasmtime

Topic: wasmtime / PR #12685 Add insertion methods with fallible ...

view this post on Zulip Wasmtime GitHub notifications bot (Feb 27 2026 at 00:00):

fitzgen opened PR #12685 from fitzgen:bforest-fallible-insertion-methods to bytecodealliance:main:

<!--
Please make sure you include the following information:

Our development process is documented in the Wasmtime book:
https://docs.wasmtime.dev/contributing-development-process.html

Please ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->

view this post on Zulip Wasmtime GitHub notifications bot (Feb 27 2026 at 00:00):

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

view this post on Zulip Wasmtime GitHub notifications bot (Feb 27 2026 at 00:00):

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

view this post on Zulip Wasmtime GitHub notifications bot (Feb 27 2026 at 00:00):

fitzgen requested alexcrichton for a review on PR #12685.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 27 2026 at 00:00):

fitzgen requested wasmtime-default-reviewers for a review on PR #12685.

view this post on Zulip Wasmtime GitHub notifications bot (Feb 27 2026 at 00:29):

alexcrichton commented on PR #12685:

Before going too too far down this route (this PR is fine in isolation though), could you detail a bit more the end state here? I'm assuming this is eventually going to make its way into the ModuleRegistry within a Store in wasmtime to replace the BTreeMaps there currently. I'm not familiar with the data structures in this crate, but currently K and V are both bounded by Copy which doesn't satisfy the current usage within ModuleRegistry.

So overall I'm not quite sure I see the vision of where this is going to end up, hence the question -- could you detail a bit more about how this is going to make its way into Wasmtime? We have a surprisingly large number of BTreeMaps used in the runtime, and is this aimed at all of them or just a subset?

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

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

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

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

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

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

Subscribe to Label Action

cc @fitzgen

<details>
This issue or pull request has been labeled: "cranelift", "fuzzing"

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 27 2026 at 19:43):

fitzgen commented on PR #12685:

Before going too too far down this route (this PR is fine in isolation though), could you detail a bit more the end state here? I'm assuming this is eventually going to make its way into the ModuleRegistry within a Store in wasmtime to replace the BTreeMaps there currently. I'm not familiar with the data structures in this crate, but currently K and V are both bounded by Copy which doesn't satisfy the current usage within ModuleRegistry.

So overall I'm not quite sure I see the vision of where this is going to end up, hence the question -- could you detail a bit more about how this is going to make its way into Wasmtime? We have a surprisingly large number of BTreeMaps used in the runtime, and is this aimed at all of them or just a subset?

Yeah, we do use BTreeMaps in a bunch of core places in the core runtime, and we use them in ways that make it hard to replace with other data structures.

My plan is to create a wasmtime_environ::collections::BTreeMap that looks something like this:

#[derive(...)]
struct BTreeMapValueIndex(u32);
entity_impl!(BTreeMapValueIndex);


pub struct BTreeMap<K, V>
where
    K: Copy,
{
    values: PrimaryMap<BTreeMapValueIndex, V>,
    forest: cranelift_bforest::MapForest<K, BTreeMapValueIndex>,
    map: cranelift_bforest::Map<BTreeMapKey, BTreeMapValueIndex>,
}

impl<K, V> BTreeMap<K, V>
where
    K: Copy,
{
    pub fn get(&self, key: K) -> Option<&V>
    where
        K: Ord,
    {
        let idx = self.map.get(key, &self.forest, &()?;
        Some(&self.values[idx])
    }

    // etc...
}

I haven't done a full audit, but everything I've encountered so far has Copy keys (which, as you note, cranelift_bforest::Map requires), so we wouldn't need another indirection for keys in the map, like we have with values here. But if we have to, we can add that as well. It would unfortunately have the extra wrinkle of requiring some kind of hash consing or something tho, but that is not insurmountable.

If you are concerned about the performance implications this extra indirection has, we can put it behind a cargo feature. When the feature is not enabled, we would wrap std::collections::BTreeMap instead of doing the above, exposing the same OOM-handling methods/interface/API to users of the collection, but not actually attempting to handle OOM internally in this scenario.

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

fitzgen edited a comment on PR #12685:

Before going too too far down this route (this PR is fine in isolation though), could you detail a bit more the end state here? I'm assuming this is eventually going to make its way into the ModuleRegistry within a Store in wasmtime to replace the BTreeMaps there currently. I'm not familiar with the data structures in this crate, but currently K and V are both bounded by Copy which doesn't satisfy the current usage within ModuleRegistry.

So overall I'm not quite sure I see the vision of where this is going to end up, hence the question -- could you detail a bit more about how this is going to make its way into Wasmtime? We have a surprisingly large number of BTreeMaps used in the runtime, and is this aimed at all of them or just a subset?

Yeah, we do use BTreeMaps in a bunch of core places in the core runtime, and we use them in ways that make it hard to replace with other data structures.

My plan is to create a wasmtime_environ::collections::BTreeMap that looks something like this:

#[derive(...)]
struct BTreeMapValueIndex(u32);
entity_impl!(BTreeMapValueIndex);


pub struct BTreeMap<K, V>
where
    K: Copy,
{
    values: PrimaryMap<BTreeMapValueIndex, V>,
    forest: cranelift_bforest::MapForest<K, BTreeMapValueIndex>,
    map: cranelift_bforest::Map<K, BTreeMapValueIndex>,
}

impl<K, V> BTreeMap<K, V>
where
    K: Copy,
{
    pub fn get(&self, key: K) -> Option<&V>
    where
        K: Ord,
    {
        let idx = self.map.get(key, &self.forest, &()?;
        Some(&self.values[idx])
    }

    // etc...
}

I haven't done a full audit, but everything I've encountered so far has Copy keys (which, as you note, cranelift_bforest::Map requires), so we wouldn't need another indirection for keys in the map, like we have with values here. But if we have to, we can add that as well. It would unfortunately have the extra wrinkle of requiring some kind of hash consing or something tho, but that is not insurmountable.

If you are concerned about the performance implications this extra indirection has, we can put it behind a cargo feature. When the feature is not enabled, we would wrap std::collections::BTreeMap instead of doing the above, exposing the same OOM-handling methods/interface/API to users of the collection, but not actually attempting to handle OOM internally in this scenario.

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

alexcrichton commented on PR #12685:

Ah ok that makes sense yeah. And to confirm, I'm not familiar with the implementation of bforest, but given the documented caveats you're confident that this is a suitable replacement for our usages of BTreeMap? I'm not sure if that BTreeMap would, for example, end up being many times larger in the by-value size than std::collections::BTreeMap with the various collections it contains.

Also, that design may be a bit tricky insofar as it won't easily support removal without further maps/etc for tracking that. I don't think we need to remove from Store-based maps in ModuleRegistry, but we will need a solution for removing from the global map that has all loaded modules.

Perf-wise I'm not familiar enough with bforest to have much of an opinion on that. I don't think we need a hyper-optimal data structure here and just something that isn't O(n) in the worst case. I do think this is a reasonable enough time to rethink our data structures, though, perhaps?

For example BTreeMap feels rightly necessary for the global map (or some sort of sorted map thingy), but for ModuleRegistry in theory BTreeMap is way overkill for our use case. Almost all stores have just a single module or component in them and it's quite rare to have a very large number, so we might actually be able to get away with just a plain old sorted Vec<T>. I realize that I just also said we shouldn't do O(n) things which runs counter to that, but we could in theory also dynamically switch between a Vec<T> and a map after crossing some threshold (e.g. 100+ modules).

It's been a bit though since I looked at ModuleRegistry too closely, but WDYT about maybe first refactoring to remove some BTreeMaps to reduce the number of constraints on our future TryBTreeMap?

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

fitzgen commented on PR #12685:

Ah ok that makes sense yeah. And to confirm, I'm not familiar with the implementation of bforest, but given the documented caveats you're confident that this is a suitable replacement for our usages of BTreeMap? I'm not sure if that BTreeMap would, for example, end up being many times larger in the by-value size than std::collections::BTreeMap with the various collections it contains.

Those documented caveats seem workable, AFAICT.

I haven't investigated exact size differences, but I think it should be within a constant factor of the same size.

Also, that design may be a bit tricky insofar as it won't easily support removal without further maps/etc for tracking that. I don't think we need to remove from Store-based maps in ModuleRegistry, but we will need a solution for removing from the global map that has all loaded modules.

I guess my initial sketch had values: PrimaryMap<BTreeMapValueIndex, V>, but we probably actually want values: Slab<V>, so we have a free list for reusing entries and don't require a value for every entry in the arena. Then remove is simply something like this:

pub fn remove(&mut self, key: K) -> Option<V> {
    let id = self.map.remove(key, &mut self.forest, &())?;
    Some(self.values.dealloc(id))
}

but for ModuleRegistry in theory BTreeMap is way overkill for our use case. Almost all stores have just a single module or component in them and it's quite rare to have a very large number, so we might actually be able to get away with just a plain old sorted Vec<T>. I realize that I just also said we shouldn't do O(n) things which runs counter to that, but we could in theory also dynamically switch between a Vec<T> and a map after crossing some threshold (e.g. 100+ modules).

It's been a bit though since I looked at ModuleRegistry too closely, but WDYT about maybe first refactoring to remove some BTreeMaps to reduce the number of constraints on our future TryBTreeMap?

Generally a fan of re-thinking data structures where it makes sense as we go through and touch various things.

However, in the particular case of ModuleRegistry, and doing something like

enum ModuleRegistryData {
    Few(Vec<Module>),
    Many(BTreeMap<RegisteredModuleId, Module>),
}

I'm fairly meh. We need a BTreeMap implementation either way, so it isn't saving implementation work. Also, a single BTree node is roughly equivalent to a Vec of a small size if you squint, so I am not sure it would make a meaningful perf difference.

What might be worth it would be something like this tho:

enum ModuleRegistryData {
    One(Module),
    Many(BTreeMap<RegisteredModuleId, Module>),
}

This would let us avoid any allocation at all in the extremely common case of a single module in the registry.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 02 2026 at 15:58):

alexcrichton submitted PR review:

Well, in any case, this is of course fine as-is, and probably best to keep discussing in further PRs/issues/etc.

I think it should be within a constant factor of the same size

Mind double-checking? I'd basically want to make sure the constant isn't so big to be egregious. Store<T> is probably already way too big as-is...

we probably actually want values: Slab<V>

makes sense yeah

and doing something like ... I'm fairly meh

I agree yeah, I don't think we've crossed the complexity threshold to those just yet, and I agree it doesn't remove the need for BTreeMap, so it's probably fine to defer that to some future optimizations

Along the lines of rethinking data structures, one example is that within ModuleRegistry I don't think that either of ModuleRegistry::{store_code, modules} need to be a BTreeMap. Those look like they can both be hash maps. ModuleRegistry::loaded_code is kind of the most fundamental one, but we can probably get away with removing LoadedCode::modules. The latter needs range queries but we can probably switch that to a sorted vector since it's not dynamically added to (it's a per-component thing so we could precompute it at component-load-time or something like that).

The GlobalRegistry is also pretty fundamentally a BTreeMap, but overall I think we'll only need two in the long-run?

view this post on Zulip Wasmtime GitHub notifications bot (Mar 02 2026 at 16:03):

cfallin commented on PR #12685:

don't think ... ModuleRegistry::modules needs to be a BTreeMap

Agreed, but one caveat I should mention is that its iteration order is exposed via the debug APIs (Store::debug_all_modules()) so if we use a HashMap instead we should probably sort in that method before returning for determinism. (We don't have a strict determinism guarantee stated for debugging but it's nice to trend in that direction IMHO.) Just something to keep in mind in general I guess.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 02 2026 at 16:15):

alexcrichton commented on PR #12685:

Good point yeah, that'd be a better fit for IndexMap than HashMap in that case

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

fitzgen added PR #12685 Add insertion methods with fallible allocation to cranelift_bforest::{Map,Set} to the merge queue

view this post on Zulip Wasmtime GitHub notifications bot (Mar 02 2026 at 21:48):

fitzgen merged PR #12685.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 02 2026 at 21:48):

fitzgen removed PR #12685 Add insertion methods with fallible allocation to cranelift_bforest::{Map,Set} from the merge queue

view this post on Zulip Wasmtime GitHub notifications bot (Mar 03 2026 at 00:22):

fitzgen commented on PR #12685:

Mind double-checking? I'd basically want to make sure the constant isn't so big to be egregious. Store<T> is probably already way too big as-is...

Whipped up a quick example to check the max resident size (in kilobytes) of a process that inserts 10_000_000 entries into a BTreeMap<K, V> with std::collections::BTreeMap<K, V> vs the bforest-based BTreeMap sketched above.

It looks like the overheads get smaller the larger the value gets, and after u128 and larger values, the bforest-based implementation actually starts outperforming the std implementation:

K V std-based bforest-based Overhead (bforest/std)
u32 u8 154720 288572 1.87
u32 u32 206880 288588 1.39
u32 u64 284708 327684 1.15
u32 u128 414908 405752 0.98
u32 [u8; 64] 1274536 874644 0.69

Increasing the size of the keys does cause more overhead in the bforest-based implementation, but not by too much:

K V std-based bforest-based Overhead (bforest/std)
u32 u128 414908 405752 0.98
u64 u128 493052 509948 1.03
u128 u128 649228 718268 1.11
[u128; 2] u128 935820 1082820 1.16

Overall, I think this is probably fine?

view this post on Zulip Wasmtime GitHub notifications bot (Mar 03 2026 at 01:10):

alexcrichton commented on PR #12685:

Sounds reasonable to me :+1:, thanks for checking!

Last updated: Mar 23 2026 at 16:19 UTC