How to optimize the free() operation of a C memory allocator?

Question

I have a C memory allocator implemented with a circular linked list. The blocks in the freelist are address-sorted. Every time a block is returned to the freelist, the list is iterated to find the proper position to insert and merge with adjacent blocks?

The question is: is there a way to improve the free() operation in terms of performance so that it does not need to iterate through the whole list every time to find the position to insert the block?

I got this question asked in an interview today and had no idea. Can we use a hash or something?

Answer 1

There are many ways to try and optimize access to items in an ordered list.

• Hashing is unlikely to help because you are not trying to find an item in the list, but find the proper place to insert a new item in the list or merge it with an existing one, so you never scan for an existing item.
• keeping the last freed item as the list pointer is simple and efficient if blocks are frequently freed in ascending order of addresses, which may occur in many cases.
• other more sophisticated methods such as trees may help locate the point of insertion faster but must be maintained properly when a free block is later reused. The cost of this maintenance may obviate the advantage in the free() function, especially in a multi-threaded environment.

This allocation strategy does not seem to have any real advantage over classic arena based doubly linked lists or size bins with simple local free lists.