Re: [PATCH v3 7/7] revision.c: refactor basic topo-order logic

> From: Derrick Stolee <dstolee@microsoft.com>
>
> When running a command like 'git rev-list --topo-order HEAD',
> Git performed the following steps:
>
> 1. Run limit_list(), which parses all reachable commits,
>     adds them to a linked list, and distributes UNINTERESTING
>     flags. If all unprocessed commits are UNINTERESTING, then
>     it may terminate without walking all reachable commits.
>     This does not occur if we do not specify UNINTERESTING
>     commits.
>
> 2. Run sort_in_topological_order(), which is an implementation
>     of Kahn's algorithm. It first iterates through the entire
>     set of important commits and computes the in-degree of each
>     (plus one, as we use 'zero' as a special value here). Then,
>     we walk the commits in priority order, adding them to the
>     priority queue if and only if their in-degree is one. As
>     we remove commits from this priority queue, we decrement the
>     in-degree of their parents.
>
> 3. While we are peeling commits for output, get_revision_1()
>     uses pop_commit on the full list of commits computed by
>     sort_in_topological_order().
>
> In the new algorithm, these three steps correspond to three
> different commit walks. We run these walks simultaneously,
> and advance each only as far as necessary to satisfy the
> requirements of the 'higher order' walk. We know when we can
> pause each walk by using generation numbers from the commit-
> graph feature.

> In my local testing, I used the following Git commands on the
> Linux repository in three modes: HEAD~1 with no commit-graph,
> HEAD~1 with a commit-graph, and HEAD with a commit-graph. This
> allows comparing the benefits we get from parsing commits from
> the commit-graph and then again the benefits we get by
> restricting the set of commits we walk.
>
> Test: git rev-list --topo-order -100 HEAD
> HEAD~1, no commit-graph: 6.80 s
> HEAD~1, w/ commit-graph: 0.77 s
>    HEAD, w/ commit-graph: 0.02 s
>
> Test: git rev-list --topo-order -100 HEAD -- tools
> HEAD~1, no commit-graph: 9.63 s
> HEAD~1, w/ commit-graph: 6.06 s
>    HEAD, w/ commit-graph: 0.06 s