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

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

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

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