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

On Tuesday, June 19, 2012 09:58:43 PM Robert Haas wrote:
> On Tue, Jun 19, 2012 at 3:48 PM, Andres Freund <andres@2ndquadrant.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.
Heh, yes ;). Ive hit several times as you uncovered at least twice ;)

> > 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.
Well, if its the name, I have no problem with changing it, but I don't see how 
you can keep the api as it currently is and address my points.

If there is some buyin I can try to go either way (keeping the existing name, 
changing the api, adjusting the callers or just adjust the callers, throw away 
the old implementation) I just don't want to get into that just to see 
somebody isn't agreeing with the fundamental idea.

The most contentious point is probably relying on USE_INLINE being available 
anywhere. Which I believe to be the point now that we have gotten rid of some 
platforms.

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