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

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

 



On 4/3/2018 6:18 AM, Ævar Arnfjörð Bjarmason wrote:
On Tue, Apr 03 2018, Lars Schneider wrote:
What is the state of this series? I can't find it in git/git nor in
git-for-windows/git. I think Stolee mentioned the config in
his Git Merge talk [1] and I was about to test it/roll it out :-)
It's in the gvfs branch of git@xxxxxxxxxx:Microsoft/git.git, i.e. it's
not in Git for Windows, but used in Microsoft's own in-house version
used for Windows.git.

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.

I may be misunderstanding this feature, but my impression was that it
was a kludge as a workaround until the commit graph code landed, because
once we have that then surely we can just cheaply report the actual (or
approximate?) number in the common case, but of course it may still be
slow if your commit graph file is out of date.

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



[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