Re: [PATCH v2 1/5] core.aheadbehind: add new config setting

On 4/3/2018 6:18 AM, Ævar Arnfjörð Bjarmason wrote:

Thanks for adding me to CC. I mentioned it in my talk because that was one thing we shipped internally as a "quick fix" until we could do the right thing.

If I remember correctly, Jeff abandoned shipping this upstream because it did have the feel of a hack and we wanted to see if users used the config setting or really cared about the output values. We saw fast adoption of the feature and even turned the config setting on automatically in the following version of GVFS.

You are correct that the commit-graph file may be out of date, causing slower performance. Even worse: the current graph patch only provides a constant-multiple speedup (still walking the same number of commits, but each commit is parsed much faster).

Speaking of our GVFS-specific fork [0], the 'gvfs' branch was updated just yesterday with a couple of changes that I am prepping for submission upstream:

* Lazy-load trees when parsing commits from commit-graph [1]
* Compute and consume generation numbers [2]

Each of these will speed up this ahead/behind calculation in different ways. [1] makes the cost of loading each commit a bit faster, saving up to 20% overall. [2] uses generation numbers in paint_down_to_common() to make the while() condition O(1) instead of O(Q) where Q is the size of the priority queue. The Windows repo is particularly "wide" with many parallel branches being merged in complicated ways, so the queue becomes quite large. This use of generation numbers saves about 4% on some ahead/behind calculations. This speedup is modest, but the existing code already made good use of limiting the commit walk to be mostly the "important" commits.

The real benefit of generation numbers will manifest in a way to make --topo-order much faster when rendering a small number of commits.

The generation numbers _could_ be used to approximate the ahead/behind calculation in the following way: When comparing A and B, and gen(A) < gen(B), then A is at least (gen(B) - gen(A)) behind. That's the only information that can be gathered directly from those values, but may be enough to short circuit an exact count.

To truly accelerate these ahead/behind calculations to be sub-linear* in the ahead/behind counts, we would need a bitmap-based approach. The object-reachability bitmap is a non-starter for client machines in the Windows repo, but perhaps a commit-reachability bitmap could be interesting. Performing set operations on the bitmaps could more quickly answer these questions. Just thinking about it makes me want to go down a deep rabbit hole, investigating ways to compute, store, and use these bitmaps. However: let's wait and see how necessary it is as the commit-graph feature stabilizes. (*These bitmap approaches are not guaranteed to be sub-linear, because it may include iterating through a list of O(N) bits, but good run-length encodings will likely make the count operation very fast, even with a set-difference operation included.)

There are too many fun things to work on, not enough time!

Thanks, -Stolee

[0] https://github.com/microsoft/git
     Fork of GitForWindows that ships to Windows developers

[1] 
https://github.com/Microsoft/git/commit/29114bf86f591f5c87075f779a1faa2d0f17b92f
     Lazy-load trees when parsing commits from commit-graph 
(accidentally squashed to one commit)

[2] 
https://github.com/microsoft/git/compare/879b7d3b1bddea2587b28cdd656c9c655018683a...a0731ca93a35fd042560c4b30e8e0edbdfa4bf9f
     Compute and consume generation numbers