Optimization: Storing bins as a singly-linked ring saves one u32 per Node

[djkoloski]

Thanks for providing a quality general-purpose external allocator! The community has been very much in need of one. I came up with a small optimization I use in my personal TLSF implementation that might be of interest to you.

In the original TLSF paper and most implementations, SL freelists (I think they're called bins in this implementation) are maintained as doubly-linked lists where the control structure points to the head of the list. However, a singly-linked list can be used instead for external allocation data with a little elbow grease.

Terminology

The "leader" of a bin is the block in the bin that the control structure points to. This is like the head of a free list, except it's for a singly-linked loop of free blocks.

For inserts into the free loop:

• If the loop is empty, make a new loop. Set the leader of the free loop to the inserted block and have the next_free of the block point to itself.
• If the loop is not empty, point the inserted block's next_free to the leader's next_free and point the leader's next_free to the inserted block.

For removals from the free loop:

• If the removed node points to itself (next_free = block index), then removing it makes the free loop entry. Set the leader to null.
• Otherwise, there are at least two nodes in the free loop. Since the previous node in the free loop is pointing at this node and we don't know which one that is, we can't just remove it from the list. Instead, we want to find another free block ahead of this block in the free loop, swap the contents of these blocks, and then remove the block we swapped this node's contents into. There's one more wrinkle here: the control structure may be pointing to one of those nodes if it's the leader. There are a few options for how to address this:
  • When a block is swap-removed, always set the leader of the free loop to the current node (the one we swapped the next node into).
  • If the next node is the leader, swap-remove with the node after the leader (the "nextnext" node).

Optional optimization

You can avoid checking the control structure to see which node is the leader by maintaining an additional invariant that the leader of a free loop is the block with the lowest index. For inserts, just update the leader if you insert a lower block. For removals, just swap-remove with whichever of next and nextnext has the higher index since that can't be the leader (or just next if it has a higher index than the block being removed).