{"thread":{"id":"63235","subject":"[PATCH 0/2] bundle: fix non-linear performance scaling with refs","startedAt":"2025-04-01T17:01:05Z","lastAt":"2025-04-10T09:04:49Z","messageCount":10,"participants":["Karthik Nayak","Toon Claes"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"515454","messageId":"20250401-488-generating-bundles-with-many-references-has-non-linear-performance-v1-0-6d23b2d96557@gmail.com","threadId":"63235","inReplyTo":null,"subject":"[PATCH 0/2] bundle: fix non-linear performance scaling with refs","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2025-04-01T17:00:55Z","receivedAt":"2025-04-01T17:01:05Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Hello, \n\nAt GitLab, we noticed that bundle creation doesn't seem to scale linearly \nthe number of references in a repository. The following benchmark demostrates\nthe issue:\n\nBenchmark 1: bundle (refcount = 100)\n  Time (mean ± σ):       4.4 ms ±   0.5 ms    [User: 1.8 ms, System: 2.4 ms]\n  Range (min … max):     3.4 ms …   7.7 ms    434 runs\n\nBenchmark 2: bundle (refcount = 1000)\n  Time (mean ± σ):      16.5 ms ±   1.7 ms    [User: 9.6 ms, System: 7.2 ms]\n  Range (min … max):    14.1 ms …  21.7 ms    176 runs\n\nBenchmark 3: bundle (refcount = 10000)\n  Time (mean ± σ):     220.6 ms ±   3.2 ms    [User: 171.6 ms, System: 55.7 ms]\n  Range (min … max):   215.8 ms … 224.9 ms    13 runs\n\nBenchmark 4: bundle (refcount = 100000)\n  Time (mean ± σ):      9.622 s ±  0.063 s    [User: 9.143 s, System: 0.546 s]\n  Range (min … max):    9.563 s …  9.738 s    10 runs\n\nSummary\n  bundle (refcount = 100) ran\n    3.79 ± 0.61 times faster than bundle (refcount = 1000)\n   50.63 ± 6.39 times faster than bundle (refcount = 10000)\n 2207.95 ± 277.35 times faster than bundle (refcount = 100000)\n\nDigging into this, the reason for this is because we check for duplicate refnames\nadded by the user. But this check uses an O(N^2) algorithm, which would not \nscale linearly with the number of refs.\n\nThe first commit in this small series adds a bunch of tests for this behavior,\nwhile also discovering a missed edge case. The second commit introduces an \nalternative approach which uses an 'strset' to check for duplicates. The new\napproach fixes the performance problems noticed while also fixing the earlier\nmissed edge case. Overall we see a 6x performance improvement with this series.\n\nI found that there is a conflict with 'ps/object-wo-the-repository' in seen,\nthe resolution seems simple enough. Happy to support as needed.\n\n---\n bundle.c               | 10 +++++++++-\n object.c               | 33 -------------------------------\n object.h               |  6 ------\n t/t6020-bundle-misc.sh | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 62 insertions(+), 40 deletions(-)\n\nKarthik Nayak (2):\n      t6020: test for duplicate refnames in bundle creation\n      bundle: fix non-linear performance scaling with refs\n---\n\n\n\n---\n\nbase-commit: 683c54c999c301c2cd6f715c411407c413b1d84e\nchange-id: 20250322-488-generating-bundles-with-many-references-has-non-linear-performance-64aec8e0cf1d\n\nThanks\n- Karthik\n\n"},{"id":"515455","messageId":"20250401-488-generating-bundles-with-many-references-has-non-linear-performance-v1-1-6d23b2d96557@gmail.com","threadId":"63235","inReplyTo":"20250401-488-generating-bundles-with-many-references-has-non-linear-performance-v1-0-6d23b2d96557@gmail.com","subject":"[PATCH 1/2] t6020: test for duplicate refnames in bundle creation","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2025-04-01T17:00:56Z","receivedAt":"2025-04-01T17:01:06Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"The commit b2a6d1c686 (bundle: allow the same ref to be given more than\nonce, 2009-01-17) added functionality to detect and remove duplicate\nrefnames from being added during bundle creation. This ensured that\nclones created from such bundles wouldn't barf about duplicate refnames.\n\nThe following commit will add some optimizations to make this check\nfaster, but before doing that, it would be optimal to add tests to\ncapture the current behavior.\n\nAdd tests to capture duplicate refnames provided by the user during\nbundle creation. This can be a combination of:\n\n  - refnames directly provided by the user.\n  - refname duplicate by using the '--all' flag alongside manual\n    references being provided.\n  - exclusion criteria provided via a refname \"main^!\".\n  - short forms of refnames provided, \"main\" vs \"refs/heads/main\".\n\nNote that currently duplicates due to usage of short and long forms goes\nundetected. This should be fixed with the optimizations made in the next\ncommit.\n\nSigned-off-by: Karthik Nayak <karthik.188@gmail.com>\n---\n t/t6020-bundle-misc.sh | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 57 insertions(+)\n\ndiff --git a/t/t6020-bundle-misc.sh b/t/t6020-bundle-misc.sh\nindex b3807e8f35..dd09df1287 100755\n--- a/t/t6020-bundle-misc.sh\n+++ b/t/t6020-bundle-misc.sh\n@@ -673,6 +673,63 @@ test_expect_success 'bundle progress with --no-quiet' '\n \tgrep \"%\" err\n '\n \n+test_expect_success 'create bundle with duplicate refnames' '\n+\tgit bundle create out.bdl \"main\" \"main\" &&\n+\n+\tgit bundle list-heads out.bdl |\n+\t\tmake_user_friendly_and_stable_output >actual &&\n+\tcat >expect <<-\\EOF &&\n+\t<COMMIT-P> refs/heads/main\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n+# This exhibits a bug, since the same refname is now added to the bundle twice.\n+test_expect_success 'create bundle with duplicate refnames and --all' '\n+\tgit bundle create out.bdl --all \"main\" \"main\" &&\n+\n+\tgit bundle list-heads out.bdl |\n+\t\tmake_user_friendly_and_stable_output >actual &&\n+\tcat >expect <<-\\EOF &&\n+\t<COMMIT-P> refs/heads/main\n+\t<COMMIT-N> refs/heads/release\n+\t<COMMIT-D> refs/heads/topic/1\n+\t<COMMIT-H> refs/heads/topic/2\n+\t<COMMIT-D> refs/pull/1/head\n+\t<COMMIT-G> refs/pull/2/head\n+\t<TAG-1> refs/tags/v1\n+\t<TAG-2> refs/tags/v2\n+\t<TAG-3> refs/tags/v3\n+\t<COMMIT-P> HEAD\n+\t<COMMIT-P> refs/heads/main\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'create bundle with duplicate exlusion refnames' '\n+\tgit bundle create out.bdl \"main\" \"main^!\" &&\n+\n+\tgit bundle list-heads out.bdl |\n+\t\tmake_user_friendly_and_stable_output >actual &&\n+\tcat >expect <<-\\EOF &&\n+\t<COMMIT-P> refs/heads/main\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n+# This exhibits a bug, since the same refname is now added to the bundle twice.\n+test_expect_success 'create bundle with duplicate refname short-form' '\n+\tgit bundle create out.bdl \"main\" \"main\" \"refs/heads/main\" \"refs/heads/main\" &&\n+\n+\tgit bundle list-heads out.bdl |\n+\t\tmake_user_friendly_and_stable_output >actual &&\n+\tcat >expect <<-\\EOF &&\n+\t<COMMIT-P> refs/heads/main\n+\t<COMMIT-P> refs/heads/main\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success 'read bundle over stdin' '\n \tgit bundle create some.bundle HEAD &&\n \n\n-- \n2.48.1\n\n"},{"id":"515456","messageId":"20250401-488-generating-bundles-with-many-references-has-non-linear-performance-v1-2-6d23b2d96557@gmail.com","threadId":"63235","inReplyTo":"20250401-488-generating-bundles-with-many-references-has-non-linear-performance-v1-0-6d23b2d96557@gmail.com","subject":"[PATCH 2/2] bundle: fix non-linear performance scaling with refs","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2025-04-01T17:00:57Z","receivedAt":"2025-04-01T17:01:07Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"The 'git bundle create' command has non-linear performance with the\nnumber of refs in the repository. Benchmarking the command shows that\na large portion of the time (~75%) is spent in the\n`object_array_remove_duplicates()` function.\n\nThe `object_array_remove_duplicates()` function was added in\nb2a6d1c686 (bundle: allow the same ref to be given more than once,\n2009-01-17) to skip duplicate refs provided by the user from being\nwritten to the bundle. Since this is an O(N^2) algorithm, in repos with\nlarge number of references, this can take up a large amount of time.\n\nLet's instead use a 'strset' to skip duplicates inside\n`write_bundle_refs()`. This improves the performance by around 6 times\nwhen tested against in repository with 100000 refs:\n\nBenchmark 1: bundle (refcount = 100000, revision = master)\n  Time (mean ± σ):     14.653 s ±  0.203 s    [User: 13.940 s, System: 0.762 s]\n  Range (min … max):   14.237 s … 14.920 s    10 runs\n\nBenchmark 2: bundle (refcount = 100000, revision = HEAD)\n  Time (mean ± σ):      2.394 s ±  0.023 s    [User: 1.684 s, System: 0.798 s]\n  Range (min … max):    2.364 s …  2.425 s    10 runs\n\nSummary\n  bundle (refcount = 100000, revision = HEAD) ran\n    6.12 ± 0.10 times faster than bundle (refcount = 100000, revision = master)\n\nPreviously, `object_array_remove_duplicates()` ensured that both the\nrefname and the object it pointed to were checked for duplicates. The\nnew approach, implemented within `write_bundle_refs()`, eliminates\nduplicate refnames without comparing the objects they reference. This\nworks because, for bundle creation, we only need to prevent duplicate\nrefs from being written to the bundle header. The `revs->pending` array\ncan contain duplicates of multiple types.\n\nFirst, references which resolve to the same refname. For e.g. \"git\nbundle create out.bdl master master\" or \"git bundle create out.bdl\nrefs/heads/master refs/heads/master\" or \"git bundle create out.bdl\nmaster refs/heads/master\". In these scenarios we want to prevent writing\n\"refs/heads/master\" twice to the bundle header. Since both the refnames\nhere would point to the same object (unless there is a race), we do not\nneed to check equality of the object.\n\nSecond, refnames which are duplicates but do not point to the same\nobject. This can happen when we use an exclusion criteria. For e.g. \"git\nbundle create out.bdl master master^!\", Here `revs->pending` would\ncontain two elements, both with refname set to \"master\". However, each\nof them would be pointing to an INTERESTING and UNINTERESTING object\nrespectively. Since we only write refnames with INTERESTING objects to\nthe bundle header, we perform our duplicate checks only on such objects.\n\nSigned-off-by: Karthik Nayak <karthik.188@gmail.com>\n---\n bundle.c               | 10 +++++++++-\n object.c               | 33 ---------------------------------\n object.h               |  6 ------\n t/t6020-bundle-misc.sh |  4 ----\n 4 files changed, 9 insertions(+), 44 deletions(-)\n\ndiff --git a/bundle.c b/bundle.c\nindex d7ad690843..30cfba0be2 100644\n--- a/bundle.c\n+++ b/bundle.c\n@@ -384,6 +384,9 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n {\n \tint i;\n \tint ref_count = 0;\n+\tstruct strset objects;\n+\n+\tstrset_init(&objects);\n \n \tfor (i = 0; i < revs->pending.nr; i++) {\n \t\tstruct object_array_entry *e = revs->pending.objects + i;\n@@ -401,6 +404,9 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n \t\t\tflag = 0;\n \t\tdisplay_ref = (flag & REF_ISSYMREF) ? e->name : ref;\n \n+\t\tif (strset_contains(&objects, display_ref))\n+\t\t\tgoto skip_write_ref;\n+\n \t\tif (e->item->type == OBJ_TAG &&\n \t\t\t\t!is_tag_in_date_range(e->item, revs)) {\n \t\t\te->item->flags |= UNINTERESTING;\n@@ -423,6 +429,7 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n \t\t}\n \n \t\tref_count++;\n+\t\tstrset_add(&objects, display_ref);\n \t\twrite_or_die(bundle_fd, oid_to_hex(&e->item->oid), the_hash_algo->hexsz);\n \t\twrite_or_die(bundle_fd, \" \", 1);\n \t\twrite_or_die(bundle_fd, display_ref, strlen(display_ref));\n@@ -431,6 +438,8 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n \t\tfree(ref);\n \t}\n \n+\tstrset_clear(&objects);\n+\n \t/* end header */\n \twrite_or_die(bundle_fd, \"\\n\", 1);\n \treturn ref_count;\n@@ -566,7 +575,6 @@ int create_bundle(struct repository *r, const char *path,\n \t */\n \trevs.blob_objects = revs.tree_objects = 0;\n \ttraverse_commit_list(&revs, write_bundle_prerequisites, NULL, &bpi);\n-\tobject_array_remove_duplicates(&revs_copy.pending);\n \n \t/* write bundle refs */\n \tref_count = write_bundle_refs(bundle_fd, &revs_copy);\ndiff --git a/object.c b/object.c\nindex 100bf9b8d1..a2c5986178 100644\n--- a/object.c\n+++ b/object.c\n@@ -491,39 +491,6 @@ void object_array_clear(struct object_array *array)\n \tarray->nr = array->alloc = 0;\n }\n \n-/*\n- * Return true if array already contains an entry.\n- */\n-static int contains_object(struct object_array *array,\n-\t\t\t   const struct object *item, const char *name)\n-{\n-\tunsigned nr = array->nr, i;\n-\tstruct object_array_entry *object = array->objects;\n-\n-\tfor (i = 0; i < nr; i++, object++)\n-\t\tif (item == object->item && !strcmp(object->name, name))\n-\t\t\treturn 1;\n-\treturn 0;\n-}\n-\n-void object_array_remove_duplicates(struct object_array *array)\n-{\n-\tunsigned nr = array->nr, src;\n-\tstruct object_array_entry *objects = array->objects;\n-\n-\tarray->nr = 0;\n-\tfor (src = 0; src < nr; src++) {\n-\t\tif (!contains_object(array, objects[src].item,\n-\t\t\t\t     objects[src].name)) {\n-\t\t\tif (src != array->nr)\n-\t\t\t\tobjects[array->nr] = objects[src];\n-\t\t\tarray->nr++;\n-\t\t} else {\n-\t\t\tobject_array_release_entry(&objects[src]);\n-\t\t}\n-\t}\n-}\n-\n void clear_object_flags(unsigned flags)\n {\n \tint i;\ndiff --git a/object.h b/object.h\nindex 17f32f1103..0e12c75922 100644\n--- a/object.h\n+++ b/object.h\n@@ -324,12 +324,6 @@ typedef int (*object_array_each_func_t)(struct object_array_entry *, void *);\n void object_array_filter(struct object_array *array,\n \t\t\t object_array_each_func_t want, void *cb_data);\n \n-/*\n- * Remove from array all but the first entry with a given name.\n- * Warning: this function uses an O(N^2) algorithm.\n- */\n-void object_array_remove_duplicates(struct object_array *array);\n-\n /*\n  * Remove any objects from the array, freeing all used memory; afterwards\n  * the array is ready to store more objects with add_object_array().\ndiff --git a/t/t6020-bundle-misc.sh b/t/t6020-bundle-misc.sh\nindex dd09df1287..500c81b8a1 100755\n--- a/t/t6020-bundle-misc.sh\n+++ b/t/t6020-bundle-misc.sh\n@@ -684,7 +684,6 @@ test_expect_success 'create bundle with duplicate refnames' '\n \ttest_cmp expect actual\n '\n \n-# This exhibits a bug, since the same refname is now added to the bundle twice.\n test_expect_success 'create bundle with duplicate refnames and --all' '\n \tgit bundle create out.bdl --all \"main\" \"main\" &&\n \n@@ -701,7 +700,6 @@ test_expect_success 'create bundle with duplicate refnames and --all' '\n \t<TAG-2> refs/tags/v2\n \t<TAG-3> refs/tags/v3\n \t<COMMIT-P> HEAD\n-\t<COMMIT-P> refs/heads/main\n \tEOF\n \ttest_cmp expect actual\n '\n@@ -717,7 +715,6 @@ test_expect_success 'create bundle with duplicate exlusion refnames' '\n \ttest_cmp expect actual\n '\n \n-# This exhibits a bug, since the same refname is now added to the bundle twice.\n test_expect_success 'create bundle with duplicate refname short-form' '\n \tgit bundle create out.bdl \"main\" \"main\" \"refs/heads/main\" \"refs/heads/main\" &&\n \n@@ -725,7 +722,6 @@ test_expect_success 'create bundle with duplicate refname short-form' '\n \t\tmake_user_friendly_and_stable_output >actual &&\n \tcat >expect <<-\\EOF &&\n \t<COMMIT-P> refs/heads/main\n-\t<COMMIT-P> refs/heads/main\n \tEOF\n \ttest_cmp expect actual\n '\n\n-- \n2.48.1\n\n"},{"id":"515604","messageId":"874iz5f4i4.fsf@iotcl.com","threadId":"63235","inReplyTo":"20250401-488-generating-bundles-with-many-references-has-non-linear-performance-v1-2-6d23b2d96557@gmail.com","subject":"Re: [PATCH 2/2] bundle: fix non-linear performance scaling with refs","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-04-03T19:07:31Z","receivedAt":"2025-04-03T19:07:46Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Karthik Nayak <karthik.188@gmail.com> writes:\n\n> The 'git bundle create' command has non-linear performance with the\n> number of refs in the repository. Benchmarking the command shows that\n> a large portion of the time (~75%) is spent in the\n> `object_array_remove_duplicates()` function.\n>\n> The `object_array_remove_duplicates()` function was added in\n> b2a6d1c686 (bundle: allow the same ref to be given more than once,\n> 2009-01-17) to skip duplicate refs provided by the user from being\n> written to the bundle. Since this is an O(N^2) algorithm, in repos with\n> large number of references, this can take up a large amount of time.\n>\n> Let's instead use a 'strset' to skip duplicates inside\n> `write_bundle_refs()`. This improves the performance by around 6 times\n> when tested against in repository with 100000 refs:\n>\n> Benchmark 1: bundle (refcount = 100000, revision = master)\n>   Time (mean ± σ):     14.653 s ±  0.203 s    [User: 13.940 s, System: 0.762 s]\n>   Range (min … max):   14.237 s … 14.920 s    10 runs\n>\n> Benchmark 2: bundle (refcount = 100000, revision = HEAD)\n>   Time (mean ± σ):      2.394 s ±  0.023 s    [User: 1.684 s, System: 0.798 s]\n>   Range (min … max):    2.364 s …  2.425 s    10 runs\n>\n> Summary\n>   bundle (refcount = 100000, revision = HEAD) ran\n>     6.12 ± 0.10 times faster than bundle (refcount = 100000, revision = master)\n\nThat's a good find!\n\n> Previously, `object_array_remove_duplicates()` ensured that both the\n> refname and the object it pointed to were checked for duplicates. The\n> new approach, implemented within `write_bundle_refs()`, eliminates\n> duplicate refnames without comparing the objects they reference. This\n> works because, for bundle creation, we only need to prevent duplicate\n> refs from being written to the bundle header. The `revs->pending` array\n> can contain duplicates of multiple types.\n\nMakes sense to me.\n\n> First, references which resolve to the same refname. For e.g. \"git\n> bundle create out.bdl master master\" or \"git bundle create out.bdl\n> refs/heads/master refs/heads/master\" or \"git bundle create out.bdl\n> master refs/heads/master\". In these scenarios we want to prevent writing\n> \"refs/heads/master\" twice to the bundle header. Since both the refnames\n> here would point to the same object (unless there is a race), we do not\n> need to check equality of the object.\n\nYeah, we can never be sure about the changes that happen while the\nbundle is being created. I fixed another race[1] recently which also was\ncomparing equality of the object, that causes the ref to be omitted. We\ncan only act by \"best effort\" and having the ref point to /some/ object\nis the best we can do.\n\n[1]: https://lore.kernel.org/git/20241211-fix-bundle-create-race-v3-1-0587f6f9db1b@iotcl.com/\n\n> Second, refnames which are duplicates but do not point to the same\n> object. This can happen when we use an exclusion criteria. For e.g. \"git\n> bundle create out.bdl master master^!\", Here `revs->pending` would\n> contain two elements, both with refname set to \"master\". However, each\n> of them would be pointing to an INTERESTING and UNINTERESTING object\n> respectively. Since we only write refnames with INTERESTING objects to\n> the bundle header, we perform our duplicate checks only on such\n> objects.\n\nThanks for that context, I didn't consider that.\n\n> Signed-off-by: Karthik Nayak <karthik.188@gmail.com>\n> ---\n>  bundle.c               | 10 +++++++++-\n>  object.c               | 33 ---------------------------------\n>  object.h               |  6 ------\n>  t/t6020-bundle-misc.sh |  4 ----\n>  4 files changed, 9 insertions(+), 44 deletions(-)\n>\n> diff --git a/bundle.c b/bundle.c\n> index d7ad690843..30cfba0be2 100644\n> --- a/bundle.c\n> +++ b/bundle.c\n> @@ -384,6 +384,9 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n>  {\n>  \tint i;\n>  \tint ref_count = 0;\n> +\tstruct strset objects;\n> +\n> +\tstrset_init(&objects);\n\nAny reason why you're not using the `STRMAP_INIT` macro?\n\n>  \n>  \tfor (i = 0; i < revs->pending.nr; i++) {\n>  \t\tstruct object_array_entry *e = revs->pending.objects + i;\n> @@ -401,6 +404,9 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n>  \t\t\tflag = 0;\n>  \t\tdisplay_ref = (flag & REF_ISSYMREF) ? e->name : ref;\n>  \n> +\t\tif (strset_contains(&objects, display_ref))\n> +\t\t\tgoto skip_write_ref;\n> +\n>  \t\tif (e->item->type == OBJ_TAG &&\n>  \t\t\t\t!is_tag_in_date_range(e->item, revs)) {\n>  \t\t\te->item->flags |= UNINTERESTING;\n> @@ -423,6 +429,7 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n>  \t\t}\n>  \n>  \t\tref_count++;\n> +\t\tstrset_add(&objects, display_ref);\n>  \t\twrite_or_die(bundle_fd, oid_to_hex(&e->item->oid), the_hash_algo->hexsz);\n>  \t\twrite_or_die(bundle_fd, \" \", 1);\n>  \t\twrite_or_die(bundle_fd, display_ref, strlen(display_ref));\n> @@ -431,6 +438,8 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n>  \t\tfree(ref);\n>  \t}\n>  \n> +\tstrset_clear(&objects);\n> +\n>  \t/* end header */\n>  \twrite_or_die(bundle_fd, \"\\n\", 1);\n>  \treturn ref_count;\n> @@ -566,7 +575,6 @@ int create_bundle(struct repository *r, const char *path,\n>  \t */\n>  \trevs.blob_objects = revs.tree_objects = 0;\n>  \ttraverse_commit_list(&revs, write_bundle_prerequisites, NULL, &bpi);\n> -\tobject_array_remove_duplicates(&revs_copy.pending);\n>  \n>  \t/* write bundle refs */\n>  \tref_count = write_bundle_refs(bundle_fd, &revs_copy);\n> diff --git a/object.c b/object.c\n> index 100bf9b8d1..a2c5986178 100644\n> --- a/object.c\n> +++ b/object.c\n> @@ -491,39 +491,6 @@ void object_array_clear(struct object_array *array)\n>  \tarray->nr = array->alloc = 0;\n>  }\n>  \n> -/*\n> - * Return true if array already contains an entry.\n> - */\n> -static int contains_object(struct object_array *array,\n> -\t\t\t   const struct object *item, const char *name)\n> -{\n> -\tunsigned nr = array->nr, i;\n> -\tstruct object_array_entry *object = array->objects;\n> -\n> -\tfor (i = 0; i < nr; i++, object++)\n> -\t\tif (item == object->item && !strcmp(object->name, name))\n> -\t\t\treturn 1;\n> -\treturn 0;\n> -}\n> -\n> -void object_array_remove_duplicates(struct object_array *array)\n> -{\n> -\tunsigned nr = array->nr, src;\n> -\tstruct object_array_entry *objects = array->objects;\n> -\n> -\tarray->nr = 0;\n> -\tfor (src = 0; src < nr; src++) {\n> -\t\tif (!contains_object(array, objects[src].item,\n> -\t\t\t\t     objects[src].name)) {\n> -\t\t\tif (src != array->nr)\n> -\t\t\t\tobjects[array->nr] = objects[src];\n> -\t\t\tarray->nr++;\n> -\t\t} else {\n> -\t\t\tobject_array_release_entry(&objects[src]);\n> -\t\t}\n> -\t}\n> -}\n> -\n>  void clear_object_flags(unsigned flags)\n>  {\n>  \tint i;\n> diff --git a/object.h b/object.h\n> index 17f32f1103..0e12c75922 100644\n> --- a/object.h\n> +++ b/object.h\n> @@ -324,12 +324,6 @@ typedef int (*object_array_each_func_t)(struct object_array_entry *, void *);\n>  void object_array_filter(struct object_array *array,\n>  \t\t\t object_array_each_func_t want, void *cb_data);\n>  \n> -/*\n> - * Remove from array all but the first entry with a given name.\n> - * Warning: this function uses an O(N^2) algorithm.\n\nFunny this has been here for more than 10 years. Thanks for this cleanup.\n\n> - */\n> -void object_array_remove_duplicates(struct object_array *array);\n> -\n>  /*\n>   * Remove any objects from the array, freeing all used memory; afterwards\n>   * the array is ready to store more objects with add_object_array().\n> diff --git a/t/t6020-bundle-misc.sh b/t/t6020-bundle-misc.sh\n> index dd09df1287..500c81b8a1 100755\n> --- a/t/t6020-bundle-misc.sh\n> +++ b/t/t6020-bundle-misc.sh\n> @@ -684,7 +684,6 @@ test_expect_success 'create bundle with duplicate refnames' '\n>  \ttest_cmp expect actual\n>  '\n>  \n> -# This exhibits a bug, since the same refname is now added to the bundle twice.\n>  test_expect_success 'create bundle with duplicate refnames and --all' '\n>  \tgit bundle create out.bdl --all \"main\" \"main\" &&\n>  \n> @@ -701,7 +700,6 @@ test_expect_success 'create bundle with duplicate refnames and --all' '\n>  \t<TAG-2> refs/tags/v2\n>  \t<TAG-3> refs/tags/v3\n>  \t<COMMIT-P> HEAD\n> -\t<COMMIT-P> refs/heads/main\n>  \tEOF\n>  \ttest_cmp expect actual\n>  '\n> @@ -717,7 +715,6 @@ test_expect_success 'create bundle with duplicate exlusion refnames' '\n>  \ttest_cmp expect actual\n>  '\n>  \n> -# This exhibits a bug, since the same refname is now added to the bundle twice.\n>  test_expect_success 'create bundle with duplicate refname short-form' '\n>  \tgit bundle create out.bdl \"main\" \"main\" \"refs/heads/main\" \"refs/heads/main\" &&\n>  \n> @@ -725,7 +722,6 @@ test_expect_success 'create bundle with duplicate refname short-form' '\n>  \t\tmake_user_friendly_and_stable_output >actual &&\n>  \tcat >expect <<-\\EOF &&\n>  \t<COMMIT-P> refs/heads/main\n> -\t<COMMIT-P> refs/heads/main\n>  \tEOF\n>  \ttest_cmp expect actual\n>  '\n\nGreat work on the alternative implmentation. And thanks for adding these\ntests and actually fixing them. I've been manually testing a few more\nedge cases, I couldn't find any other scenario that's not covered by the\ncurrent implementation.\n\nI approve.\n\n--\nToon\n"},{"id":"515738","messageId":"CAOLa=ZRKP=g5vN9O+9-UfP8j1KNTQgj1we2qYkQe+3Z3uy3dQQ@mail.gmail.com","threadId":"63235","inReplyTo":"874iz5f4i4.fsf@iotcl.com","subject":"Re: [PATCH 2/2] bundle: fix non-linear performance scaling with refs","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2025-04-06T20:48:40Z","receivedAt":"2025-04-06T20:48:41Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Toon Claes <toon@iotcl.com> writes:\n\n> Karthik Nayak <karthik.188@gmail.com> writes:\n>\n>> The 'git bundle create' command has non-linear performance with the\n>> number of refs in the repository. Benchmarking the command shows that\n>> a large portion of the time (~75%) is spent in the\n>> `object_array_remove_duplicates()` function.\n>>\n>> The `object_array_remove_duplicates()` function was added in\n>> b2a6d1c686 (bundle: allow the same ref to be given more than once,\n>> 2009-01-17) to skip duplicate refs provided by the user from being\n>> written to the bundle. Since this is an O(N^2) algorithm, in repos with\n>> large number of references, this can take up a large amount of time.\n>>\n>> Let's instead use a 'strset' to skip duplicates inside\n>> `write_bundle_refs()`. This improves the performance by around 6 times\n>> when tested against in repository with 100000 refs:\n>>\n>> Benchmark 1: bundle (refcount = 100000, revision = master)\n>>   Time (mean ± σ):     14.653 s ±  0.203 s    [User: 13.940 s, System: 0.762 s]\n>>   Range (min … max):   14.237 s … 14.920 s    10 runs\n>>\n>> Benchmark 2: bundle (refcount = 100000, revision = HEAD)\n>>   Time (mean ± σ):      2.394 s ±  0.023 s    [User: 1.684 s, System: 0.798 s]\n>>   Range (min … max):    2.364 s …  2.425 s    10 runs\n>>\n>> Summary\n>>   bundle (refcount = 100000, revision = HEAD) ran\n>>     6.12 ± 0.10 times faster than bundle (refcount = 100000, revision = master)\n>\n> That's a good find!\n>\n>> Previously, `object_array_remove_duplicates()` ensured that both the\n>> refname and the object it pointed to were checked for duplicates. The\n>> new approach, implemented within `write_bundle_refs()`, eliminates\n>> duplicate refnames without comparing the objects they reference. This\n>> works because, for bundle creation, we only need to prevent duplicate\n>> refs from being written to the bundle header. The `revs->pending` array\n>> can contain duplicates of multiple types.\n>\n> Makes sense to me.\n>\n>> First, references which resolve to the same refname. For e.g. \"git\n>> bundle create out.bdl master master\" or \"git bundle create out.bdl\n>> refs/heads/master refs/heads/master\" or \"git bundle create out.bdl\n>> master refs/heads/master\". In these scenarios we want to prevent writing\n>> \"refs/heads/master\" twice to the bundle header. Since both the refnames\n>> here would point to the same object (unless there is a race), we do not\n>> need to check equality of the object.\n>\n> Yeah, we can never be sure about the changes that happen while the\n> bundle is being created. I fixed another race[1] recently which also was\n> comparing equality of the object, that causes the ref to be omitted. We\n> can only act by \"best effort\" and having the ref point to /some/ object\n> is the best we can do.\n>\n> [1]: https://lore.kernel.org/git/20241211-fix-bundle-create-race-v3-1-0587f6f9db1b@iotcl.com/\n>\n>> Second, refnames which are duplicates but do not point to the same\n>> object. This can happen when we use an exclusion criteria. For e.g. \"git\n>> bundle create out.bdl master master^!\", Here `revs->pending` would\n>> contain two elements, both with refname set to \"master\". However, each\n>> of them would be pointing to an INTERESTING and UNINTERESTING object\n>> respectively. Since we only write refnames with INTERESTING objects to\n>> the bundle header, we perform our duplicate checks only on such\n>> objects.\n>\n> Thanks for that context, I didn't consider that.\n>\n\nI didn't at first, but luckily we have a test for such refs, which got\ntripped and allowed me to consider that scenario too!\n\n>> Signed-off-by: Karthik Nayak <karthik.188@gmail.com>\n>> ---\n>>  bundle.c               | 10 +++++++++-\n>>  object.c               | 33 ---------------------------------\n>>  object.h               |  6 ------\n>>  t/t6020-bundle-misc.sh |  4 ----\n>>  4 files changed, 9 insertions(+), 44 deletions(-)\n>>\n>> diff --git a/bundle.c b/bundle.c\n>> index d7ad690843..30cfba0be2 100644\n>> --- a/bundle.c\n>> +++ b/bundle.c\n>> @@ -384,6 +384,9 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n>>  {\n>>  \tint i;\n>>  \tint ref_count = 0;\n>> +\tstruct strset objects;\n>> +\n>> +\tstrset_init(&objects);\n>\n> Any reason why you're not using the `STRMAP_INIT` macro?\n>\n\nNone. This should be the ideal way to do it, will change in the next\nversion.\n\n>>\n>>  \tfor (i = 0; i < revs->pending.nr; i++) {\n>>  \t\tstruct object_array_entry *e = revs->pending.objects + i;\n>> @@ -401,6 +404,9 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n>>  \t\t\tflag = 0;\n>>  \t\tdisplay_ref = (flag & REF_ISSYMREF) ? e->name : ref;\n>>\n>> +\t\tif (strset_contains(&objects, display_ref))\n>> +\t\t\tgoto skip_write_ref;\n>> +\n>>  \t\tif (e->item->type == OBJ_TAG &&\n>>  \t\t\t\t!is_tag_in_date_range(e->item, revs)) {\n>>  \t\t\te->item->flags |= UNINTERESTING;\n>> @@ -423,6 +429,7 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n>>  \t\t}\n>>\n>>  \t\tref_count++;\n>> +\t\tstrset_add(&objects, display_ref);\n>>  \t\twrite_or_die(bundle_fd, oid_to_hex(&e->item->oid), the_hash_algo->hexsz);\n>>  \t\twrite_or_die(bundle_fd, \" \", 1);\n>>  \t\twrite_or_die(bundle_fd, display_ref, strlen(display_ref));\n>> @@ -431,6 +438,8 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n>>  \t\tfree(ref);\n>>  \t}\n>>\n>> +\tstrset_clear(&objects);\n>> +\n>>  \t/* end header */\n>>  \twrite_or_die(bundle_fd, \"\\n\", 1);\n>>  \treturn ref_count;\n>> @@ -566,7 +575,6 @@ int create_bundle(struct repository *r, const char *path,\n>>  \t */\n>>  \trevs.blob_objects = revs.tree_objects = 0;\n>>  \ttraverse_commit_list(&revs, write_bundle_prerequisites, NULL, &bpi);\n>> -\tobject_array_remove_duplicates(&revs_copy.pending);\n>>\n>>  \t/* write bundle refs */\n>>  \tref_count = write_bundle_refs(bundle_fd, &revs_copy);\n>> diff --git a/object.c b/object.c\n>> index 100bf9b8d1..a2c5986178 100644\n>> --- a/object.c\n>> +++ b/object.c\n>> @@ -491,39 +491,6 @@ void object_array_clear(struct object_array *array)\n>>  \tarray->nr = array->alloc = 0;\n>>  }\n>>\n>> -/*\n>> - * Return true if array already contains an entry.\n>> - */\n>> -static int contains_object(struct object_array *array,\n>> -\t\t\t   const struct object *item, const char *name)\n>> -{\n>> -\tunsigned nr = array->nr, i;\n>> -\tstruct object_array_entry *object = array->objects;\n>> -\n>> -\tfor (i = 0; i < nr; i++, object++)\n>> -\t\tif (item == object->item && !strcmp(object->name, name))\n>> -\t\t\treturn 1;\n>> -\treturn 0;\n>> -}\n>> -\n>> -void object_array_remove_duplicates(struct object_array *array)\n>> -{\n>> -\tunsigned nr = array->nr, src;\n>> -\tstruct object_array_entry *objects = array->objects;\n>> -\n>> -\tarray->nr = 0;\n>> -\tfor (src = 0; src < nr; src++) {\n>> -\t\tif (!contains_object(array, objects[src].item,\n>> -\t\t\t\t     objects[src].name)) {\n>> -\t\t\tif (src != array->nr)\n>> -\t\t\t\tobjects[array->nr] = objects[src];\n>> -\t\t\tarray->nr++;\n>> -\t\t} else {\n>> -\t\t\tobject_array_release_entry(&objects[src]);\n>> -\t\t}\n>> -\t}\n>> -}\n>> -\n>>  void clear_object_flags(unsigned flags)\n>>  {\n>>  \tint i;\n>> diff --git a/object.h b/object.h\n>> index 17f32f1103..0e12c75922 100644\n>> --- a/object.h\n>> +++ b/object.h\n>> @@ -324,12 +324,6 @@ typedef int (*object_array_each_func_t)(struct object_array_entry *, void *);\n>>  void object_array_filter(struct object_array *array,\n>>  \t\t\t object_array_each_func_t want, void *cb_data);\n>>\n>> -/*\n>> - * Remove from array all but the first entry with a given name.\n>> - * Warning: this function uses an O(N^2) algorithm.\n>\n> Funny this has been here for more than 10 years. Thanks for this cleanup.\n>\n>> - */\n>> -void object_array_remove_duplicates(struct object_array *array);\n>> -\n>>  /*\n>>   * Remove any objects from the array, freeing all used memory; afterwards\n>>   * the array is ready to store more objects with add_object_array().\n>> diff --git a/t/t6020-bundle-misc.sh b/t/t6020-bundle-misc.sh\n>> index dd09df1287..500c81b8a1 100755\n>> --- a/t/t6020-bundle-misc.sh\n>> +++ b/t/t6020-bundle-misc.sh\n>> @@ -684,7 +684,6 @@ test_expect_success 'create bundle with duplicate refnames' '\n>>  \ttest_cmp expect actual\n>>  '\n>>\n>> -# This exhibits a bug, since the same refname is now added to the bundle twice.\n>>  test_expect_success 'create bundle with duplicate refnames and --all' '\n>>  \tgit bundle create out.bdl --all \"main\" \"main\" &&\n>>\n>> @@ -701,7 +700,6 @@ test_expect_success 'create bundle with duplicate refnames and --all' '\n>>  \t<TAG-2> refs/tags/v2\n>>  \t<TAG-3> refs/tags/v3\n>>  \t<COMMIT-P> HEAD\n>> -\t<COMMIT-P> refs/heads/main\n>>  \tEOF\n>>  \ttest_cmp expect actual\n>>  '\n>> @@ -717,7 +715,6 @@ test_expect_success 'create bundle with duplicate exlusion refnames' '\n>>  \ttest_cmp expect actual\n>>  '\n>>\n>> -# This exhibits a bug, since the same refname is now added to the bundle twice.\n>>  test_expect_success 'create bundle with duplicate refname short-form' '\n>>  \tgit bundle create out.bdl \"main\" \"main\" \"refs/heads/main\" \"refs/heads/main\" &&\n>>\n>> @@ -725,7 +722,6 @@ test_expect_success 'create bundle with duplicate refname short-form' '\n>>  \t\tmake_user_friendly_and_stable_output >actual &&\n>>  \tcat >expect <<-\\EOF &&\n>>  \t<COMMIT-P> refs/heads/main\n>> -\t<COMMIT-P> refs/heads/main\n>>  \tEOF\n>>  \ttest_cmp expect actual\n>>  '\n>\n> Great work on the alternative implmentation. And thanks for adding these\n> tests and actually fixing them. I've been manually testing a few more\n> edge cases, I couldn't find any other scenario that's not covered by the\n> current implementation.\n>\n> I approve.\n>\n> --\n> Toon\n\nAppreciate you taking the time and exploring all scenarios. Thanks for\nthe review.\n\nKarthik\n"},{"id":"515844","messageId":"20250408-488-generating-bundles-with-many-references-has-non-linear-performance-v2-0-0802fc36a23d@gmail.com","threadId":"63235","inReplyTo":"20250401-488-generating-bundles-with-many-references-has-non-linear-performance-v1-0-6d23b2d96557@gmail.com","subject":"[PATCH v2 0/2] bundle: fix non-linear performance scaling with refs","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2025-04-08T09:00:51Z","receivedAt":"2025-04-08T09:00:57Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Hello, \n\nAt GitLab, we noticed that bundle creation doesn't seem to scale linearly \nthe number of references in a repository. The following benchmark demostrates\nthe issue:\n\nBenchmark 1: bundle (refcount = 100)\n  Time (mean ± σ):       4.4 ms ±   0.5 ms    [User: 1.8 ms, System: 2.4 ms]\n  Range (min … max):     3.4 ms …   7.7 ms    434 runs\n\nBenchmark 2: bundle (refcount = 1000)\n  Time (mean ± σ):      16.5 ms ±   1.7 ms    [User: 9.6 ms, System: 7.2 ms]\n  Range (min … max):    14.1 ms …  21.7 ms    176 runs\n\nBenchmark 3: bundle (refcount = 10000)\n  Time (mean ± σ):     220.6 ms ±   3.2 ms    [User: 171.6 ms, System: 55.7 ms]\n  Range (min … max):   215.8 ms … 224.9 ms    13 runs\n\nBenchmark 4: bundle (refcount = 100000)\n  Time (mean ± σ):      9.622 s ±  0.063 s    [User: 9.143 s, System: 0.546 s]\n  Range (min … max):    9.563 s …  9.738 s    10 runs\n\nSummary\n  bundle (refcount = 100) ran\n    3.79 ± 0.61 times faster than bundle (refcount = 1000)\n   50.63 ± 6.39 times faster than bundle (refcount = 10000)\n 2207.95 ± 277.35 times faster than bundle (refcount = 100000)\n\nDigging into this, the reason for this is because we check for duplicate refnames\nadded by the user. But this check uses an O(N^2) algorithm, which would not \nscale linearly with the number of refs.\n\nThe first commit in this small series adds a bunch of tests for this behavior,\nwhile also discovering a missed edge case. The second commit introduces an \nalternative approach which uses an 'strset' to check for duplicates. The new\napproach fixes the performance problems noticed while also fixing the earlier\nmissed edge case. Overall we see a 6x performance improvement with this series.\n\nI found that there is a conflict with 'ps/object-wo-the-repository' in seen,\nthe resolution seems simple enough. Happy to support as needed.\n\n---\nChanges in v2:\n- Use STRSET_INIT macro instead of strset_init(). \n- Link to v1: https://lore.kernel.org/r/20250401-488-generating-bundles-with-many-references-has-non-linear-performance-v1-0-6d23b2d96557@gmail.com\n\n---\n bundle.c               |  8 +++++++-\n object.c               | 33 -------------------------------\n object.h               |  6 ------\n t/t6020-bundle-misc.sh | 53 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 60 insertions(+), 40 deletions(-)\n\nKarthik Nayak (2):\n      t6020: test for duplicate refnames in bundle creation\n      bundle: fix non-linear performance scaling with refs\n---\n\nRange-diff versus v1:\n\n1:  1fd141cd34 = 1:  2b608cb908 t6020: test for duplicate refnames in bundle creation\n2:  25b86d1a6c ! 2:  054389419f bundle: fix non-linear performance scaling with refs\n    @@ bundle.c: static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n      {\n      \tint i;\n      \tint ref_count = 0;\n    -+\tstruct strset objects;\n    -+\n    -+\tstrset_init(&objects);\n    ++\tstruct strset objects = STRSET_INIT;\n      \n      \tfor (i = 0; i < revs->pending.nr; i++) {\n      \t\tstruct object_array_entry *e = revs->pending.objects + i;\n\n\n---\n\nbase-commit: 683c54c999c301c2cd6f715c411407c413b1d84e\nchange-id: 20250322-488-generating-bundles-with-many-references-has-non-linear-performance-64aec8e0cf1d\n\nThanks\n- Karthik\n\n"},{"id":"515845","messageId":"20250408-488-generating-bundles-with-many-references-has-non-linear-performance-v2-1-0802fc36a23d@gmail.com","threadId":"63235","inReplyTo":"20250408-488-generating-bundles-with-many-references-has-non-linear-performance-v2-0-0802fc36a23d@gmail.com","subject":"[PATCH v2 1/2] t6020: test for duplicate refnames in bundle creation","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2025-04-08T09:00:52Z","receivedAt":"2025-04-08T09:00:58Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"The commit b2a6d1c686 (bundle: allow the same ref to be given more than\nonce, 2009-01-17) added functionality to detect and remove duplicate\nrefnames from being added during bundle creation. This ensured that\nclones created from such bundles wouldn't barf about duplicate refnames.\n\nThe following commit will add some optimizations to make this check\nfaster, but before doing that, it would be optimal to add tests to\ncapture the current behavior.\n\nAdd tests to capture duplicate refnames provided by the user during\nbundle creation. This can be a combination of:\n\n  - refnames directly provided by the user.\n  - refname duplicate by using the '--all' flag alongside manual\n    references being provided.\n  - exclusion criteria provided via a refname \"main^!\".\n  - short forms of refnames provided, \"main\" vs \"refs/heads/main\".\n\nNote that currently duplicates due to usage of short and long forms goes\nundetected. This should be fixed with the optimizations made in the next\ncommit.\n\nSigned-off-by: Karthik Nayak <karthik.188@gmail.com>\n---\n t/t6020-bundle-misc.sh | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 57 insertions(+)\n\ndiff --git a/t/t6020-bundle-misc.sh b/t/t6020-bundle-misc.sh\nindex b3807e8f35..dd09df1287 100755\n--- a/t/t6020-bundle-misc.sh\n+++ b/t/t6020-bundle-misc.sh\n@@ -673,6 +673,63 @@ test_expect_success 'bundle progress with --no-quiet' '\n \tgrep \"%\" err\n '\n \n+test_expect_success 'create bundle with duplicate refnames' '\n+\tgit bundle create out.bdl \"main\" \"main\" &&\n+\n+\tgit bundle list-heads out.bdl |\n+\t\tmake_user_friendly_and_stable_output >actual &&\n+\tcat >expect <<-\\EOF &&\n+\t<COMMIT-P> refs/heads/main\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n+# This exhibits a bug, since the same refname is now added to the bundle twice.\n+test_expect_success 'create bundle with duplicate refnames and --all' '\n+\tgit bundle create out.bdl --all \"main\" \"main\" &&\n+\n+\tgit bundle list-heads out.bdl |\n+\t\tmake_user_friendly_and_stable_output >actual &&\n+\tcat >expect <<-\\EOF &&\n+\t<COMMIT-P> refs/heads/main\n+\t<COMMIT-N> refs/heads/release\n+\t<COMMIT-D> refs/heads/topic/1\n+\t<COMMIT-H> refs/heads/topic/2\n+\t<COMMIT-D> refs/pull/1/head\n+\t<COMMIT-G> refs/pull/2/head\n+\t<TAG-1> refs/tags/v1\n+\t<TAG-2> refs/tags/v2\n+\t<TAG-3> refs/tags/v3\n+\t<COMMIT-P> HEAD\n+\t<COMMIT-P> refs/heads/main\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'create bundle with duplicate exlusion refnames' '\n+\tgit bundle create out.bdl \"main\" \"main^!\" &&\n+\n+\tgit bundle list-heads out.bdl |\n+\t\tmake_user_friendly_and_stable_output >actual &&\n+\tcat >expect <<-\\EOF &&\n+\t<COMMIT-P> refs/heads/main\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n+# This exhibits a bug, since the same refname is now added to the bundle twice.\n+test_expect_success 'create bundle with duplicate refname short-form' '\n+\tgit bundle create out.bdl \"main\" \"main\" \"refs/heads/main\" \"refs/heads/main\" &&\n+\n+\tgit bundle list-heads out.bdl |\n+\t\tmake_user_friendly_and_stable_output >actual &&\n+\tcat >expect <<-\\EOF &&\n+\t<COMMIT-P> refs/heads/main\n+\t<COMMIT-P> refs/heads/main\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success 'read bundle over stdin' '\n \tgit bundle create some.bundle HEAD &&\n \n\n-- \n2.48.1\n\n"},{"id":"515846","messageId":"20250408-488-generating-bundles-with-many-references-has-non-linear-performance-v2-2-0802fc36a23d@gmail.com","threadId":"63235","inReplyTo":"20250408-488-generating-bundles-with-many-references-has-non-linear-performance-v2-0-0802fc36a23d@gmail.com","subject":"[PATCH v2 2/2] bundle: fix non-linear performance scaling with refs","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2025-04-08T09:00:53Z","receivedAt":"2025-04-08T09:00:59Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"The 'git bundle create' command has non-linear performance with the\nnumber of refs in the repository. Benchmarking the command shows that\na large portion of the time (~75%) is spent in the\n`object_array_remove_duplicates()` function.\n\nThe `object_array_remove_duplicates()` function was added in\nb2a6d1c686 (bundle: allow the same ref to be given more than once,\n2009-01-17) to skip duplicate refs provided by the user from being\nwritten to the bundle. Since this is an O(N^2) algorithm, in repos with\nlarge number of references, this can take up a large amount of time.\n\nLet's instead use a 'strset' to skip duplicates inside\n`write_bundle_refs()`. This improves the performance by around 6 times\nwhen tested against in repository with 100000 refs:\n\nBenchmark 1: bundle (refcount = 100000, revision = master)\n  Time (mean ± σ):     14.653 s ±  0.203 s    [User: 13.940 s, System: 0.762 s]\n  Range (min … max):   14.237 s … 14.920 s    10 runs\n\nBenchmark 2: bundle (refcount = 100000, revision = HEAD)\n  Time (mean ± σ):      2.394 s ±  0.023 s    [User: 1.684 s, System: 0.798 s]\n  Range (min … max):    2.364 s …  2.425 s    10 runs\n\nSummary\n  bundle (refcount = 100000, revision = HEAD) ran\n    6.12 ± 0.10 times faster than bundle (refcount = 100000, revision = master)\n\nPreviously, `object_array_remove_duplicates()` ensured that both the\nrefname and the object it pointed to were checked for duplicates. The\nnew approach, implemented within `write_bundle_refs()`, eliminates\nduplicate refnames without comparing the objects they reference. This\nworks because, for bundle creation, we only need to prevent duplicate\nrefs from being written to the bundle header. The `revs->pending` array\ncan contain duplicates of multiple types.\n\nFirst, references which resolve to the same refname. For e.g. \"git\nbundle create out.bdl master master\" or \"git bundle create out.bdl\nrefs/heads/master refs/heads/master\" or \"git bundle create out.bdl\nmaster refs/heads/master\". In these scenarios we want to prevent writing\n\"refs/heads/master\" twice to the bundle header. Since both the refnames\nhere would point to the same object (unless there is a race), we do not\nneed to check equality of the object.\n\nSecond, refnames which are duplicates but do not point to the same\nobject. This can happen when we use an exclusion criteria. For e.g. \"git\nbundle create out.bdl master master^!\", Here `revs->pending` would\ncontain two elements, both with refname set to \"master\". However, each\nof them would be pointing to an INTERESTING and UNINTERESTING object\nrespectively. Since we only write refnames with INTERESTING objects to\nthe bundle header, we perform our duplicate checks only on such objects.\n\nSigned-off-by: Karthik Nayak <karthik.188@gmail.com>\n---\n bundle.c               |  8 +++++++-\n object.c               | 33 ---------------------------------\n object.h               |  6 ------\n t/t6020-bundle-misc.sh |  4 ----\n 4 files changed, 7 insertions(+), 44 deletions(-)\n\ndiff --git a/bundle.c b/bundle.c\nindex d7ad690843..0614426e20 100644\n--- a/bundle.c\n+++ b/bundle.c\n@@ -384,6 +384,7 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n {\n \tint i;\n \tint ref_count = 0;\n+\tstruct strset objects = STRSET_INIT;\n \n \tfor (i = 0; i < revs->pending.nr; i++) {\n \t\tstruct object_array_entry *e = revs->pending.objects + i;\n@@ -401,6 +402,9 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n \t\t\tflag = 0;\n \t\tdisplay_ref = (flag & REF_ISSYMREF) ? e->name : ref;\n \n+\t\tif (strset_contains(&objects, display_ref))\n+\t\t\tgoto skip_write_ref;\n+\n \t\tif (e->item->type == OBJ_TAG &&\n \t\t\t\t!is_tag_in_date_range(e->item, revs)) {\n \t\t\te->item->flags |= UNINTERESTING;\n@@ -423,6 +427,7 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n \t\t}\n \n \t\tref_count++;\n+\t\tstrset_add(&objects, display_ref);\n \t\twrite_or_die(bundle_fd, oid_to_hex(&e->item->oid), the_hash_algo->hexsz);\n \t\twrite_or_die(bundle_fd, \" \", 1);\n \t\twrite_or_die(bundle_fd, display_ref, strlen(display_ref));\n@@ -431,6 +436,8 @@ static int write_bundle_refs(int bundle_fd, struct rev_info *revs)\n \t\tfree(ref);\n \t}\n \n+\tstrset_clear(&objects);\n+\n \t/* end header */\n \twrite_or_die(bundle_fd, \"\\n\", 1);\n \treturn ref_count;\n@@ -566,7 +573,6 @@ int create_bundle(struct repository *r, const char *path,\n \t */\n \trevs.blob_objects = revs.tree_objects = 0;\n \ttraverse_commit_list(&revs, write_bundle_prerequisites, NULL, &bpi);\n-\tobject_array_remove_duplicates(&revs_copy.pending);\n \n \t/* write bundle refs */\n \tref_count = write_bundle_refs(bundle_fd, &revs_copy);\ndiff --git a/object.c b/object.c\nindex 100bf9b8d1..a2c5986178 100644\n--- a/object.c\n+++ b/object.c\n@@ -491,39 +491,6 @@ void object_array_clear(struct object_array *array)\n \tarray->nr = array->alloc = 0;\n }\n \n-/*\n- * Return true if array already contains an entry.\n- */\n-static int contains_object(struct object_array *array,\n-\t\t\t   const struct object *item, const char *name)\n-{\n-\tunsigned nr = array->nr, i;\n-\tstruct object_array_entry *object = array->objects;\n-\n-\tfor (i = 0; i < nr; i++, object++)\n-\t\tif (item == object->item && !strcmp(object->name, name))\n-\t\t\treturn 1;\n-\treturn 0;\n-}\n-\n-void object_array_remove_duplicates(struct object_array *array)\n-{\n-\tunsigned nr = array->nr, src;\n-\tstruct object_array_entry *objects = array->objects;\n-\n-\tarray->nr = 0;\n-\tfor (src = 0; src < nr; src++) {\n-\t\tif (!contains_object(array, objects[src].item,\n-\t\t\t\t     objects[src].name)) {\n-\t\t\tif (src != array->nr)\n-\t\t\t\tobjects[array->nr] = objects[src];\n-\t\t\tarray->nr++;\n-\t\t} else {\n-\t\t\tobject_array_release_entry(&objects[src]);\n-\t\t}\n-\t}\n-}\n-\n void clear_object_flags(unsigned flags)\n {\n \tint i;\ndiff --git a/object.h b/object.h\nindex 17f32f1103..0e12c75922 100644\n--- a/object.h\n+++ b/object.h\n@@ -324,12 +324,6 @@ typedef int (*object_array_each_func_t)(struct object_array_entry *, void *);\n void object_array_filter(struct object_array *array,\n \t\t\t object_array_each_func_t want, void *cb_data);\n \n-/*\n- * Remove from array all but the first entry with a given name.\n- * Warning: this function uses an O(N^2) algorithm.\n- */\n-void object_array_remove_duplicates(struct object_array *array);\n-\n /*\n  * Remove any objects from the array, freeing all used memory; afterwards\n  * the array is ready to store more objects with add_object_array().\ndiff --git a/t/t6020-bundle-misc.sh b/t/t6020-bundle-misc.sh\nindex dd09df1287..500c81b8a1 100755\n--- a/t/t6020-bundle-misc.sh\n+++ b/t/t6020-bundle-misc.sh\n@@ -684,7 +684,6 @@ test_expect_success 'create bundle with duplicate refnames' '\n \ttest_cmp expect actual\n '\n \n-# This exhibits a bug, since the same refname is now added to the bundle twice.\n test_expect_success 'create bundle with duplicate refnames and --all' '\n \tgit bundle create out.bdl --all \"main\" \"main\" &&\n \n@@ -701,7 +700,6 @@ test_expect_success 'create bundle with duplicate refnames and --all' '\n \t<TAG-2> refs/tags/v2\n \t<TAG-3> refs/tags/v3\n \t<COMMIT-P> HEAD\n-\t<COMMIT-P> refs/heads/main\n \tEOF\n \ttest_cmp expect actual\n '\n@@ -717,7 +715,6 @@ test_expect_success 'create bundle with duplicate exlusion refnames' '\n \ttest_cmp expect actual\n '\n \n-# This exhibits a bug, since the same refname is now added to the bundle twice.\n test_expect_success 'create bundle with duplicate refname short-form' '\n \tgit bundle create out.bdl \"main\" \"main\" \"refs/heads/main\" \"refs/heads/main\" &&\n \n@@ -725,7 +722,6 @@ test_expect_success 'create bundle with duplicate refname short-form' '\n \t\tmake_user_friendly_and_stable_output >actual &&\n \tcat >expect <<-\\EOF &&\n \t<COMMIT-P> refs/heads/main\n-\t<COMMIT-P> refs/heads/main\n \tEOF\n \ttest_cmp expect actual\n '\n\n-- \n2.48.1\n\n"},{"id":"515942","messageId":"871pu0fl6u.fsf@iotcl.com","threadId":"63235","inReplyTo":"20250408-488-generating-bundles-with-many-references-has-non-linear-performance-v2-2-0802fc36a23d@gmail.com","subject":"Re: [PATCH v2 2/2] bundle: fix non-linear performance scaling with refs","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-04-10T08:57:29Z","receivedAt":"2025-04-10T08:57:44Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Karthik Nayak <karthik.188@gmail.com> writes:\n\n> The 'git bundle create' command has non-linear performance with the\n> number of refs in the repository. Benchmarking the command shows that\n> a large portion of the time (~75%) is spent in the\n> `object_array_remove_duplicates()` function.\n>\n> The `object_array_remove_duplicates()` function was added in\n> b2a6d1c686 (bundle: allow the same ref to be given more than once,\n> 2009-01-17) to skip duplicate refs provided by the user from being\n> written to the bundle. Since this is an O(N^2) algorithm, in repos with\n> large number of references, this can take up a large amount of time.\n>\n> Let's instead use a 'strset' to skip duplicates inside\n> `write_bundle_refs()`. This improves the performance by around 6 times\n> when tested against in repository with 100000 refs:\n>\n> Benchmark 1: bundle (refcount = 100000, revision = master)\n>   Time (mean ± σ):     14.653 s ±  0.203 s    [User: 13.940 s, System: 0.762 s]\n>   Range (min … max):   14.237 s … 14.920 s    10 runs\n>\n> Benchmark 2: bundle (refcount = 100000, revision = HEAD)\n>   Time (mean ± σ):      2.394 s ±  0.023 s    [User: 1.684 s, System: 0.798 s]\n>   Range (min … max):    2.364 s …  2.425 s    10 runs\n>\n> Summary\n>   bundle (refcount = 100000, revision = HEAD) ran\n>     6.12 ± 0.10 times faster than bundle (refcount = 100000, revision = master)\n\nI've done some benchmarking with some \"real life\" repositories, which\nonly have a couple of thousand refs and there the difference\n(expectedly) barely noticable. Which is good to know there also isn't\nany regression.\n\nThis version looks good to me, I approve.\n\n--\nToon\n"},{"id":"515943","messageId":"CAOLa=ZQUkv=QpzzOaxv8EUhaoTpQdTPO1fHT=-DY2vfVCK4NyA@mail.gmail.com","threadId":"63235","inReplyTo":"871pu0fl6u.fsf@iotcl.com","subject":"Re: [PATCH v2 2/2] bundle: fix non-linear performance scaling with refs","fromName":"Karthik Nayak","fromEmail":"karthik.188@gmail.com","sentAt":"2025-04-10T09:04:48Z","receivedAt":"2025-04-10T09:04:49Z","isPatch":true,"sender":{"key":"karthik.188@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1786334?v=4"},"body":"Toon Claes <toon@iotcl.com> writes:\n\n> Karthik Nayak <karthik.188@gmail.com> writes:\n>\n>> The 'git bundle create' command has non-linear performance with the\n>> number of refs in the repository. Benchmarking the command shows that\n>> a large portion of the time (~75%) is spent in the\n>> `object_array_remove_duplicates()` function.\n>>\n>> The `object_array_remove_duplicates()` function was added in\n>> b2a6d1c686 (bundle: allow the same ref to be given more than once,\n>> 2009-01-17) to skip duplicate refs provided by the user from being\n>> written to the bundle. Since this is an O(N^2) algorithm, in repos with\n>> large number of references, this can take up a large amount of time.\n>>\n>> Let's instead use a 'strset' to skip duplicates inside\n>> `write_bundle_refs()`. This improves the performance by around 6 times\n>> when tested against in repository with 100000 refs:\n>>\n>> Benchmark 1: bundle (refcount = 100000, revision = master)\n>>   Time (mean ± σ):     14.653 s ±  0.203 s    [User: 13.940 s, System: 0.762 s]\n>>   Range (min … max):   14.237 s … 14.920 s    10 runs\n>>\n>> Benchmark 2: bundle (refcount = 100000, revision = HEAD)\n>>   Time (mean ± σ):      2.394 s ±  0.023 s    [User: 1.684 s, System: 0.798 s]\n>>   Range (min … max):    2.364 s …  2.425 s    10 runs\n>>\n>> Summary\n>>   bundle (refcount = 100000, revision = HEAD) ran\n>>     6.12 ± 0.10 times faster than bundle (refcount = 100000, revision = master)\n>\n> I've done some benchmarking with some \"real life\" repositories, which\n> only have a couple of thousand refs and there the difference\n> (expectedly) barely noticable. Which is good to know there also isn't\n> any regression.\n>\n> This version looks good to me, I approve.\n>\n> --\n> Toon\n\nThanks Toon. That is good news. That is also what the earlier benchmarks\nshowed. For smaller repositories the difference becomes inconsequential,\nbut for large repos, this can take significant amount of time.\n"}]}