Re: [PATCH 1/5] trailer: use singly-linked list, not doubly

From: Jeff King <peff@peff.net>
Date: Oct 12, 2016, 17:26 UTC
Message-ID: <20161012172605.tudfyg657cn4e5sj@sigill.intra.peff.net>
In-Reply-To: <CAP8UFD03sOgVVb5-VEgHxHaXBBUPJ9UTB0=Y=th8YnUCk+Aa4Q@mail.gmail.com>

On Wed, Oct 12, 2016 at 05:38:14PM +0200, Christian Couder wrote:

Show 12 quoted lines

> On Wed, Oct 12, 2016 at 3:23 AM, Jonathan Tan <jonathantanmy@google.com> wrote:
> > Use singly-linked lists (instead of doubly-linked lists) in trailer to
> > keep track of arguments (whether implicit from configuration or explicit
> > from the command line) and trailer items.
> >
> > This change significantly reduces the code length and simplifies the code.
> 
> It's true that the code can be simplified a lot by using a
> singly-linked list, but if we already had and used some generic
> functions or macros to handle doubly-linked list, I doubt there would
> be a significant simplification (as the generic code could not be
> deleted in this case).

We didn't have such generic macros when you wrote the trailer code originally, but we do now, in list.h (they come from the kernel's doubly-linked list implementation). I used them recently in a series and found them pretty pleasant and complete.

Maybe it's worth trying the conversion here to see if it simplifies the code.

Show 13 quoted lines

> > There are now fewer pointers to be manipulated, but most trailer
> > manipulations now require seeking from beginning to end, so there might
> > be a slight net decrease in performance; however the number of trailers
> > is usually small (10 to 15 at the most) so this should not cause a big
> > impact.
> 
> By default we append new trailers at the end of the trailer list, so a
> singly-linked list is theoretically not well suited at all for
> handling trailer lists.
> 
> You say that at most there is a small number of trailers, and that may
> be true indeed for the Linux kernel and most projects these days, but
> I am not sure it is a good assumption to make in general.

I agree. As somebody who has fixed quite a number of accidentally quadratic cases in the number of refs, width of the commit graph, etc, over the years, these things have a way of creeping up or finding pathological cases.

You _can_ append to a singly linked list in O(1) if you keep a tail pointer, but I think using list.h would be even nicer.

-Peff