wee_alloc icon indicating copy to clipboard operation
wee_alloc copied to clipboard
verified publisher icon rustwasm

Investigate making the free list doubly linked

Open fitzgen opened this issue 7 years ago • 3 comments

Summary

Investigate rounding up allocations to at least two words, and making the free list doubly linked.

Motivation

This could simplify code, maybe shrink code size, and lessen fragmentation.

Details

  • We could remove deferred consolidation of cells. Simplifying code and hopefully also shrinking code size.

  • We could always consolidate a free cell with both of its neighbors, if they are also free. Right now we can only do one or the other because the free list is singly linked, and doesn't afford these kinds of manipulations in O(1) time.

  • Downside is that heap allocations of size < 2 words get rounded up. I think this is probably an OK choice.

  • We would make FreeCell have another link prev_free_raw that is the previous free list pointer.

  • Anywhere we insert into or remove from the free list, we would need to make sure that the new link is kept valid.

Happy to mentor anyone who wants to try their hand at this!

fitzgen avatar Feb 23 '18 18:02 fitzgen

I would like to give this a shot! I've started looking through the code.

manaskarekar avatar Mar 06 '18 12:03 manaskarekar

Great! Let me know if you run into any questions or anything. See also http://fitzgeraldnick.com/2018/02/09/wee-alloc.html for an overview of the design.

Note that #32 just changed things up a little bit, but the design largely remains the same.

fitzgen avatar Mar 06 '18 17:03 fitzgen

Hey @fitzgen sorry about the hiatus. I was thinking about jumping into this again, but just wanted to check if there are any updates to keep in mind?

Thanks!

manaskarekar avatar Aug 24 '18 22:08 manaskarekar