{"thread":{"id":"62038","subject":"[PATCH 0/2] refs/files: use heuristic to decide whether to repack with `--auto`","startedAt":"2024-09-02T13:48:34Z","lastAt":"2024-09-05T09:58:29Z","messageCount":16,"participants":["Patrick Steinhardt","karthik nayak","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"501986","messageId":"cover.1725280479.git.ps@pks.im","threadId":"62038","inReplyTo":null,"subject":"[PATCH 0/2] refs/files: use heuristic to decide whether to repack with `--auto`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-02T13:48:29Z","receivedAt":"2024-09-02T13:48:34Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nI recently noticed that `git maintenance run --auto` always ends up\nrepacking loose references. This is because the \"files\" backend does not\nyet have any heuristics wired up to decide whether or not packing refs\nis in order. The consequence is that we always decided to pack them,\nwhich is of course quite a waste of time.\n\nThis small patch series fixes this by introducing a new heuristic for\nthe \"files\" backend. The heuristic is rather simple: the bigger the\n\"packed-refs\" file, the more loose refs we require before we decide to\nrepack. We have been using this heurisitc successfully for a long time\nin Gitaly by now.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (2):\n t0601: merge tests for auto-packing of refs\n refs/files: use heuristic to decide whether to repack with `--auto`\n\n refs/files-backend.c | 75 +++++++++++++++++++++++++\n refs/packed-backend.c | 18 ++++++\n refs/packed-backend.h | 7 +++\n t/t0601-reffiles-pack-refs.sh | 101 ++++++++++++++++++++++++++++------\n 4 files changed, 185 insertions(+), 16 deletions(-)\n\n-- \n2.46.0.421.g159f2d50e7.dirty\n\n"},{"id":"501987","messageId":"3a8063e8b2c05315a5cbe8159a6acae43c12d39c.1725280479.git.ps@pks.im","threadId":"62038","inReplyTo":"cover.1725280479.git.ps@pks.im","subject":"[PATCH 1/2] t0601: merge tests for auto-packing of refs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-02T13:48:35Z","receivedAt":"2024-09-02T13:48:38Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We have two tests in t0601 which exercise the same underlying logic,\nonce via `git pack-refs --auto` and once via `git maintenance run\n--auto`. Merge these two tests into one such that it becomes easier to\nextend test coverage for both commands at the same time.\n\nSigned-off-by: Patrick Steinhardt \n---\n t/t0601-reffiles-pack-refs.sh | 36 +++++++++++++++++++----------------\n 1 file changed, 20 insertions(+), 16 deletions(-)\n\ndiff --git a/t/t0601-reffiles-pack-refs.sh b/t/t0601-reffiles-pack-refs.sh\nindex 60a544b8ee8..ed9652bb829 100755\n--- a/t/t0601-reffiles-pack-refs.sh\n+++ b/t/t0601-reffiles-pack-refs.sh\n@@ -161,13 +161,6 @@ test_expect_success 'test --exclude takes precedence over --include' '\n \tgit pack-refs --include \"refs/heads/pack*\" --exclude \"refs/heads/pack*\" &&\n \ttest -f .git/refs/heads/dont_pack5'\n \n-test_expect_success '--auto packs and prunes refs as usual' '\n-\tgit branch auto &&\n-\ttest_path_is_file .git/refs/heads/auto &&\n-\tgit pack-refs --auto --all &&\n-\ttest_path_is_missing .git/refs/heads/auto\n-'\n-\n test_expect_success 'see if up-to-date packed refs are preserved' '\n \tgit branch q &&\n \tgit pack-refs --all --prune &&\n@@ -367,14 +360,25 @@ test_expect_success 'pack-refs does not drop broken refs during deletion' '\n \ttest_cmp expect actual\n '\n \n-test_expect_success 'maintenance --auto unconditionally packs loose refs' '\n-\tgit update-ref refs/heads/something HEAD &&\n-\ttest_path_is_file .git/refs/heads/something &&\n-\tgit rev-parse refs/heads/something >expect &&\n-\tgit maintenance run --task=pack-refs --auto &&\n-\ttest_path_is_missing .git/refs/heads/something &&\n-\tgit rev-parse refs/heads/something >actual &&\n-\ttest_cmp expect actual\n-'\n+for command in \"git pack-refs --all --auto\" \"git maintenance run --task=pack-refs --auto\"\n+do\n+\ttest_expect_success \"$command unconditionally packs loose refs\" '\n+\t\ttest_when_finished \"rm -rf repo\" &&\n+\t\tgit init repo &&\n+\t\t(\n+\t\t\tcd repo &&\n+\t\t\tgit config set maintenance.auto false &&\n+\t\t\ttest_commit initial &&\n+\n+\t\t\tgit update-ref refs/heads/something HEAD &&\n+\t\t\ttest_path_is_file .git/refs/heads/something &&\n+\t\t\tgit rev-parse refs/heads/something >expect &&\n+\t\t\t$command &&\n+\t\t\ttest_path_is_missing .git/refs/heads/something &&\n+\t\t\tgit rev-parse refs/heads/something >actual &&\n+\t\t\ttest_cmp expect actual\n+\t\t)\n+\t'\n+done\n \n test_done\n-- \n2.46.0.421.g159f2d50e7.dirty\n\n"},{"id":"501988","messageId":"9a63abfe3b812a32d69c7393004bea4f88971559.1725280479.git.ps@pks.im","threadId":"62038","inReplyTo":"cover.1725280479.git.ps@pks.im","subject":"[PATCH 2/2] refs/files: use heuristic to decide whether to repack with `--auto`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-02T13:48:37Z","receivedAt":"2024-09-02T13:48:40Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `--auto` flag for git-pack-refs(1) allows the ref backend to decide\nwhether or not a repack is in order. This switch has been introduced\nmostly with the \"reftable\" backend in mind, which already knows to\nauto-compact its tables during normal operations. When the flag is set,\nthen it will use the same auto-compaction mechanism and thus end up\ndoing nothing in most cases.\n\nThe \"files\" backend does not have any such heuristic yet and instead\npacks any loose references unconditionally. So we rewrite the complete\n\"packed-refs\" file even if there's only a single loose reference to be\npacked.\n\nEven worse, starting with 9f6714ab3e (builtin/gc: pack refs when using\n`git maintenance run --auto`, 2024-03-25), `git pack-refs --auto` is\nunconditionally executed via our auto maintenance, so we end up repacking\nreferences every single time auto maintenance kicks in. And while that\ncommit already mentioned that the \"files\" backend unconditionally packs\nrefs now, the author obviously didn't quite think about the consequences\nthereof. So while the idea was sound, we really should have added a\nheuristic to the \"files\" backend before implementing it.\n\nIntroduce a heuristic that decides whether or not it is worth to pack\nloose references. The important factors to decide here are the number of\nloose references in comparison to the overall size of the \"packed-refs\"\nfile. The bigger the \"packed-refs\" file, the longer it takes to rewrite\nit and thus we scale up the limit of allowed loose references before we\nrepack.\n\nAs is the nature of heuristics, this mechansim isn't obviously\n\"correct\", but should rather be seen as a tradeoff between how much\nresources we spend packing refs and how inefficient the ref store\nbecomes. For all I can say, we have successfully been using the exact\nsame heuristic in Gitaly for several years by now.\n\nSigned-off-by: Patrick Steinhardt \n---\n refs/files-backend.c | 75 +++++++++++++++++++++++++++++++\n refs/packed-backend.c | 18 ++++++++\n refs/packed-backend.h | 7 +++\n t/t0601-reffiles-pack-refs.sh | 85 ++++++++++++++++++++++++++++++-----\n 4 files changed, 175 insertions(+), 10 deletions(-)\n\ndiff --git a/refs/files-backend.c b/refs/files-backend.c\nindex 1cff65f6ae5..261e2b8570f 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -1311,6 +1311,78 @@ static int should_pack_ref(struct files_ref_store *refs,\n \treturn 0;\n }\n \n+static size_t fastlog2(size_t sz)\n+{\n+\tsize_t l = 0;\n+\tif (!sz)\n+\t\treturn 0;\n+\tfor (; sz; sz /= 2)\n+\t\tl++;\n+\treturn l - 1;\n+}\n+\n+static int should_pack_refs(struct files_ref_store *refs,\n+\t\t\t struct pack_refs_opts *opts)\n+{\n+\tstruct ref_iterator *iter;\n+\tsize_t packed_size;\n+\tsize_t refcount = 0;\n+\tsize_t limit;\n+\tint ret;\n+\n+\tif (!(opts->flags & PACK_REFS_AUTO))\n+\t\treturn 1;\n+\n+\tret = packed_refs_size(refs->packed_ref_store, &packed_size);\n+\tif (ret < 0)\n+\t\tdie(\"cannot determine packed-refs size\");\n+\n+\t/*\n+\t * Packing loose references into the packed-refs file scales with the\n+\t * number of references we're about to write. We thus decide whether we\n+\t * repack refs by weighing the current size of the packed-refs file\n+\t * against the number of loose references. This is done such that we do\n+\t * not repack too often on repositories with a huge number of\n+\t * references, where we can expect a lot of churn in the number of\n+\t * references.\n+\t *\n+\t * As a heuristic, we repack if the number of loose references in the\n+\t * repository exceeds `log2(nr_packed_refs) * 5`, where we estimate\n+\t * `nr_packed_refs = packed_size / 100`, which scales as following:\n+\t *\n+\t * - 1kB ~ 10 packed refs: 16 refs\n+\t * - 10kB ~ 100 packed refs: 33 refs\n+\t * - 100kB ~ 1k packed refs: 49 refs\n+\t * - 1MB ~ 10k packed refs: 66 refs\n+\t * - 10MB ~ 100k packed refs: 82 refs\n+\t * - 100MB ~ 1m packed refs: 99 refs\n+\t *\n+\t * We thus allow roughly 16 additional loose refs per factor of ten of\n+\t * packed refs. This heuristic may be tweaked in the future, but should\n+\t * serve as a sufficiently good first iteration.\n+\t */\n+\tlimit = fastlog2(packed_size / 100) * 5;\n+\tif (limit < 16)\n+\t\tlimit = 16;\n+\n+\titer = cache_ref_iterator_begin(get_loose_ref_cache(refs, 0), NULL,\n+\t\t\t\t\trefs->base.repo, 0);\n+\twhile ((ret = ref_iterator_advance(iter)) == ITER_OK) {\n+\t\tif (should_pack_ref(refs, iter->refname, iter->oid,\n+\t\t\t\t iter->flags, opts))\n+\t\t\trefcount++;\n+\t\tif (refcount >= limit) {\n+\t\t\tref_iterator_abort(iter);\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\n+\tif (ret != ITER_DONE)\n+\t\tdie(\"error while iterating over references\");\n+\n+\treturn 0;\n+}\n+\n static int files_pack_refs(struct ref_store *ref_store,\n \t\t\t struct pack_refs_opts *opts)\n {\n@@ -1323,6 +1395,9 @@ static int files_pack_refs(struct ref_store *ref_store,\n \tstruct strbuf err = STRBUF_INIT;\n \tstruct ref_transaction *transaction;\n \n+\tif (!should_pack_refs(refs, opts))\n+\t\treturn 0;\n+\n \ttransaction = ref_store_transaction_begin(refs->packed_ref_store, &err);\n \tif (!transaction)\n \t\treturn -1;\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 7a0a695ca2f..07c57fd541a 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -1250,6 +1250,24 @@ int packed_refs_is_locked(struct ref_store *ref_store)\n \treturn is_lock_file_locked(&refs->lock);\n }\n \n+int packed_refs_size(struct ref_store *ref_store,\n+\t\t size_t *out)\n+{\n+\tstruct packed_ref_store *refs = packed_downcast(ref_store, REF_STORE_READ,\n+\t\t\t\t\t\t\t\"packed_refs_size\");\n+\tstruct stat st;\n+\n+\tif (stat(refs->path, &st) < 0) {\n+\t\tif (errno != ENOENT)\n+\t\t\treturn -1;\n+\t\t*out = 0;\n+\t\treturn 0;\n+\t}\n+\n+\t*out = st.st_size;\n+\treturn 0;\n+}\n+\n /*\n * The packed-refs header line that we write out. Perhaps other traits\n * will be added later.\ndiff --git a/refs/packed-backend.h b/refs/packed-backend.h\nindex 09437ad13bd..9481d5e7c2e 100644\n--- a/refs/packed-backend.h\n+++ b/refs/packed-backend.h\n@@ -27,6 +27,13 @@ int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)\n void packed_refs_unlock(struct ref_store *ref_store);\n int packed_refs_is_locked(struct ref_store *ref_store);\n \n+/*\n+ * Obtain the size of the `packed-refs` file. Reports `0` as size in case there\n+ * is no packed-refs file. Returns 0 on success, negative otherwise.\n+ */\n+int packed_refs_size(struct ref_store *ref_store,\n+\t\t size_t *out);\n+\n /*\n * Return true if `transaction` really needs to be carried out against\n * the specified packed_ref_store, or false if it can be skipped\ndiff --git a/t/t0601-reffiles-pack-refs.sh b/t/t0601-reffiles-pack-refs.sh\nindex ed9652bb829..d8cbd3f202b 100755\n--- a/t/t0601-reffiles-pack-refs.sh\n+++ b/t/t0601-reffiles-pack-refs.sh\n@@ -362,21 +362,86 @@ test_expect_success 'pack-refs does not drop broken refs during deletion' '\n \n for command in \"git pack-refs --all --auto\" \"git maintenance run --task=pack-refs --auto\"\n do\n-\ttest_expect_success \"$command unconditionally packs loose refs\" '\n+\ttest_expect_success \"$command does not repack below 16 refs without packed-refs\" '\n \t\ttest_when_finished \"rm -rf repo\" &&\n \t\tgit init repo &&\n \t\t(\n \t\t\tcd repo &&\n \t\t\tgit config set maintenance.auto false &&\n-\t\t\ttest_commit initial &&\n-\n-\t\t\tgit update-ref refs/heads/something HEAD &&\n-\t\t\ttest_path_is_file .git/refs/heads/something &&\n-\t\t\tgit rev-parse refs/heads/something >expect &&\n-\t\t\t$command &&\n-\t\t\ttest_path_is_missing .git/refs/heads/something &&\n-\t\t\tgit rev-parse refs/heads/something >actual &&\n-\t\t\ttest_cmp expect actual\n+\t\t\tgit commit --allow-empty --message \"initial\" &&\n+\n+\t\t\t# Create 14 additional references, which brings us to\n+\t\t\t# 15 together with the default branch.\n+\t\t\tprintf \"create refs/heads/loose-%d HEAD\\n\" $(test_seq 14) >stdin &&\n+\t\t\tgit update-ref --stdin stdin &&\n+\t\t\tgit update-ref --stdin stdin &&\n+\t\t\tgit update-ref --stdin stdin &&\n+\t\t\tgit update-ref --stdin stdin &&\n+\t\t\tgit update-ref --stdin writes:\n\n> The `--auto` flag for git-pack-refs(1) allows the ref backend to decide\n> whether or not a repack is in order. This switch has been introduced\n> mostly with the \"reftable\" backend in mind, which already knows to\n> auto-compact its tables during normal operations. When the flag is set,\n> then it will use the same auto-compaction mechanism and thus end up\n> doing nothing in most cases.\n>\n> The \"files\" backend does not have any such heuristic yet and instead\n\nNit: s/instead/will instead/\n\n> packs any loose references unconditionally. So we rewrite the complete\n> \"packed-refs\" file even if there's only a single loose reference to be\n> packed.\n>\n> Even worse, starting with 9f6714ab3e (builtin/gc: pack refs when using\n> `git maintenance run --auto`, 2024-03-25), `git pack-refs --auto` is\n> unconditionally executed via our auto maintenance, so we end up repacking\n> references every single time auto maintenance kicks in. And while that\n> commit already mentioned that the \"files\" backend unconditionally packs\n> refs now, the author obviously didn't quite think about the consequences\n> thereof. So while the idea was sound, we really should have added a\n> heuristic to the \"files\" backend before implementing it.\n>\n> Introduce a heuristic that decides whether or not it is worth to pack\n> loose references. The important factors to decide here are the number of\n> loose references in comparison to the overall size of the \"packed-refs\"\n> file. The bigger the \"packed-refs\" file, the longer it takes to rewrite\n> it and thus we scale up the limit of allowed loose references before we\n> repack.\n>\n> As is the nature of heuristics, this mechansim isn't obviously\n> \"correct\", but should rather be seen as a tradeoff between how much\n> resources we spend packing refs and how inefficient the ref store\n> becomes. For all I can say, we have successfully been using the exact\n> same heuristic in Gitaly for several years by now.\n>\n> Signed-off-by: Patrick Steinhardt \n> ---\n> refs/files-backend.c | 75 +++++++++++++++++++++++++++++++\n> refs/packed-backend.c | 18 ++++++++\n> refs/packed-backend.h | 7 +++\n> t/t0601-reffiles-pack-refs.sh | 85 ++++++++++++++++++++++++++++++-----\n> 4 files changed, 175 insertions(+), 10 deletions(-)\n>\n> diff --git a/refs/files-backend.c b/refs/files-backend.c\n> index 1cff65f6ae5..261e2b8570f 100644\n> --- a/refs/files-backend.c\n> +++ b/refs/files-backend.c\n> @@ -1311,6 +1311,78 @@ static int should_pack_ref(struct files_ref_store *refs,\n> \treturn 0;\n> }\n>\n> +static size_t fastlog2(size_t sz)\n\nNit: We already `reftable/stack_test.c:fastlog2` and `bisect.c:log2i`. I\nwonder if it would be nice to consolidate all of them. But I guess it's\nokay, since the reftable code anyways is isolated from the rest of the\nGit code.\n\n> +{\n> +\tsize_t l = 0;\n> +\tif (!sz)\n> +\t\treturn 0;\n> +\tfor (; sz; sz /= 2)\n> +\t\tl++;\n> +\treturn l - 1;\n> +}\n\n[snip]\n\nThe rest of the patch looks great!\n"},{"id":"502019","messageId":"ZtbVbn5rxrmLFuNa@pks.im","threadId":"62038","inReplyTo":"CAOLa=ZRGvU4LvX9kjvF3dJCTvKR6CC1CwPTp515c3Wt5M8a5vA@mail.gmail.com","subject":"Re: [PATCH 2/2] refs/files: use heuristic to decide whether to repack with `--auto`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-03T09:23:00Z","receivedAt":"2024-09-03T09:23:05Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Sep 03, 2024 at 02:00:16AM -0700, karthik nayak wrote:\n> Patrick Steinhardt writes:\n> > diff --git a/refs/files-backend.c b/refs/files-backend.c\n> > index 1cff65f6ae5..261e2b8570f 100644\n> > --- a/refs/files-backend.c\n> > +++ b/refs/files-backend.c\n> > @@ -1311,6 +1311,78 @@ static int should_pack_ref(struct files_ref_store *refs,\n> > \treturn 0;\n> > }\n> >\n> > +static size_t fastlog2(size_t sz)\n> \n> Nit: We already `reftable/stack_test.c:fastlog2` and `bisect.c:log2i`. I\n> wonder if it would be nice to consolidate all of them. But I guess it's\n> okay, since the reftable code anyways is isolated from the rest of the\n> Git code.\n\nYeah, the version we have here is in fact an (almost exact) copy of the\nfunction in our reftable codebase. And as you note, we do not want to\ndeduplicate these such that the reftable library is somewhat isolated\nfrom the rest of the codebase.\n\nI also noticed `log2i()`, but honestly the only reason why I didn't\nreuse it is that I had no clue where to put it. There isn't any header\nthat would be a good fit for it, and creating a new \"math.h\" header for\na single function felt overblown to me. So I decided to just not bother.\nI'm happy to adjust though if somebody has a suggestion for where to put\nit.\n\nPatrick\n"},{"id":"502053","messageId":"xmqq4j6wlhpr.fsf@gitster.g","threadId":"62038","inReplyTo":"ZtbVbn5rxrmLFuNa@pks.im","subject":"Re: [PATCH 2/2] refs/files: use heuristic to decide whether to repack with `--auto`","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-03T18:23:12Z","receivedAt":"2024-09-03T18:23:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> I also noticed `log2i()`, but honestly the only reason why I didn't\n> reuse it is that I had no clue where to put it. There isn't any header\n> that would be a good fit for it, and creating a new \"math.h\" header for\n> a single function felt overblown to me. So I decided to just not bother.\n> I'm happy to adjust though if somebody has a suggestion for where to put\n> it.\n\nGiven the existing contents of wrapper.h (near the end of the file),\nI think wrapper.c would be a good place to do so.\n\nShouldn't this essentially be a call to ffs() with the argument\ntweaked, by the way?\n\n"},{"id":"502098","messageId":"ZtgPSGMD0ZV3S0Nn@pks.im","threadId":"62038","inReplyTo":"xmqq4j6wlhpr.fsf@gitster.g","subject":"Re: [PATCH 2/2] refs/files: use heuristic to decide whether to repack with `--auto`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-04T07:42:06Z","receivedAt":"2024-09-04T07:42:11Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Sep 03, 2024 at 11:23:12AM -0700, Junio C Hamano wrote:\n> Patrick Steinhardt writes:\n> \n> > I also noticed `log2i()`, but honestly the only reason why I didn't\n> > reuse it is that I had no clue where to put it. There isn't any header\n> > that would be a good fit for it, and creating a new \"math.h\" header for\n> > a single function felt overblown to me. So I decided to just not bother.\n> > I'm happy to adjust though if somebody has a suggestion for where to put\n> > it.\n> \n> Given the existing contents of wrapper.h (near the end of the file),\n> I think wrapper.c would be a good place to do so.\n\nIndeed. Quite a grab bag of functions, thanks for the hint!\n\n> Shouldn't this essentially be a call to ffs() with the argument\n> tweaked, by the way?\n\nWe are looking for the last set bit, not for the first set bit. We can\nmassage things a bit, but wouldn't that require us to be aware of the\nplatforms endianess?\n\nIn any case, GCC is clever enough to notice what we're doing:\n\n fastlog2(unsigned long):\n xor eax, eax\n test rdi, rdi\n je .L5\n bsr rax, rdi\n .L5:\n ret\n\nThe `log2i()` function looks a bit less efficient:\n\n log2i(unsigned long):\n test rdi, rdi\n je .L3\n bsr rdi, rdi\n lea eax, [rdi+1]\n cdqe\n ret\n .L3:\n xor eax, eax\n ret\n\nClang isn't yet clever enough with v18.1, but is with trunk:\n\n log2i(unsigned long):\n bsr rax, rdi\n inc rax\n test rdi, rdi\n cmove rax, rdi\n ret\n\n fastlog2(unsigned long):\n test rdi, rdi\n je .LBB1_1\n shr rdi\n bsr rcx, rdi\n mov eax, 127\n cmovne rax, rcx\n xor eax, -64\n add eax, 65\n ret\n .LBB1_1:\n mov eax, -1\n ret\n\nSo with the following definition we're optimizing both with GCC and\nClang:\n\n size_t fastlog2(size_t sz)\n {\n size_t l = 0;\n if (!sz)\n return 0;\n for (; sz; sz >>= 1)\n l++;\n return l;\n }\n\nI'd thus say we can just pick that function instead of caring about\nplatform endianess with `ffs()`.\n\nPatrick\n"},{"id":"502101","messageId":"ZtgfIPOZO1p4_ExF@pks.im","threadId":"62038","inReplyTo":"CAOLa=ZRGvU4LvX9kjvF3dJCTvKR6CC1CwPTp515c3Wt5M8a5vA@mail.gmail.com","subject":"Re: [PATCH 2/2] refs/files: use heuristic to decide whether to repack with `--auto`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-04T08:49:40Z","receivedAt":"2024-09-04T08:49:47Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Tue, Sep 03, 2024 at 02:00:16AM -0700, karthik nayak wrote:\n> Patrick Steinhardt writes:\n> \n> > The `--auto` flag for git-pack-refs(1) allows the ref backend to decide\n> > whether or not a repack is in order. This switch has been introduced\n> > mostly with the \"reftable\" backend in mind, which already knows to\n> > auto-compact its tables during normal operations. When the flag is set,\n> > then it will use the same auto-compaction mechanism and thus end up\n> > doing nothing in most cases.\n> >\n> > The \"files\" backend does not have any such heuristic yet and instead\n> \n> Nit: s/instead/will instead/\n> \n> > packs any loose references unconditionally. So we rewrite the complete\n> > \"packed-refs\" file even if there's only a single loose reference to be\n> > packed.\n\nRevisiting this: isn't the current version of this sentence correct?\nReplacing it with \"will instead\" certainly makes it incorrect without\nalso changing \"packs\" to \"pack\".\n\nPatrick\n"},{"id":"502102","messageId":"cover.1725439407.git.ps@pks.im","threadId":"62038","inReplyTo":"cover.1725280479.git.ps@pks.im","subject":"[PATCH v2 0/3] refs/files: use heuristics to decide whether to repack with `--auto`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-04T08:52:58Z","receivedAt":"2024-09-04T08:53:01Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"Hi,\n\nthis is the second version of my patch series that introduces a new\nheuristic for packing refs with the \"files\" backend. This heuristic is\ndesigned to avoid needlessly rewriting the \"packed-refs\" file when there\nare only a small set of loose refs. The number of loose refs required\nscales with the size of the \"packed-refs\" file.\n\nThere is only one change compared to v1, namely a deduplication of the\nlog2 functions we have in our tree.\n\nThanks!\n\nPatrick\n\nPatrick Steinhardt (3):\n wrapper: introduce `log2u()`\n t0601: merge tests for auto-packing of refs\n refs/files: use heuristic to decide whether to repack with `--auto`\n\n bisect.c | 12 +---\n refs/files-backend.c | 65 ++++++++++++++++++++++\n refs/packed-backend.c | 18 ++++++\n refs/packed-backend.h | 7 +++\n t/t0601-reffiles-pack-refs.sh | 101 ++++++++++++++++++++++++++++------\n wrapper.h | 18 ++++++\n 6 files changed, 194 insertions(+), 27 deletions(-)\n\nRange-diff against v1:\n-: ----------- > 1: df8c5dffffe wrapper: introduce `log2u()`\n1: 3a8063e8b2c = 2: 4a59cec205d t0601: merge tests for auto-packing of refs\n2: 9a63abfe3b8 ! 3: 49f953142b1 refs/files: use heuristic to decide whether to repack with `--auto`\n @@ refs/files-backend.c: static int should_pack_ref(struct files_ref_store *refs,\n \treturn 0;\n }\n \n -+static size_t fastlog2(size_t sz)\n -+{\n -+\tsize_t l = 0;\n -+\tif (!sz)\n -+\t\treturn 0;\n -+\tfor (; sz; sz /= 2)\n -+\t\tl++;\n -+\treturn l - 1;\n -+}\n -+\n +static int should_pack_refs(struct files_ref_store *refs,\n +\t\t\t struct pack_refs_opts *opts)\n +{\n @@ refs/files-backend.c: static int should_pack_ref(struct files_ref_store *refs,\n +\t * packed refs. This heuristic may be tweaked in the future, but should\n +\t * serve as a sufficiently good first iteration.\n +\t */\n -+\tlimit = fastlog2(packed_size / 100) * 5;\n ++\tlimit = log2u(packed_size / 100) * 5;\n +\tif (limit < 16)\n +\t\tlimit = 16;\n +\n\nbase-commit: 4590f2e9412378c61eac95966709c78766d326ba\n-- \n2.46.0.519.g2e7b89e038.dirty\n\n"},{"id":"502103","messageId":"df8c5dffffed0edd9068406fcf39ac6608bc930f.1725439407.git.ps@pks.im","threadId":"62038","inReplyTo":"cover.1725439407.git.ps@pks.im","subject":"[PATCH v2 1/3] wrapper: introduce `log2u()`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-04T08:53:00Z","receivedAt":"2024-09-04T08:53:04Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We have an implementation of a function that computes the log2 for an\ninteger. While we could instead use log2(3P), that involves floating\npoint numbers and is thus needlessly complex and inefficient.\n\nWe're about to add a second caller that wants to compute log2 for a\n`size_t`. Let's thus move the function into \"wrapper.h\" such that it\nbecomes generally available.\n\nWhile at it, tweak the implementation a bit:\n\n - The parameter is converted from `int` to `uintmax_t`. This\n conversion is safe to do in \"bisect.c\" because we already check that\n the argument is positive.\n\n - The return value is an `unsigned`. It cannot ever be negative, so it\n is pointless for it to be a signed integer.\n\n - Loop until `!n` instead of requiring that `n > 1` and then subtract\n 1 from the result and add a special case for `!sz`. This helps\n compilers to generate more efficient code.\n\nCompilers recognize the pattern of this function and optimize\naccordingly. On GCC 14.2 x86_64:\n\n log2u(unsigned long):\n test rdi, rdi\n je .L3\n bsr rax, rdi\n ret\n .L3:\n mov eax, -1\n ret\n\nClang 18.1 does not yet recognize the pattern, but starts to do so on\nClang trunk x86_64. The code isn't quite as efficient as the one\ngenerated by GCC, but still manages to optimize away the loop:\n\n log2u(unsigned long):\n test rdi, rdi\n je .LBB0_1\n shr rdi\n bsr rcx, rdi\n mov eax, 127\n cmovne rax, rcx\n xor eax, -64\n add eax, 65\n ret\n .LBB0_1:\n mov eax, -1\n ret\n\nThe pattern is also recognized on other platforms like ARM64 GCC 14.2.0,\nwhere we end up using `clz`:\n\n log2u(unsigned long):\n clz x2, x0\n cmp x0, 0\n mov w1, 63\n sub w0, w1, w2\n csinv w0, w0, wzr, ne\n ret\n\nNote that we have a similar function `fastlog2()` in the reftable code.\nAs that codebase is separate from the Git codebase we do not adapt it to\nuse the new function.\n\nSigned-off-by: Patrick Steinhardt \n---\n bisect.c | 12 +-----------\n wrapper.h | 18 ++++++++++++++++++\n 2 files changed, 19 insertions(+), 11 deletions(-)\n\ndiff --git a/bisect.c b/bisect.c\nindex 4406fc44cf9..4713226fad4 100644\n--- a/bisect.c\n+++ b/bisect.c\n@@ -1130,16 +1130,6 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix)\n \treturn res;\n }\n \n-static inline int log2i(int n)\n-{\n-\tint log2 = 0;\n-\n-\tfor (; n > 1; n >>= 1)\n-\t\tlog2++;\n-\n-\treturn log2;\n-}\n-\n static inline int exp2i(int n)\n {\n \treturn 1 << n;\n@@ -1162,7 +1152,7 @@ int estimate_bisect_steps(int all)\n \tif (all < 3)\n \t\treturn 0;\n \n-\tn = log2i(all);\n+\tn = log2u(all);\n \te = exp2i(n);\n \tx = all - e;\n \ndiff --git a/wrapper.h b/wrapper.h\nindex 1b2b047ea06..a6b3e1f09ec 100644\n--- a/wrapper.h\n+++ b/wrapper.h\n@@ -140,4 +140,22 @@ int csprng_bytes(void *buf, size_t len);\n */\n uint32_t git_rand(void);\n \n+/* Provide log2 of the given `size_t`. */\n+static inline unsigned log2u(uintmax_t sz)\n+{\n+\tunsigned l = 0;\n+\n+\t/*\n+\t * Technically this isn't required, but it helps the compiler optimize\n+\t * this to a `bsr` instruction.\n+\t */\n+\tif (!sz)\n+\t\treturn 0;\n+\n+\tfor (; sz; sz >>= 1)\n+\t\tl++;\n+\n+\treturn l - 1;\n+}\n+\n #endif /* WRAPPER_H */\n-- \n2.46.0.519.g2e7b89e038.dirty\n\n"},{"id":"502104","messageId":"4a59cec205df7c09bc23a1f2609e728f2df5cef8.1725439407.git.ps@pks.im","threadId":"62038","inReplyTo":"cover.1725439407.git.ps@pks.im","subject":"[PATCH v2 2/3] t0601: merge tests for auto-packing of refs","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-04T08:53:03Z","receivedAt":"2024-09-04T08:53:07Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"We have two tests in t0601 which exercise the same underlying logic,\nonce via `git pack-refs --auto` and once via `git maintenance run\n--auto`. Merge these two tests into one such that it becomes easier to\nextend test coverage for both commands at the same time.\n\nSigned-off-by: Patrick Steinhardt \n---\n t/t0601-reffiles-pack-refs.sh | 36 +++++++++++++++++++----------------\n 1 file changed, 20 insertions(+), 16 deletions(-)\n\ndiff --git a/t/t0601-reffiles-pack-refs.sh b/t/t0601-reffiles-pack-refs.sh\nindex 60a544b8ee8..ed9652bb829 100755\n--- a/t/t0601-reffiles-pack-refs.sh\n+++ b/t/t0601-reffiles-pack-refs.sh\n@@ -161,13 +161,6 @@ test_expect_success 'test --exclude takes precedence over --include' '\n \tgit pack-refs --include \"refs/heads/pack*\" --exclude \"refs/heads/pack*\" &&\n \ttest -f .git/refs/heads/dont_pack5'\n \n-test_expect_success '--auto packs and prunes refs as usual' '\n-\tgit branch auto &&\n-\ttest_path_is_file .git/refs/heads/auto &&\n-\tgit pack-refs --auto --all &&\n-\ttest_path_is_missing .git/refs/heads/auto\n-'\n-\n test_expect_success 'see if up-to-date packed refs are preserved' '\n \tgit branch q &&\n \tgit pack-refs --all --prune &&\n@@ -367,14 +360,25 @@ test_expect_success 'pack-refs does not drop broken refs during deletion' '\n \ttest_cmp expect actual\n '\n \n-test_expect_success 'maintenance --auto unconditionally packs loose refs' '\n-\tgit update-ref refs/heads/something HEAD &&\n-\ttest_path_is_file .git/refs/heads/something &&\n-\tgit rev-parse refs/heads/something >expect &&\n-\tgit maintenance run --task=pack-refs --auto &&\n-\ttest_path_is_missing .git/refs/heads/something &&\n-\tgit rev-parse refs/heads/something >actual &&\n-\ttest_cmp expect actual\n-'\n+for command in \"git pack-refs --all --auto\" \"git maintenance run --task=pack-refs --auto\"\n+do\n+\ttest_expect_success \"$command unconditionally packs loose refs\" '\n+\t\ttest_when_finished \"rm -rf repo\" &&\n+\t\tgit init repo &&\n+\t\t(\n+\t\t\tcd repo &&\n+\t\t\tgit config set maintenance.auto false &&\n+\t\t\ttest_commit initial &&\n+\n+\t\t\tgit update-ref refs/heads/something HEAD &&\n+\t\t\ttest_path_is_file .git/refs/heads/something &&\n+\t\t\tgit rev-parse refs/heads/something >expect &&\n+\t\t\t$command &&\n+\t\t\ttest_path_is_missing .git/refs/heads/something &&\n+\t\t\tgit rev-parse refs/heads/something >actual &&\n+\t\t\ttest_cmp expect actual\n+\t\t)\n+\t'\n+done\n \n test_done\n-- \n2.46.0.519.g2e7b89e038.dirty\n\n"},{"id":"502105","messageId":"49f953142b1b20a63102b87a1d96f5bc1f79da82.1725439407.git.ps@pks.im","threadId":"62038","inReplyTo":"cover.1725439407.git.ps@pks.im","subject":"[PATCH v2 3/3] refs/files: use heuristic to decide whether to repack with `--auto`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-04T08:53:08Z","receivedAt":"2024-09-04T08:53:11Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"The `--auto` flag for git-pack-refs(1) allows the ref backend to decide\nwhether or not a repack is in order. This switch has been introduced\nmostly with the \"reftable\" backend in mind, which already knows to\nauto-compact its tables during normal operations. When the flag is set,\nthen it will use the same auto-compaction mechanism and thus end up\ndoing nothing in most cases.\n\nThe \"files\" backend does not have any such heuristic yet and instead\npacks any loose references unconditionally. So we rewrite the complete\n\"packed-refs\" file even if there's only a single loose reference to be\npacked.\n\nEven worse, starting with 9f6714ab3e (builtin/gc: pack refs when using\n`git maintenance run --auto`, 2024-03-25), `git pack-refs --auto` is\nunconditionally executed via our auto maintenance, so we end up repacking\nreferences every single time auto maintenance kicks in. And while that\ncommit already mentioned that the \"files\" backend unconditionally packs\nrefs now, the author obviously didn't quite think about the consequences\nthereof. So while the idea was sound, we really should have added a\nheuristic to the \"files\" backend before implementing it.\n\nIntroduce a heuristic that decides whether or not it is worth to pack\nloose references. The important factors to decide here are the number of\nloose references in comparison to the overall size of the \"packed-refs\"\nfile. The bigger the \"packed-refs\" file, the longer it takes to rewrite\nit and thus we scale up the limit of allowed loose references before we\nrepack.\n\nAs is the nature of heuristics, this mechansim isn't obviously\n\"correct\", but should rather be seen as a tradeoff between how much\nresources we spend packing refs and how inefficient the ref store\nbecomes. For all I can say, we have successfully been using the exact\nsame heuristic in Gitaly for several years by now.\n\nSigned-off-by: Patrick Steinhardt \n---\n refs/files-backend.c | 65 +++++++++++++++++++++++++++\n refs/packed-backend.c | 18 ++++++++\n refs/packed-backend.h | 7 +++\n t/t0601-reffiles-pack-refs.sh | 85 ++++++++++++++++++++++++++++++-----\n 4 files changed, 165 insertions(+), 10 deletions(-)\n\ndiff --git a/refs/files-backend.c b/refs/files-backend.c\nindex 1cff65f6ae5..51bcd16f821 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -1311,6 +1311,68 @@ static int should_pack_ref(struct files_ref_store *refs,\n \treturn 0;\n }\n \n+static int should_pack_refs(struct files_ref_store *refs,\n+\t\t\t struct pack_refs_opts *opts)\n+{\n+\tstruct ref_iterator *iter;\n+\tsize_t packed_size;\n+\tsize_t refcount = 0;\n+\tsize_t limit;\n+\tint ret;\n+\n+\tif (!(opts->flags & PACK_REFS_AUTO))\n+\t\treturn 1;\n+\n+\tret = packed_refs_size(refs->packed_ref_store, &packed_size);\n+\tif (ret < 0)\n+\t\tdie(\"cannot determine packed-refs size\");\n+\n+\t/*\n+\t * Packing loose references into the packed-refs file scales with the\n+\t * number of references we're about to write. We thus decide whether we\n+\t * repack refs by weighing the current size of the packed-refs file\n+\t * against the number of loose references. This is done such that we do\n+\t * not repack too often on repositories with a huge number of\n+\t * references, where we can expect a lot of churn in the number of\n+\t * references.\n+\t *\n+\t * As a heuristic, we repack if the number of loose references in the\n+\t * repository exceeds `log2(nr_packed_refs) * 5`, where we estimate\n+\t * `nr_packed_refs = packed_size / 100`, which scales as following:\n+\t *\n+\t * - 1kB ~ 10 packed refs: 16 refs\n+\t * - 10kB ~ 100 packed refs: 33 refs\n+\t * - 100kB ~ 1k packed refs: 49 refs\n+\t * - 1MB ~ 10k packed refs: 66 refs\n+\t * - 10MB ~ 100k packed refs: 82 refs\n+\t * - 100MB ~ 1m packed refs: 99 refs\n+\t *\n+\t * We thus allow roughly 16 additional loose refs per factor of ten of\n+\t * packed refs. This heuristic may be tweaked in the future, but should\n+\t * serve as a sufficiently good first iteration.\n+\t */\n+\tlimit = log2u(packed_size / 100) * 5;\n+\tif (limit < 16)\n+\t\tlimit = 16;\n+\n+\titer = cache_ref_iterator_begin(get_loose_ref_cache(refs, 0), NULL,\n+\t\t\t\t\trefs->base.repo, 0);\n+\twhile ((ret = ref_iterator_advance(iter)) == ITER_OK) {\n+\t\tif (should_pack_ref(refs, iter->refname, iter->oid,\n+\t\t\t\t iter->flags, opts))\n+\t\t\trefcount++;\n+\t\tif (refcount >= limit) {\n+\t\t\tref_iterator_abort(iter);\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\n+\tif (ret != ITER_DONE)\n+\t\tdie(\"error while iterating over references\");\n+\n+\treturn 0;\n+}\n+\n static int files_pack_refs(struct ref_store *ref_store,\n \t\t\t struct pack_refs_opts *opts)\n {\n@@ -1323,6 +1385,9 @@ static int files_pack_refs(struct ref_store *ref_store,\n \tstruct strbuf err = STRBUF_INIT;\n \tstruct ref_transaction *transaction;\n \n+\tif (!should_pack_refs(refs, opts))\n+\t\treturn 0;\n+\n \ttransaction = ref_store_transaction_begin(refs->packed_ref_store, &err);\n \tif (!transaction)\n \t\treturn -1;\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 7a0a695ca2f..07c57fd541a 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -1250,6 +1250,24 @@ int packed_refs_is_locked(struct ref_store *ref_store)\n \treturn is_lock_file_locked(&refs->lock);\n }\n \n+int packed_refs_size(struct ref_store *ref_store,\n+\t\t size_t *out)\n+{\n+\tstruct packed_ref_store *refs = packed_downcast(ref_store, REF_STORE_READ,\n+\t\t\t\t\t\t\t\"packed_refs_size\");\n+\tstruct stat st;\n+\n+\tif (stat(refs->path, &st) < 0) {\n+\t\tif (errno != ENOENT)\n+\t\t\treturn -1;\n+\t\t*out = 0;\n+\t\treturn 0;\n+\t}\n+\n+\t*out = st.st_size;\n+\treturn 0;\n+}\n+\n /*\n * The packed-refs header line that we write out. Perhaps other traits\n * will be added later.\ndiff --git a/refs/packed-backend.h b/refs/packed-backend.h\nindex 09437ad13bd..9481d5e7c2e 100644\n--- a/refs/packed-backend.h\n+++ b/refs/packed-backend.h\n@@ -27,6 +27,13 @@ int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)\n void packed_refs_unlock(struct ref_store *ref_store);\n int packed_refs_is_locked(struct ref_store *ref_store);\n \n+/*\n+ * Obtain the size of the `packed-refs` file. Reports `0` as size in case there\n+ * is no packed-refs file. Returns 0 on success, negative otherwise.\n+ */\n+int packed_refs_size(struct ref_store *ref_store,\n+\t\t size_t *out);\n+\n /*\n * Return true if `transaction` really needs to be carried out against\n * the specified packed_ref_store, or false if it can be skipped\ndiff --git a/t/t0601-reffiles-pack-refs.sh b/t/t0601-reffiles-pack-refs.sh\nindex ed9652bb829..d8cbd3f202b 100755\n--- a/t/t0601-reffiles-pack-refs.sh\n+++ b/t/t0601-reffiles-pack-refs.sh\n@@ -362,21 +362,86 @@ test_expect_success 'pack-refs does not drop broken refs during deletion' '\n \n for command in \"git pack-refs --all --auto\" \"git maintenance run --task=pack-refs --auto\"\n do\n-\ttest_expect_success \"$command unconditionally packs loose refs\" '\n+\ttest_expect_success \"$command does not repack below 16 refs without packed-refs\" '\n \t\ttest_when_finished \"rm -rf repo\" &&\n \t\tgit init repo &&\n \t\t(\n \t\t\tcd repo &&\n \t\t\tgit config set maintenance.auto false &&\n-\t\t\ttest_commit initial &&\n-\n-\t\t\tgit update-ref refs/heads/something HEAD &&\n-\t\t\ttest_path_is_file .git/refs/heads/something &&\n-\t\t\tgit rev-parse refs/heads/something >expect &&\n-\t\t\t$command &&\n-\t\t\ttest_path_is_missing .git/refs/heads/something &&\n-\t\t\tgit rev-parse refs/heads/something >actual &&\n-\t\t\ttest_cmp expect actual\n+\t\t\tgit commit --allow-empty --message \"initial\" &&\n+\n+\t\t\t# Create 14 additional references, which brings us to\n+\t\t\t# 15 together with the default branch.\n+\t\t\tprintf \"create refs/heads/loose-%d HEAD\\n\" $(test_seq 14) >stdin &&\n+\t\t\tgit update-ref --stdin stdin &&\n+\t\t\tgit update-ref --stdin stdin &&\n+\t\t\tgit update-ref --stdin stdin &&\n+\t\t\tgit update-ref --stdin stdin &&\n+\t\t\tgit update-ref --stdin writes:\n\n> Introduce a heuristic that decides whether or not it is worth to pack\n> loose references. The important factors to decide here are the number of\n> loose references in comparison to the overall size of the \"packed-refs\"\n> file. The bigger the \"packed-refs\" file, the longer it takes to rewrite\n> it and thus we scale up the limit of allowed loose references before we\n> repack.\n>\n> As is the nature of heuristics, this mechansim isn't obviously\n> \"correct\", but should rather be seen as a tradeoff between how much\n> resources we spend packing refs and how inefficient the ref store\n> becomes. For all I can say, we have successfully been using the exact\n> same heuristic in Gitaly for several years by now.\n\nThis seems to hit the balance between the thoroughness of repack\n(leaving fewer loose refs is good) and the frequencey (doing repack\nless often is good) in a quite sensible way.\n\nI also have to wonder if it adds a good component to the heuristics\nto leave younger loose refs (wrt mtime) out of packed-refs, with the\nexpectation that they are more likely to be updated again soon than\nrefs that were written long time ago and stayed the same value.\n\nThanks.\n"},{"id":"502148","messageId":"xmqqzfonbdkq.fsf@gitster.g","threadId":"62038","inReplyTo":"ZtgPSGMD0ZV3S0Nn@pks.im","subject":"Re: [PATCH 2/2] refs/files: use heuristic to decide whether to repack with `--auto`","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-09-04T16:15:01Z","receivedAt":"2024-09-04T16:15:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Patrick Steinhardt writes:\n\n> In any case, GCC is clever enough to notice what we're doing:\n>\n> fastlog2(unsigned long):\n> xor eax, eax\n> test rdi, rdi\n> je .L5\n> bsr rax, rdi\n> .L5:\n> ret\n\nNice. Aiming to compile to \"bsr\" is very good.\n\n> So with the following definition we're optimizing both with GCC and\n> Clang:\n>\n> size_t fastlog2(size_t sz)\n> {\n> size_t l = 0;\n> if (!sz)\n> return 0;\n> for (; sz; sz >>= 1)\n> l++;\n> return l;\n> }\n>\n> I'd thus say we can just pick that function instead of caring about\n> platform endianess with `ffs()`.\n\nThe above loop that compilers seem to know to reduce to \"bsr\" is\ngood.\n\nFWIW, because the definition of \"first bit\" in ffs() is \"least\nsignificant bit\", you do not need to worry about endianness at all,\nbut what we want is most significant, so it is not directly usable.\n"},{"id":"502200","messageId":"CAOLa=ZRQW0sUXEVSs8weK-jke7a2rUmG=Bw5q4yZvtFP4wvQKw@mail.gmail.com","threadId":"62038","inReplyTo":"ZtgfIPOZO1p4_ExF@pks.im","subject":"Re: [PATCH 2/2] refs/files: use heuristic to decide whether to repack with `--auto`","fromName":"karthik nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2024-09-05T08:44:03Z","receivedAt":"2024-09-05T08:44:05Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Patrick Steinhardt writes:\n\n> On Tue, Sep 03, 2024 at 02:00:16AM -0700, karthik nayak wrote:\n>> Patrick Steinhardt writes:\n>>\n>> > The `--auto` flag for git-pack-refs(1) allows the ref backend to decide\n>> > whether or not a repack is in order. This switch has been introduced\n>> > mostly with the \"reftable\" backend in mind, which already knows to\n>> > auto-compact its tables during normal operations. When the flag is set,\n>> > then it will use the same auto-compaction mechanism and thus end up\n>> > doing nothing in most cases.\n>> >\n>> > The \"files\" backend does not have any such heuristic yet and instead\n>>\n>> Nit: s/instead/will instead/\n>>\n>> > packs any loose references unconditionally. So we rewrite the complete\n>> > \"packed-refs\" file even if there's only a single loose reference to be\n>> > packed.\n>\n> Revisiting this: isn't the current version of this sentence correct?\n> Replacing it with \"will instead\" certainly makes it incorrect without\n> also changing \"packs\" to \"pack\".\n>\n> Patrick\n\nYou're right, I did missread.\n"},{"id":"502206","messageId":"ZtmAvvSJC2fMoXSz@pks.im","threadId":"62038","inReplyTo":"xmqqmskncugz.fsf@gitster.g","subject":"Re: [PATCH v2 3/3] refs/files: use heuristic to decide whether to repack with `--auto`","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2024-09-05T09:58:22Z","receivedAt":"2024-09-05T09:58:29Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Wed, Sep 04, 2024 at 08:24:44AM -0700, Junio C Hamano wrote:\n> Patrick Steinhardt writes:\n> \n> > Introduce a heuristic that decides whether or not it is worth to pack\n> > loose references. The important factors to decide here are the number of\n> > loose references in comparison to the overall size of the \"packed-refs\"\n> > file. The bigger the \"packed-refs\" file, the longer it takes to rewrite\n> > it and thus we scale up the limit of allowed loose references before we\n> > repack.\n> >\n> > As is the nature of heuristics, this mechansim isn't obviously\n> > \"correct\", but should rather be seen as a tradeoff between how much\n> > resources we spend packing refs and how inefficient the ref store\n> > becomes. For all I can say, we have successfully been using the exact\n> > same heuristic in Gitaly for several years by now.\n> \n> This seems to hit the balance between the thoroughness of repack\n> (leaving fewer loose refs is good) and the frequencey (doing repack\n> less often is good) in a quite sensible way.\n> \n> I also have to wonder if it adds a good component to the heuristics\n> to leave younger loose refs (wrt mtime) out of packed-refs, with the\n> expectation that they are more likely to be updated again soon than\n> refs that were written long time ago and stayed the same value.\n\nMaybe.\n\nIn general, I expect that most users typically only touch a very small\nset of refs, e.g. the four or five feature branches that they have. So\neven without such an additional component we would not end up repacking\nall that often.\n\nThat picture changes once you consider remotes, because with bigger\nteams it's quite likely that you'll get many ref updates there. I'm not\nsure a time-based heuristic would be a good fit for this usecase,\nbecause I'd think that repacking those right away is sensible most of\nthe time.\n\nWe also have to consider that an mtime-based component makes the overall\nsystem harder to understand and indeterministic. Which isn't to say that\nit doesn't make sense. But I rather think we should land the simple and\nstupid solution first, and in case we see that it's insufficient we can\niterate and improve it in the future.\n\nPatrick\n"}]}