{"thread":{"id":"64736","subject":"[PATCH] cat-file: only use bitmaps when filtering","startedAt":"2026-01-06T10:26:00Z","lastAt":"2026-01-16T16:45:51Z","messageCount":3,"participants":["Jeff King","Patrick Steinhardt"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"533124","messageId":"20260106102558.GA68914@coredump.intra.peff.net","threadId":"64736","inReplyTo":null,"subject":"[PATCH] cat-file: only use bitmaps when filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-01-06T10:25:58Z","receivedAt":"2026-01-06T10:26:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Commit 8002e8ee18 (builtin/cat-file: use bitmaps to efficiently filter\nby object type, 2025-04-02) introduced a performance regression when we\nare not filtering objects: it uses bitmaps even when they won't help,\nincurring extra costs. For example, running the new perf tests from this\ncommit, which check the performance of listing objects by oid:\n\n  $ export GIT_PERF_LARGE_REPO=/path/to/linux.git\n  $ git -C \"$GIT_PERF_LARGE_REPO\" repack -adb\n  $ GIT_SKIP_TESTS=p1006.1 ./run 8002e8ee18^ 8002e8ee18 p1006-cat-file.sh\n  [...]\n  Test                                  8002e8ee18^       8002e8ee18\n  -------------------------------------------------------------------------------\n  1006.2: list all objects (sorted)     1.48(1.44+0.04)   6.39(6.35+0.04) +331.8%\n  1006.3: list all objects (unsorted)   3.01(2.97+0.04)   3.40(3.29+0.10) +13.0%\n  1006.4: list blobs                    4.85(4.67+0.17)   1.68(1.58+0.10) -65.4%\n\nAn invocation that filters, like listing all blobs (1006.4), does\nbenefit from using the bitmaps; it now doesn't have to check the type of\neach object from the pack data, so the tradeoff is worth it.\n\nBut for listing all objects in sorted idx order (1006.2), we otherwise\nwould never open the bitmap nor the revindex file. Worse, our sorting\nstep gets much worse. Normally we append into an array in pack .idx\norder, and the sort step is trivial. But with bitmaps, we get the\nobjects in pack order, which is apparently random with respect to oid,\nand have to sort the whole thing. (Note that this freshly-packed state\nrepresents the best case for .idx sorting; if we had two packs, then\nwe'd have their objects one after the other and qsort would have to\ninterleave them).\n\nThe unsorted test in 1006.3 is interesting: there we are going in pack\norder, so we load the revindex for the pack anyway. And though we don't\nsort the result, we do use an oidset to check for duplicates. So we can\nsee in the 8002e8ee18^ timings that those two things cost ~1.5s over the\nsorted case (mostly the oidset hash cost). We also incur the extra cost\nto open the bitmap file as of 8002e8ee18, which seems to be ~400ms.\n(This would probably be faster with a bitmap lookup table, but writing\nthat out is not yet the default).\n\nSo we know that bitmaps help when there's filtering to be done, but\notherwise make things worse. Let's only use them when there's a filter.\n\nThe perf script shows that we've fixed the regressions without hurting\nthe bitmap case:\n\n  Test                                  8002e8ee18^       8002e8ee18                HEAD\n  --------------------------------------------------------------------------------------------------------\n  1006.2: list all objects (sorted)     1.56(1.53+0.03)   6.44(6.37+0.06) +312.8%   1.62(1.54+0.06) +3.8%\n  1006.3: list all objects (unsorted)   3.04(2.98+0.06)   3.45(3.38+0.07) +13.5%    3.04(2.99+0.04) +0.0%\n  1006.4: list blobs                    5.14(4.98+0.15)   1.76(1.68+0.06) -65.8%    1.73(1.64+0.09) -66.3%\n\nNote that there's another related case: we might have a filter that\ncannot be used with bitmaps. That check is handled already for us in\nfor_each_bitmapped_object(), though we'd still load the bitmap and\nrevindex files pointlessly in that case. I don't think it can happen in\npractice for cat-file, though, since it allows only blob:none,\nblob:limit, and object:type filters, all of which work with bitmaps.\n\nIt would be easy-ish to insert an extra check like:\n\n  can_filter_bitmap(&opt->objects_filter);\n\ninto the conditional, but I didn't bother here. It would be redundant\nwith the call in for_each_bitmapped_object(), and the can_filter helper\nfunction is static local in the bitmap code (so we'd have to make it\npublic).\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nThere are some timing tests in 8002e8ee18 that claim the non-filter case\nis not regressed, but it's not clear to me exactly which commands were\nrun. Given the size of the repo there and the fact that it's more I/O\nbound, I'd guess it is using an output format that requires looking at\nthe packed objects.\n\nYou can see the mean user CPU does jump by almost 2 seconds in the\ntimings given there. So it may be that the problem was there but drowned\nout by I/O noise. At any rate, the new t/perf tests isolate it better\nand reproduce consistently for me.\n\n builtin/cat-file.c       |  8 +++++---\n t/perf/p1006-cat-file.sh | 14 ++++++++++++++\n 2 files changed, 19 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex 505ddaa12f..3cb725940d 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -846,12 +846,14 @@ static void batch_each_object(struct batch_options *opt,\n \t\t.callback = callback,\n \t\t.payload = _payload,\n \t};\n-\tstruct bitmap_index *bitmap = prepare_bitmap_git(the_repository);\n+\tstruct bitmap_index *bitmap = NULL;\n \n \tfor_each_loose_object(the_repository->objects, batch_one_object_loose, &payload, 0);\n \n-\tif (bitmap && !for_each_bitmapped_object(bitmap, &opt->objects_filter,\n-\t\t\t\t\t\t batch_one_object_bitmapped, &payload)) {\n+\tif (opt->objects_filter.choice != LOFC_DISABLED &&\n+\t    (bitmap = prepare_bitmap_git(the_repository)) &&\n+\t    !for_each_bitmapped_object(bitmap, &opt->objects_filter,\n+\t\t\t\t       batch_one_object_bitmapped, &payload)) {\n \t\tstruct packed_git *pack;\n \n \t\trepo_for_each_pack(the_repository, pack) {\ndiff --git a/t/perf/p1006-cat-file.sh b/t/perf/p1006-cat-file.sh\nindex dcd8015379..da34ece242 100755\n--- a/t/perf/p1006-cat-file.sh\n+++ b/t/perf/p1006-cat-file.sh\n@@ -9,4 +9,18 @@ test_perf 'cat-file --batch-check' '\n \tgit cat-file --batch-all-objects --batch-check\n '\n \n+test_perf 'list all objects (sorted)' '\n+\tgit cat-file --batch-all-objects --batch-check=\"%(objectname)\"\n+'\n+\n+test_perf 'list all objects (unsorted)' '\n+\tgit cat-file --batch-all-objects --batch-check=\"%(objectname)\" \\\n+\t\t--unordered\n+'\n+\n+test_perf 'list blobs' '\n+\tgit cat-file --batch-all-objects --batch-check=\"%(objectname)\" \\\n+\t\t--unordered --filter=object:type=blob\n+'\n+\n test_done\n-- \n2.52.0.664.g9f53c65b4c\n"},{"id":"533186","messageId":"aV4Xa9ceY4ahYj2m@pks.im","threadId":"64736","inReplyTo":"20260106102558.GA68914@coredump.intra.peff.net","subject":"Re: [PATCH] cat-file: only use bitmaps when filtering","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-01-07T08:20:59Z","receivedAt":"2026-01-07T08:21:04Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Jan 06, 2026 at 05:25:58AM -0500, Jeff King wrote:\n> There are some timing tests in 8002e8ee18 that claim the non-filter case\n> is not regressed, but it's not clear to me exactly which commands were\n> run. Given the size of the repo there and the fact that it's more I/O\n> bound, I'd guess it is using an output format that requires looking at\n> the packed objects.\n\nI honestly can't remember anymore, either. I really should stick with\nthe actual command run in the Hyperfine benchmark names.\n\n> You can see the mean user CPU does jump by almost 2 seconds in the\n> timings given there. So it may be that the problem was there but drowned\n> out by I/O noise. At any rate, the new t/perf tests isolate it better\n> and reproduce consistently for me.\n\nCould be, yeah.\n\n> diff --git a/builtin/cat-file.c b/builtin/cat-file.c\n> index 505ddaa12f..3cb725940d 100644\n> --- a/builtin/cat-file.c\n> +++ b/builtin/cat-file.c\n> @@ -846,12 +846,14 @@ static void batch_each_object(struct batch_options *opt,\n>  \t\t.callback = callback,\n>  \t\t.payload = _payload,\n>  \t};\n> -\tstruct bitmap_index *bitmap = prepare_bitmap_git(the_repository);\n> +\tstruct bitmap_index *bitmap = NULL;\n>  \n>  \tfor_each_loose_object(the_repository->objects, batch_one_object_loose, &payload, 0);\n>  \n> -\tif (bitmap && !for_each_bitmapped_object(bitmap, &opt->objects_filter,\n> -\t\t\t\t\t\t batch_one_object_bitmapped, &payload)) {\n> +\tif (opt->objects_filter.choice != LOFC_DISABLED &&\n> +\t    (bitmap = prepare_bitmap_git(the_repository)) &&\n> +\t    !for_each_bitmapped_object(bitmap, &opt->objects_filter,\n> +\t\t\t\t       batch_one_object_bitmapped, &payload)) {\n>  \t\tstruct packed_git *pack;\n>  \n>  \t\trepo_for_each_pack(the_repository, pack) {\n\nYeah, this seems like a reasonable change to me. I would've preferred to\navoid the assignment in the conditional, but other than that this looks\ngood to me.\n\nThanks!\n\nPatrick\n"},{"id":"534053","messageId":"20260116164549.GA1636797@coredump.intra.peff.net","threadId":"64736","inReplyTo":"aV4Xa9ceY4ahYj2m@pks.im","subject":"Re: [PATCH] cat-file: only use bitmaps when filtering","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-01-16T16:45:49Z","receivedAt":"2026-01-16T16:45:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 07, 2026 at 09:20:59AM +0100, Patrick Steinhardt wrote:\n\n> > -\tif (bitmap && !for_each_bitmapped_object(bitmap, &opt->objects_filter,\n> > -\t\t\t\t\t\t batch_one_object_bitmapped, &payload)) {\n> > +\tif (opt->objects_filter.choice != LOFC_DISABLED &&\n> > +\t    (bitmap = prepare_bitmap_git(the_repository)) &&\n> > +\t    !for_each_bitmapped_object(bitmap, &opt->objects_filter,\n> > +\t\t\t\t       batch_one_object_bitmapped, &payload)) {\n> >  \t\tstruct packed_git *pack;\n> >  \n> >  \t\trepo_for_each_pack(the_repository, pack) {\n> \n> Yeah, this seems like a reasonable change to me. I would've preferred to\n> avoid the assignment in the conditional, but other than that this looks\n> good to me.\n\nYeah, I tried to rewrite this to avoid the assignment-in-conditional,\nbut the logic gets even more convoluted because we need to get to the\n\"else\" clause from multiple places then.\n\nI do think that the for_each_bitmapped_object() interface is making this\na bit harder. Before it was added, the main bitmap entry point was\nalways prepare_bitmap_walk(), which opened the bitmap file itself (and\nonly after doing the cheap can_filter_bitmap() check).\n\nBut here that doesn't quite work, because we need the bitmap_index to\npersist after the for_each_bitmapped_object() call so that we can check\nbitmap_index_contains_pack() on it.\n\nI was tempted to suggest that for_each_bitmapped_object() should return\nthe bitmap_index itself, and then this code would become:\n\n   if (filter.choice != LOFC_DISABLED)\n\t   bitmap = for_each_bitmapped_object(filter, cb, &payload);\n   if (bitmap) {\n\t   /* we iterated those objects; check for other packs */\n   } else {\n\t   /* we did nothing; look at all packs */\n   }\n\n   free_bitmap_index(bitmap);\n\nwhich is not too bad. Mostly I wanted to make the fix as small as\npossible, but I was also a little hesitant to tweak the API when we have\nonly one caller (and we don't know what a second caller might want).\nBut we could always revisit it on top.\n\n-Peff\n"}]}