best-fit algorithm with bitmap heap

[Wilco Dijkstra]

Ondřej Bílka wrote:
> No, there is no searching and as I described it is really easy.

There is always a search here and that is completely unavoidable.

If you have a free list which contains multiple different sizes, you need
to walk it until you get a block that fits. This could be slow if there are
thousands of entries in that free list. If you use individual free lists for
every supported allocation size (only practical for small sizes), and the
free list for the requested size is empty, you now need to search all larger
free lists until you find one which isn't empty (if you cache which sizes
have free blocks then that's yet another data structure to keep up to date).

I think bitmaps are a good choice for allocation of small fixed size blocks,
but for medium sized blocks it's less clear.

Wilco