Can heap managing be made more efficient?

[ghzcrlvct]

Not developing an OS myself, but as far as I know linked lists are commonly used for heap management, with each node being stored before the actual heap block a user allocates.

Is there some way this method seems to be so commonly used? Is there not a better way to manage a heap out there?

[klange]

Heaps made of linked lists are only a simple beginner implementation. Real heap implementations don't work that way and have been tuned for various performance properties.

[Octacone]

People (not beginners) typically use self-balancing binary trees. Such as AVL trees, red black trees, splay trees, AA-trees etc...

[bzt]

each node being stored before the actual heap block a user allocates.

That's pretty specific to Doug Lea's malloc and its successor, ptmalloc which was based on it. Most allocators don't do that (like Hoard, jemalloc etc.).

The Linux kernel for example uses linked lists of slabs, one node per partition (each partition stores allocations of the same quantum size, called slabs).

My allocator for example never mixes node data with application data, and it doesn't use linked lists at all (it has three different node types depending on quantum size).

Cheers,
bzt