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

["René Scharfe" <l.s.r@web.de>]

On 5/14/26 9:57 PM, Derrick Stolee wrote:
> 
> This is good. Is there any chance that you could demonstrate this with
> any commits in the Git repo? It does have some interesting behavior,
> especially around point releases that are independent from the 'master'
> branch and thus could have lopsided symmetric differences using well-
> established tag names.
Couldn't find cases where the patch avoids quadratic runtimes, but nice
speedups nonetheless:


Benchmark 1: ./git_main rev-list --bisect v2.0.1..v2.10.1
  Time (mean ± σ):     108.2 ms ±   1.3 ms    [User: 104.3 ms, System: 3.3 ms]
  Range (min … max):   106.3 ms … 110.4 ms    27 runs

Benchmark 2: ./git rev-list --bisect v2.0.1..v2.10.1
  Time (mean ± σ):      93.4 ms ±   0.7 ms    [User: 89.3 ms, System: 3.3 ms]
  Range (min … max):    92.2 ms …  94.7 ms    31 runs

Summary
  ./git rev-list --bisect v2.0.1..v2.10.1 ran
    1.16 ± 0.02 times faster than ./git_main rev-list --bisect v2.0.1..v2.10.1


Benchmark 1: ./git_main rev-list --bisect v2.0.1..v2.20.1
  Time (mean ± σ):     200.6 ms ±   1.8 ms    [User: 196.1 ms, System: 3.7 ms]
  Range (min … max):   197.3 ms … 203.2 ms    14 runs

Benchmark 2: ./git rev-list --bisect v2.0.1..v2.20.1
  Time (mean ± σ):     160.1 ms ±   0.9 ms    [User: 155.5 ms, System: 3.8 ms]
  Range (min … max):   158.7 ms … 161.7 ms    18 runs

Summary
  ./git rev-list --bisect v2.0.1..v2.20.1 ran
    1.25 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.20.1


Benchmark 1: ./git_main rev-list --bisect v2.0.1..v2.30.1
  Time (mean ± σ):     384.7 ms ±   2.1 ms    [User: 379.8 ms, System: 4.0 ms]
  Range (min … max):   382.5 ms … 390.0 ms    10 runs

Benchmark 2: ./git rev-list --bisect v2.0.1..v2.30.1
  Time (mean ± σ):     300.6 ms ±   0.6 ms    [User: 295.7 ms, System: 4.0 ms]
  Range (min … max):   299.9 ms … 301.7 ms    10 runs

Summary
  ./git rev-list --bisect v2.0.1..v2.30.1 ran
    1.28 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.30.1


Benchmark 1: ./git_main rev-list --bisect v2.0.1..v2.40.1
  Time (mean ± σ):     630.7 ms ±   4.2 ms    [User: 625.5 ms, System: 4.4 ms]
  Range (min … max):   625.0 ms … 637.4 ms    10 runs

Benchmark 2: ./git rev-list --bisect v2.0.1..v2.40.1
  Time (mean ± σ):     496.9 ms ±   1.6 ms    [User: 491.6 ms, System: 4.3 ms]
  Range (min … max):   494.2 ms … 499.5 ms    10 runs

Summary
  ./git rev-list --bisect v2.0.1..v2.40.1 ran
    1.27 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.40.1


Benchmark 1: ./git_main rev-list --bisect v2.0.1..v2.50.1
  Time (mean ± σ):     954.3 ms ±   7.9 ms    [User: 948.3 ms, System: 5.1 ms]
  Range (min … max):   943.0 ms … 965.6 ms    10 runs

Benchmark 2: ./git rev-list --bisect v2.0.1..v2.50.1
  Time (mean ± σ):     754.8 ms ±   4.4 ms    [User: 748.9 ms, System: 5.0 ms]
  Range (min … max):   750.4 ms … 765.6 ms    10 runs

Summary
  ./git rev-list --bisect v2.0.1..v2.50.1 ran
    1.26 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.50.1

René