{"thread":{"id":"58135","subject":"[PATCH] ref-filter: disable save_commit_buffer while traversing","startedAt":"2022-07-11T14:48:10Z","lastAt":"2022-07-11T21:27:19Z","messageCount":4,"participants":["Jeff King","Ævar Arnfjörð Bjarmason","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"458794","messageId":"Ysw4JtoHW1vWmqhz@coredump.intra.peff.net","threadId":"58135","inReplyTo":null,"subject":"[PATCH] ref-filter: disable save_commit_buffer while traversing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-07-11T14:48:06Z","receivedAt":"2022-07-11T14:48:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Various ref-filter options like \"--contains\" or \"--merged\" may cause us\nto traverse large segments of the history graph. It's counter-productive\nto have save_commit_buffer turned on, as that will instruct the commit\ncode to cache in-memory the object contents for each commit we traverse.\n\nThis increases the amount of heap memory used while providing little or\nno benefit, since we're not actually planning to display those commits\n(which is the usual reason that tools like git-log want to keep them\naround). We can easily disable this feature while ref-filter is running.\nThis lowers peak heap (as measured by massif) for running:\n\n  git tag --contains 1da177e4c3\n\nin linux.git from ~100MB to ~20MB. It also seems to improve runtime by\n4-5% (600ms vs 630ms).\n\nA few points to note:\n\n  - it should be safe to temporarily disable save_commit_buffer like\n    this. The saved buffers are accessed through get_commit_buffer(),\n    which treats the saved ones like a cache, and loads on-demand from\n    the object database on a cache miss. So any code that was using this\n    would not be wrong, it might just incur an extra object lookup for\n    some objects. But...\n\n  - I don't think any ref-filter related code is using the cache. While\n    it's true that an option like \"--format=%(*contents:subject)\" or\n    \"--sort=*authordate\" will need to look at the commit contents,\n    ref-filter doesn't use get_commit_buffer() to do so! It always reads\n    the objects directly via read_object_file(), though it does avoid\n    re-reading objects if the format can be satisfied without them.\n\n    Timing \"git tag --format=%(*authordate)\" shows that we're the same\n    before and after, as expected.\n\n  - Note that all of this assumes you don't have a commit-graph file. if\n    you do, then the heap usage is even lower, and the runtime is 10x\n    faster. So in that sense this is not urgent, as there's a much\n    better solution. But since it's such an obvious and easy win for\n    fallback cases (including commits which aren't yet in the graph\n    file), there's no reason not to.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nJust pulling this out of the discussion in:\n\n  https://lore.kernel.org/git/YswuaPx6Mk7YkIim@coredump.intra.peff.net/\n\nas it's an easy win.\n\nI doubt that anyone even cares about restoring the value of\nsave_commit_buffer. So this _could_ be a one-liner turning it off,\nrather than doing the save/restore dance. I was mostly erring on the\nconservative side, but maybe fewer lines of code is a worthwhile thing.\n\n ref-filter.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/ref-filter.c b/ref-filter.c\nindex d3c90e5dbe..bdf39fa761 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -2405,13 +2405,17 @@ static void reach_filter(struct ref_array *array,\n int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int type)\n {\n \tstruct ref_filter_cbdata ref_cbdata;\n+\tint save_commit_buffer_orig;\n \tint ret = 0;\n \n \tref_cbdata.array = array;\n \tref_cbdata.filter = filter;\n \n \tfilter->kind = type & FILTER_REFS_KIND_MASK;\n \n+\tsave_commit_buffer_orig = save_commit_buffer;\n+\tsave_commit_buffer = 0;\n+\n \tinit_contains_cache(&ref_cbdata.contains_cache);\n \tinit_contains_cache(&ref_cbdata.no_contains_cache);\n \n@@ -2444,6 +2448,7 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int\n \treach_filter(array, filter->reachable_from, INCLUDE_REACHED);\n \treach_filter(array, filter->unreachable_from, EXCLUDE_REACHED);\n \n+\tsave_commit_buffer = save_commit_buffer_orig;\n \treturn ret;\n }\n \n-- \n2.37.0.424.g982e2d45d0\n"},{"id":"458802","messageId":"220711.8635f77j7s.gmgdl@evledraar.gmail.com","threadId":"58135","inReplyTo":"Ysw4JtoHW1vWmqhz@coredump.intra.peff.net","subject":"Re: [PATCH] ref-filter: disable save_commit_buffer while traversing","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-07-11T15:12:37Z","receivedAt":"2022-07-11T15:38:40Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Jul 11 2022, Jeff King wrote:\n\n> Various ref-filter options like \"--contains\" or \"--merged\" may cause us\n> to traverse large segments of the history graph. It's counter-productive\n> to have save_commit_buffer turned on, as that will instruct the commit\n> code to cache in-memory the object contents for each commit we traverse.\n>\n> This increases the amount of heap memory used while providing little or\n> no benefit, since we're not actually planning to display those commits\n> (which is the usual reason that tools like git-log want to keep them\n> around). We can easily disable this feature while ref-filter is running.\n> This lowers peak heap (as measured by massif) for running:\n>\n>   git tag --contains 1da177e4c3\n>\n> in linux.git from ~100MB to ~20MB. It also seems to improve runtime by\n> 4-5% (600ms vs 630ms).\n>\n> A few points to note:\n>\n>   - it should be safe to temporarily disable save_commit_buffer like\n>     this. The saved buffers are accessed through get_commit_buffer(),\n>     which treats the saved ones like a cache, and loads on-demand from\n>     the object database on a cache miss. So any code that was using this\n>     would not be wrong, it might just incur an extra object lookup for\n>     some objects. But...\n>\n>   - I don't think any ref-filter related code is using the cache. While\n>     it's true that an option like \"--format=%(*contents:subject)\" or\n>     \"--sort=*authordate\" will need to look at the commit contents,\n>     ref-filter doesn't use get_commit_buffer() to do so! It always reads\n>     the objects directly via read_object_file(), though it does avoid\n>     re-reading objects if the format can be satisfied without them.\n>\n>     Timing \"git tag --format=%(*authordate)\" shows that we're the same\n>     before and after, as expected.\n\nHrm, so for doing the format we're leaving some performance on the table\nas we're currently not making use of this cache, so this makes nothing\nworse on that front.\n\nBut doesn't this approach then also close the door on using the same\ncache for performance improvements in that area? I.e. spotting that\nwe've already parsed that commit, so we can get it from the cache?\n\nB.t.w. did you try to benchmark this with --no-contains too, I tried e.g.:\n\n    ./git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"\n\nWhich gives me:\n\n\t$ git hyperfine -L rev HEAD~1,HEAD -s 'make CFLAGS=-O3' './git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"' -w 1 \n\tBenchmark 1: ./git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"' in 'HEAD~1\n\t  Time (mean ± σ):      1.437 s ±  0.107 s    [User: 1.252 s, System: 0.082 s]\n\t  Range (min … max):    1.306 s …  1.653 s    10 runs\n\t \n\tBenchmark 2: ./git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"' in 'HEAD\n\t  Time (mean ± σ):      1.335 s ±  0.044 s    [User: 1.230 s, System: 0.050 s]\n\t  Range (min … max):    1.260 s …  1.417 s    10 runs\n\t \n\tSummary\n\t  './git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"' in 'HEAD' ran\n\t    1.08 ± 0.09 times faster than './git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"' in 'HEAD~1'\n\t\nWhereas just --contains shows the benefit you're noting:\n\t\n\t$ git hyperfine -L rev HEAD~1,HEAD -s 'make CFLAGS=-O3' './git -P tag --contains 88ce3ef636b -- \"v*\"' -w 1 \n\tBenchmark 1: ./git -P tag --contains 88ce3ef636b -- \"v*\"' in 'HEAD~1\n\t  Time (mean ± σ):      1.068 s ±  0.102 s    [User: 0.886 s, System: 0.068 s]\n\t  Range (min … max):    0.889 s …  1.272 s    10 runs\n\t \n\tBenchmark 2: ./git -P tag --contains 88ce3ef636b -- \"v*\"' in 'HEAD\n\t  Time (mean ± σ):     931.6 ms ±  39.9 ms    [User: 865.3 ms, System: 34.3 ms]\n\t  Range (min … max):   880.5 ms … 990.1 ms    10 runs\n\t \n\tSummary\n\t  './git -P tag --contains 88ce3ef636b -- \"v*\"' in 'HEAD' ran\n\t    1.15 ± 0.12 times faster than './git -P tag --contains 88ce3ef636b -- \"v*\"' in 'HEAD~1'\n\nBut this is against git.git on a loaded system, so maybe it means\nnothing...\n"},{"id":"458806","messageId":"YsxiSwQGvLhzNQrt@coredump.intra.peff.net","threadId":"58135","inReplyTo":"220711.8635f77j7s.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH] ref-filter: disable save_commit_buffer while traversing","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2022-07-11T17:47:55Z","receivedAt":"2022-07-11T17:48:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 11, 2022 at 05:12:37PM +0200, Ævar Arnfjörð Bjarmason wrote:\n\n> Hrm, so for doing the format we're leaving some performance on the table\n> as we're currently not making use of this cache, so this makes nothing\n> worse on that front.\n> \n> But doesn't this approach then also close the door on using the same\n> cache for performance improvements in that area? I.e. spotting that\n> we've already parsed that commit, so we can get it from the cache?\n\nYes, it does close that door, or at least make it more challenging. But\nI suspect it's not a very fruitful door in the first place:\n\n  - it only helps at all if your sort field or format dereferences the\n    tag to get to the commit\n\n  - it only helps if you actually use the traversal options\n\n  - done naively, it's a tradeoff. You might traverse a million commits,\n    but display only a handful of them. Is using all of that memory\n    worth avoiding re-inflating a few commits? Certainly you can come up\n    with a pathological case, but I doubt that it helps in practice.\n\n  - you _could_ do it less naively by caching only the commits directly\n    pointed to by refs. But the depths of the traversals don't know what\n    those are. So you'd probably do it by pre-loading those commits\n    before any traversal, which would work just fine before or after my\n    patch. But I probably wouldn't because of the extra code complexity,\n    and because...\n\n  - if the commit is in a commit-graph file, then pre-loading it is\n    actively harmful (because you might not need it anyway!). So really,\n    the best performance will come from just having a commit graph. I\n    don't see the point in writing more code to micro-optimize the\n    fallback case. For this patch, it's just that the existing code is\n    being actively stupid.\n\n> B.t.w. did you try to benchmark this with --no-contains too, I tried e.g.:\n> \n>     ./git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"\n\nI didn't, but doing it now showed the same 5% speedup.\n\n> Which gives me:\n> \n> \t$ git hyperfine -L rev HEAD~1,HEAD -s 'make CFLAGS=-O3' './git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"' -w 1 \n> \tBenchmark 1: ./git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"' in 'HEAD~1\n> \t  Time (mean ± σ):      1.437 s ±  0.107 s    [User: 1.252 s, System: 0.082 s]\n> \t  Range (min … max):    1.306 s …  1.653 s    10 runs\n> \t \n> \tBenchmark 2: ./git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"' in 'HEAD\n> \t  Time (mean ± σ):      1.335 s ±  0.044 s    [User: 1.230 s, System: 0.050 s]\n> \t  Range (min … max):    1.260 s …  1.417 s    10 runs\n> \t \n> \tSummary\n> \t  './git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"' in 'HEAD' ran\n> \t    1.08 ± 0.09 times faster than './git -P tag --contains 88ce3ef636b --no-contains a39b4003f0e -- \"v*\"' in 'HEAD~1'\n\nIsn't that showing that it's slightly faster with my patch? It's not as\nfast as your \"just --contains\" example, but the exact improvement will\ndepend on how many commits your particular query has to traverse (and\nfrom the improved overall time, it seems that \"just --contains\" is\ntraversing less). And I'd expect a fair bit of noise here. This really\nisn't making anything faster; it's just using less memory, so any\nspeedup is coming from things like less-full memory caches.\n\nBTW, I picked \"--contains 1da177e4c3\" in linux.git because I thought it\nwould have to traverse a lot (because that's the oldest commit), but it\nactually isn't the worst case. Just asking about \"--contains HEAD\"\nrequires more traversal, but still shows a speed improvement (7.45s\nbefore my patch, 7.26s after).\n\nBut I was curious about the heap savings there, since the numbers should\nbe larger. And indeed they are. Here's peak heap for two runs:\n\n  1093721590 ./git.old --no-pager tag --contains HEAD\n   218077941 ./git.new --no-pager tag --contains HEAD\n\nWhoops, that is indeed 1GB of heap, which is what Olaf was seeing\n(though I don't know what repo he's using, it's roughly proportional to\nthe number of commits). And 200MB afterwards. So indeed, I'd expect this\npatch (or the hackier version I showed earlier) to make a significant\ndent in his workload.\n\nOf course the even better solution is to use commit-graphs. That drops\nthe memory usage to a few megabytes, and the time to only a few\nmilliseconds (because generation numbers let us avoid most of the\ntraversal).\n\n-Peff\n"},{"id":"458825","messageId":"xmqqilo3mjbp.fsf@gitster.g","threadId":"58135","inReplyTo":"Ysw4JtoHW1vWmqhz@coredump.intra.peff.net","subject":"Re: [PATCH] ref-filter: disable save_commit_buffer while traversing","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-07-11T21:27:06Z","receivedAt":"2022-07-11T21:27:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n>   - Note that all of this assumes you don't have a commit-graph file. if\n>     you do, then the heap usage is even lower, and the runtime is 10x\n>     faster. So in that sense this is not urgent, as there's a much\n>     better solution. But since it's such an obvious and easy win for\n>     fallback cases (including commits which aren't yet in the graph\n>     file), there's no reason not to.\n\nSounds sensible.\n\n> Signed-off-by: Jeff King <peff@peff.net>\n> ---\n> Just pulling this out of the discussion in:\n>\n>   https://lore.kernel.org/git/YswuaPx6Mk7YkIim@coredump.intra.peff.net/\n>\n> as it's an easy win.\n>\n> I doubt that anyone even cares about restoring the value of\n> save_commit_buffer. So this _could_ be a one-liner turning it off,\n> rather than doing the save/restore dance. I was mostly erring on the\n> conservative side, but maybe fewer lines of code is a worthwhile thing.\n>\n>  ref-filter.c | 5 +++++\n>  1 file changed, 5 insertions(+)\n>\n> diff --git a/ref-filter.c b/ref-filter.c\n> index d3c90e5dbe..bdf39fa761 100644\n> --- a/ref-filter.c\n> +++ b/ref-filter.c\n> @@ -2405,13 +2405,17 @@ static void reach_filter(struct ref_array *array,\n>  int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int type)\n>  {\n>  \tstruct ref_filter_cbdata ref_cbdata;\n> +\tint save_commit_buffer_orig;\n>  \tint ret = 0;\n>  \n>  \tref_cbdata.array = array;\n>  \tref_cbdata.filter = filter;\n>  \n>  \tfilter->kind = type & FILTER_REFS_KIND_MASK;\n>  \n> +\tsave_commit_buffer_orig = save_commit_buffer;\n> +\tsave_commit_buffer = 0;\n> +\n>  \tinit_contains_cache(&ref_cbdata.contains_cache);\n>  \tinit_contains_cache(&ref_cbdata.no_contains_cache);\n>  \n> @@ -2444,6 +2448,7 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int\n>  \treach_filter(array, filter->reachable_from, INCLUDE_REACHED);\n>  \treach_filter(array, filter->unreachable_from, EXCLUDE_REACHED);\n>  \n> +\tsave_commit_buffer = save_commit_buffer_orig;\n>  \treturn ret;\n>  }\n"}]}