{"thread":{"id":"62945","subject":"Poor performance using reftable with many refs","startedAt":"2025-02-13T00:02:08Z","lastAt":"2025-02-13T22:17:41Z","messageCount":12,"participants":["brian m. carlson","Patrick Steinhardt","Jeff King","Christian Couder","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"512334","messageId":"Z602dzQggtDdcgCX@tapette.crustytoothpaste.net","threadId":"62945","inReplyTo":null,"subject":"Poor performance using reftable with many refs","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2025-02-13T00:01:59Z","receivedAt":"2025-02-13T00:02:08Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"I've been doing some testing of reftable at $DAYJOB and I found an\ninteresting performance problem when creating many refs.\n\nI've attached a script which takes 50,000 recent commits, creates a file\nsuitable for `git update-ref --stdin`, deletes all of the existing refs,\nand then uses that file to create the 50,000 refs. The ref creation is\ntimed using Linux's `/usr/bin/time`. (This is partially extracted from\na larger script, so please accept my apologies for some untidiness.)\n\nWith the files backend, the output is as below:\n\n 1.75user 3.73system 0:05.50elapsed 99%CPU (0avgtext+0avgdata 166344maxresident)k\n 0inputs+442880outputs (0major+27962minor)pagefaults 0swaps\n\nWith the reftable backend, this is the output:\n\n 56.91user 0.52system 0:57.44elapsed 99%CPU (0avgtext+0avgdata 160416maxresident)k\n 0inputs+6784outputs (0major+26151minor)pagefaults 0swaps\n\nBoth measurements are on next, so they should have all relevant patches\nthat I'm aware of. I've tested on two X1 Carbons, one with Ubuntu 24.04\nand one with Debian unstable, so they're both reasonably beefy machines\nwith modern Linux OSes.\n\nIt takes about 30 times as long to perform using the reftable backend,\nwhich is concerning. While this is a synthetic measurement, I had\nintended to use it to determine the performance characteristics of\nthe reference update portion when pushing a large repository for the\nfirst time.\n\nI admit I haven't done any other particular investigation as to what's\ngoing wrong here, but the behaviour is very noticeable so it may be easy\nto profile.\n\nOne note: the script will be faster and more useful to reproduce if you\nchange the repository source to a local clone of the Linux repo.\n\n----\n#!/bin/sh -e\n# This script will reproduce a performance problem with many (50000) refs using\n# the current version of reftable in next. The directory `testcase` under the\n# current directory will be removed and replaced.\n#\n# Once the script is finished, you can do `cat testcase/tracedir/*/re-creation`\n# to see the performance characteristics of the files backend (first) and the\n# reftable backend (second).\n\n# Your friendly neighbourhood Linux repository. This may be any valid remote,\n# including an HTTPS or SSH URL.\nREPO_SRC=\"https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git\"\nTAG=\"v6.13\"\n\nexport GIT_CONFIG_GLOBAL=/dev/null\n\ntimed_op () {\n local output=\"$1\"\n local message=\"$2\"\n shift\n shift\n printf '%s...' \"$message\" >&2\n /usr/bin/time -o \"$TRACEDIR/$output\" \"$@\"\n printf 'done.\\n' >&2\n}\n\ndelete_refs () {\n local output=\"$1\"\n (\n echo \"start\"\n git for-each-ref --format=\"%(refname)\" | sed -e 's/^/delete /'\n echo \"prepare\"\n echo \"commit\"\n ) | timed_op \"$output\" \"Deleting all references\" git update-ref --stdin\n}\n\nfake_refs=true\nwhile [ $# -gt 0 ]\ndo\n case \"$1\" in\n --real-refs)\n fake_refs=false\n shift\n ;;\n *)\n break\n ;;\n esac\ndone\n\nrm -fr testcase\nmkdir testcase\ncd testcase\ngit clone --bare \"$REPO_SRC\" repo\n\nmkdir tracedir\n\nfor backend in files reftable\ndo\n git clone --bare repo $backend\n (\n set -e\n cd $backend\n TRACEDIR=\"$(realpath \"../tracedir/$backend\")\"\n mkdir -p \"$TRACEDIR\"\n\n if [ \"$backend\" = reftable ]\n then\n timed_op \"migration\" \"Migrating to reftable\" git refs migrate --ref-format=reftable\n fi\n\n if $fake_refs\n then\n git rev-list \"$TAG\" | head -n 50000 | perl -pe '\n $count++;\n $choice = $count % 4;\n if ($choice == 0) {\n s!^(.*)$!create refs/heads/ref-$count $1!;\n } elsif ($choice == 1) {\n s!^(.*)$!create refs/remotes/bk2204/ref-$count $1!;\n } elsif ($choice == 2) {\n s!^(.*)$!create refs/remotes/origin/ref-$count $1!;\n } elsif ($choice == 3) {\n s!^(.*)$!create refs/tags/tag-$count $1!;\n }\n ' | sort >all-refs\n else\n git for-each-ref --format=\"%(refname) %(objectname)\" | sed -e 's/^/create /' >all-refs\n fi\n delete_refs \"deletion\"\n timed_op \"re-creation\" \"Re-creating refs\" git update-ref --stdin It takes about 30 times as long to perform using the reftable backend,\n> which is concerning. While this is a synthetic measurement, I had\n> intended to use it to determine the performance characteristics of\n> the reference update portion when pushing a large repository for the\n> first time.\n\nInteresting, that's an edge case I didn't yet see. I know about some\ncases where reftables are ~10% slower, but 30x slower is in a different\nballpark.\n\n> I admit I haven't done any other particular investigation as to what's\n> going wrong here, but the behaviour is very noticeable so it may be easy\n> to profile.\n\nNo worries, I'm already happy to have gotten the report in the first\nplace :) I'll investigate, but probably won't get to it before next\nweek.\n\nThanks!\n\nPatrick\n"},{"id":"512348","messageId":"Z62booOOXODOl_sZ@pks.im","threadId":"62945","inReplyTo":"Z62NFXja4CkrxSil@pks.im","subject":"Re: Poor performance using reftable with many refs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-02-13T07:13:38Z","receivedAt":"2025-02-13T07:13:49Z","isPatch":false,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Feb 13, 2025 at 07:11:33AM +0100, Patrick Steinhardt wrote:\n> On Thu, Feb 13, 2025 at 12:01:59AM +0000, brian m. carlson wrote:\n> > It takes about 30 times as long to perform using the reftable backend,\n> > which is concerning. While this is a synthetic measurement, I had\n> > intended to use it to determine the performance characteristics of\n> > the reference update portion when pushing a large repository for the\n> > first time.\n> \n> Interesting, that's an edge case I didn't yet see. I know about some\n> cases where reftables are ~10% slower, but 30x slower is in a different\n> ballpark.\n\nWell, I just cannot resist and had to investigate immediately. I can\nindeed reproduce the issue with \"linux.git\" rather easily:\n\n Benchmark 1: update-ref (refformat = files)\n Time (mean ± σ): 223.0 ms ± 2.4 ms [User: 76.1 ms, System: 145.6 ms]\n Range (min … max): 220.2 ms … 226.6 ms 5 runs\n\n Benchmark 2: update-ref (refformat = reftable)\n Time (mean ± σ): 17.472 s ± 0.153 s [User: 17.402 s, System: 0.049 s]\n Range (min … max): 17.390 s … 17.745 s 5 runs\n\n Summary\n update-ref (refformat = files) ran\n 78.35 ± 1.09 times faster than update-ref (refformat = reftable)\n\nOops, that indeed doesn't look great.\n\nTurns out that you're hitting quite a funny edge case: the issue comes\nfrom you first deleting all preexisting refs in the target repository\nbefore recreating them. With \"packed-refs\", this leads to a repository\nthat has neither a \"packed-refs\" file nor any loose ref, except for HEAD\nof course. But with \"reftables\" it doesn't:\n\n total 368\n -rw-r--r-- 1 pks users 332102 Feb 13 08:00 0x000000000001-0x000000000001-d8285c7c.ref\n -rw-r--r-- 1 pks users 32941 Feb 13 08:00 0x000000000002-0x000000000003-f1a8ebf9.ref\n -rw-r--r-- 1 pks users 86 Feb 13 08:00 tables.list\n\nWe end up with two tables: the first one has been created when cloning\nthe repository and contains all references. The second one has been\ncreated when deleting all references, so it only contains ref deletions.\nBecause deletions don't have to carry an object ID, the resulting table\nis also much smaller. This has the effect that auto-compaction does not\nkick in, because we see that the geometric sequence is still intact. And\nconsequently, all the checks that we perform when recreating the refs\nare way more expensive now because we have to search for conflicts.\n\nA \"fix\" would be to pack references after you have deleted refs. This\nleads to a significant speedup and makes the reftable backend outperform\nthe files backend:\n\n Benchmark 1: update-ref (refformat = files)\n Time (mean ± σ): 223.1 ms ± 0.6 ms [User: 71.2 ms, System: 150.8 ms]\n Range (min … max): 222.5 ms … 224.2 ms 5 runs\n\n Benchmark 2: update-ref (refformat = reftable)\n Time (mean ± σ): 129.1 ms ± 2.1 ms [User: 84.4 ms, System: 44.1 ms]\n Range (min … max): 127.2 ms … 132.7 ms 5 runs\n\n Summary\n update-ref (refformat = reftable) ran\n 1.73 ± 0.03 times faster than update-ref (refformat = files)\n\nI don't really think there's a general fix for this issue though, as the\nissue comes from the design of how tombstone references work.\n\nThat being said, I found an optimization in how we parse ref updates in\ngit-update-ref(1): when we see an exact object ID, we can skip the call\nto `repo_get_oid()`. This function is quite expensive because it doesn't\nonly parse object IDs, but revisions in general. This didn't have much\nof an impact on \"packed-refs\", because there are no references in the\nfirst place. But it did have a significant impact on the \"reftable\"\nbackend, where we do have deleted references.\n\nSo optimizing this edge case leads to a significant speedup for the\n\"reftable\" backend, but also to a small speedup for the \"files\" backend:\n\n Benchmark 1: update-ref (refformat = files, revision = master)\n Time (mean ± σ): 224.7 ms ± 2.9 ms [User: 79.4 ms, System: 143.5 ms]\n Range (min … max): 220.2 ms … 228.0 ms 5 runs\n\n Benchmark 2: update-ref (refformat = reftable, revision = master)\n Time (mean ± σ): 16.304 s ± 0.429 s [User: 16.216 s, System: 0.051 s]\n Range (min … max): 15.865 s … 16.862 s 5 runs\n\n Benchmark 3: update-ref (refformat = files, revision = pks-reftable-optimization)\n Time (mean ± σ): 181.3 ms ± 2.4 ms [User: 69.5 ms, System: 110.7 ms]\n Range (min … max): 178.5 ms … 185.0 ms 5 runs\n\n Benchmark 4: update-ref (refformat = reftable, revision = pks-reftable-optimization)\n Time (mean ± σ): 5.939 s ± 0.060 s [User: 5.895 s, System: 0.028 s]\n Range (min … max): 5.875 s … 6.026 s 5 runs\n\n Summary\n update-ref (refformat = files, revision = pks-reftable-optimization) ran\n 1.24 ± 0.02 times faster than update-ref (refformat = files, revision = master)\n 32.76 ± 0.55 times faster than update-ref (refformat = reftable, revision = pks-reftable-optimization)\n 89.93 ± 2.65 times faster than update-ref (refformat = reftable, revision = master)\n\nI will continue digging a bit to see whether there is more to find in\nthis context and will send a patch to the mailing list later today or\ntomorrow.\n\nPatrick\n"},{"id":"512349","messageId":"20250213082221.GA916028@coredump.intra.peff.net","threadId":"62945","inReplyTo":"Z62booOOXODOl_sZ@pks.im","subject":"Re: Poor performance using reftable with many refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-02-13T08:22:21Z","receivedAt":"2025-02-13T08:22:28Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Feb 13, 2025 at 08:13:38AM +0100, Patrick Steinhardt wrote:\n\n> Turns out that you're hitting quite a funny edge case: the issue comes\n> from you first deleting all preexisting refs in the target repository\n> before recreating them. With \"packed-refs\", this leads to a repository\n> that has neither a \"packed-refs\" file nor any loose ref, except for HEAD\n> of course. But with \"reftables\" it doesn't:\n> \n> total 368\n> -rw-r--r-- 1 pks users 332102 Feb 13 08:00 0x000000000001-0x000000000001-d8285c7c.ref\n> -rw-r--r-- 1 pks users 32941 Feb 13 08:00 0x000000000002-0x000000000003-f1a8ebf9.ref\n> -rw-r--r-- 1 pks users 86 Feb 13 08:00 tables.list\n> \n> We end up with two tables: the first one has been created when cloning\n> the repository and contains all references. The second one has been\n> created when deleting all references, so it only contains ref deletions.\n> Because deletions don't have to carry an object ID, the resulting table\n> is also much smaller. This has the effect that auto-compaction does not\n> kick in, because we see that the geometric sequence is still intact. And\n> consequently, all the checks that we perform when recreating the refs\n> are way more expensive now because we have to search for conflicts.\n\nThat makes sense. But that's only 360k of reftables. Why does it take so\nlong to process?\n\nIt's been a while since I looked at reftables, but I'd think for a\nnormal lookup we should be able to binary-search or similar in each\ntable, find the relevant entries, and be done.\n\nBut I guess we can't easily do that for finding write conflicts, because\nwriting \"foo/bar\" means we need to care about \"foo\" and \"foo/bar/baz\" as\nwell. Finding \"foo\" is easy; we just break apart the proposed refname\nand look for each leading path. But \"foo/bar/baz\" is harder; we have to\nmerge the tables to get an authoritative sorted list of the current\nstate, and then look for the entries adjacent to where our proposed ref\ngoes. Looking at a profiling output, we're spending a lot of time in\nmerged_iter_next_void() and its children, which supports that.\n\nBut the run-time scales linearly with the number of refs we're adding,\nwhich implies that we're doing this iteration independently once per ref\nwe're adding. Instead, if we're given a list of N refs to write, we\nshould be able to sort that list and walk it in parallel with the\nmerged_iter result, making a single pass over the lists.\n\nSo I guess we'd need a version of refs_verify_refname_available() that\ntakes a list of refs rather than a single name. And then you could do\nthat single-pass walk. And as a bonus, you'd be able to de-dup the\nleading prefixes you're looking for (e.g., most of your refs will start\nwith \"refs/heads/\", so we only need to check it once).\n\n> That being said, I found an optimization in how we parse ref updates in\n> git-update-ref(1): when we see an exact object ID, we can skip the call\n> to `repo_get_oid()`. This function is quite expensive because it doesn't\n> only parse object IDs, but revisions in general. This didn't have much\n> of an impact on \"packed-refs\", because there are no references in the\n> first place. But it did have a significant impact on the \"reftable\"\n> backend, where we do have deleted references.\n\nYes, we do similarly spend a lot of time there. But the problem isn't\nquite that repo_get_oid() also parses revisions. When we see a full\nobject id we return it quickly. But you can fall afoul of 798c35fcd8\n(get_sha1: warn about full or short object names that look like refs,\n2013-05-29), which does a full dwim_ref() lookup for each one!\n\nTry:\n\n git -c core.warnAmbiguousRefs=false update-ref --stdin\n\nto disable that. Internally there's a warn_on_object_refname_ambiguity\nflag that some code (like cat-file) sets when it knows it may be asked\nto do a resolve a lot of entries that are likely to be oids.\n\nI kind of wonder if we should ditch that warning. But if we wanted to\nkeep it, maybe adding a flag to get_oid_with_context() would be a less\nhacky way of disabling that warning on a per-call basis.\n\n-Peff\n"},{"id":"512355","messageId":"CAP8UFD3E8_mTwneUgNkC_hZbkaeznAT-dG9njT5wjnm-=iMmcw@mail.gmail.com","threadId":"62945","inReplyTo":"Z62booOOXODOl_sZ@pks.im","subject":"Re: Poor performance using reftable with many refs","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2025-02-13T09:27:39Z","receivedAt":"2025-02-13T09:27:52Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Thu, Feb 13, 2025 at 8:13 AM Patrick Steinhardt wrote:\n\n> We end up with two tables: the first one has been created when cloning\n> the repository and contains all references. The second one has been\n> created when deleting all references, so it only contains ref deletions.\n> Because deletions don't have to carry an object ID, the resulting table\n> is also much smaller. This has the effect that auto-compaction does not\n> kick in, because we see that the geometric sequence is still intact.\n\nNot that I think we should work on this right now, but theoretically,\ncould we \"just\" count the number of entries in each file and base the\ngeometric sequence on the number of entries in each file instead of\nfile size?\n"},{"id":"512360","messageId":"Z63VY_wa7Z6lrUfY@pks.im","threadId":"62945","inReplyTo":"20250213082221.GA916028@coredump.intra.peff.net","subject":"Re: Poor performance using reftable with many refs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-02-13T11:20:03Z","receivedAt":"2025-02-13T11:20:09Z","isPatch":false,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Feb 13, 2025 at 03:22:21AM -0500, Jeff King wrote:\n> On Thu, Feb 13, 2025 at 08:13:38AM +0100, Patrick Steinhardt wrote:\n> \n> > Turns out that you're hitting quite a funny edge case: the issue comes\n> > from you first deleting all preexisting refs in the target repository\n> > before recreating them. With \"packed-refs\", this leads to a repository\n> > that has neither a \"packed-refs\" file nor any loose ref, except for HEAD\n> > of course. But with \"reftables\" it doesn't:\n> > \n> > total 368\n> > -rw-r--r-- 1 pks users 332102 Feb 13 08:00 0x000000000001-0x000000000001-d8285c7c.ref\n> > -rw-r--r-- 1 pks users 32941 Feb 13 08:00 0x000000000002-0x000000000003-f1a8ebf9.ref\n> > -rw-r--r-- 1 pks users 86 Feb 13 08:00 tables.list\n> > \n> > We end up with two tables: the first one has been created when cloning\n> > the repository and contains all references. The second one has been\n> > created when deleting all references, so it only contains ref deletions.\n> > Because deletions don't have to carry an object ID, the resulting table\n> > is also much smaller. This has the effect that auto-compaction does not\n> > kick in, because we see that the geometric sequence is still intact. And\n> > consequently, all the checks that we perform when recreating the refs\n> > are way more expensive now because we have to search for conflicts.\n> \n> That makes sense. But that's only 360k of reftables. Why does it take so\n> long to process?\n> \n> It's been a while since I looked at reftables, but I'd think for a\n> normal lookup we should be able to binary-search or similar in each\n> table, find the relevant entries, and be done.\n> \n> But I guess we can't easily do that for finding write conflicts, because\n> writing \"foo/bar\" means we need to care about \"foo\" and \"foo/bar/baz\" as\n> well. Finding \"foo\" is easy; we just break apart the proposed refname\n> and look for each leading path. But \"foo/bar/baz\" is harder; we have to\n> merge the tables to get an authoritative sorted list of the current\n> state, and then look for the entries adjacent to where our proposed ref\n> goes. Looking at a profiling output, we're spending a lot of time in\n> merged_iter_next_void() and its children, which supports that.\n> \n> But the run-time scales linearly with the number of refs we're adding,\n> which implies that we're doing this iteration independently once per ref\n> we're adding. Instead, if we're given a list of N refs to write, we\n> should be able to sort that list and walk it in parallel with the\n> merged_iter result, making a single pass over the lists.\n> \n> So I guess we'd need a version of refs_verify_refname_available() that\n> takes a list of refs rather than a single name. And then you could do\n> that single-pass walk. And as a bonus, you'd be able to de-dup the\n> leading prefixes you're looking for (e.g., most of your refs will start\n> with \"refs/heads/\", so we only need to check it once).\n\nYes, `refs_verify_refname_available()` is exactly the problem. We spend\n~80% of the time in that function after the optimization I have pointed\nout for `repo_get_oid()`. I assume that we'd see similar performance for\nthe \"files\" backend if we had 360k refs and inserted 360k other refs,\nbut haven't verified this claim.\n\nI've already noticed multiple times that this function is a significant\nslowdown in lots of cases. I've already started looking at it a bit, and\nwill think about ways to fix this.\n\n> > That being said, I found an optimization in how we parse ref updates in\n> > git-update-ref(1): when we see an exact object ID, we can skip the call\n> > to `repo_get_oid()`. This function is quite expensive because it doesn't\n> > only parse object IDs, but revisions in general. This didn't have much\n> > of an impact on \"packed-refs\", because there are no references in the\n> > first place. But it did have a significant impact on the \"reftable\"\n> > backend, where we do have deleted references.\n> \n> Yes, we do similarly spend a lot of time there. But the problem isn't\n> quite that repo_get_oid() also parses revisions. When we see a full\n> object id we return it quickly. But you can fall afoul of 798c35fcd8\n> (get_sha1: warn about full or short object names that look like refs,\n> 2013-05-29), which does a full dwim_ref() lookup for each one!\n> \n> Try:\n> \n> git -c core.warnAmbiguousRefs=false update-ref --stdin\n> \n> to disable that. Internally there's a warn_on_object_refname_ambiguity\n> flag that some code (like cat-file) sets when it knows it may be asked\n> to do a resolve a lot of entries that are likely to be oids.\n> \n> I kind of wonder if we should ditch that warning. But if we wanted to\n> keep it, maybe adding a flag to get_oid_with_context() would be a less\n> hacky way of disabling that warning on a per-call basis.\n\nAh, that makes a lot of sense. I don't really think the warning makes\nsense for git-update-ref(1), so introducing a flag is probably the best\nway to go about this.\n\nThanks for your input!\n\nPatrick\n"},{"id":"512363","messageId":"Z63x1MTZfVfI7Q1a@pks.im","threadId":"62945","inReplyTo":"CAP8UFD3E8_mTwneUgNkC_hZbkaeznAT-dG9njT5wjnm-=iMmcw@mail.gmail.com","subject":"Re: Poor performance using reftable with many refs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-02-13T13:21:24Z","receivedAt":"2025-02-13T13:21:30Z","isPatch":false,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Feb 13, 2025 at 10:27:39AM +0100, Christian Couder wrote:\n> On Thu, Feb 13, 2025 at 8:13 AM Patrick Steinhardt wrote:\n> \n> > We end up with two tables: the first one has been created when cloning\n> > the repository and contains all references. The second one has been\n> > created when deleting all references, so it only contains ref deletions.\n> > Because deletions don't have to carry an object ID, the resulting table\n> > is also much smaller. This has the effect that auto-compaction does not\n> > kick in, because we see that the geometric sequence is still intact.\n> \n> Not that I think we should work on this right now, but theoretically,\n> could we \"just\" count the number of entries in each file and base the\n> geometric sequence on the number of entries in each file instead of\n> file size?\n\nIn theory we could, and that may lead to better results in edge cases\nlike these indeed. And I think if either the header or footer of\nreftables contained a total count of contained records that might have\nbeen a viable thing to do indeed. But they don't, so we'd have to open\nand parse every complete reftable to do so.\n\nBecause of that I think the cost of this would ultimately outweight the\nbenfit. After all, this logic kicks in on every write to determine if we\nneed to auto-compact. As a result, it needs to remain cheap.\n\nPatrick\n"},{"id":"512365","messageId":"Z64CU1sG4B1o52uA@pks.im","threadId":"62945","inReplyTo":"Z63VY_wa7Z6lrUfY@pks.im","subject":"Re: Poor performance using reftable with many refs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2025-02-13T14:31:47Z","receivedAt":"2025-02-13T14:31:57Z","isPatch":false,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Feb 13, 2025 at 12:20:03PM +0100, Patrick Steinhardt wrote:\n> On Thu, Feb 13, 2025 at 03:22:21AM -0500, Jeff King wrote:\n> > On Thu, Feb 13, 2025 at 08:13:38AM +0100, Patrick Steinhardt wrote:\n> > \n> > > Turns out that you're hitting quite a funny edge case: the issue comes\n> > > from you first deleting all preexisting refs in the target repository\n> > > before recreating them. With \"packed-refs\", this leads to a repository\n> > > that has neither a \"packed-refs\" file nor any loose ref, except for HEAD\n> > > of course. But with \"reftables\" it doesn't:\n> > > \n> > > total 368\n> > > -rw-r--r-- 1 pks users 332102 Feb 13 08:00 0x000000000001-0x000000000001-d8285c7c.ref\n> > > -rw-r--r-- 1 pks users 32941 Feb 13 08:00 0x000000000002-0x000000000003-f1a8ebf9.ref\n> > > -rw-r--r-- 1 pks users 86 Feb 13 08:00 tables.list\n> > > \n> > > We end up with two tables: the first one has been created when cloning\n> > > the repository and contains all references. The second one has been\n> > > created when deleting all references, so it only contains ref deletions.\n> > > Because deletions don't have to carry an object ID, the resulting table\n> > > is also much smaller. This has the effect that auto-compaction does not\n> > > kick in, because we see that the geometric sequence is still intact. And\n> > > consequently, all the checks that we perform when recreating the refs\n> > > are way more expensive now because we have to search for conflicts.\n> > \n> > That makes sense. But that's only 360k of reftables. Why does it take so\n> > long to process?\n> > \n> > It's been a while since I looked at reftables, but I'd think for a\n> > normal lookup we should be able to binary-search or similar in each\n> > table, find the relevant entries, and be done.\n> > \n> > But I guess we can't easily do that for finding write conflicts, because\n> > writing \"foo/bar\" means we need to care about \"foo\" and \"foo/bar/baz\" as\n> > well. Finding \"foo\" is easy; we just break apart the proposed refname\n> > and look for each leading path. But \"foo/bar/baz\" is harder; we have to\n> > merge the tables to get an authoritative sorted list of the current\n> > state, and then look for the entries adjacent to where our proposed ref\n> > goes. Looking at a profiling output, we're spending a lot of time in\n> > merged_iter_next_void() and its children, which supports that.\n> > \n> > But the run-time scales linearly with the number of refs we're adding,\n> > which implies that we're doing this iteration independently once per ref\n> > we're adding. Instead, if we're given a list of N refs to write, we\n> > should be able to sort that list and walk it in parallel with the\n> > merged_iter result, making a single pass over the lists.\n> > \n> > So I guess we'd need a version of refs_verify_refname_available() that\n> > takes a list of refs rather than a single name. And then you could do\n> > that single-pass walk. And as a bonus, you'd be able to de-dup the\n> > leading prefixes you're looking for (e.g., most of your refs will start\n> > with \"refs/heads/\", so we only need to check it once).\n> \n> Yes, `refs_verify_refname_available()` is exactly the problem. We spend\n> ~80% of the time in that function after the optimization I have pointed\n> out for `repo_get_oid()`. I assume that we'd see similar performance for\n> the \"files\" backend if we had 360k refs and inserted 360k other refs,\n> but haven't verified this claim.\n> \n> I've already noticed multiple times that this function is a significant\n> slowdown in lots of cases. I've already started looking at it a bit, and\n> will think about ways to fix this.\n\nThis turns out to be harder to implement than anticipated. While\niterating through refnames and the ref iterator in tandem sounds nice,\nit would cause problems when the ref iterator yields millions of refs.\nYou don't want to fully iterate through all of them.\n\nWhat we really want to do is to reuse the iterator and have it skip\nentries: we'd basically create the iterator and re-seek it for every\nrefname we want to check for collisions. This allows us to reuse some of\nthe data structures, and in the best case the underlying backend knows\nto optimize.\n\nThis is something that I have spent a significant time on to implement\nin the last couple months for the reftable backend. But while we have\nreseekable iterators there, which already got us a bit of a performance\nimprovement due to more reuse of data structures, we don't yet know to\nspecifically optimize for some specific seeks. We could e.g. easily skip\nre-reading a block if we already know that it will contain the reference\nwe're searching for.\n\nBut the bigger problem is that the generic reftable iterator does not\nyet have this capability. We first have to revamp their lifetime in the\nsame way that I revamped the lifetime of reftable iterators. A generic\niterator that has hit its end is currently getting free'd immediately,\nwhich I always found to be a bit awkward. But because of this it's\nimpossible to reseek them, as they have lost all their state.\n\nOh, well, I guess that's what I'll be working on now then. But please,\nsomebody stop me if I'm not seeing the forest for the trees.\n\nPatrick\n"},{"id":"512378","messageId":"20250213194256.GA934256@coredump.intra.peff.net","threadId":"62945","inReplyTo":"Z63VY_wa7Z6lrUfY@pks.im","subject":"Re: Poor performance using reftable with many refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-02-13T19:42:56Z","receivedAt":"2025-02-13T19:42:59Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Feb 13, 2025 at 12:20:03PM +0100, Patrick Steinhardt wrote:\n\n> Yes, `refs_verify_refname_available()` is exactly the problem. We spend\n> ~80% of the time in that function after the optimization I have pointed\n> out for `repo_get_oid()`. I assume that we'd see similar performance for\n> the \"files\" backend if we had 360k refs and inserted 360k other refs,\n> but haven't verified this claim.\n\nYeah. I didn't test it, but reading your analysis, I similarly thought\nthat having non-deleted refs might cause the same problem.\n\n> > Try:\n> > \n> > git -c core.warnAmbiguousRefs=false update-ref --stdin\n> > \n> > to disable that. Internally there's a warn_on_object_refname_ambiguity\n> > flag that some code (like cat-file) sets when it knows it may be asked\n> > to do a resolve a lot of entries that are likely to be oids.\n> > \n> > I kind of wonder if we should ditch that warning. But if we wanted to\n> > keep it, maybe adding a flag to get_oid_with_context() would be a less\n> > hacky way of disabling that warning on a per-call basis.\n> \n> Ah, that makes a lot of sense. I don't really think the warning makes\n> sense for git-update-ref(1), so introducing a flag is probably the best\n> way to go about this.\n\nSo I think the core of my suggestion is to just turn off the existing\nflag, like:\n\ndiff --git a/builtin/update-ref.c b/builtin/update-ref.c\nindex 4d35bdc4b4..00e340a53b 100644\n--- a/builtin/update-ref.c\n+++ b/builtin/update-ref.c\n@@ -618,6 +618,8 @@ static void update_refs_stdin(void)\n \tif (!transaction)\n \t\tdie(\"%s\", err.buf);\n \n+\twarn_on_object_refname_ambiguity = 0; /* XXX should also restore after */\n+\n \t/* Read each line dispatch its command */\n \twhile (!strbuf_getwholeline(&input, stdin, line_termination)) {\n \t\tconst struct parse_cmd *cmd = NULL;\n\nwhich would solve the immediate problem, and is what we do elsewhere for\nstdin modes.\n\nBut I'm not sure if my suggestion to do a per-call flag makes sense. A\npatch for that is below, but it gets weird for commands like rev-list.\nThere we turn off the warning for --stdin, but leave it on for arguments\non the command line. But they both end up in handle_revision(), so if we\nconvert that global into a per-call flag, they'll both be affected. You\ncould mitigate that by passing the flags down to handle_revision(), but\nit gets even weirder with stuff like collect_changed_submodules(), which\nputs a potentially large number of entries into a fake argv to call\nsetup_revisions().\n\nSo the patch below, which illustrates the idea, probably weakens the\nwarning to the point of being useless, as commands that use revision.c\nwould never warn at all. So probably we're better off with the hacky\nglobal, or just getting rid of the warning entirely. I have trouble\nimagining it helping much beyond something like:\n\n git branch $some_oid\n\nwhich creates refs/heads/$some_oid. But we probably would be better off\nwarning about that at the time of writing rather than checking for\nambiguity on each read.\n\n-Peff\n\n---\ndiff --git a/builtin/cat-file.c b/builtin/cat-file.c\nindex b13561cf73..ad7a0a6407 100644\n--- a/builtin/cat-file.c\n+++ b/builtin/cat-file.c\n@@ -526,7 +526,7 @@ static void batch_one_object(const char *obj_name,\n {\n \tstruct object_context ctx = {0};\n \tint flags =\n-\t\tGET_OID_HASH_ANY |\n+\t\tGET_OID_HASH_ANY | GET_OID_SKIP_OBJREF |\n \t\t(opt->follow_symlinks ? GET_OID_FOLLOW_SYMLINKS : 0);\n \tenum get_oid_result result;\n \n@@ -781,7 +781,6 @@ static int batch_objects(struct batch_options *opt)\n \tstruct strbuf input = STRBUF_INIT;\n \tstruct strbuf output = STRBUF_INIT;\n \tstruct expand_data data;\n-\tint save_warning;\n \tint retval = 0;\n \n \t/*\n@@ -850,16 +849,6 @@ static int batch_objects(struct batch_options *opt)\n \t\treturn 0;\n \t}\n \n-\t/*\n-\t * We are going to call get_sha1 on a potentially very large number of\n-\t * objects. In most large cases, these will be actual object sha1s. The\n-\t * cost to double-check that each one is not also a ref (just so we can\n-\t * warn) ends up dwarfing the actual cost of the object lookups\n-\t * themselves. We can work around it by just turning off the warning.\n-\t */\n-\tsave_warning = warn_on_object_refname_ambiguity;\n-\twarn_on_object_refname_ambiguity = 0;\n-\n \tif (opt->batch_mode == BATCH_MODE_QUEUE_AND_DISPATCH) {\n \t\tbatch_objects_command(opt, &output, &data);\n \t\tgoto cleanup;\n@@ -886,7 +875,6 @@ static int batch_objects(struct batch_options *opt)\n cleanup:\n \tstrbuf_release(&input);\n \tstrbuf_release(&output);\n-\twarn_on_object_refname_ambiguity = save_warning;\n \treturn retval;\n }\n \ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 58a9b16126..128cc39860 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -4190,17 +4190,13 @@ static void get_object_list(struct rev_info *revs, int ac, const char **av)\n \t};\n \tchar line[1000];\n \tint flags = 0;\n-\tint save_warning;\n \n \tsave_commit_buffer = 0;\n \tsetup_revisions(ac, av, revs, &s_r_opt);\n \n \t/* make sure shallows are read */\n \tis_repository_shallow(the_repository);\n \n-\tsave_warning = warn_on_object_refname_ambiguity;\n-\twarn_on_object_refname_ambiguity = 0;\n-\n \twhile (fgets(line, sizeof(line), stdin) != NULL) {\n \t\tint len = strlen(line);\n \t\tif (len && line[len - 1] == '\\n')\n@@ -4227,8 +4223,6 @@ static void get_object_list(struct rev_info *revs, int ac, const char **av)\n \t\t\tdie(_(\"bad revision '%s'\"), line);\n \t}\n \n-\twarn_on_object_refname_ambiguity = save_warning;\n-\n \tif (use_bitmap_index && !get_object_list_from_bitmap(revs))\n \t\treturn;\n \ndiff --git a/environment.c b/environment.c\nindex e5b361bb5d..b619d0c2b8 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -36,7 +36,6 @@ int minimum_abbrev = 4, default_abbrev = -1;\n int ignore_case;\n int assume_unchanged;\n int is_bare_repository_cfg = -1; /* unspecified */\n-int warn_on_object_refname_ambiguity = 1;\n int repository_format_precious_objects;\n char *git_commit_encoding;\n char *git_log_output_encoding;\ndiff --git a/environment.h b/environment.h\nindex 2f43340f0b..87f71807b7 100644\n--- a/environment.h\n+++ b/environment.h\n@@ -156,7 +156,6 @@ extern int has_symlinks;\n extern int minimum_abbrev, default_abbrev;\n extern int ignore_case;\n extern int assume_unchanged;\n-extern int warn_on_object_refname_ambiguity;\n extern char *apply_default_whitespace;\n extern char *apply_default_ignorewhitespace;\n extern char *git_attributes_file;\ndiff --git a/hash.h b/hash.h\nindex 4367acfec5..e9d881c06e 100644\n--- a/hash.h\n+++ b/hash.h\n@@ -204,6 +204,7 @@ struct object_id {\n #define GET_OID_ONLY_TO_DIE 04000\n #define GET_OID_REQUIRE_PATH 010000\n #define GET_OID_HASH_ANY 020000\n+#define GET_OID_SKIP_OBJREF 040000\n \n #define GET_OID_DISAMBIGUATORS \\\n \t(GET_OID_COMMIT | GET_OID_COMMITTISH | \\\ndiff --git a/object-name.c b/object-name.c\nindex 945d5bdef2..516f214562 100644\n--- a/object-name.c\n+++ b/object-name.c\n@@ -961,7 +961,8 @@ static int get_oid_basic(struct repository *r, const char *str, int len,\n \tint fatal = !(flags & GET_OID_QUIETLY);\n \n \tif (len == r->hash_algo->hexsz && !get_oid_hex(str, oid)) {\n-\t\tif (repo_settings_get_warn_ambiguous_refs(r) && warn_on_object_refname_ambiguity) {\n+\t\tif (repo_settings_get_warn_ambiguous_refs(r) &&\n+\t\t !(flags & GET_OID_SKIP_OBJREF)) {\n \t\t\trefs_found = repo_dwim_ref(r, str, len, &tmp_oid, &real_ref, 0);\n \t\t\tif (refs_found > 0) {\n \t\t\t\twarning(warn_msg, len, str);\ndiff --git a/revision.c b/revision.c\nindex 474fa1e767..5c8e80a0c2 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2184,7 +2184,7 @@ static int handle_revision_arg_1(const char *arg_, struct rev_info *revs, int fl\n \tint local_flags;\n \tconst char *arg = arg_;\n \tint cant_be_filename = revarg_opt & REVARG_CANNOT_BE_FILENAME;\n-\tunsigned get_sha1_flags = GET_OID_RECORD_PATH;\n+\tunsigned get_sha1_flags = GET_OID_RECORD_PATH | GET_OID_SKIP_OBJREF;\n \tint ret;\n \n \tflags = flags & UNINTERESTING ? flags | BOTTOM : flags & ~BOTTOM;\n@@ -2914,12 +2914,8 @@ static void read_revisions_from_stdin(struct rev_info *revs,\n \tstruct strbuf sb;\n \tint seen_dashdash = 0;\n \tint seen_end_of_options = 0;\n-\tint save_warning;\n \tint flags = 0;\n \n-\tsave_warning = warn_on_object_refname_ambiguity;\n-\twarn_on_object_refname_ambiguity = 0;\n-\n \tstrbuf_init(&sb, 1000);\n \twhile (strbuf_getline(&sb, stdin) != EOF) {\n \t\tif (!sb.len)\n@@ -2952,7 +2948,6 @@ static void read_revisions_from_stdin(struct rev_info *revs,\n \t\tread_pathspec_from_stdin(&sb, prune);\n \n \tstrbuf_release(&sb);\n-\twarn_on_object_refname_ambiguity = save_warning;\n }\n \n static void NORETURN diagnose_missing_default(const char *def)\ndiff --git a/submodule.c b/submodule.c\nindex b361076c5b..e63019a6f5 100644\n--- a/submodule.c\n+++ b/submodule.c\n@@ -916,16 +916,12 @@ static void collect_changed_submodules(struct repository *r,\n {\n \tstruct rev_info rev;\n \tconst struct commit *commit;\n-\tint save_warning;\n \tstruct setup_revision_opt s_r_opt = {\n \t\t.assume_dashdash = 1,\n \t};\n \n-\tsave_warning = warn_on_object_refname_ambiguity;\n-\twarn_on_object_refname_ambiguity = 0;\n \trepo_init_revisions(r, &rev, NULL);\n \tsetup_revisions(argv->nr, argv->v, &rev, &s_r_opt);\n-\twarn_on_object_refname_ambiguity = save_warning;\n \tif (prepare_revision_walk(&rev))\n \t\tdie(_(\"revision walk setup failed\"));\n \n"},{"id":"512379","messageId":"20250213195316.GB934256@coredump.intra.peff.net","threadId":"62945","inReplyTo":"Z64CU1sG4B1o52uA@pks.im","subject":"Re: Poor performance using reftable with many refs","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-02-13T19:53:16Z","receivedAt":"2025-02-13T19:53:17Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Feb 13, 2025 at 03:31:47PM +0100, Patrick Steinhardt wrote:\n\n> This turns out to be harder to implement than anticipated. While\n> iterating through refnames and the ref iterator in tandem sounds nice,\n> it would cause problems when the ref iterator yields millions of refs.\n> You don't want to fully iterate through all of them.\n> \n> What we really want to do is to reuse the iterator and have it skip\n> entries: we'd basically create the iterator and re-seek it for every\n> refname we want to check for collisions. This allows us to reuse some of\n> the data structures, and in the best case the underlying backend knows\n> to optimize.\n\nNot having looked at the reftable code much, I'll take your word that it\nisn't easy. ;)\n\nI suspect the files backend isn't very good at this either. It knows to\ntake a starting point in ref_iterator_begin(), and should binary-search\nthe packed-refs file to the right point. But if you want to then ask it\n\"OK, now skip ahead until you see entry 'foo'\", it would just walk\nlinearly to get there. I.e., there is no real seeking. So I guess the\nbest it could do is restart that same binary-search, and the order in\nwhich we feed the refnames is not even really important.\n\nAnd I don't know how seeking works with reftables, since \"skip ahead\"\nrequires merging all of the tables.\n\n> But the bigger problem is that the generic reftable iterator does not\n> yet have this capability. We first have to revamp their lifetime in the\n> same way that I revamped the lifetime of reftable iterators. A generic\n> iterator that has hit its end is currently getting free'd immediately,\n> which I always found to be a bit awkward. But because of this it's\n> impossible to reseek them, as they have lost all their state.\n\nI do think if you feed the refnames in sorted order your seeks would\nalways be forward. So if you hit the end of iteration, there should be\nnothing left to check.\n\n> Oh, well, I guess that's what I'll be working on now then. But please,\n> somebody stop me if I'm not seeing the forest for the trees.\n\nNo, I think it's actually a hard problem. :)\n\n-Peff\n"},{"id":"512381","messageId":"xmqqed01ob7p.fsf@gitster.g","threadId":"62945","inReplyTo":"20250213194256.GA934256@coredump.intra.peff.net","subject":"Re: Poor performance using reftable with many refs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-13T20:12:42Z","receivedAt":"2025-02-13T20:12:46Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> ... I have trouble\n> imagining it helping much beyond something like:\n>\n> git branch $some_oid\n>\n> which creates refs/heads/$some_oid. But we probably would be better off\n> warning about that at the time of writing rather than checking for\n> ambiguity on each read.\n\nCertainly. Thanks for a well thought-out analysis.\n"},{"id":"512387","messageId":"Z65vgud7t3qRMD1a@tapette.crustytoothpaste.net","threadId":"62945","inReplyTo":"20250213082221.GA916028@coredump.intra.peff.net","subject":"Re: Poor performance using reftable with many refs","fromName":"brian m. carlson","fromEmail":"sandals@crustytoothpaste.net","sentAt":"2025-02-13T22:17:38Z","receivedAt":"2025-02-13T22:17:41Z","isPatch":false,"sender":{"key":"sandals@crustytoothpaste.net","avatar":"https://avatars.githubusercontent.com/u/497054?v=4"},"body":"On 2025-02-13 at 08:22:21, Jeff King wrote:\n> Yes, we do similarly spend a lot of time there. But the problem isn't\n> quite that repo_get_oid() also parses revisions. When we see a full\n> object id we return it quickly. But you can fall afoul of 798c35fcd8\n> (get_sha1: warn about full or short object names that look like refs,\n> 2013-05-29), which does a full dwim_ref() lookup for each one!\n> \n> Try:\n> \n> git -c core.warnAmbiguousRefs=false update-ref --stdin\n> \n> to disable that. Internally there's a warn_on_object_refname_ambiguity\n> flag that some code (like cat-file) sets when it knows it may be asked\n> to do a resolve a lot of entries that are likely to be oids.\n\nYeah, I think both of these would be great improvements. The kind of\ncase I'm interested in is reference updates in the context of pushes or\nvarious API calls, where we're always going to have a full object ID and\nthere is never a human connected to the output of Git. I expect that is\nthe case for a lot of users.\n\nI also think it's unlikely that even the general scripter who's working\nwith `git update-ref` is going to want that warning. Most users of that\ncommand are GUIs, APIs, server backends, or the like, and even if I used\nthe command in my Git aliases or some custom commands, I still wouldn't\nreally care for that kind of extra output. I _do_ always want screaming\nperformance in `git update-ref` though, since I frequently, even in my\neveryday scripting, work with large numbers of refs.\n-- \nbrian m. carlson (they/them or he/him)\nToronto, Ontario, CA\n"}]}