Re: [PATCH 04/16] Add embedded list interface (header only)

On Tuesday, June 19, 2012 09:16:41 PM Robert Haas wrote:
> On Wed, Jun 13, 2012 at 7:28 AM, Andres Freund <andres(at)2ndquadrant(dot)com>
wrote:
> > Adds a single and a double linked list which can easily embedded into
> > other datastructures and can be used without any additional allocations.
>
> dllist.h advertises that it's embeddable. Can you use that instead,
> or enhance it slightly to support what you want to do?
Oh, wow. Didn't know that existed. I had $subject lying around from a play-
around project, so I didn't look too hard.
Why is that code not used more widely? Quite a bit of our list usage should be
replaced embedding list element in larger structs imo. There are also open-
coded inline list manipulations around (check aset.c for example).

*looks*

Not really that happy with it though:

1. dllist.h has double the element overhead by having an inline value pointer
(which is not needed when embedding) and a pointer to the list (which I have a
hard time seing as being useful)
2. only double linked list, mine provided single and double linked ones
3. missing macros to use when embedded in a larger struct (containerof()
wrappers and for(...) support basically)
4. most things are external function calls...
5. way much more branches/complexity in most of the functions. My
implementation doesn't use any branches for the typical easy modifications
(push, pop, remove element somewhere) and only one for the typical tests
(empty, has-next, ...)

The performance and memory aspects were crucial for the aforementioned toy
project (slab allocator for postgres). Its not that crucial for the applycache
where the lists currently are mostly used although its also relatively
performance sensitive and obviously does a lot of list manipulation/iteration.

If I had to decide I would add the missing api in dllist.h to my
implementation and then remove it. Its barely used - and only in an embedded
fashion - as far as I can see.
I can understand though if that argument is met with doubt by others ;). If
thats the way it has to go I would add some more convenience support for
embedding data to dllist.h and settle for that.

Greetings,

Andres

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services