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

Jeff King [off-list ref] wrote:

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

quoted

quoted

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.

quoted

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 :)