I study malloc, sbrk and free list management. Now I wonder why the free list isn't sorted in some way, it seems that it could benefit from being a search tree instead of a plain linked list. The way it looks in the book I'm reading is just a list with free chunks of memory of arbitrary sizes. It seems trivial that if we keep the list sorted then the first fit will also be the best fit.
I'm certain this has been considered before but why isn't it done?
Most of the algorithms presented in that section mostly aim at reducing fragmentation and search cost. Under the section "Other Ideas" he mentions his reasoning when presenting first fit, best fit, worst fit etc...
One major problem with many of the approaches described above is their lack of scaling. Specifically, searching lists can be quite slow. Thus, advanced allocators use more complex data structures to address these costs, trading simplicity for performance. Examples include balanced binary trees, splay trees, or partially-ordered trees [W+95].