[RFC] Better data-structure for determining best-fit.

[OndÅej BÃlka <neleai at seznam dot cz>]

Hi,

With different memory layout we could remove most of complexity by using
better data structure which can quickly determine best fit for arbitrary
size.

As I wrote earlier a best fit may not be best from cache reasons as
there may be recently freed block that is slighlty larger but is mostly
in cache. These concerns need to be addressed later, a posible way is
have several generations and keep data structure for each of these.

Approach is almost same as for bins but recursive. For simplicity we 
restrict to 64bit systems where we use a 64ary trie. In leafs of that
trie we will keep linked lists with specified size.

This will allow answer sizes upto 16*64 = 1024 bytes in one lookup, 
upto bytes in two lookups, 4194304 in three lookups and for four 
lookups we hit maximal dynamic mmap treshold.

This causes small additional memory overhead, which is of order 
O(n ^ (1/2)) where n is freed memory, reason is that you could assign a
chunk to each nonempty trie entry and while size trie is 520 bytes
each chunk needs to be 1024 bytes larger than previous one.

For allocating these a best way is use dedicated heap not to block
trimming and also when we return a node we know that it is zeroed.

Here is a lookup code, insertion/deletion would take some work so 
this depends if we could integrate this or write a newgenmalloc
allocator.


#define ARITY 64
#define WIDTH 6

struct trie_node
{
  uint64_t mask; /* i-th bit is nonzero if next[i] is nonnull. */
  struct trie_node *next[ARITY];
  void *least_next; /* Least entry bigger than maximum of trie_node
                       subrange. */
}

struct header
{
  struct trie_node level[10];
}

void *
rec_lookup (struct trie_node *b, uint64_t n, int shift)
{
  int idx = (n >> shift) % ARITY;

  if (b->mask >> idx == 0)
    return b->least_next;

  int next_idx = idx + __builtin_ctz (b->mask >> idx);

  if (shift == 0)
    return b->next[idx];
  else
    return lookup (b->next[idx], n, shift - WIDTH);
}

void *
lookup (struct header *h, uint64_t size)
{
  uint64_t n = size / 16;
  if (__glibc_likely (n < 64)))
    return rec_lookup (h->level[0], n, 0 * WIDTH);

  if (__glibc_likely (n < 64 * 64))
    return rec_lookup (h->level[1], n, 1 * WIDTH);

  if (__glibc_likely (n < 64 * 64 * 64))
    return rec_lookup (h->level[2], n, 2 * WIDTH);

  if (__glibc_likely (n < 64 * 64 * 64 * 64))
    return rec_lookup (h->level[3], n, 3 * WIDTH);

  if (__glibc_likely (n < 64 * 64 * 64 * 64 * 64))
    return rec_lookup (h->level[4], n, 4 * WIDTH);

  return fallback (h, n);
}