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

From: Jeff King <peff@peff.net>
Date: Aug 5, 2016, 08:11 UTC
Message-ID: <20160805081103.t5f4bapmia6vircg@sigill.intra.peff.net>
In-Reply-To: <20160805080231.GA25379@starla>

On Fri, Aug 05, 2016 at 08:02:31AM +0000, Eric Wong wrote:

Show 6 quoted lines

> > 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'm not sure which mallocs you mean. I allocate one struct per node, which seems like a requirement for a linked list. If you mean holding an extra list struct around an existing pointer (rather than shoving the prev/next pointers into the pointed-to- item), then yes, we could do that. But it feels like a bit dirty, since the point of the list is explicitly to provide an alternate ordering over an existing set of items.

It also doesn't make a big difference for my use case. All I really care about is the speed of delete-from-middle-and-insert-at-front, which is trivially O(1) and involves no mallocs.

Show 5 quoted lines

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

We never remove packed_git structs, but it is not because of the list data structure. We may be holding open mmaps to packs that are deleted and continue using them. And in some cases other code may even hold pointers to our packed_git structs. So you'd have to figure out some memory ownership questions first.

-Peff