Re: [PATCH 0/6] Compute and consume generation numbers

[Derrick Stolee <stolee@gmail.com>]

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