Investigate making the free list doubly linked

fitzgen commented 6 years ago

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

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

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!

manaskarekar commented 6 years ago

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

fitzgen commented 6 years ago

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.

manaskarekar commented 6 years ago

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!

rustwasm / wee_alloc