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:26:30AM +0000, Eric Wong wrote:

quoted

quoted

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.

My big problem with it is that it gets confusing when a particular
struct is a member of several lists. We have had bugs in git where
a struct ended up being used in two different lists, but accidentally
using the same "next" pointer.

It might actually be easier since you would rarely (if ever)
touch the "next"/"prev" fields in your code.  This encourages
users to give meaningful names to list_head fields.

So you need one "list_head" for each list that your struct may be a part
of. Sometimes that's simple, but it's awkward when the code which wants
the list is different than the code which "owns" the struct. Besides
leaking concerns across modules, the struct may not want to pay the
memory price for storing pointers for all of the possible lists it could
be a member of.

Yes, the key is this list is flexible enough to be used either way:

	/* there are millions of these structs in practice */
	struct common_struct {
		struct list_head hot_ent;
		...
	};

	/* and only a handful of these */
	struct rarely_used_wrapper {
		struct list_head cold_ent;
		struct common_struct *common;
		...
	};

For instance, I think it would be a mistake to convert the current
commit_list code to something like this.

Of course, often a doubly-linked list is not needed or the extra
pointer is too expensive.  Linux/URCU have hlist for this reason.

I'm no expert on git internals, either; but there can be
readability improvements, too.  For example, I find http-walker.c
is easier-to-follow after 94e99012fc7a
("http-walker: reduce O(n) ops with doubly-linked list")