Re: [PATCH 0/3] Lazy-load trees when reading commit-graph

[Derrick Stolee <stolee@gmail.com>]

On 4/3/2018 9:06 AM, Jeff King wrote:
> On Tue, Apr 03, 2018 at 08:00:54AM -0400, Derrick Stolee wrote:
>
>> There are several commit-graph walks that require loading many commits
>> but never walk the trees reachable from those commits. However, the
>> current logic in parse_commit() requires the root tree to be loaded.
>> This only uses lookup_tree(), but when reading commits from the commit-
>> graph file, the hashcpy() to load the root tree hash and the time spent
>> checking the object cache take more time than parsing the rest of the
>> commit.
>>
>> In this patch series, all direct references to accessing the 'tree'
>> member of struct commit are replaced instead by one of the following
>> methods:
>>
>> 	struct tree *get_commit_tree(struct commit *)
>> 	struct object_id *get_commit_tree_oid(struct commit *)
> This seems like a pretty sane thing to do. There may still be a few
> parts of the code, notably fsck, that are reliant on a "struct object"
> having been instantiated to determine whether an object is "used".  I
> tried to clean that up around the time of c2d17b3b6e (fsck: check
> HAS_OBJ more consistently, 2017-01-16), but I won't be surprised if
> there's still some hidden assumptions.
>
> I peeked at the fsck.c parts of patch 2, and it looks like we may be OK,
> since you use get_commit_tree() during the walk.
>
>> This replacement was assisted by a Coccinelle script, but the 'tree'
>> member is overloaded in other types, so the script gave false-positives
>> that were removed from the diff.
> That catches any existing in-tree callers, but not any topics in flight.
> We could add the Coccinelle script and re-run it to catch any future
> ones. But perhaps simpler still: can we rename the "tree" member to
> "maybe_tree" or something, since nobody should be accessing it directly?
> That will give us a compile error if an older topic is merged.

That's a good idea. I can reorg in v2 to rename 'tree' to 'maybe_tree' 
(and add an explicit comment that 'maybe_tree' could be NULL, so don't 
reference it directly). The check that the rename patch is correct is 
simply "does it compile?" Then Coccinelle could do the transfer of 
"c->maybe_tree" to "get_commit_tree(c)" safely, and can be added to the 
scripts.

I guess one caveat is to not include the mutators (c->maybe_tree = ...), 
but that's probably something Coccinelle can do.

>
>> On the Linux repository, performance tests were run for the following
>> command:
>>
>>      git log --graph --oneline -1000
>>
>> Before: 0.83s
>> After:  0.65s
>> Rel %: -21.6%
> Neat.
>
> Not strictly related, but I happened across another thing today that
> might be worth investigating here. We allocate "struct commit" in these
> nice big allocation blocks. But then for every commit we allocate at
> least one "struct commit_list" to store the parent pointer.
>
> I was looking at this from a memory consumption angle (I found a
> pathological repository full of single-parent commits, and this wastes
> an extra 16 bytes plus malloc overhead for every 64-byte "struct
> commit").
>
> But I wonder if it could also have non-negligible overhead in calling
> malloc() for your case, since you've optimized out so much of the rest
> of the work.

That is a pattern I'm seeing: we strip out one bit and something else 
shows up as a hot spot. This game of whack-a-mole is quite productive.

> I'm not sure what the exact solution would be, but I imagine something
> like variable-sized "struct commit"s with the parent pointers embedded,
> with some kind of flag to indicate the number of parents (and probably
> some fallback to break out to a linked list for extreme cases of more
> than 2 parents).  It may end up pretty invasive, though, as there's a
> lot of open-coded traversals of that parent list.
>
> Anyway, not anything to do with this patch, but food for thought as you
> micro-optimize these traversals.

One other thing that I've been thinking about is that 'struct commit' is 
so much bigger than the other structs in 'union any_object'. This means 
that the object cache, which I think creates blocks of 'union 
any_object' for memory-alignment reasons, is overly bloated. This would 
be especially true when walking many more trees than commits.

Perhaps there are other memory concerns in that case (such as cached 
buffers) that the 'union any_object' is not a concern, but it is worth 
thinking about as we brainstorm how to reduce the parent-list memory.

Thanks,
-Stolee