Skip site navigation (1) Skip section navigation (2)

embedded list v2

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 (view raw or flat)
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: 0003-Remove-usage-of-lib-dllist.h-and-replace-it-by-the-n.patch
Description: text/x-patch (23.4 KB)
Attachment: 0002-Rework-the-newly-added-ilist-interface-to-be-usable-.patch
Description: text/x-patch (10.3 KB)
Attachment: 0001-Add-embedded-list-interface-header-only.patch
Description: text/x-patch (14.3 KB)

Responses

pgsql-hackers by date

Next:From: Tom LaneDate: 2012-06-26 23:30:09
Subject: Re: Posix Shared Mem patch
Previous:From: Alvaro HerreraDate: 2012-06-26 23:15:26
Subject: Re: Posix Shared Mem patch

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group