{"thread":{"id":"65700","subject":"[PATCH 0/3] revision: use priority queue for streaming walks","startedAt":"2026-05-27T15:50:05Z","lastAt":"2026-05-27T15:50:08Z","messageCount":4,"participants":["Kristofer Karlsson via GitGitGadget"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"544171","messageId":"pull.2127.git.1779897003.gitgitgadget@gmail.com","threadId":"65700","inReplyTo":null,"subject":"[PATCH 0/3] revision: use priority queue for streaming walks","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-27T15:49:59Z","receivedAt":"2026-05-27T15:50:05Z","isPatch":true,"body":"This is a follow-up to kk/limit-list-optim (now in master), which replaced\nthe O(N) sorted linked-list insertion in limit_list() with a priority queue.\nIn the review thread for that patch, I mentioned that the same approach\ncould be applied to the streaming (non-limited) walk in get_revision_1().\nJunio suggested doing it as a separate topic, and Peff noted he had a local\nbranch (jk/revs-commits-prio-queue) doing a broader conversion of\nrevs->commits to prio_queue entirely.\n\nThis series takes a lighter-weight approach: it keeps the linked list for\nsetup and external callers, and adds a separate commit_queue field that the\nstreaming walk drains into on first use. This avoids touching bisect,\nline-log, and list-objects code, at the cost of a \"only one should be\nnon-empty\" invariant between the two fields.\n\nTogether with the limit_list() change already in master, this eliminates all\ncommit_list_insert_by_date() callers from revision.c.\n\nPatch 1 is a small leak fix -- a missing release_revisions() call in\npack-objects that becomes visible once the commit queue uses a dynamically\nallocated prio_queue array.\n\nPatch 2 introduces a rev_walk_mode enum to replace the repeated if/else\nchains in get_revision_1(). The function dispatches on walk mode in multiple\nplaces (next commit, expand parents, flag clearing) and these chains must\nstay in sync. The enum resolves the mode once and both dispatch sites switch\non the same variable. This is a lighter alternative to the vtable-based\nrefactoring I mentioned before. No functional change.\n\nPatch 3 is the actual conversion of the streaming walk to use a priority\nqueue.\n\n== Why this helps ==\n\nThe streaming walk in get_revision_1() inserts newly discovered parent\ncommits into a date-sorted queue. On master, this uses\ncommit_list_insert_by_date(), which walks the linked list to find the\ninsertion point -- O(w) per insert, where w is the queue width (active walk\nfrontier).\n\nIn merge-heavy repositories, the walk frontier stays wide:\n\n\nRepository Commits Peak width Avg width\n=======================================\n\nmonorepo (2.4M) 2,420K 2,653 1,700 linux.git 1,445K 581 235 git.git 82K 188\n82\n\nOn the monorepo, each of the 2.4M commits requires scanning an average of\n1,700 list entries to find the insertion point. With the priority queue,\nthis drops to ~11 heap comparisons.\n\n== Benchmarks ==\n\nAll benchmarks: best of 3 runs, same machine, commit-graph present.\n\nStreaming walks (affected by this series):\n\ngit rev-list --count HEAD (monorepo, 2.4M commits)\n\n  master:   17.94s\n  patched:   3.38s   (5.3x faster)\n\ngit rev-list HEAD (monorepo, full output)\n\n  master:   27.72s\n  patched:   8.61s   (2.8x faster, I/O-bound fraction unchanged)\n\n\nRegression checks -- non-merge-heavy repos (streaming path, but frontier\nstays narrow so O(w) insertion was never the bottleneck):\n\ngit rev-list --count HEAD (linux.git, 1.4M commits)\n\n  master:    1.76s\n  patched:   1.81s   (no change)\n\ngit rev-list HEAD (linux.git, full output)\n\n  master:    4.46s\n  patched:   4.52s   (no change)\n\ngit rev-list --count HEAD (git.git, 82K commits)\n\n  master:     83ms\n  patched:    86ms   (no change)\n\n\nRegression checks -- other walk modes (not affected by this series):\n\ngit rev-list --count HEAD~5000...HEAD (monorepo, limited path)\n\n  master:    7.36s\n  patched:   7.02s   (no change)\n\n\n== Profile breakdown ==\n\nperf profiling of rev-list --count HEAD on the monorepo shows where the time\ngoes:\n\nmaster (17.94s): commit_list_insert_by_date 79% 14.25s fixed overhead\n(parse/lookup) 21% 3.69s\n\npatched (3.38s): heap ops (compare + sift) 16% 0.53s fixed overhead\n(parse/lookup) 84% 2.85s\n\nThe queue maintenance itself sped up 27x (14.25s to 0.53s). The overall 5.3x\nis lower because the fixed costs -- object lookup (17%), commit-graph\nparsing (14%), memory allocation (10%) -- are roughly constant between the\ntwo versions at ~3s.\n\nThis means the patch removes the dominant bottleneck entirely. After the\npatch, the walk cost is dominated by irreducible per-commit work (parsing\nand object lookup) which scales linearly with commit count regardless of\nfrontier width.\n\nKristofer Karlsson (3):\n  pack-objects: call release_revisions() after cruft traversal\n  revision: introduce rev_walk_mode to clarify get_revision_1()\n  revision: use priority queue for non-limited streaming walks\n\n builtin/pack-objects.c |   1 +\n commit.c               |  13 -----\n commit.h               |   2 -\n revision.c             | 113 +++++++++++++++++++++++++++--------------\n revision.h             |  12 ++++-\n 5 files changed, 88 insertions(+), 53 deletions(-)\n\n\nbase-commit: c69baaf57ba26cf117c2b6793802877f19738b0d\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2127%2Fspkrka%2Fstreaming-prio-queue-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2127/spkrka/streaming-prio-queue-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2127\n-- \ngitgitgadget\n"},{"id":"544172","messageId":"743adab469c748aed66555e5390379b54154216d.1779897003.git.gitgitgadget@gmail.com","threadId":"65700","inReplyTo":"pull.2127.git.1779897003.gitgitgadget@gmail.com","subject":"[PATCH 1/3] pack-objects: call release_revisions() after cruft traversal","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-27T15:50:00Z","receivedAt":"2026-05-27T15:50:06Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nenumerate_and_traverse_cruft_objects() initializes a rev_info on the\nstack but never calls release_revisions() afterwards.  This is not\nvisible on master but becomes a leak once the revision walking\nmachinery uses dynamically allocated structures.\n\nAdd the missing release_revisions() call.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n builtin/pack-objects.c | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 480cc0bd8c..67025e8625 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4275,6 +4275,7 @@ static void enumerate_and_traverse_cruft_objects(struct string_list *fresh_packs\n \ttraverse_commit_list(&revs, show_cruft_commit, show_cruft_object, NULL);\n \n \tstop_progress(&progress_state);\n+\trelease_revisions(&revs);\n }\n \n static void read_cruft_objects(void)\n-- \ngitgitgadget\n\n"},{"id":"544173","messageId":"99917cb3077e1c353c9e95cc88460484121d1f88.1779897003.git.gitgitgadget@gmail.com","threadId":"65700","inReplyTo":"pull.2127.git.1779897003.gitgitgadget@gmail.com","subject":"[PATCH 2/3] revision: introduce rev_walk_mode to clarify get_revision_1()","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-27T15:50:01Z","receivedAt":"2026-05-27T15:50:07Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nget_revision_1() dispatches to different walk strategies based on a\ncombination of rev_info flags: reflog_info, topo_walk_info, and\nlimited.  These conditions are checked in multiple places within\nthe function -- once to select the next commit, and again to decide\nhow to expand parents -- and the two chains must stay in sync.\n\nExtract the mode selection into a rev_walk_mode enum and a small\nget_walk_mode() helper, resolved once at the top of get_revision_1().\nBoth dispatch sites now switch on the same mode variable, making it\nobvious that they agree and easier to verify that all modes are\nhandled.\n\nNo functional change.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n revision.c | 62 ++++++++++++++++++++++++++++++++++++++++++------------\n 1 file changed, 48 insertions(+), 14 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex e1970b9c5d..9d0fc696d0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -4327,22 +4327,48 @@ static void track_linear(struct rev_info *revs, struct commit *commit)\n \trevs->previous_parents = commit_list_copy(commit->parents);\n }\n \n+enum rev_walk_mode {\n+\tREV_WALK_REFLOG,\n+\tREV_WALK_TOPO,\n+\tREV_WALK_LIMITED,\n+\tREV_WALK_STREAMING,\n+};\n+\n+static enum rev_walk_mode get_walk_mode(struct rev_info *revs)\n+{\n+\tif (revs->reflog_info)\n+\t\treturn REV_WALK_REFLOG;\n+\tif (revs->topo_walk_info)\n+\t\treturn REV_WALK_TOPO;\n+\tif (revs->limited)\n+\t\treturn REV_WALK_LIMITED;\n+\treturn REV_WALK_STREAMING;\n+}\n+\n static struct commit *get_revision_1(struct rev_info *revs)\n {\n+\tenum rev_walk_mode mode = get_walk_mode(revs);\n+\n \twhile (1) {\n \t\tstruct commit *commit;\n \n-\t\tif (revs->reflog_info)\n+\t\tswitch (mode) {\n+\t\tcase REV_WALK_REFLOG:\n \t\t\tcommit = next_reflog_entry(revs->reflog_info);\n-\t\telse if (revs->topo_walk_info)\n+\t\t\tbreak;\n+\t\tcase REV_WALK_TOPO:\n \t\t\tcommit = next_topo_commit(revs);\n-\t\telse\n+\t\t\tbreak;\n+\t\tcase REV_WALK_LIMITED:\n+\t\tcase REV_WALK_STREAMING:\n \t\t\tcommit = pop_commit(&revs->commits);\n+\t\t\tbreak;\n+\t\t}\n \n \t\tif (!commit)\n \t\t\treturn NULL;\n \n-\t\tif (revs->reflog_info)\n+\t\tif (mode == REV_WALK_REFLOG)\n \t\t\tcommit->object.flags &= ~(ADDED | SEEN | SHOWN);\n \n \t\t/*\n@@ -4350,20 +4376,28 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t * the parents here. We also need to do the date-based limiting\n \t\t * that we'd otherwise have done in limit_list().\n \t\t */\n-\t\tif (!revs->limited) {\n-\t\t\tif (revs->max_age != -1 &&\n-\t\t\t    comparison_date(revs, commit) < revs->max_age)\n-\t\t\t\tcontinue;\n+\t\tif (mode != REV_WALK_LIMITED &&\n+\t\t    revs->max_age != -1 &&\n+\t\t    comparison_date(revs, commit) < revs->max_age)\n+\t\t\tcontinue;\n \n-\t\t\tif (revs->reflog_info)\n-\t\t\t\ttry_to_simplify_commit(revs, commit);\n-\t\t\telse if (revs->topo_walk_info)\n-\t\t\t\texpand_topo_walk(revs, commit);\n-\t\t\telse if (process_parents(revs, commit, &revs->commits, NULL) < 0) {\n+\t\tswitch (mode) {\n+\t\tcase REV_WALK_REFLOG:\n+\t\t\ttry_to_simplify_commit(revs, commit);\n+\t\t\tbreak;\n+\t\tcase REV_WALK_TOPO:\n+\t\t\texpand_topo_walk(revs, commit);\n+\t\t\tbreak;\n+\t\tcase REV_WALK_STREAMING:\n+\t\t\tif (process_parents(revs, commit,\n+\t\t\t\t\t    &revs->commits, NULL) < 0) {\n \t\t\t\tif (!revs->ignore_missing_links)\n \t\t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n-\t\t\t\t\t\toid_to_hex(&commit->object.oid));\n+\t\t\t\t\t    oid_to_hex(&commit->object.oid));\n \t\t\t}\n+\t\t\tbreak;\n+\t\tcase REV_WALK_LIMITED:\n+\t\t\tbreak;\n \t\t}\n \n \t\tswitch (simplify_commit(revs, commit)) {\n-- \ngitgitgadget\n\n"},{"id":"544174","messageId":"c0e78707f1e0fa97e96bcd6522648699f593590a.1779897003.git.gitgitgadget@gmail.com","threadId":"65700","inReplyTo":"pull.2127.git.1779897003.gitgitgadget@gmail.com","subject":"[PATCH 3/3] revision: use priority queue for non-limited streaming walks","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-27T15:50:02Z","receivedAt":"2026-05-27T15:50:08Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nThe streaming (non-limited) walk in get_revision_1() inserts newly\ndiscovered parent commits into a date-sorted queue via\ncommit_list_insert_by_date(), which scans the linked list to find the\ninsertion point -- O(w) per insert, where w is the width of the active\nwalk frontier.  Replace this with an O(log w) priority queue.\n\nAdd a commit_queue field to rev_info alongside the existing commits\nlinked list.  The two representations are mutually exclusive: setup\nand external callers that need list access use the linked list, then\nget_revision_1() lazily drains it into the priority queue on first\ncall.  Add a REV_WALK_NO_WALK enum value to distinguish the no_walk\ncase (which still uses the commit list) from the streaming case.\n\nThe conversion function rev_info_commit_list_to_queue() is public so\ncallers that know they will iterate can convert early.\n\nCombined with the limit_list() priority queue change already in\nmaster, this eliminates all O(w) sorted linked-list insertion from\nthe revision walk machinery.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n commit.c   | 13 -------------\n commit.h   |  2 --\n revision.c | 55 +++++++++++++++++++++++++++++-------------------------\n revision.h | 12 +++++++++++-\n 4 files changed, 41 insertions(+), 41 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex e3e7352e69..5112c7b2af 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -729,19 +729,6 @@ void commit_list_free(struct commit_list *list)\n \t\tpop_commit(&list);\n }\n \n-struct commit_list * commit_list_insert_by_date(struct commit *item, struct commit_list **list)\n-{\n-\tstruct commit_list **pp = list;\n-\tstruct commit_list *p;\n-\twhile ((p = *pp) != NULL) {\n-\t\tif (p->item->date < item->date) {\n-\t\t\tbreak;\n-\t\t}\n-\t\tpp = &p->next;\n-\t}\n-\treturn commit_list_insert(item, pp);\n-}\n-\n static int commit_list_compare_by_date(const struct commit_list *a,\n \t\t\t\t       const struct commit_list *b)\n {\ndiff --git a/commit.h b/commit.h\nindex 58150045af..385492fbb1 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -191,8 +191,6 @@ int commit_list_contains(struct commit *item,\n struct commit_list **commit_list_append(struct commit *commit,\n \t\t\t\t\tstruct commit_list **next);\n unsigned commit_list_count(const struct commit_list *l);\n-struct commit_list *commit_list_insert_by_date(struct commit *item,\n-\t\t\t\t    struct commit_list **list);\n void commit_list_sort_by_date(struct commit_list **list);\n \n /* Shallow copy of the input list */\ndiff --git a/revision.c b/revision.c\nindex 9d0fc696d0..4bb3b16e43 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1116,7 +1116,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n }\n \n static int process_parents(struct rev_info *revs, struct commit *commit,\n-\t\t\t   struct commit_list **list, struct prio_queue *queue)\n+\t\t\t   struct prio_queue *queue)\n {\n \tstruct commit_list *parent = commit->parents;\n \tunsigned pass_flags;\n@@ -1158,8 +1158,6 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\tif (p->object.flags & SEEN)\n \t\t\t\tcontinue;\n \t\t\tp->object.flags |= (SEEN | NOT_USER_GIVEN);\n-\t\t\tif (list)\n-\t\t\t\tcommit_list_insert_by_date(p, list);\n \t\t\tif (queue)\n \t\t\t\tprio_queue_put(queue, p);\n \t\t\tif (revs->exclude_first_parent_only)\n@@ -1207,8 +1205,6 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\tp->object.flags |= pass_flags | CHILD_VISITED;\n \t\tif (!(p->object.flags & SEEN)) {\n \t\t\tp->object.flags |= (SEEN | NOT_USER_GIVEN);\n-\t\t\tif (list)\n-\t\t\t\tcommit_list_insert_by_date(p, list);\n \t\t\tif (queue)\n \t\t\t\tprio_queue_put(queue, p);\n \t\t}\n@@ -1470,7 +1466,7 @@ 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, NULL, &queue) < 0) {\n+\t\tif (process_parents(revs, commit, &queue) < 0) {\n \t\t\tclear_prio_queue(&queue);\n \t\t\treturn -1;\n \t\t}\n@@ -3257,6 +3253,7 @@ static void free_void_commit_list(void *list)\n void release_revisions(struct rev_info *revs)\n {\n \tcommit_list_free(revs->commits);\n+\tclear_prio_queue(&revs->commit_queue);\n \tcommit_list_free(revs->ancestry_path_bottoms);\n \trelease_display_notes(&revs->notes_opt);\n \tobject_array_clear(&revs->pending);\n@@ -3726,7 +3723,7 @@ static void explore_walk_step(struct rev_info *revs)\n \tif (revs->max_age != -1 && (c->date < revs->max_age))\n \t\tc->object.flags |= UNINTERESTING;\n \n-\tif (process_parents(revs, c, NULL, NULL) < 0)\n+\tif (process_parents(revs, c, NULL) < 0)\n \t\treturn;\n \n \tif (c->object.flags & UNINTERESTING)\n@@ -3902,7 +3899,7 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_list *p;\n \tstruct topo_walk_info *info = revs->topo_walk_info;\n-\tif (process_parents(revs, commit, NULL, NULL) < 0) {\n+\tif (process_parents(revs, commit, NULL) < 0) {\n \t\tif (!revs->ignore_missing_links)\n \t\t\tdie(\"Failed to traverse parents of commit %s\",\n \t\t\t    oid_to_hex(&commit->object.oid));\n@@ -3938,6 +3935,13 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n \t}\n }\n \n+void rev_info_commit_list_to_queue(struct rev_info *revs)\n+{\n+\twhile (revs->commits)\n+\t\tprio_queue_put(&revs->commit_queue, pop_commit(&revs->commits));\n+}\n+\n+\n int prepare_revision_walk(struct rev_info *revs)\n {\n \tint i;\n@@ -4006,7 +4010,7 @@ static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n \tfor (;;) {\n \t\tstruct commit *p = *pp;\n \t\tif (!revs->limited)\n-\t\t\tif (process_parents(revs, p, NULL, queue) < 0)\n+\t\t\tif (process_parents(revs, p, queue) < 0)\n \t\t\t\treturn rewrite_one_error;\n \t\tif (p->object.flags & UNINTERESTING)\n \t\t\treturn rewrite_one_ok;\n@@ -4020,27 +4024,18 @@ static enum rewrite_result rewrite_one_1(struct rev_info *revs,\n \t}\n }\n \n-static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list)\n+static void merge_queue_into_prio_queue(struct prio_queue *from,\n+\t\t\t\t\tstruct prio_queue *to)\n {\n-\twhile (q->nr) {\n-\t\tstruct commit *item = prio_queue_peek(q);\n-\t\tstruct commit_list *p = *list;\n-\n-\t\tif (p && p->item->date >= item->date)\n-\t\t\tlist = &p->next;\n-\t\telse {\n-\t\t\tp = commit_list_insert(item, list);\n-\t\t\tlist = &p->next; /* skip newly added item */\n-\t\t\tprio_queue_get(q); /* pop item */\n-\t\t}\n-\t}\n+\twhile (from->nr)\n+\t\tprio_queue_put(to, prio_queue_get(from));\n }\n \n static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)\n {\n \tstruct prio_queue queue = { compare_commits_by_commit_date };\n \tenum rewrite_result ret = rewrite_one_1(revs, pp, &queue);\n-\tmerge_queue_into_list(&queue, &revs->commits);\n+\tmerge_queue_into_prio_queue(&queue, &revs->commit_queue);\n \tclear_prio_queue(&queue);\n \treturn ret;\n }\n@@ -4331,6 +4326,7 @@ enum rev_walk_mode {\n \tREV_WALK_REFLOG,\n \tREV_WALK_TOPO,\n \tREV_WALK_LIMITED,\n+\tREV_WALK_NO_WALK,\n \tREV_WALK_STREAMING,\n };\n \n@@ -4342,6 +4338,8 @@ static enum rev_walk_mode get_walk_mode(struct rev_info *revs)\n \t\treturn REV_WALK_TOPO;\n \tif (revs->limited)\n \t\treturn REV_WALK_LIMITED;\n+\tif (revs->no_walk)\n+\t\treturn REV_WALK_NO_WALK;\n \treturn REV_WALK_STREAMING;\n }\n \n@@ -4349,6 +4347,9 @@ static struct commit *get_revision_1(struct rev_info *revs)\n {\n \tenum rev_walk_mode mode = get_walk_mode(revs);\n \n+\tif (mode == REV_WALK_STREAMING && revs->commits)\n+\t\trev_info_commit_list_to_queue(revs);\n+\n \twhile (1) {\n \t\tstruct commit *commit;\n \n@@ -4360,9 +4361,12 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tcommit = next_topo_commit(revs);\n \t\t\tbreak;\n \t\tcase REV_WALK_LIMITED:\n-\t\tcase REV_WALK_STREAMING:\n+\t\tcase REV_WALK_NO_WALK:\n \t\t\tcommit = pop_commit(&revs->commits);\n \t\t\tbreak;\n+\t\tcase REV_WALK_STREAMING:\n+\t\t\tcommit = prio_queue_get(&revs->commit_queue);\n+\t\t\tbreak;\n \t\t}\n \n \t\tif (!commit)\n@@ -4390,12 +4394,13 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\tbreak;\n \t\tcase REV_WALK_STREAMING:\n \t\t\tif (process_parents(revs, commit,\n-\t\t\t\t\t    &revs->commits, NULL) < 0) {\n+\t\t\t\t\t    &revs->commit_queue) < 0) {\n \t\t\t\tif (!revs->ignore_missing_links)\n \t\t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n \t\t\t\t\t    oid_to_hex(&commit->object.oid));\n \t\t\t}\n \t\t\tbreak;\n+\t\tcase REV_WALK_NO_WALK:\n \t\tcase REV_WALK_LIMITED:\n \t\t\tbreak;\n \t\t}\ndiff --git a/revision.h b/revision.h\nindex 584f1338b5..04982a3d47 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -12,6 +12,7 @@\n #include \"decorate.h\"\n #include \"ident.h\"\n #include \"list-objects-filter-options.h\"\n+#include \"prio-queue.h\"\n #include \"strvec.h\"\n \n /**\n@@ -122,8 +123,14 @@ struct oidset;\n struct topo_walk_info;\n \n struct rev_info {\n-\t/* Starting list */\n+\t/*\n+\t * Work queue of commits, stored as either a linked list or a\n+\t * priority queue, but never both at the same time.\n+\t * rev_info_commit_list_to_queue() converts list to queue.\n+\t */\n \tstruct commit_list *commits;\n+\tstruct prio_queue commit_queue;\n+\n \tstruct object_array pending;\n \tstruct repository *repo;\n \n@@ -400,6 +407,7 @@ struct rev_info {\n  * uninitialized.\n  */\n #define REV_INFO_INIT { \\\n+\t.commit_queue = { .compare = compare_commits_by_commit_date }, \\\n \t.abbrev = DEFAULT_ABBREV, \\\n \t.simplify_history = 1, \\\n \t.pruning.flags.recursive = 1, \\\n@@ -478,6 +486,8 @@ void reset_revision_walk(void);\n  */\n int prepare_revision_walk(struct rev_info *revs);\n \n+/* Drain the commits linked list into the priority queue. */\n+void rev_info_commit_list_to_queue(struct rev_info *revs);\n /**\n  * Takes a pointer to a `rev_info` structure and iterates over it, returning a\n  * `struct commit *` each time you call it. The end of the revision list is\n-- \ngitgitgadget\n"}]}