What type of input would slow down execution time of dynamic memory allocators malloc() and free()?

Question

I am curious about calculating Worst Case Execution Time of a real-time system and I am trying to find extreme scenarios to predict a worst case time.

What type of input scenarios would slow down the dynamic memory allocation? Thank you.

Answer 1

The free-list being empty would be one case, needing new memory from the OS. The free-list being huge but filled with small blocks too small to satisfy the current request would be another: could trigger walking a big list before finding one, or falling back to another way of getting new memory.

So obviously you'd want to design an allocator's data structures to avoid that problem, perhaps by grouping free lists by size, especially when real-time worst case is a concern.

That's just off the top of my head, and not something I've been involved with designing, so it's certainly not an exhaustive list.