wasmtime / issue #3738 Pooling allocator: add a reuse-aff... · git-wasmtime

Stream: git-wasmtime

Topic: wasmtime / issue #3738 Pooling allocator: add a reuse-aff...

Wasmtime GitHub notifications bot (Jan 28 2022 at 08:11):

After writing this, it occurs to me that the reuse policy as stated will choose with equal probability a module whose freelist we still from, but this does not imply equal probability for any slot to be stolen.

In other words, if we have one module with average occupancy of 500 preinitialized slots out of 1000, and 500 others with 1 slot each, and a new module comes along and wants a slot, we have only 1/501 chance of picking one of the 500.

To unbias this I should probably keep a global freelist (whole pool of choices mixed together), randomly pick from that freelist, and keep a reverse-index of slot to last-allocated module to remove the index from that module's freelist (or lazily do so next time we look at that list). I'll take a closer look at this tomorrow!

Wasmtime GitHub notifications bot (Jan 28 2022 at 08:11):

cfallin edited a comment on issue #3738:

After writing this, it occurs to me that the reuse policy as stated will choose with equal probability a module whose freelist we steal from, but this does not imply equal probability for any slot to be stolen.

In other words, if we have one module with average occupancy of 500 preinitialized slots out of 1000, and 500 others with 1 slot each, and a new module comes along and wants a slot, we have only 1/501 chance of picking one of the 500.

To unbias this I should probably keep a global freelist (whole pool of choices mixed together), randomly pick from that freelist, and keep a reverse-index of slot to last-allocated module to remove the index from that module's freelist (or lazily do so next time we look at that list). I'll take a closer look at this tomorrow!

Wasmtime GitHub notifications bot (Jan 28 2022 at 08:35):

github-actions[bot] commented on issue #3738:

Subscribe to Label Action

cc @peterhuene

<details>
This issue or pull request has been labeled: "wasmtime:api"

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

peterhuene: wasmtime:api

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

Learn more.
</details>

Wasmtime GitHub notifications bot (Jan 29 2022 at 01:29):

cfallin commented on issue #3738:

I've updated this PR now to use a better data structure/algorithm design. It performs a fair random choice of victim slot when no slots with the desired affinity are available, and it has all O(1) updates -- somewhat tricky given the need to maintain two freelists (global and per-module) and remove from both. This is done by keeping Vecs and using swap_remove, and tracking a slot's position in each freelist in a separate reverse-index. Hopefully the comments make this a little more clear.

I've added a randomized test that counts ID-reuse (a little random simulation of sorts) and verifies a reasonable hit rate (at least twice what would be expected with random reuse) as well.

Wasmtime GitHub notifications bot (Jan 31 2022 at 17:09):

fitzgen commented on issue #3738:

The policy tracks a freelist per "compiled module ID", and when
allocating a slot for an instance, tries these three options in order:

A slot from the freelist for this module (i.e., last used for another
instantiation of this particular module), or

A slot that was last used by some other module or never before.

1..3 :eyes:

Wasmtime GitHub notifications bot (Jan 31 2022 at 17:10):

fitzgen edited a comment on issue #3738:

The policy tracks a freelist per "compiled module ID", and when
allocating a slot for an instance, tries these three options in order:


1. A slot from the freelist for this module (i.e., last used for another
  instantiation of this particular module), or

3. A slot that was last used by some other module or never before.

1..3 :eyes:

Wasmtime GitHub notifications bot (Jan 31 2022 at 17:39):

cfallin commented on issue #3738:

1..3 :eyes:

Incomplete edit, sorry! The distinction between the last two (empty, and then slot with other affinity) was removed because it made the data structure simpler, and in steady-state (past the first n_slot instantiations in the process) no slots will be empty.

Wasmtime GitHub notifications bot (Jan 31 2022 at 22:44):

cfallin commented on issue #3738:

I think I addressed all your comments; thanks @fitzgen ! This is rebased on the latest #3697 as well.

Last updated: Nov 22 2024 at 16:03 UTC