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.


Andres Freund

Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:

Reply via email to