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

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

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

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