{"thread":{"id":"63683","subject":"Perf bug: rev-list w/ 2+ paths relatively slow with commit-graph","startedAt":"2025-06-23T17:58:16Z","lastAt":"2025-06-24T13:32:41Z","messageCount":7,"participants":["Kai Koponen","Junio C Hamano","Lidong Yan"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"520577","messageId":"CADYQcGqaMC=4jgbmnF9Q11oC11jfrqyvH8EuiRRHytpMXd4wYA@mail.gmail.com","threadId":"63683","inReplyTo":null,"subject":"Perf bug: rev-list w/ 2+ paths relatively slow with commit-graph","fromName":"Kai Koponen","fromEmail":"kaikoponen@google.com","sentAt":"2025-06-23T17:58:03Z","receivedAt":"2025-06-23T17:58:16Z","isPatch":false,"sender":{"key":"kaikoponen@google.com","avatar":"https://avatars.githubusercontent.com/u/161378660?v=4"},"body":"Reproduce steps:\n```\ngit clone https://github.com/golang/go.git\ncd go\ngit config core.commitGraph true\ngit commit-graph write --split --reachable --changed-paths  # Without\nthis, all calls equally slow (~1s)\ntime git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\nsrc/clean.bash > /dev/null  # ~90ms\ntime git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\nsrc/Make.dist > /dev/null  # ~100ms\ntime git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\nsrc/clean.bash src/Make.dist > /dev/null  # ~650ms\n```\n\nThe rev-list call with multiple paths takes over 3x longer than the\nsum of individual calls to it for the same files.\n\nExpectation: rev-list with multiple paths should take <= the sum of\nthe time it takes to call it with each path individually (ideally <,\nsince with the count limit it should be able to early-exit and search\nless commits for either path).\n\nAlso reproduces without the -10 arg, or with a lower count (double\ninstead of triple w/ -1), but these results are perhaps most\nsurprising with a count present.\n"},{"id":"520580","messageId":"CADYQcGoH3jHMZ5K1Hrc5YVyqH5-Tm+LxN81iUchOqsHb00nD4g@mail.gmail.com","threadId":"63683","inReplyTo":"CADYQcGqaMC=4jgbmnF9Q11oC11jfrqyvH8EuiRRHytpMXd4wYA@mail.gmail.com","subject":"Re: Perf bug: rev-list w/ 2+ paths relatively slow with commit-graph","fromName":"Kai Koponen","fromEmail":"kaikoponen@google.com","sentAt":"2025-06-23T18:04:12Z","receivedAt":"2025-06-23T18:04:25Z","isPatch":false,"sender":{"key":"kaikoponen@google.com","avatar":"https://avatars.githubusercontent.com/u/161378660?v=4"},"body":"Re: rev-list perf bug, some `git bugreport` version information:\n\n[System Info]\ngit version:\ngit version 2.50.0.714.g196bf9f422-goog\ncpu: x86_64\nno commit associated with this build\nsizeof-long: 8\nsizeof-size_t: 8\nshell-path: /bin/sh\nlibcurl: 8.13.0\nOpenSSL: OpenSSL 3.4.1 11 Feb 2025\nzlib: 1.3.1\nSHA-1: SHA1_DC\nSHA-256: SHA256_BLK\ncompiler info: gnuc: 14.2\nlibc info: glibc: 2.41\n\nOn Mon, Jun 23, 2025 at 1:58 PM Kai Koponen <kaikoponen@google.com> wrote:\n>\n> Reproduce steps:\n> ```\n> git clone https://github.com/golang/go.git\n> cd go\n> git config core.commitGraph true\n> git commit-graph write --split --reachable --changed-paths  # Without\n> this, all calls equally slow (~1s)\n> time git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\n> src/clean.bash > /dev/null  # ~90ms\n> time git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\n> src/Make.dist > /dev/null  # ~100ms\n> time git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\n> src/clean.bash src/Make.dist > /dev/null  # ~650ms\n> ```\n>\n> The rev-list call with multiple paths takes over 3x longer than the\n> sum of individual calls to it for the same files.\n>\n> Expectation: rev-list with multiple paths should take <= the sum of\n> the time it takes to call it with each path individually (ideally <,\n> since with the count limit it should be able to early-exit and search\n> less commits for either path).\n>\n> Also reproduces without the -10 arg, or with a lower count (double\n> instead of triple w/ -1), but these results are perhaps most\n> surprising with a count present.\n"},{"id":"520585","messageId":"xmqq8qli5jyi.fsf@gitster.g","threadId":"63683","inReplyTo":"CADYQcGqaMC=4jgbmnF9Q11oC11jfrqyvH8EuiRRHytpMXd4wYA@mail.gmail.com","subject":"Re: Perf bug: rev-list w/ 2+ paths relatively slow with commit-graph","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-06-23T19:36:21Z","receivedAt":"2025-06-23T19:36:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kai Koponen <kaikoponen@google.com> writes:\n\n> Reproduce steps:\n> ```\n> git clone https://github.com/golang/go.git\n> cd go\n> git config core.commitGraph true\n> git commit-graph write --split --reachable --changed-paths  # Without\n> this, all calls equally slow (~1s)\n> time git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\n> src/clean.bash > /dev/null  # ~90ms\n> time git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\n> src/Make.dist > /dev/null  # ~100ms\n> time git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\n> src/clean.bash src/Make.dist > /dev/null  # ~650ms\n> ```\n>\n> The rev-list call with multiple paths takes over 3x longer than the\n> sum of individual calls to it for the same files.\n>\n> Expectation: rev-list with multiple paths should take <= the sum of\n> the time it takes to call it with each path individually (ideally <,\n> since with the count limit it should be able to early-exit and search\n> less commits for either path).\n>\n> Also reproduces without the -10 arg, or with a lower count (double\n> instead of triple w/ -1), but these results are perhaps most\n> surprising with a count present.\n\nI asked \n\n    How does \"git log -- path\" use the changed-paths bloom filter\n    stored in the commit-graph file?\n\nto https://deepwiki.com/git/git (there is a text field in the bottom\nof the page), and an early part of its answer explains why in a\nfairly convincing way ;-)\n\n    When you run git log -- path, Git first prepares to use bloom\n    filters in the prepare_to_use_bloom_filter function. This function:\n\n     1. Validates the pathspec - It calls forbid_bloom_filters to check\n        if bloom filters can be used revision.c:674-686 . Bloom filters\n        are disabled for wildcards, multiple paths, or complex pathspec\n        magic.\n\n     ...\n\nIn short, the changed-path filter is used only when following\npathspec with a single element that is not a wildcard.  So the\nobserved result is (unfortunately) quite expected.\n\n"},{"id":"520588","messageId":"CADYQcGrR0mKLEWSYZCrL6b7NYLGfdsZsuKCCFQ_ptpMJ8mofmQ@mail.gmail.com","threadId":"63683","inReplyTo":"xmqq8qli5jyi.fsf@gitster.g","subject":"Re: Perf bug: rev-list w/ 2+ paths relatively slow with commit-graph","fromName":"Kai Koponen","fromEmail":"kaikoponen@google.com","sentAt":"2025-06-23T20:19:13Z","receivedAt":"2025-06-23T20:19:26Z","isPatch":false,"sender":{"key":"kaikoponen@google.com","avatar":"https://avatars.githubusercontent.com/u/161378660?v=4"},"body":"I see, more of a perf FR than a bug then.\nI don't have much expertise here, but on the surface of it, it doesn't\nseem to me like there would be any reason the algorithm couldn't check\neach path's bloom filter in turn while searching, other than that this\nwould be a large and annoying change.\n\nOn Mon, Jun 23, 2025 at 3:36 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Kai Koponen <kaikoponen@google.com> writes:\n>\n> > Reproduce steps:\n> > ```\n> > git clone https://github.com/golang/go.git\n> > cd go\n> > git config core.commitGraph true\n> > git commit-graph write --split --reachable --changed-paths  # Without\n> > this, all calls equally slow (~1s)\n> > time git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\n> > src/clean.bash > /dev/null  # ~90ms\n> > time git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\n> > src/Make.dist > /dev/null  # ~100ms\n> > time git rev-list -10 3730814f2f2bf24550920c39a16841583de2dac1 --\n> > src/clean.bash src/Make.dist > /dev/null  # ~650ms\n> > ```\n> >\n> > The rev-list call with multiple paths takes over 3x longer than the\n> > sum of individual calls to it for the same files.\n> >\n> > Expectation: rev-list with multiple paths should take <= the sum of\n> > the time it takes to call it with each path individually (ideally <,\n> > since with the count limit it should be able to early-exit and search\n> > less commits for either path).\n> >\n> > Also reproduces without the -10 arg, or with a lower count (double\n> > instead of triple w/ -1), but these results are perhaps most\n> > surprising with a count present.\n>\n> I asked\n>\n>     How does \"git log -- path\" use the changed-paths bloom filter\n>     stored in the commit-graph file?\n>\n> to https://deepwiki.com/git/git (there is a text field in the bottom\n> of the page), and an early part of its answer explains why in a\n> fairly convincing way ;-)\n>\n>     When you run git log -- path, Git first prepares to use bloom\n>     filters in the prepare_to_use_bloom_filter function. This function:\n>\n>      1. Validates the pathspec - It calls forbid_bloom_filters to check\n>         if bloom filters can be used revision.c:674-686 . Bloom filters\n>         are disabled for wildcards, multiple paths, or complex pathspec\n>         magic.\n>\n>      ...\n>\n> In short, the changed-path filter is used only when following\n> pathspec with a single element that is not a wildcard.  So the\n> observed result is (unfortunately) quite expected.\n>\n"},{"id":"520590","messageId":"xmqq34bq5g29.fsf@gitster.g","threadId":"63683","inReplyTo":"CADYQcGrR0mKLEWSYZCrL6b7NYLGfdsZsuKCCFQ_ptpMJ8mofmQ@mail.gmail.com","subject":"Re: Perf bug: rev-list w/ 2+ paths relatively slow with commit-graph","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-06-23T21:00:30Z","receivedAt":"2025-06-23T21:00:32Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Kai Koponen <kaikoponen@google.com> writes:\n\n> I see, more of a perf FR than a bug then.\n> I don't have much expertise here, but on the surface of it, it doesn't\n> seem to me like there would be any reason the algorithm couldn't check\n> each path's bloom filter in turn while searching, other than that this\n> would be a large and annoying change.\n\nIt looks like that the necessary changes are probably fairly well\nisolated to two functions, i.e., prepare_to_use_bloom_filter() and\nforbid_bloom_filters().  Right now, for a pathspec that has one\nelement \"dir/file\", the code uses two bloom keys for \"dir\" and\n\"dir/file\", but if we have \"dir1/file1\" as well, then it does look\nlike a matter of using two more (and the bloom_keys[] array is\ndesigned to be variable length).\n\nBut those who have more intimate knowledge in the area than I do may\npoint out what is missing in my \"it looks like\" gut feeling.\n"},{"id":"520626","messageId":"E6A4C972-9675-47AE-B5CE-75103DB1D153@gmail.com","threadId":"63683","inReplyTo":"xmqq34bq5g29.fsf@gitster.g","subject":"Re: Perf bug: rev-list w/ 2+ paths relatively slow with commit-graph","fromName":"Lidong Yan","fromEmail":"yldhome2d2@gmail.com","sentAt":"2025-06-24T03:16:09Z","receivedAt":"2025-06-24T03:16:25Z","isPatch":false,"sender":{"key":"yldhome2d2@gmail.com","avatar":"https://avatars.githubusercontent.com/u/77328395?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes：\n> \n> Kai Koponen <kaikoponen@google.com> writes:\n> \n>> I see, more of a perf FR than a bug then.\n>> I don't have much expertise here, but on the surface of it, it doesn't\n>> seem to me like there would be any reason the algorithm couldn't check\n>> each path's bloom filter in turn while searching, other than that this\n>> would be a large and annoying change.\n> \n> It looks like that the necessary changes are probably fairly well\n> isolated to two functions, i.e., prepare_to_use_bloom_filter() and\n> forbid_bloom_filters().  Right now, for a pathspec that has one\n> element \"dir/file\", the code uses two bloom keys for \"dir\" and\n> \"dir/file\", but if we have \"dir1/file1\" as well, then it does look\n> like a matter of using two more (and the bloom_keys[] array is\n> designed to be variable length).\n\nI believe the issue here is that revs->bloom_keys[] represents an\nAND condition, whereas what we actually want is an OR. In Kai’s example,\nwe’re trying to identify commits that modified either src/Make.dist or\nsrc/clean.bash. However, by adding src, Make.dist, and clean.bash to the\nbloom_keys, we end up filtering for commits that modified all of these, rather\nthan any of them.\n\n> But those who have more intimate knowledge in the area than I do may\n> point out what is missing in my \"it looks like\" gut feeling.\n> \n\n"},{"id":"520637","messageId":"xmqqo6ud2rk9.fsf@gitster.g","threadId":"63683","inReplyTo":"E6A4C972-9675-47AE-B5CE-75103DB1D153@gmail.com","subject":"Re: Perf bug: rev-list w/ 2+ paths relatively slow with commit-graph","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-06-24T13:32:38Z","receivedAt":"2025-06-24T13:32:41Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lidong Yan <yldhome2d2@gmail.com> writes:\n\n>> It looks like that the necessary changes are probably fairly well\n>> isolated to two functions, i.e., prepare_to_use_bloom_filter() and\n>> forbid_bloom_filters().  Right now, for a pathspec that has one\n>> element \"dir/file\", the code uses two bloom keys for \"dir\" and\n>> \"dir/file\", but if we have \"dir1/file1\" as well, then it does look\n>> like a matter of using two more (and the bloom_keys[] array is\n>> designed to be variable length).\n>\n> I believe the issue here is that revs->bloom_keys[] represents an\n> AND condition, whereas what we actually want is an OR.\n\nYeah, you're right. bloom.c:bloom_filter_contains() is called repeatedly\nby check_maybe_different_in_bloom_filter() to see if all the bloom_keys[]\nappear to judge if it is possible that the path is changed by the commit.\n\nSo if we wanted to extend in the way we discussed in the message you\nare respoinding to, revs->bloom_keys[] needs to become an array of\nbloom_keys[], one for each literal pathspec element, and then we can\nextend check_maybe_different_in_bloom_filter() to run the current\nlogic for each literal pathspec element, and combine the results by\nORing them.  The way revision.c:release_revisions() releases the\nbloom keys also need to be updated.\n"}]}