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

On Wednesday, June 20, 2012 05:01:16 AM Robert Haas wrote:
> On Tue, Jun 19, 2012 at 4:22 PM, Andres Freund <andres@2ndquadrant.com> 
wrote:
> >> > 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.
> My guess is that it wouldn't be too hard to remove some of the extra
> pointers.  Anyone who is using Dllist as a non-inline list could be
> converted to List * instead. 
There are only three users of the whole dllist.h. Catcache, autovacuum and 
postmaster. The latter two just keep a list of databases around. So any change 
will only be moderatively intrusive.

> Also, the performance-critical things
> could be reimplemented as macros. 

> I question, though, whether we really need both single and doubly linked
> lists.  That seems like it's almost certainly micro-optimization that we are
> better off not doing.
It was certainly worthwile for the memory manager (lower per allocation 
overhead). You might be right that its not worth it for many other possible 
usecases in pg. Its not much code though.

*looks around*

A quick grep found:

single linked list like code:  guc_private.h, aset.c, elog.h, regguts.h (ok, 
irrelevant), dynahash.c, resowner.c, extension.c, pgstat.c, xlog.c
Double linked like code: shmqueue.c, lwlock.c, dynahash.c, xact.c

I stopped at that point because while surely not of all of the above usecases 
could be replaced by a common implementation several could from a quick look. 
Also, several pg_list.h users could benefit from a conversion. So I think 
adding a single linked list implementation is worthwile.

> > 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.
> I would be hesitant to chuck that even though I realize it's unlikely
> that we really need !USE_INLINE.  But see sortsupport for an example
> of how we've handled this in the recent past.
I agree its possible to resolve this. But hell, do we really need to add all 
that ugliness in 2012? I don't think its worth the effort of support ancient 
compilers that don't support inline anymore. If we could stop trying to 
support catering for probably non-existing compilers we could remove some 
*very* ugly long macros for example (e.g. in htup.h).

If support for !USE_INLINE is required I would prefer to have an header define 
the functions like

#ifdef USE_INLINE
#define OPTIONALLY_INLINE static inline
#define USE_LINKED_LIST_IMPL
#endif

#ifdef USE_LINKED_LIST_IMPL

OPTIONALLY_INLINE void myFuncCall(){
...
}
#endif

which then gets included with #define USE_LINKED_LIST_IMPL by some c file 
defining OPTIONALLY_INLINE to something empty if !USE_INLINE.
Its too much code to duplicate imo.

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