Stream: git-wasmtime

Topic: wasmtime / PR #12987 Bucket allocations by size in the fr...

view this post on Zulip Wasmtime GitHub notifications bot (Apr 07 2026 at 20:31):

fitzgen opened PR #12987 from fitzgen:no-quadratic-behavior-for-n-allocations to bytecodealliance:main:

This allows us to avoid O(n) search for a block of a certain size in the worst case.

Follow up to #12969

view this post on Zulip Wasmtime GitHub notifications bot (Apr 07 2026 at 20:31):

fitzgen requested alexcrichton for a review on PR #12987.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 07 2026 at 20:31):

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

view this post on Zulip Wasmtime GitHub notifications bot (Apr 07 2026 at 20:46):

alexcrichton submitted PR review:

How worth it do you feel chasing improvements in allocation/deallocation performance are? My impression is that BTreeMap is quite large in terms of code size, pretty wasteful in terms of resources, and not really all that efficient. I think it's quite good at its job of reducing things to O(log n) algorithmic complexity but my impression is that the constant factors are quite high for micro-algorithms like a malloc and free which this more-or-less is.

Mostly in the sense that I continue to be worried that we can layer on more and more Rust data structures to make malloc and free faster but I'm worried about unintended consequences about how these all interplay with each other. For example if there were a lot of 4-byte gaps in the heap it might end up meaning that the BTreeMap to represent the free list was larger than the heap itself (or something like that). With this there's multiple layers of BTreeMap to consider and personally I inevitably get lost in the details.

All that being said complexity can still be justified and it's not like I know of anything particularly wrong with this approach. Mostly I wanted to at least ask though to get your temperature on this axis too

view this post on Zulip Wasmtime GitHub notifications bot (Apr 07 2026 at 21:00):

fitzgen commented on PR #12987:

How worth it do you feel chasing improvements in allocation/deallocation performance are?

This PR is just to address your comment here, I have no intention to continue pushing on free list performance from this point on. My hope is that between #12969 and this PR, we will have gotten it to the point where performance is acceptable enough for enabling GC by default.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 07 2026 at 21:04):

fitzgen commented on PR #12987:

My impression is that BTreeMap is quite large in terms of code size, pretty wasteful in terms of resources, and not really all that efficient. I think it's quite good at its job of reducing things to O(log n) algorithmic complexity but my impression is that the constant factors are quite high for micro-algorithms like a malloc and free which this more-or-less is.

Mostly in the sense that I continue to be worried that we can layer on more and more Rust data structures to make malloc and free faster but I'm worried about unintended consequences about how these all interplay with each other. For example if there were a lot of 4-byte gaps in the heap it might end up meaning that the BTreeMap to represent the free list was larger than the heap itself (or something like that). With this there's multiple layers of BTreeMap to consider and personally I inevitably get lost in the details.

This is all true, but note that the fast path is just bump allocation which doesn't touch the btrees; we only go to them when bump allocation fails.

Ultimately, I think there is definitely room for improvement here as far as allocators go, but this should get us to a decent state and then the self-hosting would be the next step for this code.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 07 2026 at 21:14):

fitzgen edited a comment on PR #12987:

How worth it do you feel chasing improvements in allocation/deallocation performance are?

This PR is just to address your comment here, I have no intention to continue pushing on free list performance from this point on. My hope is that between #12969 and this PR, we will have gotten it to the point where performance of the free list itself is acceptable enough for enabling GC by default.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 08 2026 at 01:06):

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

view this post on Zulip Wasmtime GitHub notifications bot (Apr 08 2026 at 01:06):

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

view this post on Zulip Wasmtime GitHub notifications bot (Apr 08 2026 at 01:07):

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

Subscribe to Label Action

cc @fitzgen

<details>
This issue or pull request has been labeled: "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 (Apr 08 2026 at 16:41):

alexcrichton submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 08 2026 at 17:18):

fitzgen added PR #12987 Bucket allocations by size in the free list to the merge queue.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 08 2026 at 18:05):

fitzgen removed PR #12987 Bucket allocations by size in the free list from the merge queue.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 08 2026 at 18:15):

fitzgen merged PR #12987.

Last updated: Apr 12 2026 at 23:10 UTC