{"thread":{"id":"65642","subject":"[PATCH] commit-reach: use the decoration hash for tips_reachable_from_bases()","startedAt":"2026-05-15T18:07:46Z","lastAt":"2026-05-21T22:50:27Z","messageCount":10,"participants":["Kristofer Karlsson via GitGitGadget","Jeff King","Kristofer Karlsson","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"543421","messageId":"pull.2116.git.1778868463992.gitgitgadget@gmail.com","threadId":"65642","inReplyTo":null,"subject":"[PATCH] commit-reach: use the decoration hash for tips_reachable_from_bases()","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-15T18:07:43Z","receivedAt":"2026-05-15T18:07:46Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\ntips_reachable_from_bases() walks the commit graph from a set of base\ncommits to find which tip commits are reachable.  The inner loop does\na linear scan over the tips array to check whether each visited commit\nis a tip, making the overall cost O(C * T) where C is commits walked\nand T is the number of tips.\n\nReplace the linear scan with the decoration hash for lookups, reducing\nthe per-commit tip check from O(T) to O(1) and the overall cost from\nO(C * T) to O(C + T).\n\nThis function is called by `git for-each-ref --merged` and\n`git branch/tag --contains/--no-contains` via reach_filter() in\nref-filter.c.\n\nBenchmark on a merge-heavy monorepo (2.3M commits, 10,000 refs):\n\n  Command                           Before    After   Speedup\n  for-each-ref --merged HEAD        6.64s     1.66s     4.0x\n  for-each-ref --no-merged HEAD     6.75s     1.74s     3.9x\n  branch --merged HEAD              0.68s     0.61s      10%\n  branch --no-merged HEAD           0.65s     0.61s       8%\n  tag --merged HEAD                 0.12s     0.12s       -\n\nThe large speedup for for-each-ref is because it checks all 10,000\nrefs as tips, making the O(T) inner loop expensive.  The branch\nsubcommand only checks local branches (fewer tips), so the improvement\nis smaller.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n    commit-reach: use the decoration hash for tips_reachable_from_bases()\n    \n    This is a single small commit that replaces an O(C*T) linear scan in\n    tips_reachable_from_bases() with an O(1) lookup using the decoration\n    hash.\n    \n    The function is called by git for-each-ref --merged and git branch/tag\n    --contains/--no-contains via reach_filter() in ref-filter.c. On a\n    merge-heavy monorepo with 2.3M commits and 10,000 refs, git for-each-ref\n    --merged HEAD goes from 6.6s to 1.7s (4x).\n    \n    The diff is intentionally minimal (+9/-6) to make the idea easy to\n    discuss before polishing. Things I'm not fully happy about:\n    \n     * Extra block scope { } just to preserve indentation of the inner body\n     * Hacking the array index into the decoration value as (void *)(i + 1)\n       instead of storing a proper pointer\n     * Relying on unsigned wraparound (- 1 on a size_t 0) to check for\n       not-found via j < tips_nr\n    \n    Happy to clean all of these up in a follow-up commit if the approach\n    makes sense.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2116%2Fspkrka%2Ftips-reachable-minimal-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2116/spkrka/tips-reachable-minimal-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2116\n\n commit-reach.c | 15 +++++++++------\n 1 file changed, 9 insertions(+), 6 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex d3a9b3ed6f..70b056eae0 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1150,6 +1150,7 @@ void tips_reachable_from_bases(struct repository *r,\n \tsize_t min_generation_index = 0;\n \ttimestamp_t min_generation;\n \tstruct commit_list *stack = NULL;\n+\tstruct decoration tip_index = { \"tip_index\" };\n \n \tif (!bases || !tips || !tips_nr)\n \t\treturn;\n@@ -1173,6 +1174,10 @@ void tips_reachable_from_bases(struct repository *r,\n \tQSORT(commits, tips_nr, compare_commit_and_index_by_generation);\n \tmin_generation = commits[0].generation;\n \n+\tfor (size_t i = 0; i < tips_nr; i++)\n+\t\tadd_decoration(&tip_index, &commits[i].commit->object,\n+\t\t\t       (void *)(i + 1));\n+\n \twhile (bases) {\n \t\trepo_parse_commit(r, bases->item);\n \t\tcommit_list_insert(bases->item, &stack);\n@@ -1183,14 +1188,11 @@ void tips_reachable_from_bases(struct repository *r,\n \t\tint explored_all_parents = 1;\n \t\tstruct commit_list *p;\n \t\tstruct commit *c = stack->item;\n-\t\ttimestamp_t c_gen = commit_graph_generation(c);\n \n \t\t/* Does it match any of our tips? */\n-\t\tfor (size_t j = min_generation_index; j < tips_nr; j++) {\n-\t\t\tif (c_gen < commits[j].generation)\n-\t\t\t\tbreak;\n-\n-\t\t\tif (commits[j].commit == c) {\n+\t\t{\n+\t\t\tsize_t j = (size_t)lookup_decoration(&tip_index, &c->object) - 1;\n+\t\t\tif (j < tips_nr) {\n \t\t\t\ttips[commits[j].index]->object.flags |= mark;\n \n \t\t\t\tif (j == min_generation_index) {\n@@ -1232,6 +1234,7 @@ void tips_reachable_from_bases(struct repository *r,\n \t}\n \n done:\n+\tclear_decoration(&tip_index, NULL);\n \tfree(commits);\n \trepo_clear_commit_marks(r, SEEN);\n \tcommit_list_free(stack);\n\nbase-commit: 59ff4886a579f4bc91e976fe18590b9ae02c7a08\n-- \ngitgitgadget\n"},{"id":"543426","messageId":"20260515211459.GA158762@coredump.intra.peff.net","threadId":"65642","inReplyTo":"pull.2116.git.1778868463992.gitgitgadget@gmail.com","subject":"Re: [PATCH] commit-reach: use the decoration hash for tips_reachable_from_bases()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-15T21:14:59Z","receivedAt":"2026-05-15T21:15:01Z","isPatch":true,"body":"On Fri, May 15, 2026 at 06:07:43PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n\n> From: Kristofer Karlsson <krka@spotify.com>\n> \n> tips_reachable_from_bases() walks the commit graph from a set of base\n> commits to find which tip commits are reachable.  The inner loop does\n> a linear scan over the tips array to check whether each visited commit\n> is a tip, making the overall cost O(C * T) where C is commits walked\n> and T is the number of tips.\n> \n> Replace the linear scan with the decoration hash for lookups, reducing\n> the per-commit tip check from O(T) to O(1) and the overall cost from\n> O(C * T) to O(C + T).\n> \n> This function is called by `git for-each-ref --merged` and\n> `git branch/tag --contains/--no-contains` via reach_filter() in\n> ref-filter.c.\n> \n> Benchmark on a merge-heavy monorepo (2.3M commits, 10,000 refs):\n> \n>   Command                           Before    After   Speedup\n>   for-each-ref --merged HEAD        6.64s     1.66s     4.0x\n>   for-each-ref --no-merged HEAD     6.75s     1.74s     3.9x\n>   branch --merged HEAD              0.68s     0.61s      10%\n>   branch --no-merged HEAD           0.65s     0.61s       8%\n>   tag --merged HEAD                 0.12s     0.12s       -\n> \n> The large speedup for for-each-ref is because it checks all 10,000\n> refs as tips, making the O(T) inner loop expensive.  The branch\n> subcommand only checks local branches (fewer tips), so the improvement\n> is smaller.\n\nHmm, I couldn't reproduce the speedup on something like linux.git (~1.4M\ncommits) with a lot of synthetic branches. I'd think that old branches\nwould be the most expensive, so I did:\n\n  old=$(git rev-list --reverse HEAD | head -n1)\n  seq --format=\"update refs/heads/branch%g $old\" 10000 |\n  git update-ref --stdin\n\nRunning \"git for-each-ref --no-merged HEAD\" takes ~650ms with stock Git.\nBut with your patch, it goes to ~830ms!\n\nSo what am I missing about your repo that it is so slow in the first\nplace?\n\n>      * Hacking the array index into the decoration value as (void *)(i + 1)\n>        instead of storing a proper pointer\n\nThe decoration API is not the most generic option here. There's an\noidmap type, but you have to embed the hashmap bits into your struct,\nwhich is a lot of boilerplate if you're just storing an int. You can\ndefine a khash with a custom value type, and I think the existing\noid_pos uses an int, which might be enough. All of those will store an\nextra copy of the oid, though for the sizes we're talking about that's\nnot the end of the world.\n\nSince we're always mapping commits, you could define a commit-slab (each\ncommit struct gets a unique id which we then index into a big array).\nSee commit-slab.h for an example.\n\nI'm not very familiar with this code, but I wonder if we actually need\nto map at all. It looks like we are mostly interested in set inclusion,\nso perhaps an oidset() would work. Or even a bit in the object-flags.\n\n-Peff\n"},{"id":"543443","messageId":"CAL71e4NoKiRMGngCc-FYNX9PH5fTd6xpzMsfONefp+JwJ1-3BA@mail.gmail.com","threadId":"65642","inReplyTo":"20260515211459.GA158762@coredump.intra.peff.net","subject":"Re: [PATCH] commit-reach: use the decoration hash for tips_reachable_from_bases()","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-05-16T08:23:11Z","receivedAt":"2026-05-16T08:23:23Z","isPatch":true,"body":"Thanks for testing this, Jeff! You're right, the patch as posted\nregresses on your synthetic test case.\n\nThe issue is that when multiple refs point to the same commit,\nadd_decoration overwrites earlier entries,\nso only one index gets stored. The marking itself is correct (the flag\nis on the shared commit object,\nso all duplicates get marked), but the j == min_generation_index check\nnever fires for the minimum tip,\nso early termination breaks. The DFS walks the entire graph instead of\nstopping when all tips are found.\n\nI have a fix for the early-termination bug (checking the flag at\nmin_generation_index instead of comparing indices),\nbut your suggestions about the API are well taken, I don't think the\ndecoration hash is the right tool here.\nSince we only need set membership (\"is this commit a tip?\"), not a\nmapping, an object-flags bit or commit-slab would\nindeed be simpler and avoid the (void *)(i + 1) hack entirely.\n\nI fixed it locally now for the linux test case and got a 4x speedup\nthere too - the problem was failing the early termination.\nSome numbers when running against the linux repo on my machine:\n\nCommand          │ Baseline │     V1 (broken)     │     V2 (fixed)      │\n--no-merged HEAD │ 1.33s    │ 2.01s (1.5x slower) │ 0.31s (4.3x faster) │\n--merged HEAD    │ 1.35s    │ 1.96s (1.5x slower) │ 0.31s (4.3x faster) │\n\nHowever, I'll still need to rethink the decoration map - I will come\nback with a better patch shortly.\n\n- Kristofer\n\nOn Fri, 15 May 2026 at 23:15, Jeff King <peff@peff.net> wrote:\n>\n> On Fri, May 15, 2026 at 06:07:43PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n>\n> > From: Kristofer Karlsson <krka@spotify.com>\n> >\n> > tips_reachable_from_bases() walks the commit graph from a set of base\n> > commits to find which tip commits are reachable.  The inner loop does\n> > a linear scan over the tips array to check whether each visited commit\n> > is a tip, making the overall cost O(C * T) where C is commits walked\n> > and T is the number of tips.\n> >\n> > Replace the linear scan with the decoration hash for lookups, reducing\n> > the per-commit tip check from O(T) to O(1) and the overall cost from\n> > O(C * T) to O(C + T).\n> >\n> > This function is called by `git for-each-ref --merged` and\n> > `git branch/tag --contains/--no-contains` via reach_filter() in\n> > ref-filter.c.\n> >\n> > Benchmark on a merge-heavy monorepo (2.3M commits, 10,000 refs):\n> >\n> >   Command                           Before    After   Speedup\n> >   for-each-ref --merged HEAD        6.64s     1.66s     4.0x\n> >   for-each-ref --no-merged HEAD     6.75s     1.74s     3.9x\n> >   branch --merged HEAD              0.68s     0.61s      10%\n> >   branch --no-merged HEAD           0.65s     0.61s       8%\n> >   tag --merged HEAD                 0.12s     0.12s       -\n> >\n> > The large speedup for for-each-ref is because it checks all 10,000\n> > refs as tips, making the O(T) inner loop expensive.  The branch\n> > subcommand only checks local branches (fewer tips), so the improvement\n> > is smaller.\n>\n> Hmm, I couldn't reproduce the speedup on something like linux.git (~1.4M\n> commits) with a lot of synthetic branches. I'd think that old branches\n> would be the most expensive, so I did:\n>\n>   old=$(git rev-list --reverse HEAD | head -n1)\n>   seq --format=\"update refs/heads/branch%g $old\" 10000 |\n>   git update-ref --stdin\n>\n> Running \"git for-each-ref --no-merged HEAD\" takes ~650ms with stock Git.\n> But with your patch, it goes to ~830ms!\n>\n> So what am I missing about your repo that it is so slow in the first\n> place?\n>\n> >      * Hacking the array index into the decoration value as (void *)(i + 1)\n> >        instead of storing a proper pointer\n>\n> The decoration API is not the most generic option here. There's an\n> oidmap type, but you have to embed the hashmap bits into your struct,\n> which is a lot of boilerplate if you're just storing an int. You can\n> define a khash with a custom value type, and I think the existing\n> oid_pos uses an int, which might be enough. All of those will store an\n> extra copy of the oid, though for the sizes we're talking about that's\n> not the end of the world.\n>\n> Since we're always mapping commits, you could define a commit-slab (each\n> commit struct gets a unique id which we then index into a big array).\n> See commit-slab.h for an example.\n>\n> I'm not very familiar with this code, but I wonder if we actually need\n> to map at all. It looks like we are mostly interested in set inclusion,\n> so perhaps an oidset() would work. Or even a bit in the object-flags.\n>\n> -Peff\n"},{"id":"543445","messageId":"pull.2116.v2.git.1778922993480.gitgitgadget@gmail.com","threadId":"65642","inReplyTo":"pull.2116.git.1778868463992.gitgitgadget@gmail.com","subject":"[PATCH v2] commit-reach: use object flags for tips_reachable_from_bases()","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-16T09:16:32Z","receivedAt":"2026-05-16T09:16:35Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\ntips_reachable_from_bases() walks the commit graph from a set of base\ncommits to find which tip commits are reachable.  The inner loop does\na linear scan over the tips array to check whether each visited commit\nis a tip, making the overall cost O(C * T) where C is commits walked\nand T is the number of tips.\n\nUse the RESULT object flag to mark tip commits, replacing the linear\nscan with a single flag test per visited commit.  This reduces the\nper-commit tip check from O(T) to O(1) and the overall cost from\nO(C * T) to O(C + T).\n\nWhen multiple refs point to the same commit, the shared object gets\nthe flag once, so all duplicates are handled automatically.  The\nearly-termination advancement loop checks the flag on the sorted\ncommits array directly, which naturally handles duplicates since the\nflag is on the shared commit object.\n\nThis also removes the index field from struct commit_and_index, since\nthe indirection through the original tips array is no longer needed.\n\nThis function is called by `git for-each-ref --merged` and\n`git branch/tag --contains/--no-contains` via reach_filter() in\nref-filter.c.\n\nBenchmark on a merge-heavy monorepo (2.3M commits, 10,000 refs):\n\n  Command                           Before    After   Speedup\n  for-each-ref --merged HEAD        6.57s     1.59s     4.1x\n  for-each-ref --no-merged HEAD     6.67s     1.66s     4.0x\n  branch --merged HEAD              0.68s     0.61s      10%\n  branch --no-merged HEAD           0.65s     0.61s       8%\n  tag --merged HEAD                 0.12s     0.12s       -\n\nOn linux.git with 10,000 synthetic branches at the root commit (worst\ncase for the DFS walk):\n\n  Command                           Before    After   Speedup\n  for-each-ref --merged HEAD        1.35s     0.35s     3.9x\n  for-each-ref --no-merged HEAD     1.82s     0.31s     5.9x\n\nThe large speedup for for-each-ref is because it checks all 10,000\nrefs as tips, making the O(T) inner loop expensive.  The branch\nsubcommand only checks local branches (fewer tips), so the improvement\nis smaller.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n    commit-reach: use object flags for tips_reachable_from_bases()\n    \n    This replaces the O(C*T) linear scan in tips_reachable_from_bases() with\n    an O(1) flag check using the RESULT object flag.\n    \n    The function is called by git for-each-ref --merged and git branch/tag\n    --contains/--no-contains via reach_filter() in ref-filter.c.\n    \n    Benchmarks on a merge-heavy monorepo (2.3M commits, 10,000 refs):\n    \n     * for-each-ref --merged HEAD: 6.6s → 1.6s (4.1x)\n     * for-each-ref --no-merged HEAD: 6.7s → 1.7s (4.0x)\n    \n    On linux.git with 10,000 synthetic branches at the root commit:\n    \n     * for-each-ref --merged HEAD: 1.35s → 0.35s (3.9x)\n     * for-each-ref --no-merged HEAD: 1.82s → 0.31s (5.9x)\n    \n    v2 of this patch, addressing Jeff King's feedback:\n    \n     * Replaced the decoration hash with the RESULT object flag (simpler, no\n       extra data structure, handles duplicate tips naturally)\n     * Fixed early-termination bug when multiple refs point to the same\n       commit (the decoration API overwrites on duplicate keys)\n     * Removed the now-unused index field from struct commit_and_index\n     * Diff is +11/-12 lines\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2116%2Fspkrka%2Ftips-reachable-minimal-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2116/spkrka/tips-reachable-minimal-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/2116\n\nRange-diff vs v1:\n\n 1:  992c0aff0e ! 1:  7399a12518 commit-reach: use the decoration hash for tips_reachable_from_bases()\n     @@ Metadata\n      Author: Kristofer Karlsson <krka@spotify.com>\n      \n       ## Commit message ##\n     -    commit-reach: use the decoration hash for tips_reachable_from_bases()\n     +    commit-reach: use object flags for tips_reachable_from_bases()\n      \n          tips_reachable_from_bases() walks the commit graph from a set of base\n          commits to find which tip commits are reachable.  The inner loop does\n     @@ Commit message\n          is a tip, making the overall cost O(C * T) where C is commits walked\n          and T is the number of tips.\n      \n     -    Replace the linear scan with the decoration hash for lookups, reducing\n     -    the per-commit tip check from O(T) to O(1) and the overall cost from\n     +    Use the RESULT object flag to mark tip commits, replacing the linear\n     +    scan with a single flag test per visited commit.  This reduces the\n     +    per-commit tip check from O(T) to O(1) and the overall cost from\n          O(C * T) to O(C + T).\n      \n     +    When multiple refs point to the same commit, the shared object gets\n     +    the flag once, so all duplicates are handled automatically.  The\n     +    early-termination advancement loop checks the flag on the sorted\n     +    commits array directly, which naturally handles duplicates since the\n     +    flag is on the shared commit object.\n     +\n     +    This also removes the index field from struct commit_and_index, since\n     +    the indirection through the original tips array is no longer needed.\n     +\n          This function is called by `git for-each-ref --merged` and\n          `git branch/tag --contains/--no-contains` via reach_filter() in\n          ref-filter.c.\n     @@ Commit message\n          Benchmark on a merge-heavy monorepo (2.3M commits, 10,000 refs):\n      \n            Command                           Before    After   Speedup\n     -      for-each-ref --merged HEAD        6.64s     1.66s     4.0x\n     -      for-each-ref --no-merged HEAD     6.75s     1.74s     3.9x\n     +      for-each-ref --merged HEAD        6.57s     1.59s     4.1x\n     +      for-each-ref --no-merged HEAD     6.67s     1.66s     4.0x\n            branch --merged HEAD              0.68s     0.61s      10%\n            branch --no-merged HEAD           0.65s     0.61s       8%\n            tag --merged HEAD                 0.12s     0.12s       -\n      \n     +    On linux.git with 10,000 synthetic branches at the root commit (worst\n     +    case for the DFS walk):\n     +\n     +      Command                           Before    After   Speedup\n     +      for-each-ref --merged HEAD        1.35s     0.35s     3.9x\n     +      for-each-ref --no-merged HEAD     1.82s     0.31s     5.9x\n     +\n          The large speedup for for-each-ref is because it checks all 10,000\n          refs as tips, making the O(T) inner loop expensive.  The branch\n          subcommand only checks local branches (fewer tips), so the improvement\n     @@ Commit message\n          Signed-off-by: Kristofer Karlsson <krka@spotify.com>\n      \n       ## commit-reach.c ##\n     +@@ commit-reach.c: void ahead_behind(struct repository *r,\n     + \n     + struct commit_and_index {\n     + \tstruct commit *commit;\n     +-\tunsigned int index;\n     + \ttimestamp_t generation;\n     + };\n     + \n      @@ commit-reach.c: void tips_reachable_from_bases(struct repository *r,\n     - \tsize_t min_generation_index = 0;\n     - \ttimestamp_t min_generation;\n     - \tstruct commit_list *stack = NULL;\n     -+\tstruct decoration tip_index = { \"tip_index\" };\n       \n     - \tif (!bases || !tips || !tips_nr)\n     - \t\treturn;\n     + \tfor (size_t i = 0; i < tips_nr; i++) {\n     + \t\tcommits[i].commit = tips[i];\n     +-\t\tcommits[i].index = i;\n     + \t\tcommits[i].generation = commit_graph_generation(tips[i]);\n     + \t}\n     + \n      @@ commit-reach.c: void tips_reachable_from_bases(struct repository *r,\n       \tQSORT(commits, tips_nr, compare_commit_and_index_by_generation);\n       \tmin_generation = commits[0].generation;\n       \n      +\tfor (size_t i = 0; i < tips_nr; i++)\n     -+\t\tadd_decoration(&tip_index, &commits[i].commit->object,\n     -+\t\t\t       (void *)(i + 1));\n     ++\t\tcommits[i].commit->object.flags |= RESULT;\n      +\n       \twhile (bases) {\n       \t\trepo_parse_commit(r, bases->item);\n     @@ commit-reach.c: void tips_reachable_from_bases(struct repository *r,\n      -\t\t\t\tbreak;\n      -\n      -\t\t\tif (commits[j].commit == c) {\n     +-\t\t\t\ttips[commits[j].index]->object.flags |= mark;\n      +\t\t{\n     -+\t\t\tsize_t j = (size_t)lookup_decoration(&tip_index, &c->object) - 1;\n     -+\t\t\tif (j < tips_nr) {\n     - \t\t\t\ttips[commits[j].index]->object.flags |= mark;\n     ++\t\t\tif (c->object.flags & RESULT) {\n     ++\t\t\t\tc->object.flags |= mark;\n       \n     - \t\t\t\tif (j == min_generation_index) {\n     +-\t\t\t\tif (j == min_generation_index) {\n     +-\t\t\t\t\tunsigned int k = j + 1;\n     ++\t\t\t\tif (commits[min_generation_index].commit->object.flags & mark) {\n     ++\t\t\t\t\tunsigned int k = min_generation_index + 1;\n     + \t\t\t\t\twhile (k < tips_nr &&\n     +-\t\t\t\t\t       (tips[commits[k].index]->object.flags & mark))\n     ++\t\t\t\t\t       (commits[k].commit->object.flags & mark))\n     + \t\t\t\t\t\tk++;\n     + \n     + \t\t\t\t\t/* Terminate early if all found. */\n      @@ commit-reach.c: void tips_reachable_from_bases(struct repository *r,\n       \t}\n       \n       done:\n     -+\tclear_decoration(&tip_index, NULL);\n     ++\tfor (size_t i = 0; i < tips_nr; i++)\n     ++\t\tcommits[i].commit->object.flags &= ~RESULT;\n       \tfree(commits);\n       \trepo_clear_commit_marks(r, SEEN);\n       \tcommit_list_free(stack);\n\n\n commit-reach.c | 23 +++++++++++------------\n 1 file changed, 11 insertions(+), 12 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex d3a9b3ed6f..82614d2409 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1125,7 +1125,6 @@ void ahead_behind(struct repository *r,\n \n struct commit_and_index {\n \tstruct commit *commit;\n-\tunsigned int index;\n \ttimestamp_t generation;\n };\n \n@@ -1165,7 +1164,6 @@ void tips_reachable_from_bases(struct repository *r,\n \n \tfor (size_t i = 0; i < tips_nr; i++) {\n \t\tcommits[i].commit = tips[i];\n-\t\tcommits[i].index = i;\n \t\tcommits[i].generation = commit_graph_generation(tips[i]);\n \t}\n \n@@ -1173,6 +1171,9 @@ void tips_reachable_from_bases(struct repository *r,\n \tQSORT(commits, tips_nr, compare_commit_and_index_by_generation);\n \tmin_generation = commits[0].generation;\n \n+\tfor (size_t i = 0; i < tips_nr; i++)\n+\t\tcommits[i].commit->object.flags |= RESULT;\n+\n \twhile (bases) {\n \t\trepo_parse_commit(r, bases->item);\n \t\tcommit_list_insert(bases->item, &stack);\n@@ -1183,20 +1184,16 @@ void tips_reachable_from_bases(struct repository *r,\n \t\tint explored_all_parents = 1;\n \t\tstruct commit_list *p;\n \t\tstruct commit *c = stack->item;\n-\t\ttimestamp_t c_gen = commit_graph_generation(c);\n \n \t\t/* Does it match any of our tips? */\n-\t\tfor (size_t j = min_generation_index; j < tips_nr; j++) {\n-\t\t\tif (c_gen < commits[j].generation)\n-\t\t\t\tbreak;\n-\n-\t\t\tif (commits[j].commit == c) {\n-\t\t\t\ttips[commits[j].index]->object.flags |= mark;\n+\t\t{\n+\t\t\tif (c->object.flags & RESULT) {\n+\t\t\t\tc->object.flags |= mark;\n \n-\t\t\t\tif (j == min_generation_index) {\n-\t\t\t\t\tunsigned int k = j + 1;\n+\t\t\t\tif (commits[min_generation_index].commit->object.flags & mark) {\n+\t\t\t\t\tunsigned int k = min_generation_index + 1;\n \t\t\t\t\twhile (k < tips_nr &&\n-\t\t\t\t\t       (tips[commits[k].index]->object.flags & mark))\n+\t\t\t\t\t       (commits[k].commit->object.flags & mark))\n \t\t\t\t\t\tk++;\n \n \t\t\t\t\t/* Terminate early if all found. */\n@@ -1232,6 +1229,8 @@ void tips_reachable_from_bases(struct repository *r,\n \t}\n \n done:\n+\tfor (size_t i = 0; i < tips_nr; i++)\n+\t\tcommits[i].commit->object.flags &= ~RESULT;\n \tfree(commits);\n \trepo_clear_commit_marks(r, SEEN);\n \tcommit_list_free(stack);\n\nbase-commit: 59ff4886a579f4bc91e976fe18590b9ae02c7a08\n-- \ngitgitgadget\n"},{"id":"543453","messageId":"5a783514-9d20-429b-8c07-200cf821a35d@gmail.com","threadId":"65642","inReplyTo":"CAL71e4NoKiRMGngCc-FYNX9PH5fTd6xpzMsfONefp+JwJ1-3BA@mail.gmail.com","subject":"Re: [PATCH] commit-reach: use the decoration hash for tips_reachable_from_bases()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-05-16T13:46:56Z","receivedAt":"2026-05-16T13:46:59Z","isPatch":true,"body":"On 5/16/26 4:23 AM, Kristofer Karlsson wrote:\n> Thanks for testing this, Jeff! You're right, the patch as posted\n> regresses on your synthetic test case.\n> \n> The issue is that when multiple refs point to the same commit,\n> add_decoration overwrites earlier entries,\n> so only one index gets stored. The marking itself is correct (the flag\n> is on the shared commit object,\n> so all duplicates get marked), but the j == min_generation_index check\n> never fires for the minimum tip,\n> so early termination breaks. The DFS walks the entire graph instead of\n> stopping when all tips are found.\n> \n> I have a fix for the early-termination bug (checking the flag at\n> min_generation_index instead of comparing indices),\n> but your suggestions about the API are well taken, I don't think the\n> decoration hash is the right tool here.\n> Since we only need set membership (\"is this commit a tip?\"), not a\n> mapping, an object-flags bit or commit-slab would\n> indeed be simpler and avoid the (void *)(i + 1) hack entirely.\n> \n> I fixed it locally now for the linux test case and got a 4x speedup\n> there too - the problem was failing the early termination.\n> Some numbers when running against the linux repo on my machine:\n> \n> Command          │ Baseline │     V1 (broken)     │     V2 (fixed)      │\n> --no-merged HEAD │ 1.33s    │ 2.01s (1.5x slower) │ 0.31s (4.3x faster) │\n> --merged HEAD    │ 1.35s    │ 1.96s (1.5x slower) │ 0.31s (4.3x faster) │\n> \n> However, I'll still need to rethink the decoration map - I will come\n> back with a better patch shortly.\n\nThis is indeed an interesting case (multiple decorations) that we should\nmake sure is covered by a test case so we don't fall into this mistake\nagain.\n\nThanks,\n-Stolee\n\n"},{"id":"543468","messageId":"pull.2116.v3.git.1778947182.gitgitgadget@gmail.com","threadId":"65642","inReplyTo":"pull.2116.v2.git.1778922993480.gitgitgadget@gmail.com","subject":"[PATCH v3 0/2] commit-reach: use object flags for tips_reachable_from_bases()","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-16T15:59:39Z","receivedAt":"2026-05-16T15:59:45Z","isPatch":true,"body":"This replaces the O(C*T) linear scan in tips_reachable_from_bases() with an\nO(1) flag check using the RESULT object flag.\n\nThe function is called by git for-each-ref --merged and git branch/tag\n--contains/--no-contains via reach_filter() in ref-filter.c.\n\nBenchmarks on a merge-heavy monorepo (2.3M commits, 10,000 refs):\n\n * for-each-ref --merged HEAD: 6.6s → 1.6s (4.1x)\n * for-each-ref --no-merged HEAD: 6.7s → 1.7s (4.0x)\n\nOn linux.git with 10,000 synthetic branches at the root commit:\n\n * for-each-ref --merged HEAD: 1.35s → 0.35s (3.9x)\n * for-each-ref --no-merged HEAD: 1.82s → 0.31s (5.9x)\n\nv2 of this patch, addressing Jeff King's feedback:\n\n * Replaced the decoration hash with the RESULT object flag (simpler, no\n   extra data structure, handles duplicate tips naturally)\n * Fixed early-termination bug when multiple refs point to the same commit\n   (the decoration API overwrites on duplicate keys)\n * Removed the now-unused index field from struct commit_and_index\n * Diff is +11/-12 lines\n\nKristofer Karlsson (2):\n  commit-reach: use object flags for tips_reachable_from_bases()\n  t6600: add tests for duplicate tips in tips_reachable_from_bases()\n\n commit-reach.c        | 23 +++++++++++-----------\n t/t6600-test-reach.sh | 45 +++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 56 insertions(+), 12 deletions(-)\n\n\nbase-commit: 59ff4886a579f4bc91e976fe18590b9ae02c7a08\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2116%2Fspkrka%2Ftips-reachable-minimal-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2116/spkrka/tips-reachable-minimal-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/2116\n\nRange-diff vs v2:\n\n 1:  7399a12518 = 1:  7399a12518 commit-reach: use object flags for tips_reachable_from_bases()\n -:  ---------- > 2:  4d11ebb79e t6600: add tests for duplicate tips in tips_reachable_from_bases()\n\n-- \ngitgitgadget\n"},{"id":"543469","messageId":"7399a12518e2021bc8f7cf3fc1f2996099f787b6.1778947182.git.gitgitgadget@gmail.com","threadId":"65642","inReplyTo":"pull.2116.v3.git.1778947182.gitgitgadget@gmail.com","subject":"[PATCH v3 1/2] commit-reach: use object flags for tips_reachable_from_bases()","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-16T15:59:40Z","receivedAt":"2026-05-16T15:59:46Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\ntips_reachable_from_bases() walks the commit graph from a set of base\ncommits to find which tip commits are reachable.  The inner loop does\na linear scan over the tips array to check whether each visited commit\nis a tip, making the overall cost O(C * T) where C is commits walked\nand T is the number of tips.\n\nUse the RESULT object flag to mark tip commits, replacing the linear\nscan with a single flag test per visited commit.  This reduces the\nper-commit tip check from O(T) to O(1) and the overall cost from\nO(C * T) to O(C + T).\n\nWhen multiple refs point to the same commit, the shared object gets\nthe flag once, so all duplicates are handled automatically.  The\nearly-termination advancement loop checks the flag on the sorted\ncommits array directly, which naturally handles duplicates since the\nflag is on the shared commit object.\n\nThis also removes the index field from struct commit_and_index, since\nthe indirection through the original tips array is no longer needed.\n\nThis function is called by `git for-each-ref --merged` and\n`git branch/tag --contains/--no-contains` via reach_filter() in\nref-filter.c.\n\nBenchmark on a merge-heavy monorepo (2.3M commits, 10,000 refs):\n\n  Command                           Before    After   Speedup\n  for-each-ref --merged HEAD        6.57s     1.59s     4.1x\n  for-each-ref --no-merged HEAD     6.67s     1.66s     4.0x\n  branch --merged HEAD              0.68s     0.61s      10%\n  branch --no-merged HEAD           0.65s     0.61s       8%\n  tag --merged HEAD                 0.12s     0.12s       -\n\nOn linux.git with 10,000 synthetic branches at the root commit (worst\ncase for the DFS walk):\n\n  Command                           Before    After   Speedup\n  for-each-ref --merged HEAD        1.35s     0.35s     3.9x\n  for-each-ref --no-merged HEAD     1.82s     0.31s     5.9x\n\nThe large speedup for for-each-ref is because it checks all 10,000\nrefs as tips, making the O(T) inner loop expensive.  The branch\nsubcommand only checks local branches (fewer tips), so the improvement\nis smaller.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n commit-reach.c | 23 +++++++++++------------\n 1 file changed, 11 insertions(+), 12 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex d3a9b3ed6f..82614d2409 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1125,7 +1125,6 @@ void ahead_behind(struct repository *r,\n \n struct commit_and_index {\n \tstruct commit *commit;\n-\tunsigned int index;\n \ttimestamp_t generation;\n };\n \n@@ -1165,7 +1164,6 @@ void tips_reachable_from_bases(struct repository *r,\n \n \tfor (size_t i = 0; i < tips_nr; i++) {\n \t\tcommits[i].commit = tips[i];\n-\t\tcommits[i].index = i;\n \t\tcommits[i].generation = commit_graph_generation(tips[i]);\n \t}\n \n@@ -1173,6 +1171,9 @@ void tips_reachable_from_bases(struct repository *r,\n \tQSORT(commits, tips_nr, compare_commit_and_index_by_generation);\n \tmin_generation = commits[0].generation;\n \n+\tfor (size_t i = 0; i < tips_nr; i++)\n+\t\tcommits[i].commit->object.flags |= RESULT;\n+\n \twhile (bases) {\n \t\trepo_parse_commit(r, bases->item);\n \t\tcommit_list_insert(bases->item, &stack);\n@@ -1183,20 +1184,16 @@ void tips_reachable_from_bases(struct repository *r,\n \t\tint explored_all_parents = 1;\n \t\tstruct commit_list *p;\n \t\tstruct commit *c = stack->item;\n-\t\ttimestamp_t c_gen = commit_graph_generation(c);\n \n \t\t/* Does it match any of our tips? */\n-\t\tfor (size_t j = min_generation_index; j < tips_nr; j++) {\n-\t\t\tif (c_gen < commits[j].generation)\n-\t\t\t\tbreak;\n-\n-\t\t\tif (commits[j].commit == c) {\n-\t\t\t\ttips[commits[j].index]->object.flags |= mark;\n+\t\t{\n+\t\t\tif (c->object.flags & RESULT) {\n+\t\t\t\tc->object.flags |= mark;\n \n-\t\t\t\tif (j == min_generation_index) {\n-\t\t\t\t\tunsigned int k = j + 1;\n+\t\t\t\tif (commits[min_generation_index].commit->object.flags & mark) {\n+\t\t\t\t\tunsigned int k = min_generation_index + 1;\n \t\t\t\t\twhile (k < tips_nr &&\n-\t\t\t\t\t       (tips[commits[k].index]->object.flags & mark))\n+\t\t\t\t\t       (commits[k].commit->object.flags & mark))\n \t\t\t\t\t\tk++;\n \n \t\t\t\t\t/* Terminate early if all found. */\n@@ -1232,6 +1229,8 @@ void tips_reachable_from_bases(struct repository *r,\n \t}\n \n done:\n+\tfor (size_t i = 0; i < tips_nr; i++)\n+\t\tcommits[i].commit->object.flags &= ~RESULT;\n \tfree(commits);\n \trepo_clear_commit_marks(r, SEEN);\n \tcommit_list_free(stack);\n-- \ngitgitgadget\n\n"},{"id":"543470","messageId":"4d11ebb79ea780c1ce619c66cf9693d819d86d4b.1778947182.git.gitgitgadget@gmail.com","threadId":"65642","inReplyTo":"pull.2116.v3.git.1778947182.gitgitgadget@gmail.com","subject":"[PATCH v3 2/2] t6600: add tests for duplicate tips in tips_reachable_from_bases()","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-05-16T15:59:41Z","receivedAt":"2026-05-16T15:59:47Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nWhen multiple refs point to the same commit, the reachability check\nmust handle them correctly.  Add three tests:\n\n - duplicate tips, all reachable\n - duplicate tips, none reachable\n - duplicate tips at the minimum generation (exercises the\n   early-termination advancement logic)\n\nSuggested-by: Derrick Stolee <stolee@gmail.com>\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n t/t6600-test-reach.sh | 45 +++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 45 insertions(+)\n\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex dc0421ed2f..9486002866 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -612,6 +612,51 @@ test_expect_success 'for-each-ref merged:none' '\n \t\t--format=\"%(refname)\" --stdin\n '\n \n+test_expect_success 'for-each-ref merged:duplicate, all reachable' '\n+\tgit branch dup-a commit-3-3 &&\n+\tgit branch dup-b commit-3-3 &&\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-1-1\n+\trefs/heads/dup-a\n+\trefs/heads/dup-b\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-1-1\n+\trefs/heads/dup-a\n+\trefs/heads/dup-b\n+\tEOF\n+\trun_all_modes git for-each-ref --merged=commit-5-5 \\\n+\t\t--format=\"%(refname)\" --stdin\n+'\n+\n+test_expect_success 'for-each-ref merged:duplicate, none reachable' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/dup-a\n+\trefs/heads/dup-b\n+\trefs/heads/commit-9-9\n+\tEOF\n+\t>expect &&\n+\trun_all_modes git for-each-ref --merged=commit-2-2 \\\n+\t\t--format=\"%(refname)\" --stdin\n+'\n+\n+test_expect_success 'for-each-ref merged:duplicate at min generation' '\n+\tgit branch dup-c commit-1-1 &&\n+\tgit branch dup-d commit-1-1 &&\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/dup-c\n+\trefs/heads/dup-d\n+\trefs/heads/commit-5-5\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-5-5\n+\trefs/heads/dup-c\n+\trefs/heads/dup-d\n+\tEOF\n+\trun_all_modes git for-each-ref --merged=commit-5-5 \\\n+\t\t--format=\"%(refname)\" --stdin\n+'\n+\n # For get_branch_base_for_tip, we only care about\n # first-parent history. Here is the test graph with\n # second parents removed:\n-- \ngitgitgadget\n"},{"id":"543573","messageId":"20260519010354.GE1612961@coredump.intra.peff.net","threadId":"65642","inReplyTo":"pull.2116.v3.git.1778947182.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 0/2] commit-reach: use object flags for tips_reachable_from_bases()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-05-19T01:03:54Z","receivedAt":"2026-05-19T01:03:56Z","isPatch":true,"body":"On Sat, May 16, 2026 at 03:59:39PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n\n> v2 of this patch, addressing Jeff King's feedback:\n> \n>  * Replaced the decoration hash with the RESULT object flag (simpler, no\n>    extra data structure, handles duplicate tips naturally)\n>  * Fixed early-termination bug when multiple refs point to the same commit\n>    (the decoration API overwrites on duplicate keys)\n>  * Removed the now-unused index field from struct commit_and_index\n>  * Diff is +11/-12 lines\n\nUsing the object flag here is so much nicer. I see you're reusing the\nRESULT flag. I'm not sure offhand if there might be any conflict with\nother uses of that flag bit. I think probably not, since it looks like\nit is cleared by the other users after they leave their respective\nfunctions?\n\nUsing a direct set-inclusion check with the flag is nice, but we still\nlook at min_generation_index. If I'm understanding the code right, this\nis mostly about counting the tips we've seen. Which at first glance\nmeans we could probably replace that code with some kind of counter. But\nI think maybe there is some notion of \"crossing off\" commits which we\ndon't actually visit, but which we know become un-visitable because we\ntraverse past their generation numbers.\n\nI think. This is really the first time I'm looking at this code. So\nAFAICT your patch as-is is correct, but it would be nice to go an ACK\nfrom Stolee.\n\n-Peff\n"},{"id":"543859","messageId":"cdea34a8-6f20-4ebc-ac75-461e0f592104@gmail.com","threadId":"65642","inReplyTo":"20260519010354.GE1612961@coredump.intra.peff.net","subject":"Re: [PATCH v3 0/2] commit-reach: use object flags for tips_reachable_from_bases()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-05-21T22:50:25Z","receivedAt":"2026-05-21T22:50:27Z","isPatch":true,"body":"On 5/18/26 9:03 PM, Jeff King wrote:\n> On Sat, May 16, 2026 at 03:59:39PM +0000, Kristofer Karlsson via GitGitGadget wrote:\n> \n>> v2 of this patch, addressing Jeff King's feedback:\n>>\n>>   * Replaced the decoration hash with the RESULT object flag (simpler, no\n>>     extra data structure, handles duplicate tips naturally)\n>>   * Fixed early-termination bug when multiple refs point to the same commit\n>>     (the decoration API overwrites on duplicate keys)\n>>   * Removed the now-unused index field from struct commit_and_index\n>>   * Diff is +11/-12 lines\n> \n> Using the object flag here is so much nicer. I see you're reusing the\n> RESULT flag. I'm not sure offhand if there might be any conflict with\n> other uses of that flag bit. I think probably not, since it looks like\n> it is cleared by the other users after they leave their respective\n> functions?\n> \n> Using a direct set-inclusion check with the flag is nice, but we still\n> look at min_generation_index. If I'm understanding the code right, this\n> is mostly about counting the tips we've seen. Which at first glance\n> means we could probably replace that code with some kind of counter. But\n> I think maybe there is some notion of \"crossing off\" commits which we\n> don't actually visit, but which we know become un-visitable because we\n> traverse past their generation numbers.\n> \n> I think. This is really the first time I'm looking at this code. So\n> AFAICT your patch as-is is correct, but it would be nice to go an ACK\n> from Stolee.\n\nSorry for the delay, but I finally took a close look at this version\nand I'm happy with the use of the RESULT bit. You clean it up and\nshouldn't interfer with the 19th bit being used in upload-pack.c as\nthe HIDDEN_REF bit.\n\nThanks,\n-Stolee\n\n"}]}