From: | Andres Freund <andres(at)anarazel(dot)de> |
---|---|
To: | Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> |
Cc: | Petr Jelinek <petr(dot)jelinek(at)2ndquadrant(dot)com>, Petr Jelinek <petr(at)2ndquadrant(dot)com>, Robert Haas <robertmhaas(at)gmail(dot)com>, John Gorman <johngorman2(at)gmail(dot)com>, pgsql-hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: PATCH: two slab-like memory allocators |
Date: | 2017-02-11 01:41:29 |
Message-ID: | 20170211014129.zriop3nw7rbevcqq@alap3.anarazel.de |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
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
From | Date | Subject | |
---|---|---|---|
Next Message | Ashutosh Sharma | 2017-02-11 01:44:29 | Re: Should we cacheline align PGXACT? |
Previous Message | Peter Geoghegan | 2017-02-11 01:39:55 | Re: amcheck (B-Tree integrity checking tool) |