Re: [RFC] Other chunks for commit-graph, part 1 - Bloom filters, topo order, etc.

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On 5/4/2018 3:40 PM, Jakub Narebski wrote:
Hello,

With early parts of commit-graph feature (ds/commit-graph and
ds/lazy-load-trees) close to being merged into "master", see
https://public-inbox.org/git/xmqq4ljtz87g.fsf@xxxxxxxxxxxxxxxxxxxxxxxxx/
I think it would be good idea to think what other data could be added
there to make Git even faster.

Before thinking about adding more data to the commit-graph, I think instead we need to finish taking advantage of the data that is already there. This means landing the generation number patch [1] (I think this is close, so I'll send a v6 this week if there is no new feedback.) and the auto-compute patch [2] (this could use more feedback, but I'll send a v1 based on the RFC feedback if no one chimes in).

[1] https://public-inbox.org/git/20180501124652.155781-1-dstolee@xxxxxxxxxxxxx/
    [PATCH v5 00/11] Compute and consume generation numbers

[2] https://public-inbox.org/git/20180417181028.198397-1-dstolee@xxxxxxxxxxxxx/
    [RFC PATCH 00/12] Integrate commit-graph into 'fsck' and 'gc'

The big wins remaining from this data are `git tag --merged` and `git log --graph`. The `tag` scenario is probably easier: this can be done by replacing the revision-walk underlying the call to use paint_down_to_common() instead. Requires adding an external method to commit.c, but not too much code.

The tougher challenge is `git log --graph`. The revision walk machinery currently uses two precompute phases before iterating results to the pager: limit_list() and sort_in_topological_order(); these correspond to two phases of Kahn's algorithm for topo-sort (compute in-degrees, then walk by peeling commits with in-degree zero). This requires O(N) time, where N is the number of reachable commits. Instead, we could make this be O(W) time to output one page of results, where W is (roughly) the number of reachable commits with generation number above the last reported result.

In order to take advantage of this approach, the two phases of Kahn's algorithm need to be done in-line with reporting results to the pager. This means keeping two queues: one is a priority queue by generation number that computes in-degrees, the other is a priority queue (by commit-date or a visit-order value to do the --topo-order priority) that peels the in-degree-zero commits (and decrements the in-degree of their parents). I have not begun this refactoring effort because appears complicated to me, and it will be hard to tease out the logic without affecting other consumers of the revision-walk machinery.

I would love it if someone picked up the `git log --graph` task, since it will be a few weeks before I have the time to focus on it.

Without completing the benefits we get from generation numbers, these investigations into other reachability indexes will be incomplete as they are comparing benefits without all consumers taking advantage of a reachability index.

[...]
Bloom filter for changed paths
------------------------------

The goal of this chunk is to speed up checking if the file or directory
was changed in given commit, for queries such as "git log -- <file>" or
"git blame <file>".  This is something that according to "Git Merge
contributor summit notes" [2] is already present in VSTS (Visual Studio
Team Services - the server counterpart of GVFS: Git Virtual File System)
at Microsoft:

AV> - VSTS adds bloom filters to know which paths have changed on the commit
AV> - tree-same check in the bloom filter is fast; speeds up file history checks
AV> - might be useful in the client as well, since limited-traversal is common
AV> - if the file history is _very_ sparse, then bloom filter is useful
AV> - but needs pre-compute, so useful to do once
AV> - first make the client do it, then think about how to serve it centrally

[2]: https://public-inbox.org/git/alpine.DEB.2.20.1803091557510.23109@alexmv-linux/

I think it was what Derrick Stolee was talking about at the end of his
part of "Making Git for Windows" presentation at Git Merge 2018:
https://youtu.be/oOMzi983Qmw?t=1835

This was also mentioned in subthread of "Re: [PATCH v2 0/4] Lazy-load
trees when reading commit-graph", starting from [3]
[3]: https://public-inbox.org/git/86y3hyeu6c.fsf@xxxxxxxxx/

Again, the benefits of Bloom filters should only be measured after already taking advantage of a reachability index during `git log`. However, you could get performance benefits from Bloom filters in a normal `git log` (no topo-order).

The tricky part about this feature is that the decisions we made in our C# implementation for the VSTS Git server may be very different than the needs for the C implementation of the Git client. Questions like "how do we handle merge commits?" may have different answers, which can only be discovered by implementing the feature.

(The answer for VSTS is that we only store Bloom filters containing the list of changed paths against the first parent. The second parent frequently has too many different paths, and if we are computing file-history simplification we have already determined the first parent is _not_ TREESAME, which requires verifying the difference by parsing trees against the first parent.)

I'm happy to provide more information on how we built this feature if someone is writing a patch. Otherwise, I plan to implement it after finishing the parts I think are higher priority.

Thanks,
-Stolee



[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]

  Powered by Linux