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

On Tue, Jun 19, 2012 at 3:48 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> 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).

Because we've got a million+ lines of code and nobody knows where all
the bodies are buried.

> 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.

I think it might be simpler to leave the name as Dllist and just
overhaul the implementation along the lines you suggest, rather than
replacing it with something completely different. Mostly, I don't
want to add a third thing if we can avoid it, given that Dllist as it
exists today is used only lightly.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company