Page 1 of 1
Can heap managing be made more efficient?
Posted: Fri Oct 09, 2020 9:50 am
by 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?
Re: Can heap managing be made more efficient?
Posted: Sat Oct 10, 2020 7:09 pm
by 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.
Re: Can heap managing be made more efficient?
Posted: Sun Oct 11, 2020 1:12 am
by Octacone
People (not beginners) typically use self-balancing binary trees. Such as AVL trees, red black trees, splay trees, AA-trees etc...
Re: Can heap managing be made more efficient?
Posted: Sun Oct 11, 2020 1:49 am
by bzt
ghzcrlvct wrote: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