Re: [HACKERS] PATCH: two slab-like memory allocators

On 2017-02-11 02:13:59 +0100, Tomas Vondra wrote:
> > > +    /* move the whole block to the right place in the freelist */
> > > +    dlist_delete(&block->node);
> > > +    dlist_push_head(&set->freelist[block->nfree], &block->node);
> > 
> > Hm.  What if we, instead of the array of doubly linked lists, just kept
> > a single linked list of blocks, and keep that list sorted by number of
> > free chunks?  Given that freeing / allocation never changes the number
> > of allocated chunks by more than 1, we'll never have to move an entry
> > far in that list to keep it sorted.
> > 
> 
> Only assuming that there'll be only few blocks with the same number of free
> chunks. If that's not the case, you'll have to walk many blocks to move the
> block to the right place in the list. The array of lists handles such cases
> way more efficiently, and I think we should keep it.

The proper datastructure would probably be a heap.  Right now
binaryheap.h is fixed-size - probably not too hard to change.

Greetings,

Andres Freund