I'm studying malloc and free and writing my own malloc and free. But when I read about the different algorithms (best fit, first fit, worst fit) then it doesn't say which algorithm is used for searching and which is used for sorting.

The best fit strategy is quite simple: first, search through the free list and find chunks of free memory that are as big or bigger than the requested size. Then, return the one that is the smallest in that group of candidates; this is the so called best-fit chunk (it could be called smallest fit too). One pass through the free list is enough to find the correct block to return. The intuition behind best fit is simple: by returning a block that is close to what the user asks, best fit tries to reduce wasted space. However, there is a cost; naive implementations pay a heavy performance penalty when performing an exhaustive search for the correct free block.

Source http://pages.cs.wisc.edu/~remzi/OSTEP/

I hope best fit uses some sort of binary search to find the best fit, is it so or what is the data structure of the free list? If we arrange the free list as a graph then we can binary search it for the best fit and it would take O(log n) to find the best fit among n chunks. Is it that way, better or worse?

  • 1
    The block of text that you quoted: where did it come from? Can you cite your source? – Robert Harvey Jul 27 '16 at 3:55
  • @RobertHarvey I put in the source. It is a good book about operating systems. More code than tanenbaum's book in fewer pages. – Niklas Jul 27 '16 at 4:00
  • 1
    Modern allocators do not work like that. For example jemalloc uses different buckets for different sizes. – CodesInChaos Jul 27 '16 at 6:55

All of the memory management techniques you described assume a singly-linked or doubly-linked list of free memory blocks.

It is certainly possible to use something other than a linked list to manage memory, and there are memory managers that do just that, using an AVL tree or something similar. But then you're no longer talking about algorithms in terms of linear searches.

  • Then I could try my idea with my malloc and free, using a binary tree of chunks instead of a linked list. – Niklas Jul 27 '16 at 4:09
  • 1
    Sure, why not.. – Robert Harvey Jul 27 '16 at 4:12

Most modern implementations of malloc are extremely efficient without using linear-time fitting strategies and instead can often use constant-time operations. See slab allocators as an example.

That said, I've noticed you seem to have an interest in writing a faster memory allocator than malloc. I hope you don't mind but I think that's a very counter-productive idea. When you try to match all the requirements of malloc like thread-safety and the ability to allocate and free arbitrary-sized memory blocks, it's almost unbeatable (maybe a computer architecture expert from Intel or something might be able to come up with something mildly better). Besides that, it's usually not the allocation algorithm that costs so much as, say, the page faults and compulsory cache misses incurred in the process of loading that memory which is an unavoidable cost whenever you request new memory from the heap.

The easiest way to get more performance out of code bottlenecked by malloc and free is to simply use these less often. You can allocate a huge chunk of memory and then just pool it to the areas in your code that need it, potentially in a straightforward sequential fashion (be careful about alignment) if you don't need to free the memory of individual chunks until you're done with the operation (at which point you can free all the pooled memory at once), or say, using a free list if all the memory blocks you are allocating are of the same size (in which case you don't even have to worry about alignment). And if you know you only need that for a given thread, you can pool the memory in a lock-free fashion.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.