On 4/3/2018 2:03 PM, Brandon Williams wrote:
On 04/03, Derrick Stolee wrote:
This is the first of several "small" patches that follow the serialized
Git commit graph patch (ds/commit-graph).
As described in Documentation/technical/commit-graph.txt, the generation
number of a commit is one more than the maximum generation number among
its parents (trivially, a commit with no parents has generation number
one).
Thanks for ensuring that this is defined and documented somewhere :)
This series makes the computation of generation numbers part of the
commit-graph write process.
Finally, generation numbers are used to order commits in the priority
queue in paint_down_to_common(). This allows a constant-time check in
queue_has_nonstale() instead of the previous linear-time check.
This does not have a significant performance benefit in repositories
of normal size, but in the Windows repository, some merge-base
calculations improve from 3.1s to 2.9s. A modest speedup, but provides
an actual consumer of generation numbers as a starting point.
A more substantial refactoring of revision.c is required before making
'git log --graph' use generation numbers effectively.
log --graph should benefit a lot more from this correct? I know we've
talked a bit about negotiation and I wonder if these generation numbers
should be able to help out a little bit with that some day.
'log --graph' should be a HUGE speedup, when it is refactored. Since the
topo-order can "stream" commits to the pager, it can be very responsive
to return the graph in almost all conditions. (The case where generation
numbers are not enough is when filters reduce the set of displayed
commits to be very sparse, so many commits are walked anyway.)
If we have generic "can X reach Y?" queries, then we can also use
generation numbers there to great effect (by not walking commits Z with
gen(Z) <= gen(Y)). Perhaps I should look at that "git branch --contains"
thread for ideas.
For negotiation, there are some things we can do here. VSTS uses
generation numbers as a heuristic for determining "all wants connected
to haves" which is a condition for halting negotiation. The idea is very
simple, and I'd be happy to discuss it on a separate thread.
Thanks,
-Stolee
