OSDev.org

The Place to Start for Operating System Developers
It is currently Fri Mar 29, 2024 12:09 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 4 posts ] 
Author Message
 Post subject: Can heap managing be made more efficient?
PostPosted: Fri Oct 09, 2020 9:50 am 
Offline

Joined: Fri Oct 09, 2020 9:44 am
Posts: 5
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?


Top
 Profile  
 
 Post subject: Re: Can heap managing be made more efficient?
PostPosted: Sat Oct 10, 2020 7:09 pm 
Offline
Member
Member

Joined: Wed Mar 30, 2011 12:31 am
Posts: 676
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.

_________________
toaruos on github | toaruos.org | gitlab | twitter | bim - a text editor


Top
 Profile  
 
 Post subject: Re: Can heap managing be made more efficient?
PostPosted: Sun Oct 11, 2020 1:12 am 
Offline
Member
Member
User avatar

Joined: Fri Aug 07, 2015 6:13 am
Posts: 1134
People (not beginners) typically use self-balancing binary trees. Such as AVL trees, red black trees, splay trees, AA-trees etc...

_________________
OS: Basic OS
About: 32 Bit Monolithic Kernel Written in C++ and Assembly, Custom FAT 32 Bootloader


Top
 Profile  
 
 Post subject: Re: Can heap managing be made more efficient?
PostPosted: Sun Oct 11, 2020 1:49 am 
Offline
Member
Member
User avatar

Joined: Thu Oct 13, 2016 4:55 pm
Posts: 1584
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


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: Bing [Bot], Google [Bot] and 85 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group