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

From: Derrick Stolee <stolee@gmail.com>
Date: Apr 8, 2018, 01:17 UTC
Message-ID: <eb861bc6-b9f0-ccaa-7cb6-abdb0d343c3d@gmail.com>
In-Reply-To: <86y3hyeu6c.fsf@gmail.com>

On 4/7/2018 2:40 PM, Jakub Narebski wrote:

Show 23 quoted lines

> Derrick Stolee <dstolee@microsoft.com> writes:
>
> [...]
>> On the Linux repository, performance tests were run for the following
>> command:
>>
>>      git log --graph --oneline -1000
>>
>>      Before: 0.92s
>>      After:  0.66s
>>      Rel %: -28.3%
>>
>> Adding '-- kernel/' to the command requires loading the root tree
>> for every commit that is walked. There was no measureable performance
>> change as a result of this patch.
> In the "Git Merge contributor summit notes" [1] one can read that:
>
>> - VSTS adds bloom filters to know which paths have changed on the commit
>> - tree-same check in the bloom filter is fast; speeds up file history checks
>> - if the file history is _very_ sparse, then bloom filter is useful
> Could this method speed up also the second case mentioned here?  Can
> anyone explain how this "path-changed bloom filter" works in VSTS?
>

The idea is simple: for every commit, store a Bloom filter containing the list of paths that are not TREESAME against the first parent. (A slight detail: have a max cap on the number of paths, and store simply "TOO_BIG" for commits with too many diffs.)

When performing 'git log -- path' queries, the most important detail for considering how to advance the walk is whether the commit is TREESAME to its first parent. For a deep path in a large repo, this is almost always true. When a Bloom filter says "TREESAME" (i.e. "this path is not in my set") it is always correct, so we can set the treesame bit and continue without walking any trees. When a Bloom filter says "MAYBE NOT TREESAME" (i.e. "this path is probably in my set") you only need to do the same work as before: walk the trees to compare against your first parent.

If a Bloom filter has a false-positive rate of X%, then you can possibly drop your number of tree comparisons by (100-X)%. This is very important for large repos where some paths were changed only ten times or so, the full graph needs to be walked and it is helpful to avoid parsing too many trees.

> Could we add something like this to the commit-graph file?

I'm not sure if it is necessary for client-side operations, but it is one of the reasons the commit-graph file has the idea of an "optional chunk". It could be added to the file format (without changing version numbers) and be ignored by clients that don't understand it. I could also be gated by a config setting for computing them. My guess is that only server-side operations will need the added response time, and can bear the cost of computing them when writing the commit-graph file. Clients are less likely to be patient waiting for a lot of diff calculations.

If we add commit-graph file downloads to the protocol, then the server could do this computation and send the data to all clients. But that would be "secondary" information that maybe clients want to verify, which is as difficult as computing it themselves.

Thanks,

-Stolee