Conversation
This was referenced Nov 12, 2022
Closed
061be6b to
6c1a860
Compare
fast allocator for WebAssembly eventually this is intended to be merged into `std.heap.GeneralPurposeAllocator`
The previous version had a fatal flaw: it did ensureCapacity(1) on the freelist when allocating, but I neglected to consider that you could free() twice in a row. Silly! This strategy allocates an intrusive freelist node with every allocation, big or small. It also does not have the problems with resize because in this case we can push the upper areas of freed stuff into the corresponding freelist.
Now it can refuse to resize when it would disturb the metadata tracking strategy, resulting in smaller code size, a simpler implementation, and less fragmentation.
6c1a860 to
7f063b2
Compare
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This is a 160-line Allocator implementation that is simpler, faster, and more memory-efficient than GeneralPurposeAllocator. It similarly buckets allocations into size classes, however, unlike GPA, it additionally uses free lists, and does not track any metadata. The only extra information stored within each allocation is an intrusive free list node, so that the allocation can be added to the free list without possibility of failure. This allocator has zero external fragmentation, but a high amount of internal fragmentation. Large allocations are never split into multiple smaller allocations, and smaller allocations are never joined into a single larger allocation.
It is WebAssembly-only because it depends on single-threaded access to global variables to keep track of allocator state, it directly calls the
@wasmMemoryGrowintrinsic, and it never gives memory back to the OS.I think this strategy could be appropriate in general when the following options are enabled:
-fsingle-threaded-OReleaseSmallsbrkfor obtaining heap memory.