On Tue, Jun 19, 2012 at 4:22 PM, Andres Freund <and...@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. 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
