{"thread":{"id":"65638","subject":"[PATCH] revision: use priority queue in limit_list()","startedAt":"2026-05-14T16:51:34Z","lastAt":"2026-05-19T21:56:28Z","messageCount":12,"participants":["Kristofer Karlsson via GitGitGadget","Junio C Hamano","Derrick Stolee","Jeff King","Kristofer Karlsson","René Scharfe"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"543341","messageId":"pull.2114.git.1778777491939.gitgitgadget@gmail.com","threadId":"65638","inReplyTo":null,"subject":"[PATCH] revision: use priority queue in limit_list()","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-14T16:51:31Z","receivedAt":"2026-05-14T16:51:34Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nlimit_list() maintains a date-sorted work queue of commits using a\nlinked list with commit_list_insert_by_date() for insertion.  Each\ninsertion walks the list to find the right position — O(n) per insert.\nIn repositories with merge-heavy histories, the symmetric difference\ncan contain thousands of commits, making this O(n) insertion the\ndominant cost.\n\nReplace the sorted linked list with a prio_queue (binary heap).  This\ngives O(log n) insertion and O(log n) extraction instead of O(n)\ninsertion and O(1) extraction, which is a net win when the queue is\nlarge.\n\nThe still_interesting() and everybody_uninteresting() helpers are\nupdated to scan the prio_queue's contiguous array instead of walking a\nlinked list.  process_parents() already accepts both a commit_list and\na prio_queue parameter, so the change in limit_list() simply switches\nwhich one is passed.\n\nBenchmark: git rev-list --left-right --count HEAD~N...HEAD\nRepository: 2.3M commits, merge-heavy DAG (monorepo)\nBest of 5 runs, times in seconds:\n\n  commits in\n  symmetric diff   baseline   patched    speedup\n  --------------   --------   -------    -------\n            10       0.01      0.01       1.0x\n            50       0.01      0.01       1.0x\n          3751      21.23      8.49       2.5x\n          4524      21.70      8.29       2.6x\n         10130      20.10      6.65       3.0x\n\nNo change for small traversals; 2.5-3.0x faster when the queue grows\nto thousands of commits.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n    revision: use priority queue in limit_list()\n    \n    This patch speeds up limit_list() by 2.5–3x on large, merge-heavy\n    repositories by replacing a sorted linked list with a priority queue.\n    \n    The sorted linked list used as a work queue in limit_list() has O(n)\n    insertion cost per commit, where n is the current queue length (the\n    \"width\" of the active walk frontier). In merge-heavy DAGs this frontier\n    grows wide — profiling on a 2.3M-commit monorepo showed 59% of total CPU\n    time in commit_list_insert_by_date(). Total cost is O(N·w) where N is\n    commits walked and w is peak queue width; in merge-heavy histories w\n    scales with N, approaching O(N²).\n    \n    Switching to a prio_queue (binary heap) reduces insertion cost to O(log\n    w), bringing total cost to O(N·log w). The practical result on the same\n    repository:\n    \n    commits in\n    symmetric diff   before     after      speedup\n    --------------   --------   -------    -------\n            3751      21.2s      8.5s       2.5x\n            4524      21.7s      8.3s       2.6x\n           10130      20.1s      6.6s       3.0x\n    \n    \n    This affects any command that triggers limit_list() — i.e., when\n    revs->limited is set — including --left-right, --cherry-mark,\n    --cherry-pick, --ancestry-path, bisect, and rebase's fork-point\n    computation. The practical trigger is git status --ahead-behind on a\n    branch that has diverged from upstream in a merge-heavy repository.\n    \n    The change is minimal (+21/−17 lines, single file) because\n    process_parents() already accepts both a commit_list and a prio_queue\n    parameter — limit_list() just switches which one it passes.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2114%2Fspkrka%2Flimit-list-prio-queue-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2114/spkrka/limit-list-prio-queue-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2114\n\n revision.c | 38 +++++++++++++++++++++-----------------\n 1 file changed, 21 insertions(+), 17 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 599b3a66c3..2b1b3bb10e 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -473,10 +473,10 @@ static struct commit *handle_commit(struct rev_info *revs,\n \tdie(\"%s is unknown object\", name);\n }\n \n-static int everybody_uninteresting(struct commit_list *orig,\n+static int everybody_uninteresting(struct prio_queue *orig,\n \t\t\t\t   struct commit **interesting_cache)\n {\n-\tstruct commit_list *list = orig;\n+\tsize_t i;\n \n \tif (*interesting_cache) {\n \t\tstruct commit *commit = *interesting_cache;\n@@ -484,9 +484,8 @@ static int everybody_uninteresting(struct commit_list *orig,\n \t\t\treturn 0;\n \t}\n \n-\twhile (list) {\n-\t\tstruct commit *commit = list->item;\n-\t\tlist = list->next;\n+\tfor (i = 0; i < orig->nr; i++) {\n+\t\tstruct commit *commit = orig->array[i].data;\n \t\tif (commit->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n \n@@ -1300,20 +1299,17 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)\n /* How many extra uninteresting commits we want to see.. */\n #define SLOP 5\n \n-static int still_interesting(struct commit_list *src, timestamp_t date, int slop,\n+static int still_interesting(struct prio_queue *src, timestamp_t date, int slop,\n \t\t\t     struct commit **interesting_cache)\n {\n \t/*\n-\t * No source list at all? We're definitely done..\n+\t * Since src is sorted by date, it is enough to peek at the\n+\t * first entry to compare dates.  No entry at all means done.\n \t */\n-\tif (!src)\n+\tstruct commit *commit = prio_queue_peek(src);\n+\tif (!commit)\n \t\treturn 0;\n-\n-\t/*\n-\t * Does the destination list contain entries with a date\n-\t * before the source list? Definitely _not_ done.\n-\t */\n-\tif (date <= src->item->date)\n+\tif (date <= commit->date)\n \t\treturn SLOP;\n \n \t/*\n@@ -1451,6 +1447,7 @@ static int limit_list(struct rev_info *revs)\n \tstruct commit_list *newlist = NULL;\n \tstruct commit_list **p = &newlist;\n \tstruct commit *interesting_cache = NULL;\n+\tstruct prio_queue queue = { .compare = compare_commits_by_commit_date };\n \n \tif (revs->ancestry_path_implicit_bottoms) {\n \t\tcollect_bottom_commits(original_list,\n@@ -1461,6 +1458,11 @@ static int limit_list(struct rev_info *revs)\n \n \twhile (original_list) {\n \t\tstruct commit *commit = pop_commit(&original_list);\n+\t\tprio_queue_put(&queue, commit);\n+\t}\n+\n+\twhile (queue.nr) {\n+\t\tstruct commit *commit = prio_queue_get(&queue);\n \t\tstruct object *obj = &commit->object;\n \n \t\tif (commit == interesting_cache)\n@@ -1468,11 +1470,13 @@ static int limit_list(struct rev_info *revs)\n \n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\n-\t\tif (process_parents(revs, commit, &original_list, NULL) < 0)\n+\t\tif (process_parents(revs, commit, NULL, &queue) < 0) {\n+\t\t\tclear_prio_queue(&queue);\n \t\t\treturn -1;\n+\t\t}\n \t\tif (obj->flags & UNINTERESTING) {\n \t\t\tmark_parents_uninteresting(revs, commit);\n-\t\t\tslop = still_interesting(original_list, date, slop, &interesting_cache);\n+\t\t\tslop = still_interesting(&queue, date, slop, &interesting_cache);\n \t\t\tif (slop)\n \t\t\t\tcontinue;\n \t\t\tbreak;\n@@ -1509,7 +1513,7 @@ static int limit_list(struct rev_info *revs)\n \t\t}\n \t}\n \n-\tcommit_list_free(original_list);\n+\tclear_prio_queue(&queue);\n \trevs->commits = newlist;\n \treturn 0;\n }\n\nbase-commit: 59ff4886a579f4bc91e976fe18590b9ae02c7a08\n-- \ngitgitgadget\n"},{"id":"543356","messageId":"xmqq5x4pg4q1.fsf@gitster.g","threadId":"65638","inReplyTo":"pull.2114.git.1778777491939.gitgitgadget@gmail.com","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-14T19:40:06Z","receivedAt":"2026-05-14T19:40:08Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" <gitgitgadget@gmail.com>\nwrites:\n\n> Benchmark: git rev-list --left-right --count HEAD~N...HEAD\n> Repository: 2.3M commits, merge-heavy DAG (monorepo)\n> Best of 5 runs, times in seconds:\n>\n>   commits in\n>   symmetric diff   baseline   patched    speedup\n>   --------------   --------   -------    -------\n>             10       0.01      0.01       1.0x\n>             50       0.01      0.01       1.0x\n>           3751      21.23      8.49       2.5x\n>           4524      21.70      8.29       2.6x\n>          10130      20.10      6.65       3.0x\n>\n> No change for small traversals; 2.5-3.0x faster when the queue grows\n> to thousands of commits.\n\nImpressive.\n\n> Signed-off-by: Kristofer Karlsson <krka@spotify.com>\n> ---\n>     revision: use priority queue in limit_list()\n> ...\n>     This affects any command that triggers limit_list() — i.e., when\n>     revs->limited is set — including --left-right, --cherry-mark,\n>     --cherry-pick, --ancestry-path, bisect, and rebase's fork-point\n>     computation. The practical trigger is git status --ahead-behind on a\n>     branch that has diverged from upstream in a merge-heavy repository.\n\nI found this description a bit curious.  Notably missing from the\nabove list of revs->limited users is a bog standard A..B and it is\nunclear the omission is because that case is not improved and if so\nwhy.\n\nI think a major reason of the omission of A..B from the above is,\ndespite my recollection that such a range (i.e., any presense of\nUNINTERESTING commit) computation _always_ worked on a limited list,\nthese days we conditionally do not when we have commit graph and we\nare showing in --topo-order (which is implicitly enabled when many\noptions other than --topo-order is in effect) since 1b4d8827\n(revision: use generation for A..B --topo-order queries, 2019-05-21).\n\nIt might be interesting to extend your benchmark over the same\nhistory with the same command line, perhaps with and without an\nexplicit \"--topo-order\" added, in a repository _without_\ncommit-graph enabled.\n\nThanks.\n"},{"id":"543358","messageId":"7e5abff7-79c9-41c3-9cfa-2aaf0e69a6a8@gmail.com","threadId":"65638","inReplyTo":"pull.2114.git.1778777491939.gitgitgadget@gmail.com","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-05-14T19:57:46Z","receivedAt":"2026-05-14T19:57:48Z","isPatch":true,"body":"On 5/14/2026 12:51 PM, Kristofer Karlsson via GitGitGadget wrote:\n> From: Kristofer Karlsson <krka@spotify.com>\n> \n> limit_list() maintains a date-sorted work queue of commits using a\n> linked list with commit_list_insert_by_date() for insertion.  Each\n> insertion walks the list to find the right position — O(n) per insert.\n> In repositories with merge-heavy histories, the symmetric difference\n> can contain thousands of commits, making this O(n) insertion the\n> dominant cost.\n\nLinear operations are bad, especially when multiplied by linear-ish\nloops, causing quadratic behavior.\n\n> Replace the sorted linked list with a prio_queue (binary heap).  This\n> gives O(log n) insertion and O(log n) extraction instead of O(n)\n> insertion and O(1) extraction, which is a net win when the queue is\n> large.\n\nYes, much better.\n\n> The still_interesting() and everybody_uninteresting() helpers are\n> updated to scan the prio_queue's contiguous array instead of walking a\n> linked list.  process_parents() already accepts both a commit_list and\n> a prio_queue parameter, so the change in limit_list() simply switches\n> which one is passed.\n> \n> Benchmark: git rev-list --left-right --count HEAD~N...HEAD\n> Repository: 2.3M commits, merge-heavy DAG (monorepo)\n> Best of 5 runs, times in seconds:\n> \n>   commits in\n>   symmetric diff   baseline   patched    speedup\n>   --------------   --------   -------    -------\n>             10       0.01      0.01       1.0x\n>             50       0.01      0.01       1.0x\n>           3751      21.23      8.49       2.5x\n>           4524      21.70      8.29       2.6x\n>          10130      20.10      6.65       3.0x\n> \n> No change for small traversals; 2.5-3.0x faster when the queue grows\n> to thousands of commits.\n\nThis is good. Is there any chance that you could demonstrate this with\nany commits in the Git repo? It does have some interesting behavior,\nespecially around point releases that are independent from the 'master'\nbranch and thus could have lopsided symmetric differences using well-\nestablished tag names.\n\n>     Switching to a prio_queue (binary heap) reduces insertion cost to O(log\n>     w), bringing total cost to O(N·log w). The practical result on the same\n>     repository:\n>     \n>     commits in\n>     symmetric diff   before     after      speedup\n>     --------------   --------   -------    -------\n>             3751      21.2s      8.5s       2.5x\n>             4524      21.7s      8.3s       2.6x\n>            10130      20.1s      6.6s       3.0x\n\nVery nice! I notice that this data is in your cover letter, but\nnot the commit message. Is that intentional?\n\n>     This affects any command that triggers limit_list() — i.e., when\n>     revs->limited is set — including --left-right, --cherry-mark,\n>     --cherry-pick, --ancestry-path, bisect, and rebase's fork-point\n>     computation. The practical trigger is git status --ahead-behind on a\n>     branch that has diverged from upstream in a merge-heavy repository.\n\nThis also impacts 'git log --graph' when there is no serialized\ncommit-graph file. We are still using limit_list() in that case.\n\n>     The change is minimal (+21/−17 lines, single file) because\n>     process_parents() already accepts both a commit_list and a prio_queue\n>     parameter — limit_list() just switches which one it passes.\n\nThe key logic is turning the initial list into the starting\npoints for the priority queue and everything else is about\nmoving types around, it seems.\n\n> @@ -1451,6 +1447,7 @@ static int limit_list(struct rev_info *revs)\n>  \tstruct commit_list *newlist = NULL;\n>  \tstruct commit_list **p = &newlist;\n>  \tstruct commit *interesting_cache = NULL;\n> +\tstruct prio_queue queue = { .compare = compare_commits_by_commit_date };\n\nHere, we are _not_ using generation numbers, which is correct\nfor this case because we are matching the date-based sorting\nof the previous list.\n\n>  \twhile (original_list) {\n>  \t\tstruct commit *commit = pop_commit(&original_list);\n> +\t\tprio_queue_put(&queue, commit);\n> +\t}\n> +\n> +\twhile (queue.nr) {\n> +\t\tstruct commit *commit = prio_queue_get(&queue);\n>  \t\tstruct object *obj = &commit->object;\n  \nThis is a fun reuse of lines to take the old \"drain the\nlist as it is being mutated\" loop and turn it into \"fill\nthe priority queue\" and \"drain the priority queue as it\nis being mutated\"\n\nThis code change looks good. No new tests are needed, since\nthis is a performance-only change. Do any of the tests in\nt/perf/ demonstrate this improvement?\n\nThanks,\n-Stolee\n\n"},{"id":"543372","messageId":"20260515041641.GA81292@coredump.intra.peff.net","threadId":"65638","inReplyTo":"pull.2114.git.1778777491939.gitgitgadget@gmail.com","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-15T04:16:41Z","receivedAt":"2026-05-15T04:16:42Z","isPatch":true,"body":"On Thu, May 14, 2026 at 04:51:31PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n\n> @@ -1451,6 +1447,7 @@ static int limit_list(struct rev_info *revs)\n>  \tstruct commit_list *newlist = NULL;\n>  \tstruct commit_list **p = &newlist;\n>  \tstruct commit *interesting_cache = NULL;\n> +\tstruct prio_queue queue = { .compare = compare_commits_by_commit_date };\n>  \n>  \tif (revs->ancestry_path_implicit_bottoms) {\n>  \t\tcollect_bottom_commits(original_list,\n> @@ -1461,6 +1458,11 @@ static int limit_list(struct rev_info *revs)\n>  \n>  \twhile (original_list) {\n>  \t\tstruct commit *commit = pop_commit(&original_list);\n> +\t\tprio_queue_put(&queue, commit);\n> +\t}\n> +\n> +\twhile (queue.nr) {\n> +\t\tstruct commit *commit = prio_queue_get(&queue);\n\nHere we push the whole starting list into the prio-queue, which will let\nus pull the commits out in date order. But is the incoming list always\nin date order?\n\nIf revs->unsorted_input, then we don't sort the initial list. So we'd\nnow see the commits in a different order, and put them onto newlist in\nthat different order.\n\nI _think_ it may not matter because we don't call limit_list() when\nrevs->no_walk is set, and we only have revs->unsorted_input when no_walk\nis also set. If that wasn't true, it would get weird when limit_list()\ncalls process_parents(), which uses commit_list_insert_by_date().\n\n\nI was on the lookout for this issue particularly because I have another\npatch which converts revs.commits to a prio_queue totally. And I\nremember running into issues (and the solution is that sometimes the\nprio_queue has a NULL comparator and acts like a LIFO queue). But if my\nanalysis is right above, we can ignore that for now. And if we\neventually move to revs.commits as a prio_queue, then it will just slot\nin nicely here (we can drop the queue generation step and just use it\ndirectly).\n\nThe rest of the patch looks as I'd expect from what my other patch does.\n\n-Peff\n"},{"id":"543383","messageId":"CAL71e4Mfq3SCO7vnTbFCxpzH9txWPTencV-vq-aQ=wJ7dPMV2g@mail.gmail.com","threadId":"65638","inReplyTo":"20260515041641.GA81292@coredump.intra.peff.net","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-15T07:47:31Z","receivedAt":"2026-05-15T07:47:44Z","isPatch":true,"body":"Thanks for the reviews!\n\n**Junio C Hamano**:\nGood question about A..B. Since 1b4d8827 (revision: use\ngeneration for A..B --topo-order queries, 2019-05-21), a plain `A..B`\nwith commit-graph avoids limit_list() entirely via init_topo_walk().\nThe commands I listed are those that still force `revs->limited = 1`\neven with a commit-graph.\n\nAs you suggested, I ran benchmarks without commit-graph. On the same\n2.3M-commit repo with `core.commitGraph=false`:\n\n    git rev-list --left-right --count HEAD~100...HEAD (3,751 sym-diff)\n\n    baseline (no commit-graph):  67.0s\n    patched  (no commit-graph):  43.1s   (1.6x speedup)\n\n    baseline (with commit-graph): 21.2s\n    patched  (with commit-graph):  8.5s   (2.5x speedup)\n\nThe gain is smaller without commit-graph because more time goes to\nparsing commits from pack, but it's still a meaningful improvement.\n\n**Derrick Stolee**:\nUnfortunately git.git's mostly-linear history doesn't\ntrigger the quadratic behavior (the queue stays narrow). Even with\n5,584 commits in the symmetric diff, `--left-right --count` finishes\nin ~0.4s on git.git for both baseline and patched. A 50-pair\ninterleaved run shows no statistically significant difference:\n\n    git rev-list --left-right --count v2.47.1...v2.54.0 (git.git, 5,584 commits)\n    50 interleaved paired runs:\n\n    baseline: mean 393ms, stdev 13ms, median 392ms\n    patched:  mean 396ms, stdev 14ms, median 393ms\n    paired t-test: +2.9ms, t=1.16, p>0.05 (not significant)\n\nThere may be a tiny constant-factor overhead (~1%) from the heap's\nbookkeeping on narrow queues (sift-up/sift-down vs simple pointer\nsplice), but it's well within noise and dwarfed by the 2.5-3x win\non wide queues.\nThe improvement is specific to merge-heavy DAGs where the active\nfrontier (queue width) grows large.\n\nI also measured `--ancestry-path`, which hits the same limit_list()\nbottleneck. 74% of CPU was in commit_list_insert_by_date():\n\n    git log --oneline --ancestry-path HEAD~100..HEAD (monorepo, 100 results)\n\n    baseline: 16.5s\n    patched:   3.8s   (4.3x speedup)\n\nYou're right that `git log --graph` without commit-graph also goes\nthrough limit_list(). I can add that to the description.\n\nRegarding the O(N·w) analysis in the cover letter vs commit message:\nI'll move the key points into the commit message in v2.\n\nThe existing t/perf tests don't cover this path. p0001 doesn't\nuse --left-right and p6010 is merge-base specific. I could add a\nperf test, though it would need a merge-heavy test repo to show the\ndifference. Would a synthetic one (like p6010 does) be useful?\n\n**Jeff King**\nConfirmed: unsorted_input is only set alongside no_walk, and\nlimit_list() is called after the no_walk early return.\nSo the incoming list is always date-sorted when limit_list() runs.\n\nThat said, even if unsorted input did reach this code, the prio_queue\nmaintains its sorted invariant on every prio_queue_put(), so the\noutput order would still be correct; the heap sorts by commit date\nregardless of insertion order.\n\nYour patch to convert revs.commits to a prio_queue sounds like a\nnatural next step; this change would indeed slot right in (the\ninitial drain-and-fill loop would just disappear).\n\nOn Fri, 15 May 2026 at 06:16, Jeff King <peff@peff.net> wrote:\n>\n> On Thu, May 14, 2026 at 04:51:31PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n>\n> > @@ -1451,6 +1447,7 @@ static int limit_list(struct rev_info *revs)\n> >       struct commit_list *newlist = NULL;\n> >       struct commit_list **p = &newlist;\n> >       struct commit *interesting_cache = NULL;\n> > +     struct prio_queue queue = { .compare = compare_commits_by_commit_date };\n> >\n> >       if (revs->ancestry_path_implicit_bottoms) {\n> >               collect_bottom_commits(original_list,\n> > @@ -1461,6 +1458,11 @@ static int limit_list(struct rev_info *revs)\n> >\n> >       while (original_list) {\n> >               struct commit *commit = pop_commit(&original_list);\n> > +             prio_queue_put(&queue, commit);\n> > +     }\n> > +\n> > +     while (queue.nr) {\n> > +             struct commit *commit = prio_queue_get(&queue);\n>\n> Here we push the whole starting list into the prio-queue, which will let\n> us pull the commits out in date order. But is the incoming list always\n> in date order?\n>\n> If revs->unsorted_input, then we don't sort the initial list. So we'd\n> now see the commits in a different order, and put them onto newlist in\n> that different order.\n>\n> I _think_ it may not matter because we don't call limit_list() when\n> revs->no_walk is set, and we only have revs->unsorted_input when no_walk\n> is also set. If that wasn't true, it would get weird when limit_list()\n> calls process_parents(), which uses commit_list_insert_by_date().\n>\n>\n> I was on the lookout for this issue particularly because I have another\n> patch which converts revs.commits to a prio_queue totally. And I\n> remember running into issues (and the solution is that sometimes the\n> prio_queue has a NULL comparator and acts like a LIFO queue). But if my\n> analysis is right above, we can ignore that for now. And if we\n> eventually move to revs.commits as a prio_queue, then it will just slot\n> in nicely here (we can drop the queue generation step and just use it\n> directly).\n>\n> The rest of the patch looks as I'd expect from what my other patch does.\n>\n> -Peff\n"},{"id":"543398","messageId":"aad34ac2-4cd5-4c85-b8ff-14c0caaa1c7b@gmail.com","threadId":"65638","inReplyTo":"CAL71e4Mfq3SCO7vnTbFCxpzH9txWPTencV-vq-aQ=wJ7dPMV2g@mail.gmail.com","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-05-15T13:10:41Z","receivedAt":"2026-05-15T13:10:43Z","isPatch":true,"body":"On 5/15/2026 3:47 AM, Kristofer Karlsson wrote:\n\n> Unfortunately git.git's mostly-linear history doesn't\n> trigger the quadratic behavior (the queue stays narrow). Even with\n> 5,584 commits in the symmetric diff, `--left-right --count` finishes\n> in ~0.4s on git.git for both baseline and patched. A 50-pair\n> interleaved run shows no statistically significant difference:\n> \n>     git rev-list --left-right --count v2.47.1...v2.54.0 (git.git, 5,584 commits)\n>     50 interleaved paired runs:\n> \n>     baseline: mean 393ms, stdev 13ms, median 392ms\n>     patched:  mean 396ms, stdev 14ms, median 393ms\n>     paired t-test: +2.9ms, t=1.16, p>0.05 (not significant)\n\nThanks for sharing these details! Consider my curiosity sated. \n> The existing t/perf tests don't cover this path. p0001 doesn't\n> use --left-right and p6010 is merge-base specific. I could add a\n> perf test, though it would need a merge-heavy test repo to show the\n> difference. Would a synthetic one (like p6010 does) be useful?\n\nI'm usually interested in encoding ways to repeatedly exercise\nthese performance gains and preventing regression in the future.\nHowever, you've demonstrated that not all repositories have a\ndata shape that reveals the performance problem.\n\nIf you happen to find a publicly-available repository that shows\nthis improvement, then documenting the performance benefits for\nthat repo would be sufficient. I'm familiar with performance\nwork that doesn't reveal its most important gains until working\nwith private repositories at the proper scale, so don't sweat\nnot having a public example.\n\nI don't think it's worth constructing a synthetic repo to\ndemonstrate this issue. I was hoping that it would be low-\nhanging fruit to cover this in the perf test suite, but that\ndoes not seem to be the case.\n\nThanks,\n-Stolee\n\n\n"},{"id":"543480","messageId":"CAL71e4MxhcZqxPVEe38Shuqt7h5dxLDGi66hN2cFXnmg-POKWA@mail.gmail.com","threadId":"65638","inReplyTo":"aad34ac2-4cd5-4c85-b8ff-14c0caaa1c7b@gmail.com","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-17T15:26:06Z","receivedAt":"2026-05-17T15:26:18Z","isPatch":true,"body":"Another note - I think I managed to apply the same change to\nget_revision_1 too - speeding up a monorepo \"git rev-list HEAD\" by\n3.3x so it seems like a reasonable thing to do.\nThis simplifies process_parents and also makes\ncommit_list_insert_by_date dead code.\n\nThe only caveat is that get_revision_1 starts to get messier and the\nrev_info struct needs both a prio_queue and a linked list of commits -\nand then flushing everything\nfrom the list into the prio_queue when executing get_revision_1.\n\nI don't want to pollute this patch with that change - should I start a\nseparate thread for it or just revisit this later?\n(Perhaps I have too many optimization patches in flux already)\n\n- Kristofer\n\nOn Fri, 15 May 2026 at 15:10, Derrick Stolee <stolee@gmail.com> wrote:\n>\n> On 5/15/2026 3:47 AM, Kristofer Karlsson wrote:\n>\n> > Unfortunately git.git's mostly-linear history doesn't\n> > trigger the quadratic behavior (the queue stays narrow). Even with\n> > 5,584 commits in the symmetric diff, `--left-right --count` finishes\n> > in ~0.4s on git.git for both baseline and patched. A 50-pair\n> > interleaved run shows no statistically significant difference:\n> >\n> >     git rev-list --left-right --count v2.47.1...v2.54.0 (git.git, 5,584 commits)\n> >     50 interleaved paired runs:\n> >\n> >     baseline: mean 393ms, stdev 13ms, median 392ms\n> >     patched:  mean 396ms, stdev 14ms, median 393ms\n> >     paired t-test: +2.9ms, t=1.16, p>0.05 (not significant)\n>\n> Thanks for sharing these details! Consider my curiosity sated.\n> > The existing t/perf tests don't cover this path. p0001 doesn't\n> > use --left-right and p6010 is merge-base specific. I could add a\n> > perf test, though it would need a merge-heavy test repo to show the\n> > difference. Would a synthetic one (like p6010 does) be useful?\n>\n> I'm usually interested in encoding ways to repeatedly exercise\n> these performance gains and preventing regression in the future.\n> However, you've demonstrated that not all repositories have a\n> data shape that reveals the performance problem.\n>\n> If you happen to find a publicly-available repository that shows\n> this improvement, then documenting the performance benefits for\n> that repo would be sufficient. I'm familiar with performance\n> work that doesn't reveal its most important gains until working\n> with private repositories at the proper scale, so don't sweat\n> not having a public example.\n>\n> I don't think it's worth constructing a synthetic repo to\n> demonstrate this issue. I was hoping that it would be low-\n> hanging fruit to cover this in the perf test suite, but that\n> does not seem to be the case.\n>\n> Thanks,\n> -Stolee\n>\n>\n"},{"id":"543482","messageId":"2ecb8188-b593-4b0e-9a55-db66cfd3a409@web.de","threadId":"65638","inReplyTo":"7e5abff7-79c9-41c3-9cfa-2aaf0e69a6a8@gmail.com","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-05-17T16:50:40Z","receivedAt":"2026-05-17T16:55:56Z","isPatch":true,"body":"On 5/14/26 9:57 PM, Derrick Stolee wrote:\n> \n> This is good. Is there any chance that you could demonstrate this with\n> any commits in the Git repo? It does have some interesting behavior,\n> especially around point releases that are independent from the 'master'\n> branch and thus could have lopsided symmetric differences using well-\n> established tag names.\nCouldn't find cases where the patch avoids quadratic runtimes, but nice\nspeedups nonetheless:\n\n\nBenchmark 1: ./git_main rev-list --bisect v2.0.1..v2.10.1\n  Time (mean ± σ):     108.2 ms ±   1.3 ms    [User: 104.3 ms, System: 3.3 ms]\n  Range (min … max):   106.3 ms … 110.4 ms    27 runs\n\nBenchmark 2: ./git rev-list --bisect v2.0.1..v2.10.1\n  Time (mean ± σ):      93.4 ms ±   0.7 ms    [User: 89.3 ms, System: 3.3 ms]\n  Range (min … max):    92.2 ms …  94.7 ms    31 runs\n\nSummary\n  ./git rev-list --bisect v2.0.1..v2.10.1 ran\n    1.16 ± 0.02 times faster than ./git_main rev-list --bisect v2.0.1..v2.10.1\n\n\nBenchmark 1: ./git_main rev-list --bisect v2.0.1..v2.20.1\n  Time (mean ± σ):     200.6 ms ±   1.8 ms    [User: 196.1 ms, System: 3.7 ms]\n  Range (min … max):   197.3 ms … 203.2 ms    14 runs\n\nBenchmark 2: ./git rev-list --bisect v2.0.1..v2.20.1\n  Time (mean ± σ):     160.1 ms ±   0.9 ms    [User: 155.5 ms, System: 3.8 ms]\n  Range (min … max):   158.7 ms … 161.7 ms    18 runs\n\nSummary\n  ./git rev-list --bisect v2.0.1..v2.20.1 ran\n    1.25 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.20.1\n\n\nBenchmark 1: ./git_main rev-list --bisect v2.0.1..v2.30.1\n  Time (mean ± σ):     384.7 ms ±   2.1 ms    [User: 379.8 ms, System: 4.0 ms]\n  Range (min … max):   382.5 ms … 390.0 ms    10 runs\n\nBenchmark 2: ./git rev-list --bisect v2.0.1..v2.30.1\n  Time (mean ± σ):     300.6 ms ±   0.6 ms    [User: 295.7 ms, System: 4.0 ms]\n  Range (min … max):   299.9 ms … 301.7 ms    10 runs\n\nSummary\n  ./git rev-list --bisect v2.0.1..v2.30.1 ran\n    1.28 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.30.1\n\n\nBenchmark 1: ./git_main rev-list --bisect v2.0.1..v2.40.1\n  Time (mean ± σ):     630.7 ms ±   4.2 ms    [User: 625.5 ms, System: 4.4 ms]\n  Range (min … max):   625.0 ms … 637.4 ms    10 runs\n\nBenchmark 2: ./git rev-list --bisect v2.0.1..v2.40.1\n  Time (mean ± σ):     496.9 ms ±   1.6 ms    [User: 491.6 ms, System: 4.3 ms]\n  Range (min … max):   494.2 ms … 499.5 ms    10 runs\n\nSummary\n  ./git rev-list --bisect v2.0.1..v2.40.1 ran\n    1.27 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.40.1\n\n\nBenchmark 1: ./git_main rev-list --bisect v2.0.1..v2.50.1\n  Time (mean ± σ):     954.3 ms ±   7.9 ms    [User: 948.3 ms, System: 5.1 ms]\n  Range (min … max):   943.0 ms … 965.6 ms    10 runs\n\nBenchmark 2: ./git rev-list --bisect v2.0.1..v2.50.1\n  Time (mean ± σ):     754.8 ms ±   4.4 ms    [User: 748.9 ms, System: 5.0 ms]\n  Range (min … max):   750.4 ms … 765.6 ms    10 runs\n\nSummary\n  ./git rev-list --bisect v2.0.1..v2.50.1 ran\n    1.26 ± 0.01 times faster than ./git_main rev-list --bisect v2.0.1..v2.50.1\n\nRené\n\n"},{"id":"543492","messageId":"xmqqecj9d35x.fsf@gitster.g","threadId":"65638","inReplyTo":"CAL71e4MxhcZqxPVEe38Shuqt7h5dxLDGi66hN2cFXnmg-POKWA@mail.gmail.com","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-05-17T23:31:06Z","receivedAt":"2026-05-17T23:31:09Z","isPatch":true,"body":"Kristofer Karlsson <krka@spotify.com> writes:\n\n> I don't want to pollute this patch with that change - should I start a\n> separate thread for it or just revisit this later?\n> (Perhaps I have too many optimization patches in flux already)\n\nThanks for a great news.  I agree that it is a good idea to find a\ngood stopping point and make improvements step-wise, and the patch\nposted for limit_list() is probably such a good stopping point.\n\nIf we do not see further comments on the current patch, let's merge\nit to 'next', cook it for the standard 7 calendar days or so before\nmerging it down to 'master'.  Further optimizations can be made on\ntop of the updated 'master' branch as new and separate topics.\n"},{"id":"543571","messageId":"20260519005429.GD1612961@coredump.intra.peff.net","threadId":"65638","inReplyTo":"CAL71e4MxhcZqxPVEe38Shuqt7h5dxLDGi66hN2cFXnmg-POKWA@mail.gmail.com","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-19T00:54:29Z","receivedAt":"2026-05-19T00:54:31Z","isPatch":true,"body":"On Sun, May 17, 2026 at 05:26:06PM +0200, Kristofer Karlsson wrote:\n\n> Another note - I think I managed to apply the same change to\n> get_revision_1 too - speeding up a monorepo \"git rev-list HEAD\" by\n> 3.3x so it seems like a reasonable thing to do.\n> This simplifies process_parents and also makes\n> commit_list_insert_by_date dead code.\n> \n> The only caveat is that get_revision_1 starts to get messier and the\n> rev_info struct needs both a prio_queue and a linked list of commits -\n> and then flushing everything\n> from the list into the prio_queue when executing get_revision_1.\n\nIMHO it is worth replacing rev_info's list with a prio_queue and letting\nthat be the source of authority. You do have to be careful to cover\ncases where the list _isn't_ date-sorted, but prio_queue supports that\nwith a NULL comparator.\n\nYou do still have to convert between list and queue at a few spots, but\nI think in the long run many of those could be converted to use a queue.\n\nYou can see my patches to do so at:\n\n  https://github.com/peff/git jk/revs-commits-prio-queue\n\nI've been running with them locally for a few years. Mostly I hadn't\ngotten around to polishing them, and I think I had wanted to do some\nmore perf testing. It sounds like you have a good candidate repo for\nshowing off the improvement. ;)\n\nIf you'd like to go in that direction, please feel free to pick out\nwhatever is useful from what you find on that branch.\n\n> I don't want to pollute this patch with that change - should I start a\n> separate thread for it or just revisit this later?\n> (Perhaps I have too many optimization patches in flux already)\n\nYes, it definitely makes sense to do that as a separate change. If you\nlook at the patches I linked above, note that they'll get a bit simpler\nby rebasing on top of your limit_list() changes, since it does some of\nthe same things.\n\n-Peff\n"},{"id":"543612","messageId":"CAL71e4O6UcnqmxDgqyGqvgvfruSzeoz6Wj5muXiwEp_8y2wAcg@mail.gmail.com","threadId":"65638","inReplyTo":"20260519005429.GD1612961@coredump.intra.peff.net","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-19T09:33:19Z","receivedAt":"2026-05-19T09:33:31Z","isPatch":true,"body":"On Tue, 19 May 2026 at 02:54, Jeff King <peff@peff.net> wrote:\n>\n> On Sun, May 17, 2026 at 05:26:06PM +0200, Kristofer Karlsson wrote:\n>\n> > Another note - I think I managed to apply the same change to\n> > get_revision_1 too - speeding up a monorepo \"git rev-list HEAD\" by\n> > 3.3x so it seems like a reasonable thing to do.\n> > This simplifies process_parents and also makes\n> > commit_list_insert_by_date dead code.\n> >\n> > The only caveat is that get_revision_1 starts to get messier and the\n> > rev_info struct needs both a prio_queue and a linked list of commits -\n> > and then flushing everything\n> > from the list into the prio_queue when executing get_revision_1.\n>\n> IMHO it is worth replacing rev_info's list with a prio_queue and letting\n> that be the source of authority. You do have to be careful to cover\n> cases where the list _isn't_ date-sorted, but prio_queue supports that\n> with a NULL comparator.\n>\n> You do still have to convert between list and queue at a few spots, but\n> I think in the long run many of those could be converted to use a queue.\n>\n> You can see my patches to do so at:\n>\n>   https://github.com/peff/git jk/revs-commits-prio-queue\n>\n> I've been running with them locally for a few years. Mostly I hadn't\n> gotten around to polishing them, and I think I had wanted to do some\n> more perf testing. It sounds like you have a good candidate repo for\n> showing off the improvement. ;)\n>\n> If you'd like to go in that direction, please feel free to pick out\n> whatever is useful from what you find on that branch.\n>\n> > I don't want to pollute this patch with that change - should I start a\n> > separate thread for it or just revisit this later?\n> > (Perhaps I have too many optimization patches in flux already)\n>\n> Yes, it definitely makes sense to do that as a separate change. If you\n> look at the patches I linked above, note that they'll get a bit simpler\n> by rebasing on top of your limit_list() changes, since it does some of\n> the same things.\n>\n> -Peff\n\n\nI didn't know about your prior work on this -- very cool!\n\nI took a look at your branch. Our approaches differ mainly in\nhow broadly the prio_queue replaces the linked list. Here's a summary\nof the tradeoffs as I see them:\n\nYour approach: replace commits entirely with struct prio_queue.\nEvery access site is converted, and boundary cases (bisect,\ntopo-sort, simplify_merges) convert queue->list->queue when they need\nlist-based APIs.\n\nMy approach: keep the linked list for setup and add a separate\ncommit_queue for the walk phase. External callers that read the\nlist between prepare_revision_walk() and the walk are unchanged.\nThe conversion happens once when the walk begins.\n\nA quick size comparison:\n\n  Your branch:  12 files changed, 167 insertions, 152 deletions\n  My branch:     4 files changed, 138 insertions,  78 deletions\n\nThe main reason mine touches fewer files is that the list stays as a\nlist during setup, so bisect.c, builtin/rev-list.c, line-log.c, and\nlist-objects.c don't need changes.\n\nOn the walk side, my second and third commits refactor\nget_revision_1() to use a vtable (\"walk_ops\") that selects the right\npop/expand strategy once and caches it:\n\n    struct revision_walk_ops {\n        void (*init)(struct rev_info *);\n        struct commit *(*next)(struct rev_info *);\n        int (*expand)(struct rev_info *, struct commit *);\n    };\n\n    static struct revision_walk_ops streaming_ops =\n        { rev_info_commit_list_to_queue, next_streaming, expand_streaming };\n    static struct revision_walk_ops limited_ops =\n        { NULL, next_commit_list, NULL };\n    /* ...reflog_ops, topo_ops, no_walk_ops... */\n\nThis replaces the nested if/else chain and makes each walk mode\nself-contained. The init function for streaming_ops drains the list\ninto the queue; limited_ops just pops from the list directly.\n\nThe thing I'm less sure about is the prio_queue dual-mode usage in\nyour branch -- using compare=NULL for FIFO mode. It works, but it\nmeans call sites need to reason about which mode the queue is in\n(heap vs array), and the queue<->list conversions at boundaries add\nup. In the two-field approach, the list is always a list and the\nqueue is always a heap.\n\nThat said, your approach is clearly cleaner long-term if the\nremaining list consumers eventually migrate. And the single-field\ndesign avoids the \"only one should be non-empty\" invariant that\nmine relies on.\n\nI benchmarked both approaches against a 2.4M-commit squash-merge-\nheavy monorepo (best of 3 runs each, commit-graph present):\n\n  Benchmark                             mainline    kk      jk\n  rev-list HEAD (streaming, full DAG)    21.8s     6.9s    6.9s\n  --ancestry-path ~100K (limited)        21.8s     4.8s    5.0s\n  rev-list --count HEAD~10000..HEAD      17.7s     3.7s    3.8s\n  log --oneline -1000                     0.1s     0.1s    0.1s\n\nBoth give ~3-5x speedups over mainline. The streaming walk is\nidentical. On limited walks kk is ~4% faster, which I think comes\nfrom avoiding the queue rebuild at the end of limit_list() -- jk's\ncommit_list_to_queue() drains the result list back into the queue,\nwhile kk leaves the result as a linked list (which the limited walk\nthen just pops from directly).\n\nThe perf profiles confirm this: compare_commits_by_commit_date is\n11.3% in jk vs 8.0% in kk for the ancestry-path case, and\nsift_down_root is 7.3% vs 5.8%. The rest of the profile is\nidentical.\n\nI put up a draft PR with the two follow-up commits (on top of the\nlimit_list change) so you can see the full picture if you're\ncurious:\n\n  https://github.com/gitgitgadget/git/pull/2118\n\nI don't have a strong preference for which approach we end up with,\nsince both will achieve the same performance. So it's mainly a\nquestion about which one is easier to maintain, where everyone else\nin this thread has more stake than I have :)\n\n- Kristofer\n"},{"id":"543709","messageId":"20260519215627.GB2278669@coredump.intra.peff.net","threadId":"65638","inReplyTo":"CAL71e4O6UcnqmxDgqyGqvgvfruSzeoz6Wj5muXiwEp_8y2wAcg@mail.gmail.com","subject":"Re: [PATCH] revision: use priority queue in limit_list()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-19T21:56:27Z","receivedAt":"2026-05-19T21:56:28Z","isPatch":true,"body":"On Tue, May 19, 2026 at 11:33:19AM +0200, Kristofer Karlsson wrote:\n\n> I took a look at your branch. Our approaches differ mainly in\n> how broadly the prio_queue replaces the linked list. Here's a summary\n> of the tradeoffs as I see them:\n> \n> Your approach: replace commits entirely with struct prio_queue.\n> Every access site is converted, and boundary cases (bisect,\n> topo-sort, simplify_merges) convert queue->list->queue when they need\n> list-based APIs.\n> \n> My approach: keep the linked list for setup and add a separate\n> commit_queue for the walk phase. External callers that read the\n> list between prepare_revision_walk() and the walk are unchanged.\n> The conversion happens once when the walk begins.\n\nYeah, I think that is an accurate summary. What I worry about with your\napproach is any code that looks at or modifies the commit list during\nthe traversal. It has to know whether to use the queue or the list.\n\n> On the walk side, my second and third commits refactor\n> get_revision_1() to use a vtable (\"walk_ops\") that selects the right\n> pop/expand strategy once and caches it:\n> \n>     struct revision_walk_ops {\n>         void (*init)(struct rev_info *);\n>         struct commit *(*next)(struct rev_info *);\n>         int (*expand)(struct rev_info *, struct commit *);\n>     };\n> \n>     static struct revision_walk_ops streaming_ops =\n>         { rev_info_commit_list_to_queue, next_streaming, expand_streaming };\n>     static struct revision_walk_ops limited_ops =\n>         { NULL, next_commit_list, NULL };\n>     /* ...reflog_ops, topo_ops, no_walk_ops... */\n\nI looked at the patch you linked for this. I'm undecided on whether this\nmakes things simpler (because the if/else-cascade is in one spot) or\nmore confusing (because now the details are all hidden behind a layer of\nabstraction). \n\n> I benchmarked both approaches against a 2.4M-commit squash-merge-\n> heavy monorepo (best of 3 runs each, commit-graph present):\n> \n>   Benchmark                             mainline    kk      jk\n>   rev-list HEAD (streaming, full DAG)    21.8s     6.9s    6.9s\n>   --ancestry-path ~100K (limited)        21.8s     4.8s    5.0s\n>   rev-list --count HEAD~10000..HEAD      17.7s     3.7s    3.8s\n>   log --oneline -1000                     0.1s     0.1s    0.1s\n> \n> Both give ~3-5x speedups over mainline. The streaming walk is\n> identical. On limited walks kk is ~4% faster, which I think comes\n> from avoiding the queue rebuild at the end of limit_list() -- jk's\n> commit_list_to_queue() drains the result list back into the queue,\n> while kk leaves the result as a linked list (which the limited walk\n> then just pops from directly).\n\nIt would be easy-ish to further convert limit_list() to store newlist as\na queue, and then transfer ownership of its fields into revs->commits\n(i.e., a struct assignment).\n\nOne possible complication is that we do pass \"newlist\" into a few\nsub-functions, like cherry_pick_list(). Looking at that function, it\niterates over the list, but it's not clear to me if the order matters.\nCertainly not in the first loop, but later we do some flag assignments.\nI _think_ they're all independent, but I'm not sure.\n\nObviously we can iterate over the prio_queue in date order with a series\nof get() calls, but that is roughly equivalent to building a list (and\nwe have to rebuild the queue after, too). Of course that is already\nhappening in limit_to_ancestry(), which builds the reverse-order list.\n\nSo I dunno. Moving to the dual-structure state feels messy and\nerror-prone to me, but it does perhaps let us move a little more\nincrementally.\n\n-Peff\n"}]}