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

[Eric Wong <e@80x24.org>]

Jeff King <peff@peff.net> wrote:
> On Fri, Aug 05, 2016 at 08:02:31AM +0000, Eric Wong wrote:
> 
> > > 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.

This pattern to avoid that one malloc-per-node using list_entry
(container_of) is actually a common idiom in the Linux kernel
and Userspace RCU (URCU).  Fwiw, I find it less error-prone and
easier-to-follow than the "void *"-first-element thing we do
with hashmap.

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

Yes, it's easier to replace a running process once in a while :)