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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
