git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
René Scharfe <l.s.r@web.de>
Date
May 17, 2026, 16:50 UTC
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:
Show 6 quoted lines
> 
> 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é
Previous: Derrick StoleeNext: Jeff King
Message 4 of 12 in “revision: use priority queue in limit_list()”
  1. revision: use priority queue in limit_list()Kristofer Karlsson via GitGitGadget, May 14, 2026
  2. Junio C HamanoMay 14, 2026
  3. Derrick StoleeMay 14, 2026
  4. René ScharfeMay 17, 2026
  5. Jeff KingMay 15, 2026
  6. Kristofer KarlssonMay 15, 2026
  7. Derrick StoleeMay 15, 2026
  8. Kristofer KarlssonMay 17, 2026
  9. Junio C HamanoMay 17, 2026
  10. Jeff KingMay 19, 2026
  11. Kristofer KarlssonMay 19, 2026
  12. Jeff KingMay 19, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.