From: | Andres Freund <andres(at)2ndquadrant(dot)com> |
---|---|
To: | pgsql-hackers(at)postgresql(dot)org |
Cc: | Robert Haas <robertmhaas(at)gmail(dot)com>, Tom Lane <tgl(at)postgresql(dot)org>, Peter Geoghegan <peter(at)2ndquadrant(dot)com> |
Subject: | embedded list v2 |
Date: | 2012-06-26 23:26:00 |
Message-ID: | 201206270126.01388.andres@2ndquadrant.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
Hi,
To recapitulate why I think this sort of embedded list is worthwile:
* minimal memory overhead (16 bytes for double linked list heads/nodes on
64bit systems)
* no additional memory allocation overhead
* no additional dereference to access the contents of a list element
* most modifications are completely branchless
* the current dllist.h interface has double the memory overhead and much more
complex manipulation operators
* Multiple places in postgres have grown local single or double linked list
implementations
* I need it ;)
Attached are three patches:
1. embedded list implementation
2. make the list implementation usable without USE_INLINE
3. convert all callers to ilist.h away from dllist.h
For 1 I:
a. added more comments and some introduction, some more functions
b. moved the file from utils/ilist.h to lib/ilist.h
c. actually included the c file with the check functions
d. did *not* split it up into single/double linked list files, doesn't seem to
be worth the trouble given how small ilist.(c|h) are
e. did *not* try to get an interface similar to dllist.h. I don't think the
old one is better and it makes the breakage more obvious should somebody else
use the old implementation although I doubt it.
I can be convinced to do d. and e. but I don't think they are an improvement.
For 2 I used ugly macro hackery to avoid declaring every function twice, in a
c file and in a header.
Opinions on the state of the above patches?
I did not expect any performance difference in the current usage, but just to
be sure I ran the following tests:
connection heavy:
pgbench -n -S -p 5501 -h /tmp -U andres postgres -c 16 -j 16 -T 10 -C
master: 3109 3024 3012
ilist: 3097 3033 3024
somewhat SearchCatCache heavy:
pgbench -n -S -p 5501 -h /tmp -U andres postgres -T 100 -c 16 -j 1
master: 98979.453879 99554.485631 99393.587880
ilist: 98960.545559 99583.319870 99498.923273
As expected the differences are on the level of noise...
Greetings,
Andres
--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services
Attachment | Content-Type | Size |
---|---|---|
0001-Add-embedded-list-interface-header-only.patch | text/x-patch | 14.3 KB |
0002-Rework-the-newly-added-ilist-interface-to-be-usable-.patch | text/x-patch | 10.3 KB |
0003-Remove-usage-of-lib-dllist.h-and-replace-it-by-the-n.patch | text/x-patch | 23.4 KB |
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2012-06-26 23:30:09 | Re: Posix Shared Mem patch |
Previous Message | Alvaro Herrera | 2012-06-26 23:15:26 | Re: Posix Shared Mem patch |