Search code examples
ckernighan-and-ritchie

K&R Storage Allocator clarification

I have some questions regarding the storage allocator in Kernighan - Ritchie: The C Programming Language - The Unix System Interface, page 185-189?

It says on page 186:

The search for a free block of adequate size begins at the point (freep) where the last block was found; this strategy helps keep the list homogeneous.

As I see, we don't necessarily need freep, we could start each search from base.

  • How does this strategy keep the list homogeneous?
  • Why do we need freep at all? Does it decrease search time? (I mean, only free blocks are in the list, so we can start anywhere, right?)
Solution

  • If you always start at the beginning, you will drain the beginning of the list of larger blocks (because they satisfy requests more easily). So the list will start with lots of smaller blocks, and requests for medium or larger sizes will have to traverse more of the list to get to something suitable.