Re: best-fit algorithm with bitmap heap

[Ondřej Bílka <neleai at seznam dot cz>]

On Wed, Mar 07, 2018 at 02:43:19PM +0000, Wilco Dijkstra wrote:
> 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.
>
No, that is pretty easy to do if you know data structures. Well I
thought that I also send mail with how I do best fit but didn't so I do
that now.

If there are 64 bins then one just needs bitmap bin_map which bins are
empty and which not. Getting first nonempty bin is just three
instructions.

int best_fit_bin(int bin)
{
  return __builtin_ctzl (bin_map & (-1L << bin));
}

For 64*64 bins you need two-level structure with 64 individual bitmaps
and one high bitmap if lower bitmaps are nonzero. Same idea, only done
in two levels.

int best_fit_bin(int bin)
{
  int bin_hi = bin / 64;
  bin = bin % 64;
  if  (bin_map[bin_hi] & (-1L << bin))
    return 64*bin_hi + __builtin_ctzl (bin_map[bin_hi] & (-1L << bin))
  else {
    bin_hi = __builtin_ctzl (high_bin_map & (-1L << (bin_hi+1)));
    return 64*bin_hi + __builtin_ctzl (bin_map[bin_hi]);
  }
}