From: René Scharfe Date: Sun, 17 May 2026 16:50:40 GMT Subject: Re: [PATCH] revision: use priority queue in limit_list() Message-ID: <2ecb8188-b593-4b0e-9a55-db66cfd3a409@web.de> In-Reply-To: <7e5abff7-79c9-41c3-9cfa-2aaf0e69a6a8@gmail.com> 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é