embedded list v2 - Mailing list pgsql-hackers

From Andres Freund
Subject embedded list v2
Date
Msg-id 201206270126.01388.andres@2ndquadrant.com
Whole thread Raw
Responses Re: embedded list v2
Re: embedded list v3
List 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

pgsql-hackers by date:

Previous
From: Alvaro Herrera
Date:
Subject: Re: Posix Shared Mem patch
Next
From: Tom Lane
Date:
Subject: Re: Posix Shared Mem patch