Re: [PATCH] revision: use priority queue in limit_list()

[Junio C Hamano <gitster@pobox.com>]

"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>
writes:

> Benchmark: git rev-list --left-right --count HEAD~N...HEAD
> Repository: 2.3M commits, merge-heavy DAG (monorepo)
> Best of 5 runs, times in seconds:
>
>   commits in
>   symmetric diff   baseline   patched    speedup
>   --------------   --------   -------    -------
>             10       0.01      0.01       1.0x
>             50       0.01      0.01       1.0x
>           3751      21.23      8.49       2.5x
>           4524      21.70      8.29       2.6x
>          10130      20.10      6.65       3.0x
>
> No change for small traversals; 2.5-3.0x faster when the queue grows
> to thousands of commits.

Impressive.

> Signed-off-by: Kristofer Karlsson <krka@spotify.com>
> ---
>     revision: use priority queue in limit_list()
> ...
>     This affects any command that triggers limit_list() — i.e., when
>     revs->limited is set — including --left-right, --cherry-mark,
>     --cherry-pick, --ancestry-path, bisect, and rebase's fork-point
>     computation. The practical trigger is git status --ahead-behind on a
>     branch that has diverged from upstream in a merge-heavy repository.

I found this description a bit curious.  Notably missing from the
above list of revs->limited users is a bog standard A..B and it is
unclear the omission is because that case is not improved and if so
why.

I think a major reason of the omission of A..B from the above is,
despite my recollection that such a range (i.e., any presense of
UNINTERESTING commit) computation _always_ worked on a limited list,
these days we conditionally do not when we have commit graph and we
are showing in --topo-order (which is implicitly enabled when many
options other than --topo-order is in effect) since 1b4d8827
(revision: use generation for A..B --topo-order queries, 2019-05-21).

It might be interesting to extend your benchmark over the same
history with the same command line, perhaps with and without an
explicit "--topo-order" added, in a repository _without_
commit-graph enabled.

Thanks.