Re: What's cooking in git.git (Aug 2016, #02; Thu, 4)

From: Eric Wong <e@80x24.org>
Date: Aug 5, 2016, 08:02 UTC
Message-ID: <20160805080231.GA25379@starla>
In-Reply-To: <20160805074552.6ow4h3lwdy7yxqva@sigill.intra.peff.net>

(Fixed Nico's address)

Jeff King <peff@peff.net> wrote:

Show 23 quoted lines

> On Thu, Aug 04, 2016 at 11:34:35PM +0000, Eric Wong wrote:
> > Junio C Hamano <gitster@pobox.com> wrote:
> > > [Graduated to "master"]
> > 
> > > * ew/http-walker (2016-07-18) 4 commits
> > >   (merged to 'next' on 2016-07-18 at a430a97)
> > >  + list: avoid incompatibility with *BSD sys/queue.h
> > >   (merged to 'next' on 2016-07-13 at 8585c03)
> > >  + http-walker: reduce O(n) ops with doubly-linked list
> > 
> > Yay!  This finally introduces the Linux kernel linked list
> > into git.  I'm not sure if it's worth the effort to introduce
> > cleanup commits to start using it in places where we already
> > have doubly-linked list implementations:
> > 
> > (+Cc Nicolas and Lukas)
> > * sha1_file.c delta_base_cache_lru is open codes this
> > * builtin/pack-redundant.c could probably be adapted, too
> >  ... any more?
> 
> I just introduced another doubly-linked list in [1]. It adds some MRU
> features on top of the list, but it could in theory be built on top of a
> generic doubly-linked list.

Yes, and you'd be avoiding the extra mallocs and be able to use list_entry (aka `container_of`) so it could be faster, too.

I was thinking packed_git could also be a doubly-linked list anyways since it would allow easier removal of unlinked pack entries. My use case would be long-running "cat-file --batch" processes being able to detect unlinked packs after someone else runs GC.

Show 6 quoted lines

> It's also possible the delta-base-cache stuff could build on top of that
> same code, but I didn't look closely at it.
> 
> -Peff
> 
> [1] http://public-inbox.org/git/20160729040659.GC22408@sigill.intra.peff.net/