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
