{"thread":{"id":"64804","subject":"[PATCH] sparse-checkout: optimize string_list construction","startedAt":"2026-01-14T19:28:20Z","lastAt":"2026-01-21T16:51:54Z","messageCount":28,"participants":["amisha","Jeff King","Amisha Chhajed","Junio C Hamano","René Scharfe","Derrick Stolee","Pushkar Singh"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"533867","messageId":"20260114192803.4852-1-amishhhaaaa@gmail.com","threadId":"64804","inReplyTo":null,"subject":"[PATCH] sparse-checkout: optimize string_list construction","fromName":"amisha","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-14T19:28:03Z","receivedAt":"2026-01-14T19:28:20Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list' by constructing it unsorted and sorting it afterwards.\n\nSigned-off-by: amisha <amishhhaaaa@gmail.com>\n---\nNote for reviewers:\nI identified this as a strong candidate for optimization because we are \npulling entries from a hashmap. Since hashmaps inherently guarantee \nuniqueness of keys, using string_list_append() is safe here.\n\n builtin/sparse-checkout.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 15d51e60a8..0a44808ed2 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -91,7 +91,7 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n \n \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n \t\t\t/* pe->pattern starts with \"/\", skip it */\n-\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n+\t\t\tstring_list_append(&sl, pe->pattern + 1);\n \t\t}\n \n \t\tstring_list_sort(&sl);\n-- \n2.51.0\n\n"},{"id":"533896","messageId":"20260114213551.GC1010080@coredump.intra.peff.net","threadId":"64804","inReplyTo":"20260114192803.4852-1-amishhhaaaa@gmail.com","subject":"Re: [PATCH] sparse-checkout: optimize string_list construction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-01-14T21:35:51Z","receivedAt":"2026-01-14T21:35:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 15, 2026 at 12:58:03AM +0530, amisha wrote:\n\n> Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list' by constructing it unsorted and sorting it afterwards.\n> \n> Signed-off-by: amisha <amishhhaaaa@gmail.com>\n\nThanks, I think the patch is an obvious improvement. In general, please\nwrap your lines to something more reasonable (usually 70 or so is\ncommon). And make sure your sign-off identity matches the DCO section of\nDocumentation/SubmittingPatches, in particular this part:\n\n  Please use a known identity in the `Signed-off-by` trailer, since we cannot\n  accept anonymous contributions. It is common, but not required, to use some form\n  of your real name. We realize that some contributors are not comfortable doing\n  so or prefer to contribute under a pseudonym or preferred name and we can accept\n  your patch either way, as long as the name and email you use are distinctive,\n  identifying, and not misleading.\n  \n  The goal of this policy is to allow us to have sufficient information to contact\n  you if questions arise about your contribution.\n\nI think what you have is probably sufficient, but if you are not opposed\nto giving more identity information, we do usually prefer more full\nnames.\n\n> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\n> index 15d51e60a8..0a44808ed2 100644\n> --- a/builtin/sparse-checkout.c\n> +++ b/builtin/sparse-checkout.c\n> @@ -91,7 +91,7 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n>  \n>  \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n>  \t\t\t/* pe->pattern starts with \"/\", skip it */\n> -\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n> +\t\t\tstring_list_append(&sl, pe->pattern + 1);\n>  \t\t}\n>  \n>  \t\tstring_list_sort(&sl);\n\nSince we already sort here, I was quite curious how this came about.  It\nlooks like the _insert() call and the _sort() were both added together\nin de11951b03 (sparse-checkout: list directories in cone mode,\n2019-12-30).\n\nI'd guess it was just a typo/brain-o to mix up append and insert.\n\nDoesn't the same issue exist in write_cone_to_file(), too (in two\nseparate spots)?\n\n-Peff\n"},{"id":"533950","messageId":"20260115125637.90345-1-amishhhaaaa@gmail.com","threadId":"64804","inReplyTo":"20260114192803.4852-1-amishhhaaaa@gmail.com","subject":"[PATCH v2] sparse-checkout: optimize string_list construction","fromName":"amisha","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-15T12:56:37Z","receivedAt":"2026-01-15T12:56:52Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list' by constructing it unsorted and sorting it afterwards.\n\nSigned-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n---\n builtin/sparse-checkout.c | 8 +++-----\n 1 file changed, 3 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 15d51e60a8..edabe7cbd9 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -91,7 +91,7 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n \n \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n \t\t\t/* pe->pattern starts with \"/\", skip it */\n-\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n+\t\t\tstring_list_append(&sl, pe->pattern + 1);\n \t\t}\n \n \t\tstring_list_sort(&sl);\n@@ -289,11 +289,10 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstring_list_sort(&sl);\n-\tstring_list_remove_duplicates(&sl, 0);\n \n \tfprintf(fp, \"/*\\n!/*/\\n\");\n \n@@ -311,13 +310,12 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstrbuf_release(&parent_pattern);\n \n \tstring_list_sort(&sl);\n-\tstring_list_remove_duplicates(&sl, 0);\n \n \tfor (i = 0; i < sl.nr; i++) {\n \t\tchar *pattern = escaped_pattern(sl.items[i].string);\n-- \n2.51.0\n\n"},{"id":"533951","messageId":"20260115130935.93526-1-amishhhaaaa@gmail.com","threadId":"64804","inReplyTo":"20260114192803.4852-1-amishhhaaaa@gmail.com","subject":"[PATCH v3] sparse-checkout: optimize string_list construction","fromName":"amisha","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-15T13:09:35Z","receivedAt":"2026-01-15T13:09:45Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list'\nby constructing it unsorted and sorting it afterwards.\n\nSigned-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n---\n builtin/sparse-checkout.c | 8 +++-----\n 1 file changed, 3 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 15d51e60a8..edabe7cbd9 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -91,7 +91,7 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n \n \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n \t\t\t/* pe->pattern starts with \"/\", skip it */\n-\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n+\t\t\tstring_list_append(&sl, pe->pattern + 1);\n \t\t}\n \n \t\tstring_list_sort(&sl);\n@@ -289,11 +289,10 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstring_list_sort(&sl);\n-\tstring_list_remove_duplicates(&sl, 0);\n \n \tfprintf(fp, \"/*\\n!/*/\\n\");\n \n@@ -311,13 +310,12 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstrbuf_release(&parent_pattern);\n \n \tstring_list_sort(&sl);\n-\tstring_list_remove_duplicates(&sl, 0);\n \n \tfor (i = 0; i < sl.nr; i++) {\n \t\tchar *pattern = escaped_pattern(sl.items[i].string);\n-- \n2.51.0\n\n"},{"id":"533952","messageId":"CAPvEtreX9sGHUn7+Y0kLo_VnK7Y=OYLq-kz-+np3bu1QtoEpnA@mail.gmail.com","threadId":"64804","inReplyTo":"20260115130935.93526-1-amishhhaaaa@gmail.com","subject":"Re: [PATCH v3] sparse-checkout: optimize string_list construction","fromName":"Amisha Chhajed","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-15T13:15:35Z","receivedAt":"2026-01-15T13:15:47Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"Made the changes for other 2 places as well!\n\nI was also very curious about the presence of\nstring_list_remove_duplicates in the original code, from my\nunderstanding string_list_insert already removed duplicates and\nstring_list_remove_duplicates was still present with it.\n\n\nOn Thu, 15 Jan 2026 at 18:39, amisha <amishhhaaaa@gmail.com> wrote:\n>\n> Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list'\n> by constructing it unsorted and sorting it afterwards.\n>\n> Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n> ---\n>  builtin/sparse-checkout.c | 8 +++-----\n>  1 file changed, 3 insertions(+), 5 deletions(-)\n>\n> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\n> index 15d51e60a8..edabe7cbd9 100644\n> --- a/builtin/sparse-checkout.c\n> +++ b/builtin/sparse-checkout.c\n> @@ -91,7 +91,7 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n>\n>                 hashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n>                         /* pe->pattern starts with \"/\", skip it */\n> -                       string_list_insert(&sl, pe->pattern + 1);\n> +                       string_list_append(&sl, pe->pattern + 1);\n>                 }\n>\n>                 string_list_sort(&sl);\n> @@ -289,11 +289,10 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n>                 if (!hashmap_contains_parent(&pl->recursive_hashmap,\n>                                              pe->pattern,\n>                                              &parent_pattern))\n> -                       string_list_insert(&sl, pe->pattern);\n> +                       string_list_append(&sl, pe->pattern);\n>         }\n>\n>         string_list_sort(&sl);\n> -       string_list_remove_duplicates(&sl, 0);\n>\n>         fprintf(fp, \"/*\\n!/*/\\n\");\n>\n> @@ -311,13 +310,12 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n>                 if (!hashmap_contains_parent(&pl->recursive_hashmap,\n>                                              pe->pattern,\n>                                              &parent_pattern))\n> -                       string_list_insert(&sl, pe->pattern);\n> +                       string_list_append(&sl, pe->pattern);\n>         }\n>\n>         strbuf_release(&parent_pattern);\n>\n>         string_list_sort(&sl);\n> -       string_list_remove_duplicates(&sl, 0);\n>\n>         for (i = 0; i < sl.nr; i++) {\n>                 char *pattern = escaped_pattern(sl.items[i].string);\n> --\n> 2.51.0\n>\n"},{"id":"533958","messageId":"xmqqtswnc75t.fsf@gitster.g","threadId":"64804","inReplyTo":"20260115130935.93526-1-amishhhaaaa@gmail.com","subject":"Re: [PATCH v3] sparse-checkout: optimize string_list construction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-01-15T13:55:10Z","receivedAt":"2026-01-15T13:55:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"amisha <amishhhaaaa@gmail.com> writes:\n\n> Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list'\n> by constructing it unsorted and sorting it afterwards.\n>\n> Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n> ---\n\nBecause your e-mail client claims that the messages is from \"amisha\n<amishhhaaaa@gmail.com>\" in its \"From:\" header line, you'd need to\ninsert an extra \"in-body header\" line, which is separate by a blank\nline from the rest of the message body, to override it as the first\nline in the message, making the body of the message begin like this.\n\n    From: Amisha Chhajed <amishhhaaaa@gmail.com>\n\n    Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list'\n    by constructing it unsorted and sorting it afterwards.\n\n    Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n\nI've tweaked the message I retrieved from the mailing list before\napplying, so no need to resend this message, but in your future\ncontributions please keep this in mind.\n\nThanks.\n\n"},{"id":"533982","messageId":"20260115200903.GB1053259@coredump.intra.peff.net","threadId":"64804","inReplyTo":"CAPvEtreX9sGHUn7+Y0kLo_VnK7Y=OYLq-kz-+np3bu1QtoEpnA@mail.gmail.com","subject":"Re: [PATCH v3] sparse-checkout: optimize string_list construction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-01-15T20:09:03Z","receivedAt":"2026-01-15T20:09:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jan 15, 2026 at 06:45:35PM +0530, Amisha Chhajed wrote:\n\n> I was also very curious about the presence of\n> string_list_remove_duplicates in the original code, from my\n> understanding string_list_insert already removed duplicates and\n> string_list_remove_duplicates was still present with it.\n\nYes, I don't think you could have duplicates when inserting with\nstring_list_insert(). Of course your patch removes that, which means\nwe're falling back on the notion that the hashmap cannot have\nduplicates, either.\n\nI think our hashmap _does_ allow duplicate entries, though. The\ninsertion code in insert_recursive_pattern() avoids duplicates in\nparent_hashmap, but adds its arguments directly to recursive_hashmap.\n\nSo I think you could get duplicates with something like:\n\n  git init\n  git sparse-checkout set --cone\n  git sparse-checkout add --stdin <<\\EOF\n  foo\n  bar\n  foo\n  EOF\n\nBefore your patch, that produces this .git/info/sparse-checkout file:\n\n  /*\n  !/*/\n  /bar/\n  /foo/\n\nand after we get:\n\n  /*\n  !/*/\n  /bar/\n  /foo/\n  /foo/\n\nSo I think we do want to retain the duplicate suppression. Switching\nfrom insert() to append() is still good, as long as we keep the\nremove_duplicates() lines.\n\n-Peff\n"},{"id":"533998","messageId":"fc14e0e5-93bc-4805-a20d-d2aa4eb87ddb@web.de","threadId":"64804","inReplyTo":"CAPvEtreX9sGHUn7+Y0kLo_VnK7Y=OYLq-kz-+np3bu1QtoEpnA@mail.gmail.com","subject":"Re: [PATCH v3] sparse-checkout: optimize string_list construction","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2026-01-15T22:26:49Z","receivedAt":"2026-01-15T22:27:00Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"On 1/15/26 2:15 PM, Amisha Chhajed wrote:\n> Made the changes for other 2 places as well!\n> \n> I was also very curious about the presence of\n> string_list_remove_duplicates in the original code, from my\n> understanding string_list_insert already removed duplicates and\n> string_list_remove_duplicates was still present with it.\n\nSo the string_list_remove_duplicates() calls were unnecessary with\nstring_list_insert(), but why is it safe to remove them now that you use\nstring_list_append() instead, which doesn't check for duplicates?\n\n> \n> On Thu, 15 Jan 2026 at 18:39, amisha <amishhhaaaa@gmail.com> wrote:\n>>\n>> Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list'\n>> by constructing it unsorted and sorting it afterwards.\n>>\n>> Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n>> ---\n>>  builtin/sparse-checkout.c | 8 +++-----\n>>  1 file changed, 3 insertions(+), 5 deletions(-)\n>>\n>> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\n>> index 15d51e60a8..edabe7cbd9 100644\n>> --- a/builtin/sparse-checkout.c\n>> +++ b/builtin/sparse-checkout.c\n>> @@ -91,7 +91,7 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n>>\n>>                 hashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n>>                         /* pe->pattern starts with \"/\", skip it */\n>> -                       string_list_insert(&sl, pe->pattern + 1);\n>> +                       string_list_append(&sl, pe->pattern + 1);\n>>                 }\n>>\n>>                 string_list_sort(&sl);\n>> @@ -289,11 +289,10 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n>>                 if (!hashmap_contains_parent(&pl->recursive_hashmap,\n>>                                              pe->pattern,\n>>                                              &parent_pattern))\n>> -                       string_list_insert(&sl, pe->pattern);\n>> +                       string_list_append(&sl, pe->pattern);\n>>         }\n>>\n>>         string_list_sort(&sl);\n>> -       string_list_remove_duplicates(&sl, 0);\n>>\n>>         fprintf(fp, \"/*\\n!/*/\\n\");\n>>\n>> @@ -311,13 +310,12 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n>>                 if (!hashmap_contains_parent(&pl->recursive_hashmap,\n>>                                              pe->pattern,\n>>                                              &parent_pattern))\n>> -                       string_list_insert(&sl, pe->pattern);\n>> +                       string_list_append(&sl, pe->pattern);\n>>         }\n>>\n>>         strbuf_release(&parent_pattern);\n>>\n>>         string_list_sort(&sl);\n>> -       string_list_remove_duplicates(&sl, 0);\n>>\n>>         for (i = 0; i < sl.nr; i++) {\n>>                 char *pattern = escaped_pattern(sl.items[i].string);\n>> --\n>> 2.51.0\n>>\n\n"},{"id":"534022","messageId":"CAPvEtrdQ7LB4p0_yCg+ef6fsWSHwxA8C1uX0SJbfnV3vfQHD_g@mail.gmail.com","threadId":"64804","inReplyTo":"fc14e0e5-93bc-4805-a20d-d2aa4eb87ddb@web.de","subject":"Re: [PATCH v3] sparse-checkout: optimize string_list construction","fromName":"Amisha Chhajed","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-16T08:30:31Z","receivedAt":"2026-01-16T08:30:44Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"It was assumed to be safe under the notion that our entries are not\nduplicate but as already pointed out, our entries are not unique so we\nneed one of those two ways either insert or remove_duplicates, this\ncan be a trivial question but i wonder how are the tests passing by\nremoving these lines, i was actually researching about it.\n\nOn Fri, 16 Jan 2026 at 03:56, René Scharfe <l.s.r@web.de> wrote:\n>\n> On 1/15/26 2:15 PM, Amisha Chhajed wrote:\n> > Made the changes for other 2 places as well!\n> >\n> > I was also very curious about the presence of\n> > string_list_remove_duplicates in the original code, from my\n> > understanding string_list_insert already removed duplicates and\n> > string_list_remove_duplicates was still present with it.\n>\n> So the string_list_remove_duplicates() calls were unnecessary with\n> string_list_insert(), but why is it safe to remove them now that you use\n> string_list_append() instead, which doesn't check for duplicates?\n>\n> >\n> > On Thu, 15 Jan 2026 at 18:39, amisha <amishhhaaaa@gmail.com> wrote:\n> >>\n> >> Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list'\n> >> by constructing it unsorted and sorting it afterwards.\n> >>\n> >> Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n> >> ---\n> >>  builtin/sparse-checkout.c | 8 +++-----\n> >>  1 file changed, 3 insertions(+), 5 deletions(-)\n> >>\n> >> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\n> >> index 15d51e60a8..edabe7cbd9 100644\n> >> --- a/builtin/sparse-checkout.c\n> >> +++ b/builtin/sparse-checkout.c\n> >> @@ -91,7 +91,7 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n> >>\n> >>                 hashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n> >>                         /* pe->pattern starts with \"/\", skip it */\n> >> -                       string_list_insert(&sl, pe->pattern + 1);\n> >> +                       string_list_append(&sl, pe->pattern + 1);\n> >>                 }\n> >>\n> >>                 string_list_sort(&sl);\n> >> @@ -289,11 +289,10 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n> >>                 if (!hashmap_contains_parent(&pl->recursive_hashmap,\n> >>                                              pe->pattern,\n> >>                                              &parent_pattern))\n> >> -                       string_list_insert(&sl, pe->pattern);\n> >> +                       string_list_append(&sl, pe->pattern);\n> >>         }\n> >>\n> >>         string_list_sort(&sl);\n> >> -       string_list_remove_duplicates(&sl, 0);\n> >>\n> >>         fprintf(fp, \"/*\\n!/*/\\n\");\n> >>\n> >> @@ -311,13 +310,12 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n> >>                 if (!hashmap_contains_parent(&pl->recursive_hashmap,\n> >>                                              pe->pattern,\n> >>                                              &parent_pattern))\n> >> -                       string_list_insert(&sl, pe->pattern);\n> >> +                       string_list_append(&sl, pe->pattern);\n> >>         }\n> >>\n> >>         strbuf_release(&parent_pattern);\n> >>\n> >>         string_list_sort(&sl);\n> >> -       string_list_remove_duplicates(&sl, 0);\n> >>\n> >>         for (i = 0; i < sl.nr; i++) {\n> >>                 char *pattern = escaped_pattern(sl.items[i].string);\n> >> --\n> >> 2.51.0\n> >>\n>\n"},{"id":"534056","messageId":"20260116165003.95314-1-amishhhaaaa@gmail.com","threadId":"64804","inReplyTo":"20260114192803.4852-1-amishhhaaaa@gmail.com","subject":"[PATCH] sparse-checkout: optimize string_list construction","fromName":"amisha","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-16T16:50:03Z","receivedAt":"2026-01-16T16:50:18Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"From: Amisha Chhajed <amishhhaaaa@gmail.com>\n\nImprove O(n^2) complexity to O(n log n) while building a sorted\n'string_list' by constructing it unsorted then sorting it\nfollowed by removing duplicates.\n\nSigned-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n---\n builtin/sparse-checkout.c | 7 ++++---\n 1 file changed, 4 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 15d51e60a8..7dfb276bf0 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n \n \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n \t\t\t/* pe->pattern starts with \"/\", skip it */\n-\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n+\t\t\tstring_list_append(&sl, pe->pattern + 1);\n \t\t}\n \n \t\tstring_list_sort(&sl);\n+\t\tstring_list_remove_duplicates(&sl, 0);\n \n \t\tfor (i = 0; i < sl.nr; i++) {\n \t\t\tquote_c_style(sl.items[i].string, NULL, stdout, 0);\n@@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstring_list_sort(&sl);\n@@ -311,7 +312,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstrbuf_release(&parent_pattern);\n-- \n2.51.0\n\n"},{"id":"534058","messageId":"CAPvEtrc4KuQhNhc966=bbMQUZw1Ne1eoG68mVoZiG6A3h4t=GQ@mail.gmail.com","threadId":"64804","inReplyTo":"20260115200903.GB1053259@coredump.intra.peff.net","subject":"Re: [PATCH v3] sparse-checkout: optimize string_list construction","fromName":"Amisha Chhajed","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-16T17:03:18Z","receivedAt":"2026-01-16T17:03:31Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"I was able to reproduce this, are we open to a patch adding a test\nthat checks if duplicate entries are present in stdin the result\nshould not have it? because the tests were passing even after removing\nall duplicates checks, and non duplicates enforcement is a part of the\nmethod's behaviour, if I am understanding correctly.\n\nOn Fri, 16 Jan 2026 at 01:39, Jeff King <peff@peff.net> wrote:\n>\n> On Thu, Jan 15, 2026 at 06:45:35PM +0530, Amisha Chhajed wrote:\n>\n> > I was also very curious about the presence of\n> > string_list_remove_duplicates in the original code, from my\n> > understanding string_list_insert already removed duplicates and\n> > string_list_remove_duplicates was still present with it.\n>\n> Yes, I don't think you could have duplicates when inserting with\n> string_list_insert(). Of course your patch removes that, which means\n> we're falling back on the notion that the hashmap cannot have\n> duplicates, either.\n>\n> I think our hashmap _does_ allow duplicate entries, though. The\n> insertion code in insert_recursive_pattern() avoids duplicates in\n> parent_hashmap, but adds its arguments directly to recursive_hashmap.\n>\n> So I think you could get duplicates with something like:\n>\n>   git init\n>   git sparse-checkout set --cone\n>   git sparse-checkout add --stdin <<\\EOF\n>   foo\n>   bar\n>   foo\n>   EOF\n>\n> Before your patch, that produces this .git/info/sparse-checkout file:\n>\n>   /*\n>   !/*/\n>   /bar/\n>   /foo/\n>\n> and after we get:\n>\n>   /*\n>   !/*/\n>   /bar/\n>   /foo/\n>   /foo/\n>\n> So I think we do want to retain the duplicate suppression. Switching\n> from insert() to append() is still good, as long as we keep the\n> remove_duplicates() lines.\n>\n> -Peff\n"},{"id":"534061","messageId":"xmqqy0lx8ojt.fsf@gitster.g","threadId":"64804","inReplyTo":"CAPvEtrdQ7LB4p0_yCg+ef6fsWSHwxA8C1uX0SJbfnV3vfQHD_g@mail.gmail.com","subject":"Re: [PATCH v3] sparse-checkout: optimize string_list construction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-01-16T17:17:42Z","receivedAt":"2026-01-16T17:17:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Amisha Chhajed <amishhhaaaa@gmail.com> writes:\n\n> It was assumed to be safe under the notion that our entries are not\n> duplicate but as already pointed out, our entries are not unique so we\n> need one of those two ways either insert or remove_duplicates, this\n> can be a trivial question but i wonder how are the tests passing by\n> removing these lines, i was actually researching about it.\n\n... suspense.  And the result of the research was???\n\nIf the answer was simply \"we lack test coverage\", it may make sense\nto add a test taken from Peff's earlier response to increase test\ncoverage, perhaps?\n\nThanks.\n"},{"id":"534075","messageId":"xmqqqzrp74q3.fsf@gitster.g","threadId":"64804","inReplyTo":"20260116165003.95314-1-amishhhaaaa@gmail.com","subject":"Re: [PATCH] sparse-checkout: optimize string_list construction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-01-16T19:11:16Z","receivedAt":"2026-01-16T19:11:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"amisha <amishhhaaaa@gmail.com> writes:\n\n> Subject: Re: [PATCH] sparse-checkout: optimize string_list construction\n\nIt would have been nice to see [PATCH v2] or whatever that signals\nthat there is an earlier iteration.\n\n> From: Amisha Chhajed <amishhhaaaa@gmail.com>\n>\n> Improve O(n^2) complexity to O(n log n) while building a sorted\n> 'string_list' by constructing it unsorted then sorting it\n> followed by removing duplicates.\n\nBy the way, do we have t/perf/ that substanticates the performance\nclaim here (in other words, how much improvement are we expecting in\npractice)?\n\nAlso, have you found out why the previous round that did not remove\nduplicates saw no failed tests?  Perhaps it is a good idea to add\nsome test that would notice if we failed to add calls to\nremove_duplicates in this patch?\n\nThis is an unrelated tangent, a possible #leftoverbits material, but\nshould not be part of this patch (or even in the same series as this\npatch).  I notice that string_list_remove_duplicates() almost always\nimmediately follow a call to string_list_sort() of the same\ninstance, which makes me wonder if we would be better off if we had\na variant of string_list_sort(), and call it string_list_sort_u().\n\nThanks.\n\n> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\n> index 15d51e60a8..7dfb276bf0 100644\n> --- a/builtin/sparse-checkout.c\n> +++ b/builtin/sparse-checkout.c\n> @@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n>  \n>  \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n>  \t\t\t/* pe->pattern starts with \"/\", skip it */\n> -\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n> +\t\t\tstring_list_append(&sl, pe->pattern + 1);\n>  \t\t}\n>  \n>  \t\tstring_list_sort(&sl);\n> +\t\tstring_list_remove_duplicates(&sl, 0);\n>  \n>  \t\tfor (i = 0; i < sl.nr; i++) {\n>  \t\t\tquote_c_style(sl.items[i].string, NULL, stdout, 0);\n> @@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n>  \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n>  \t\t\t\t\t     pe->pattern,\n>  \t\t\t\t\t     &parent_pattern))\n> -\t\t\tstring_list_insert(&sl, pe->pattern);\n> +\t\t\tstring_list_append(&sl, pe->pattern);\n>  \t}\n>  \n>  \tstring_list_sort(&sl);\n> @@ -311,7 +312,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n>  \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n>  \t\t\t\t\t     pe->pattern,\n>  \t\t\t\t\t     &parent_pattern))\n> -\t\t\tstring_list_insert(&sl, pe->pattern);\n> +\t\t\tstring_list_append(&sl, pe->pattern);\n>  \t}\n>  \n>  \tstrbuf_release(&parent_pattern);\n"},{"id":"534133","messageId":"9394755a-18db-4efd-b7c8-ce38eab57f04@gmail.com","threadId":"64804","inReplyTo":"20260114213551.GC1010080@coredump.intra.peff.net","subject":"Re: [PATCH] sparse-checkout: optimize string_list construction","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-01-18T02:39:27Z","receivedAt":"2026-01-18T02:39:30Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/14/26 4:35 PM, Jeff King wrote:\n> On Thu, Jan 15, 2026 at 12:58:03AM +0530, amisha wrote:\n> \n>> Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list' by constructing it unsorted and sorting it afterwards.\n...\n>>   \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n>>   \t\t\t/* pe->pattern starts with \"/\", skip it */\n>> -\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n>> +\t\t\tstring_list_append(&sl, pe->pattern + 1);\n>>   \t\t}\n>>   \n>>   \t\tstring_list_sort(&sl);\n> \n> Since we already sort here, I was quite curious how this came about.  It\n> looks like the _insert() call and the _sort() were both added together\n> in de11951b03 (sparse-checkout: list directories in cone mode,\n> 2019-12-30).\n> \n> I'd guess it was just a typo/brain-o to mix up append and insert.\n\nThis is exactly the case.\n\n> Doesn't the same issue exist in write_cone_to_file(), too (in two\n> separate spots)?\n\nIt would make sense that such a pattern could reappear in other areas\nin this file. I see that you have caught a few more in v3.\n\nThanks,\n-Stolee\n"},{"id":"534134","messageId":"c5631f7d-72ff-4876-9b68-ea4a70fde501@gmail.com","threadId":"64804","inReplyTo":"xmqqy0lx8ojt.fsf@gitster.g","subject":"Re: [PATCH v3] sparse-checkout: optimize string_list construction","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-01-18T02:46:18Z","receivedAt":"2026-01-18T02:46:21Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/16/26 12:17 PM, Junio C Hamano wrote:\n> Amisha Chhajed <amishhhaaaa@gmail.com> writes:\n> \n>> It was assumed to be safe under the notion that our entries are not\n>> duplicate but as already pointed out, our entries are not unique so we\n>> need one of those two ways either insert or remove_duplicates, this\n>> can be a trivial question but i wonder how are the tests passing by\n>> removing these lines, i was actually researching about it.\n> \n> ... suspense.  And the result of the research was???\n> \n> If the answer was simply \"we lack test coverage\", it may make sense\n> to add a test taken from Peff's earlier response to increase test\n> coverage, perhaps?\n\nIn addition to adding more tests to t/t1091-sparse-checkout-builtin.sh\nto cover these duplicate cases. To demonstrate your quadratic perf\nimprovement, a test in t/perf/p2000-sparse-operations.sh or similar\nwould be good to add.\n\nI expect that the test you would add doesn't matter too much about\nthe data shape, but would look very different from most tests in\np2000. You can make use of the constructed repo's directory structure\nthat has nesting directories with name f1, f2, f3, or f4.\n\nHere's something to get you started that I haven't tested myself:\n\ntest_perf 'duplicate sparse directories' '\n\t(\n\t\tcd full-v4 &&\n\t\t\n\t\tfor i in $(test_seq 1000)\n\t\tdo\n\t\t\tprintf \"f1/f2/f3/f4\\n\"\n\t\tdone >in &&\n\t\tgit sparse-checkout set --stdin <in\n\t)\n'\n\nThat should test the logic with 1000 identical directories, which\nshould be enough to have the quadratic growth show up.\n\nThanks,\n-Stolee\n\n"},{"id":"534141","messageId":"CAPvEtrceTDtZ2HdHnETRsKd0KTeeoVaiHy-K1O_+Qiuk6XAKcw@mail.gmail.com","threadId":"64804","inReplyTo":"xmqqqzrp74q3.fsf@gitster.g","subject":"Re: [PATCH] sparse-checkout: optimize string_list construction","fromName":"Amisha Chhajed","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-18T13:07:38Z","receivedAt":"2026-01-18T13:07:50Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"On Sat, 17 Jan 2026 at 00:41, Junio C Hamano <gitster@pobox.com> wrote:\n>\n> amisha <amishhhaaaa@gmail.com> writes:\n>\n> > Subject: Re: [PATCH] sparse-checkout: optimize string_list construction\n>\n> It would have been nice to see [PATCH v2] or whatever that signals\n> that there is an earlier iteration.\n>\n> > From: Amisha Chhajed <amishhhaaaa@gmail.com>\n> >\n> > Improve O(n^2) complexity to O(n log n) while building a sorted\n> > 'string_list' by constructing it unsorted then sorting it\n> > followed by removing duplicates.\n>\n> By the way, do we have t/perf/ that substanticates the performance\n> claim here (in other words, how much improvement are we expecting in\n> practice)?\n\nAfter running different perf tests i was not able to find any\nsubstantial improvement in the results output before and after this\npatch, after going through some perf tests i came to conclude that for\nthe results of this commit to shine we need a perf test that tests it\nwith many duplicates, thanks to inputs by Derrick for further\nconfirming this and giving me a starting point.\n\n> Also, have you found out why the previous round that did not remove\n> duplicates saw no failed tests?  Perhaps it is a good idea to add\n> some test that would notice if we failed to add calls to\n> remove_duplicates in this patch?\n\nYes!, actually we don't have a test that covers the line which removes\nduplicates. I wrote a test locally which fails if duplicates are found\nin the output with duplicates in input, very similar to what Jeff\nwrote for reproducing. I will create a patch sh\n\n> This is an unrelated tangent, a possible #leftoverbits material, but\n> should not be part of this patch (or even in the same series as this\n> patch).  I notice that string_list_remove_duplicates() almost always\n> immediately follow a call to string_list_sort() of the same\n> instance, which makes me wonder if we would be better off if we had\n> a variant of string_list_sort(), and call it string_list_sort_u()\n\n After running command git grep -n -e \"string_list_sort\" -e\n\"string_list_remove_duplicates\" -- clone.c fast-export.c fetch.c\nhelp.c pack-objects.c sparse-checkout.c\nfrom builtin/\ni got the output\n\nclone.c:1139:           string_list_sort(&option_recurse_submodules);\n\nclone.c:1140:\nstring_list_remove_duplicates(&option_recurse_submodules, 0);\n\nfast-export.c:1121:     string_list_sort(&extra_refs);\n\nfast-export.c:1122:     string_list_remove_duplicates(&extra_refs, 0);\n\nfetch.c:1370:           string_list_sort(&refnames);\n\nfetch.c:2587:   string_list_remove_duplicates(&list, 0);\n\nhelp.c:159:     string_list_sort(&keys);\n\nhelp.c:199:     string_list_remove_duplicates(&keys_uniq, 0);\n\npack-objects.c:3852:    string_list_sort(&include_packs);\n\npack-objects.c:3853:    string_list_remove_duplicates(&include_packs, 0);\n\npack-objects.c:3854:    string_list_sort(&exclude_packs);\n\npack-objects.c:3855:    string_list_remove_duplicates(&exclude_packs, 0);\n\npack-objects.c:3899:     * string_list_item's ->util pointer, which\nstring_list_sort() does not\n\npack-objects.c:4141:    string_list_sort(&discard_packs);\n\npack-objects.c:4142:    string_list_sort(&fresh_packs);\n\nsparse-checkout.c:97:           string_list_sort(&sl);\n\nsparse-checkout.c:98:           string_list_remove_duplicates(&sl, 0);\n\nsparse-checkout.c:296:  string_list_sort(&sl);\n\nsparse-checkout.c:297:  string_list_remove_duplicates(&sl, 0);\n\nsparse-checkout.c:320:  string_list_sort(&sl);\n\nsparse-checkout.c:321:  string_list_remove_duplicates(&sl, 0);\n\n\nThere are many places where string_list_rmeove_duplicates is directly\nnext to string_list_sort, so it is a very common pattern\n\nThank you.\n"},{"id":"534142","messageId":"CAPvEtreFgpVLG7WsJsJLjSA0_x0S3vh=PXa+VqmVnxjRTJ7WGA@mail.gmail.com","threadId":"64804","inReplyTo":"c5631f7d-72ff-4876-9b68-ea4a70fde501@gmail.com","subject":"Re: [PATCH v3] sparse-checkout: optimize string_list construction","fromName":"Amisha Chhajed","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-18T13:09:58Z","receivedAt":"2026-01-18T13:10:11Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"On Sun, 18 Jan 2026 at 08:16, Derrick Stolee <stolee@gmail.com> wrote:\n>\n> On 1/16/26 12:17 PM, Junio C Hamano wrote:\n> > Amisha Chhajed <amishhhaaaa@gmail.com> writes:\n> >\n> >> It was assumed to be safe under the notion that our entries are not\n> >> duplicate but as already pointed out, our entries are not unique so we\n> >> need one of those two ways either insert or remove_duplicates, this\n> >> can be a trivial question but i wonder how are the tests passing by\n> >> removing these lines, i was actually researching about it.\n> >\n> > ... suspense.  And the result of the research was???\n> >\n> > If the answer was simply \"we lack test coverage\", it may make sense\n> > to add a test taken from Peff's earlier response to increase test\n> > coverage, perhaps?\n>\n> In addition to adding more tests to t/t1091-sparse-checkout-builtin.sh\n> to cover these duplicate cases. To demonstrate your quadratic perf\n> improvement, a test in t/perf/p2000-sparse-operations.sh or similar\n> would be good to add.\n>\n> I expect that the test you would add doesn't matter too much about\n> the data shape, but would look very different from most tests in\n> p2000. You can make use of the constructed repo's directory structure\n> that has nesting directories with name f1, f2, f3, or f4.\n>\n> Here's something to get you started that I haven't tested myself:\n>\n> test_perf 'duplicate sparse directories' '\n>         (\n>                 cd full-v4 &&\n>\n>                 for i in $(test_seq 1000)\n>                 do\n>                         printf \"f1/f2/f3/f4\\n\"\n>                 done >in &&\n>                 git sparse-checkout set --stdin <in\n>         )\n> '\n>\n> That should test the logic with 1000 identical directories, which\n> should be enough to have the quadratic growth show up.\n>\n> Thanks,\n> -Stolee\n\n\nThank you so much for pointing me in the right direction.\n"},{"id":"534163","messageId":"20260119053251.GA1991605@coredump.intra.peff.net","threadId":"64804","inReplyTo":"xmqqqzrp74q3.fsf@gitster.g","subject":"Re: [PATCH] sparse-checkout: optimize string_list construction","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-01-19T05:32:51Z","receivedAt":"2026-01-19T05:32:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 16, 2026 at 11:11:16AM -0800, Junio C Hamano wrote:\n\n> > Improve O(n^2) complexity to O(n log n) while building a sorted\n> > 'string_list' by constructing it unsorted then sorting it\n> > followed by removing duplicates.\n> \n> By the way, do we have t/perf/ that substanticates the performance\n> claim here (in other words, how much improvement are we expecting in\n> practice)?\n\nIMHO it is not that big a deal to demonstrate the perf improvement in\nthe test suite.\n\nProbably you could feed a very long list of unique names to \"git\nsparse-checkout add --stdin\" to trigger it. But a list long enough to\ncause annoying quadratic behavior is getting far enough from the real\nworld that I'm not sure it is worth adding to the (already expensive)\nperf suite.\n\nAnd swapping append+sort for sorted insertion is a common and simple\nimprovement.  We probably don't need to prove its performance at all,\nbut if we do, a one-off hyperfine output in the commit message would be\nenough.\n\n-Peff\n"},{"id":"534180","messageId":"20260119123339.48435-1-amishhhaaaa@gmail.com","threadId":"64804","inReplyTo":"20260114192803.4852-1-amishhhaaaa@gmail.com","subject":"[PATCH v5 1/2] sparse-checkout: optimize string_list construction","fromName":"amisha","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-19T12:33:39Z","receivedAt":"2026-01-19T12:33:53Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"From: Amisha Chhajed <amishhhaaaa@gmail.com>\n\nImprove O(n^2) complexity to O(n log n) while building a sorted\n'string_list' by constructing it unsorted then sorting it\nfollowed by removing duplicates.\n\nSigned-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n---\n builtin/sparse-checkout.c | 7 ++++---\n 1 file changed, 4 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 15d51e60a8..7dfb276bf0 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n \n \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n \t\t\t/* pe->pattern starts with \"/\", skip it */\n-\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n+\t\t\tstring_list_append(&sl, pe->pattern + 1);\n \t\t}\n \n \t\tstring_list_sort(&sl);\n+\t\tstring_list_remove_duplicates(&sl, 0);\n \n \t\tfor (i = 0; i < sl.nr; i++) {\n \t\t\tquote_c_style(sl.items[i].string, NULL, stdout, 0);\n@@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstring_list_sort(&sl);\n@@ -311,7 +312,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstrbuf_release(&parent_pattern);\n-- \n2.51.0\n\n\nFrom b20a99f0773bab063a31eea6fead730e18200ca7 Mon Sep 17 00:00:00 2001\nFrom: Amisha Chhajed <amishhhaaaa@gmail.com>\nDate: Mon, 19 Jan 2026 00:20:47 +0530\nSubject: [PATCH v5 2/2] t1091: Add tests for deduplication of cone-mode sparse\n patterns\n\nSparse-checkout deduplicates repeated cone-mode patterns,\nbut this behaviour was previously untested.\n\nAdd tests that verify that sparse-checkout file contain each cone\npattern only once and sparse-checkout list reports each pattern\nonly once.\n\nSigned-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n---\n t/t1091-sparse-checkout-builtin.sh | 33 ++++++++++++++++++++++++++++++\n 1 file changed, 33 insertions(+)\n\ndiff --git a/t/t1091-sparse-checkout-builtin.sh b/t/t1091-sparse-checkout-builtin.sh\nindex b2da4feaef..858801fed3 100755\n--- a/t/t1091-sparse-checkout-builtin.sh\n+++ b/t/t1091-sparse-checkout-builtin.sh\n@@ -817,6 +817,39 @@ test_expect_success 'cone mode clears ignored subdirectories' '\n \ttest_cmp expect out\n '\n \n+test_expect_success 'sparse-checkout deduplicates repeated cone patterns' '\n+    rm -f repo/.git/info/sparse-checkout &&\n+    git -C repo sparse-checkout init --cone &&\n+    git -C repo sparse-checkout add --stdin <<-\\EOF &&\n+\t/foo/\n+\t/bar/\n+\t/foo/\n+\tEOF\n+    cat >expect <<-\\EOF &&\n+\t/*\n+\t!/*/\n+\t/bar/\n+\t/foo/\n+\tEOF\n+    test_cmp expect repo/.git/info/sparse-checkout\n+'\n+\n+test_expect_success 'sparse-checkout list deduplicates repeated cone patterns' '\n+    rm -f repo/.git/info/sparse-checkout &&\n+    git -C repo sparse-checkout init --cone &&\n+    git -C repo sparse-checkout add --stdin <<-\\EOF &&\n+\t/foo/\n+\t/bar/\n+\t/foo/\n+\tEOF\n+    git -C repo sparse-checkout list >actual &&\n+    cat >expect <<-\\EOF &&\n+\tbar\n+\tfoo\n+\tEOF\n+    test_cmp expect actual\n+'\n+\n test_expect_success 'malformed cone-mode patterns' '\n \tgit -C repo sparse-checkout init --cone &&\n \tmkdir -p repo/foo/bar &&\n-- \n2.51.0\n\n"},{"id":"534186","messageId":"36b50d7d-b9f4-4ff3-b00e-9c98ad690749@gmail.com","threadId":"64804","inReplyTo":"20260119123339.48435-1-amishhhaaaa@gmail.com","subject":"Re: [PATCH v5 1/2] sparse-checkout: optimize string_list construction","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-01-19T17:04:45Z","receivedAt":"2026-01-19T17:04:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/19/2026 7:33 AM, amisha wrote:\n> From: Amisha Chhajed <amishhhaaaa@gmail.com>\n> \n> Improve O(n^2) complexity to O(n log n) while building a sorted\n> 'string_list' by constructing it unsorted then sorting it\n> followed by removing duplicates.\n> \n> Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n> ---\n>  builtin/sparse-checkout.c | 7 ++++---\n>  1 file changed, 4 insertions(+), 3 deletions(-)\n> \n> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\n> index 15d51e60a8..7dfb276bf0 100644\n> --- a/builtin/sparse-checkout.c\n> +++ b/builtin/sparse-checkout.c\n> @@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n>  \n>  \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n>  \t\t\t/* pe->pattern starts with \"/\", skip it */\n> -\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n> +\t\t\tstring_list_append(&sl, pe->pattern + 1);\n>  \t\t}\n>  \n>  \t\tstring_list_sort(&sl);\n> +\t\tstring_list_remove_duplicates(&sl, 0);\n\nShouldn't this line be added in the other uses of string_list_append()?\n\n>  \n>  \t\tfor (i = 0; i < sl.nr; i++) {\n>  \t\t\tquote_c_style(sl.items[i].string, NULL, stdout, 0);\n> @@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n>  \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n>  \t\t\t\t\t     pe->pattern,\n>  \t\t\t\t\t     &parent_pattern))\n> -\t\t\tstring_list_insert(&sl, pe->pattern);\n> +\t\t\tstring_list_append(&sl, pe->pattern);\n>  \t}\n> \n>  \tstring_list_sort(&sl);\nActually, there is a string_list_remove_duplicates() just\noutside of the context of this diff. \n\n> @@ -311,7 +312,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n>  \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n>  \t\t\t\t\t     pe->pattern,\n>  \t\t\t\t\t     &parent_pattern))\n> -\t\t\tstring_list_insert(&sl, pe->pattern);\n> +\t\t\tstring_list_append(&sl, pe->pattern);\n>  \t}\n>  \n>  \tstrbuf_release(&parent_pattern);\n\nSame here.\n\nThis diff looks good, but I do believe it would be good to include your\nduplicate test here instead of in a second patch.\n\nAlso, the way your second patch appeared as a trailer of your first patch,\nso it didn't appear properly as a thread in my email client. Here it is\nfor review:\n\n> From b20a99f0773bab063a31eea6fead730e18200ca7 Mon Sep 17 00:00:00 2001\n> From: Amisha Chhajed <amishhhaaaa@gmail.com>\n> Date: Mon, 19 Jan 2026 00:20:47 +0530\n> Subject: [PATCH v5 2/2] t1091: Add tests for deduplication of cone-mode sparse\n>  patterns\n\nnit: this title is a little long and has incorrect capitalization. Take\nnote for later, since I expect this diff to be squashed into the previous\npatch.\n\n> +test_expect_success 'sparse-checkout deduplicates repeated cone patterns' '\n> +    rm -f repo/.git/info/sparse-checkout &&\n> +    git -C repo sparse-checkout init --cone &&\n> +    git -C repo sparse-checkout add --stdin <<-\\EOF &&\n> +\t/foo/\n> +\t/bar/\n> +\t/foo/\n> +\tEOF\n\nThis slashes are redundant for cone-mode patterns. I recommend a more\ninteresting case, such as\n\n\tfoo/bar/baz\n\ta/b/c\n\tfoo/bar/baz\n\ta/b\n\nThis should remove the duplicates foo/bar/baz during the run, but also it\nshould notice that a/b/c is contained within the recursive set defined by\na/b.\n\nThe resulting sparse-checkout file should have lines such as\n\n\t/*\n\t!/*/\n\t/a/\n\t!/a/*/\n\t/a/b\n\t/foo\n\t!/foo/*/\n\t/foo/bar\n\t!/foo/bar/*/\n\t/foo/bar/baz\n\nThe order might be different, but this is what I recall from how nested\ndirectories work in cone mode.\n\n> +    cat >expect <<-\\EOF &&\n> +\t/*\n> +\t!/*/\n> +\t/bar/\n> +\t/foo/\n> +\tEOF\n> +    test_cmp expect repo/.git/info/sparse-checkout\n> +'\n\n> +test_expect_success 'sparse-checkout list deduplicates repeated cone patterns' '\n> +    rm -f repo/.git/info/sparse-checkout &&\n> +    git -C repo sparse-checkout init --cone &&\n> +    git -C repo sparse-checkout add --stdin <<-\\EOF &&\n> +\t/foo/\n> +\t/bar/\n> +\t/foo/\n> +\tEOF\n> +    git -C repo sparse-checkout list >actual &&\n> +    cat >expect <<-\\EOF &&\n> +\tbar\n> +\tfoo\n> +\tEOF\n> +    test_cmp expect actual\n> +'\n\nThis does lead to an interesting case where the 'list' command was only\ninteracting with the sparse-checkout file, which wouldn't have duplicates\nif it was modified by the user in cone mode.\n\nKeep in mind that you're not actually testing the 'list' command, because\nthe 'add' command already deduplicated. You'll need to modify the\nsparse-checkout file itself to get an interesting test of the 'list'\ncommand.\n\nWhen not in cone mode, we should not be removing duplicates because the\norder of the patterns matters and we should not be reordering them. I'm\nnot sure if that's relevant but it's something to keep in mind while you're\ntesting, since the command will revert to non-cone mode if the\nsparse-checkout file doesn't match the cone mode pattern expectations.\n\nThanks,\n-Stolee\n"},{"id":"534189","messageId":"CALE2CrSRromrzu5ZJxtm_LQ0gke102dVusYCFb3jY8hNSRBQ=w@mail.gmail.com","threadId":"64804","inReplyTo":"36b50d7d-b9f4-4ff3-b00e-9c98ad690749@gmail.com","subject":"Re: [PATCH v5 1/2] sparse-checkout: optimize string_list construction","fromName":"Pushkar Singh","fromEmail":"pushkarkumarsingh1970@gmail.com","sentAt":"2026-01-19T18:33:25Z","receivedAt":"2026-01-19T18:33:37Z","isPatch":true,"sender":{"key":"pushkarkumarsingh1970@gmail.com","avatar":"https://avatars.githubusercontent.com/u/173247767?v=4"},"body":"Hi Amisha, Derrick,\n\nThanks for the detailed discussion here. Reading through the thread helped\nclarify the intended behavior around deduplication and testing.\n\nWhile investigating \"git sparse-checkout list\" in cone mode independently,\nI noticed a related but slightly different case than repeated identical\npatterns: semantically equivalent but syntactically different paths, for\nexample:\n\n  folder1\n  folder1/\n  ./folder1\n\nThese collapse to a single canonical entry in the output of\n\"sparse-checkout list\", even though they are distinct strings on input.\n\nThe tests in v5 cover duplicate identical patterns well, but they do not\nappear to cover this normalization aspect. It may be worth adding a test\nthat exercises \"list\" behavior with such normalized-path variants, possibly\nby modifying the sparse-checkout file directly so that \"add\" does not\nperform deduplication first, as Derrick mentioned.\n\nFor context, I sent a small test-only patch exploring this behavior here:\nhttps://lore.kernel.org/git/edbde063-2c39-4812-9970-247b67f678c7@gmail.com/T/#m68a4fd645e10cd8e82ac5e4080c48b12f8f6348a\n\nHappy to help draft or review an additional test if that would be useful.\n\nThanks,\nPushkar\n\nOn Mon, Jan 19, 2026 at 10:39 PM Derrick Stolee <stolee@gmail.com> wrote:\n>\n> On 1/19/2026 7:33 AM, amisha wrote:\n> > From: Amisha Chhajed <amishhhaaaa@gmail.com>\n> >\n> > Improve O(n^2) complexity to O(n log n) while building a sorted\n> > 'string_list' by constructing it unsorted then sorting it\n> > followed by removing duplicates.\n> >\n> > Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n> > ---\n> >  builtin/sparse-checkout.c | 7 ++++---\n> >  1 file changed, 4 insertions(+), 3 deletions(-)\n> >\n> > diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\n> > index 15d51e60a8..7dfb276bf0 100644\n> > --- a/builtin/sparse-checkout.c\n> > +++ b/builtin/sparse-checkout.c\n> > @@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n> >\n> >               hashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n> >                       /* pe->pattern starts with \"/\", skip it */\n> > -                     string_list_insert(&sl, pe->pattern + 1);\n> > +                     string_list_append(&sl, pe->pattern + 1);\n> >               }\n> >\n> >               string_list_sort(&sl);\n> > +             string_list_remove_duplicates(&sl, 0);\n>\n> Shouldn't this line be added in the other uses of string_list_append()?\n>\n> >\n> >               for (i = 0; i < sl.nr; i++) {\n> >                       quote_c_style(sl.items[i].string, NULL, stdout, 0);\n> > @@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n> >               if (!hashmap_contains_parent(&pl->recursive_hashmap,\n> >                                            pe->pattern,\n> >                                            &parent_pattern))\n> > -                     string_list_insert(&sl, pe->pattern);\n> > +                     string_list_append(&sl, pe->pattern);\n> >       }\n> >\n> >       string_list_sort(&sl);\n> Actually, there is a string_list_remove_duplicates() just\n> outside of the context of this diff.\n>\n> > @@ -311,7 +312,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n> >               if (!hashmap_contains_parent(&pl->recursive_hashmap,\n> >                                            pe->pattern,\n> >                                            &parent_pattern))\n> > -                     string_list_insert(&sl, pe->pattern);\n> > +                     string_list_append(&sl, pe->pattern);\n> >       }\n> >\n> >       strbuf_release(&parent_pattern);\n>\n> Same here.\n>\n> This diff looks good, but I do believe it would be good to include your\n> duplicate test here instead of in a second patch.\n>\n> Also, the way your second patch appeared as a trailer of your first patch,\n> so it didn't appear properly as a thread in my email client. Here it is\n> for review:\n>\n> > From b20a99f0773bab063a31eea6fead730e18200ca7 Mon Sep 17 00:00:00 2001\n> > From: Amisha Chhajed <amishhhaaaa@gmail.com>\n> > Date: Mon, 19 Jan 2026 00:20:47 +0530\n> > Subject: [PATCH v5 2/2] t1091: Add tests for deduplication of cone-mode sparse\n> >  patterns\n>\n> nit: this title is a little long and has incorrect capitalization. Take\n> note for later, since I expect this diff to be squashed into the previous\n> patch.\n>\n> > +test_expect_success 'sparse-checkout deduplicates repeated cone patterns' '\n> > +    rm -f repo/.git/info/sparse-checkout &&\n> > +    git -C repo sparse-checkout init --cone &&\n> > +    git -C repo sparse-checkout add --stdin <<-\\EOF &&\n> > +     /foo/\n> > +     /bar/\n> > +     /foo/\n> > +     EOF\n>\n> This slashes are redundant for cone-mode patterns. I recommend a more\n> interesting case, such as\n>\n>         foo/bar/baz\n>         a/b/c\n>         foo/bar/baz\n>         a/b\n>\n> This should remove the duplicates foo/bar/baz during the run, but also it\n> should notice that a/b/c is contained within the recursive set defined by\n> a/b.\n>\n> The resulting sparse-checkout file should have lines such as\n>\n>         /*\n>         !/*/\n>         /a/\n>         !/a/*/\n>         /a/b\n>         /foo\n>         !/foo/*/\n>         /foo/bar\n>         !/foo/bar/*/\n>         /foo/bar/baz\n>\n> The order might be different, but this is what I recall from how nested\n> directories work in cone mode.\n>\n> > +    cat >expect <<-\\EOF &&\n> > +     /*\n> > +     !/*/\n> > +     /bar/\n> > +     /foo/\n> > +     EOF\n> > +    test_cmp expect repo/.git/info/sparse-checkout\n> > +'\n>\n> > +test_expect_success 'sparse-checkout list deduplicates repeated cone patterns' '\n> > +    rm -f repo/.git/info/sparse-checkout &&\n> > +    git -C repo sparse-checkout init --cone &&\n> > +    git -C repo sparse-checkout add --stdin <<-\\EOF &&\n> > +     /foo/\n> > +     /bar/\n> > +     /foo/\n> > +     EOF\n> > +    git -C repo sparse-checkout list >actual &&\n> > +    cat >expect <<-\\EOF &&\n> > +     bar\n> > +     foo\n> > +     EOF\n> > +    test_cmp expect actual\n> > +'\n>\n> This does lead to an interesting case where the 'list' command was only\n> interacting with the sparse-checkout file, which wouldn't have duplicates\n> if it was modified by the user in cone mode.\n>\n> Keep in mind that you're not actually testing the 'list' command, because\n> the 'add' command already deduplicated. You'll need to modify the\n> sparse-checkout file itself to get an interesting test of the 'list'\n> command.\n>\n> When not in cone mode, we should not be removing duplicates because the\n> order of the patterns matters and we should not be reordering them. I'm\n> not sure if that's relevant but it's something to keep in mind while you're\n> testing, since the command will revert to non-cone mode if the\n> sparse-checkout file doesn't match the cone mode pattern expectations.\n>\n> Thanks,\n> -Stolee\n>\n"},{"id":"534191","messageId":"xmqqy0lt4e36.fsf@gitster.g","threadId":"64804","inReplyTo":"20260119053251.GA1991605@coredump.intra.peff.net","subject":"Re: [PATCH] sparse-checkout: optimize string_list construction","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-01-19T19:06:21Z","receivedAt":"2026-01-19T19:06:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Fri, Jan 16, 2026 at 11:11:16AM -0800, Junio C Hamano wrote:\n>\n>> > Improve O(n^2) complexity to O(n log n) while building a sorted\n>> > 'string_list' by constructing it unsorted then sorting it\n>> > followed by removing duplicates.\n>> \n>> By the way, do we have t/perf/ that substanticates the performance\n>> claim here (in other words, how much improvement are we expecting in\n>> practice)?\n>\n> IMHO it is not that big a deal to demonstrate the perf improvement in\n> the test suite.\n> ... a one-off hyperfine output in the commit message would be\n> enough.\n\nThanks, I agree with this conclusion; I didn't expect a huge\ndifference from this change unless N is meaningfully large anyway.\n\n"},{"id":"534265","messageId":"20260120153829.48044-1-amishhhaaaa@gmail.com","threadId":"64804","inReplyTo":"20260114192803.4852-1-amishhhaaaa@gmail.com","subject":"[PATCH v6] sparse-checkout: optimize string_list construction and add tests to verify deduplication.","fromName":"amisha","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-20T15:38:29Z","receivedAt":"2026-01-20T15:38:37Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"From: Amisha Chhajed <amishhhaaaa@gmail.com>\n\nImprove O(n^2) complexity to O(n log n) while building a sorted\n'string_list' by constructing it unsorted then sorting it\nfollowed by removing duplicates.\n\nsparse-checkout deduplicates repeated cone-mode patterns,\nbut this behaviour was previously untested, add tests that\nverify that sparse-checkout file contain each cone\npattern only once and sparse-checkout list reports each pattern\nonly once.\n\nSigned-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n---\n builtin/sparse-checkout.c          |  7 +++--\n t/t1091-sparse-checkout-builtin.sh | 48 ++++++++++++++++++++++++++++++\n 2 files changed, 52 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 15d51e60a8..7dfb276bf0 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n \n \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n \t\t\t/* pe->pattern starts with \"/\", skip it */\n-\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n+\t\t\tstring_list_append(&sl, pe->pattern + 1);\n \t\t}\n \n \t\tstring_list_sort(&sl);\n+\t\tstring_list_remove_duplicates(&sl, 0);\n \n \t\tfor (i = 0; i < sl.nr; i++) {\n \t\t\tquote_c_style(sl.items[i].string, NULL, stdout, 0);\n@@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstring_list_sort(&sl);\n@@ -311,7 +312,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstrbuf_release(&parent_pattern);\ndiff --git a/t/t1091-sparse-checkout-builtin.sh b/t/t1091-sparse-checkout-builtin.sh\nindex b2da4feaef..ede5c6b3f3 100755\n--- a/t/t1091-sparse-checkout-builtin.sh\n+++ b/t/t1091-sparse-checkout-builtin.sh\n@@ -817,6 +817,54 @@ test_expect_success 'cone mode clears ignored subdirectories' '\n \ttest_cmp expect out\n '\n \n+test_expect_success 'sparse-checkout deduplicates repeated cone patterns' '\n+    rm -f repo/.git/info/sparse-checkout &&\n+    git -C repo sparse-checkout init --cone &&\n+    git -C repo sparse-checkout add --stdin <<-\\EOF &&\n+\tfoo/bar/baz\n+\ta/b/c\n+\tfoo/bar/baz\n+\ta/b\n+\tEOF\n+    cat >expect <<-\\EOF &&\n+\t/*\n+\t!/*/\n+\t/a/\n+\t!/a/*/\n+\t/foo/\n+\t!/foo/*/\n+\t/foo/bar/\n+\t!/foo/bar/*/\n+\t/a/b/\n+\t/foo/bar/baz/\n+\tEOF\n+    test_cmp expect repo/.git/info/sparse-checkout\n+'\n+\n+test_expect_success 'sparse-checkout list deduplicates repeated cone patterns' '\n+    rm -f repo/.git/info/sparse-checkout &&\n+    git -C repo sparse-checkout init --cone &&\n+    cat <<-\\EOF >repo/.git/info/sparse-checkout &&\n+\t/*\n+\t!/*/\n+\t/a/\n+\t!/a/*/\n+\t/foo/\n+\t!/foo/*/\n+\t/foo/bar/\n+\t!/foo/bar/*/\n+\t/a/b/\n+\t/foo/bar/baz/\n+\t/foo/bar/baz/\n+\tEOF\n+    git -C repo sparse-checkout list >actual &&\n+    cat <<-\\EOF >expect &&\n+\ta/b\n+\tfoo/bar/baz\n+\tEOF\n+    test_cmp expect actual\n+'\n+\n test_expect_success 'malformed cone-mode patterns' '\n \tgit -C repo sparse-checkout init --cone &&\n \tmkdir -p repo/foo/bar &&\n-- \n2.51.0\n\n"},{"id":"534267","messageId":"CAPvEtrcGYXeXWn-p=EipyE07gqNcP1qx_=V94cSD5XLwk4mdDg@mail.gmail.com","threadId":"64804","inReplyTo":"36b50d7d-b9f4-4ff3-b00e-9c98ad690749@gmail.com","subject":"Re: [PATCH v5 1/2] sparse-checkout: optimize string_list construction","fromName":"Amisha Chhajed","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-20T15:47:17Z","receivedAt":"2026-01-20T15:47:31Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"On Mon, 19 Jan 2026 at 22:34, Derrick Stolee <stolee@gmail.com> wrote:\n>\n> On 1/19/2026 7:33 AM, amisha wrote:\n> > From: Amisha Chhajed <amishhhaaaa@gmail.com>\n> >\n> > Improve O(n^2) complexity to O(n log n) while building a sorted\n> > 'string_list' by constructing it unsorted then sorting it\n> > followed by removing duplicates.\n> >\n> > Signed-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n> > ---\n> >  builtin/sparse-checkout.c | 7 ++++---\n> >  1 file changed, 4 insertions(+), 3 deletions(-)\n> >\n> > diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\n> > index 15d51e60a8..7dfb276bf0 100644\n> > --- a/builtin/sparse-checkout.c\n> > +++ b/builtin/sparse-checkout.c\n> > @@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n> >\n> >               hashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n> >                       /* pe->pattern starts with \"/\", skip it */\n> > -                     string_list_insert(&sl, pe->pattern + 1);\n> > +                     string_list_append(&sl, pe->pattern + 1);\n> >               }\n> >\n> >               string_list_sort(&sl);\n> > +             string_list_remove_duplicates(&sl, 0);\n>\n> Shouldn't this line be added in the other uses of string_list_append()?\n>\n> >\n> >               for (i = 0; i < sl.nr; i++) {\n> >                       quote_c_style(sl.items[i].string, NULL, stdout, 0);\n> > @@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n> >               if (!hashmap_contains_parent(&pl->recursive_hashmap,\n> >                                            pe->pattern,\n> >                                            &parent_pattern))\n> > -                     string_list_insert(&sl, pe->pattern);\n> > +                     string_list_append(&sl, pe->pattern);\n> >       }\n> >\n> >       string_list_sort(&sl);\n> Actually, there is a string_list_remove_duplicates() just\n> outside of the context of this diff.\n\nI was wondering if the string_list_remove_duplicates here is redundant\nas if we refer to the code that adds entries in the parent hashmap,\nrefer:\n\nfrom git/dir.c\nif (hashmap_get_entry(&pl->parent_hashmap, translated, ent, NULL)) {\n/* we already included this at the parent level */\nwarning(_(\"your sparse-checkout file may have issues: pattern '%s' is\nrepeated\"),\ngiven->pattern);\ngoto clear_hashmaps;\n}\n\nIt does not add duplicates to it, and we are only iterating on\nparent_hashmap in this loop, the tests i have added in v6 do fail on\nremoval of other string_list_remove duplicates lines in this file,\nhowever here i tried testing but i was not able to find a covering\ncase for this line.\n\n> Keep in mind that you're not actually testing the 'list' command, because\n> the 'add' command already deduplicated. You'll need to modify the\n> sparse-checkout file itself to get an interesting test of the 'list'\n> command.\n>\n> When not in cone mode, we should not be removing duplicates because the\n> order of the patterns matters and we should not be reordering them. I'm\n> not sure if that's relevant but it's something to keep in mind while you're\n> testing, since the command will revert to non-cone mode if the\n> sparse-checkout file doesn't match the cone mode pattern expectations.\n>\n> Thanks,\n> -Stolee\n\nThank you it was a bit tricky to make the test fail directly on list\ncommand, i was able to do it in v6 after this guidance.\n"},{"id":"534286","messageId":"8a4430e9-26d6-4bc5-bb5d-9896c2a2df9f@gmail.com","threadId":"64804","inReplyTo":"20260120153829.48044-1-amishhhaaaa@gmail.com","subject":"Re: [PATCH v6] sparse-checkout: optimize string_list construction and add tests to verify deduplication.","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-01-20T20:37:59Z","receivedAt":"2026-01-20T20:38:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/20/2026 10:38 AM, amisha wrote:\n> From: Amisha Chhajed <amishhhaaaa@gmail.com>\n\nCode is the same as last time, which is good.\n\n> +test_expect_success 'sparse-checkout deduplicates repeated cone patterns' '\n> +    rm -f repo/.git/info/sparse-checkout &&\n> +    git -C repo sparse-checkout init --cone &&\n> +    git -C repo sparse-checkout add --stdin <<-\\EOF &&\n> +\tfoo/bar/baz\n> +\ta/b/c\n> +\tfoo/bar/baz\n> +\ta/b\n> +\tEOF\n> +    cat >expect <<-\\EOF &&\n> +\t/*\n> +\t!/*/\n> +\t/a/\n> +\t!/a/*/\n> +\t/foo/\n> +\t!/foo/*/\n> +\t/foo/bar/\n> +\t!/foo/bar/*/\n> +\t/a/b/\n> +\t/foo/bar/baz/\n> +\tEOF\n> +    test_cmp expect repo/.git/info/sparse-checkout\n> +'\n> +\n> +test_expect_success 'sparse-checkout list deduplicates repeated cone patterns' '\n> +    rm -f repo/.git/info/sparse-checkout &&\n> +    git -C repo sparse-checkout init --cone &&\n> +    cat <<-\\EOF >repo/.git/info/sparse-checkout &&\n> +\t/*\n> +\t!/*/\n> +\t/a/\n> +\t!/a/*/\n> +\t/foo/\n> +\t!/foo/*/\n> +\t/foo/bar/\n> +\t!/foo/bar/*/\n> +\t/a/b/\n> +\t/foo/bar/baz/\n> +\t/foo/bar/baz/\n> +\tEOF\n> +    git -C repo sparse-checkout list >actual &&\n> +    cat <<-\\EOF >expect &&\n> +\ta/b\n> +\tfoo/bar/baz\n> +\tEOF\n> +    test_cmp expect actual\n> +'\n> +\n\nThese tests have the right structure, but there's a problem: it appears\nthat you've used four spaces for the first level of indent and then\nuse 8-width tabs for the next level. You can see that it disagrees with\nthe last line of the previous test in the diff context. This should be\nfixed, and likely \"git rebase --whitespace=fix\" is how you landed on\nthe current use of tab characters.\n\nI think the content between the EOFs shouldn't be indented more than\nthe 'cat' it's a part of, but I could be incorrect there.\n\nOutside of the whitespace issues, I think this test looks good.\n\nThanks,\n-Stolee\n\n"},{"id":"534347","messageId":"20260121130005.72375-1-amishhhaaaa@gmail.com","threadId":"64804","inReplyTo":"20260120153829.48044-1-amishhhaaaa@gmail.com","subject":"[PATCH v7] sparse-checkout: optimize string_list construction and add tests to verify deduplication.","fromName":"Amisha Chhajed","fromEmail":"amishhhaaaa@gmail.com","sentAt":"2026-01-21T13:00:05Z","receivedAt":"2026-01-21T13:00:16Z","isPatch":true,"sender":{"key":"amishhhaaaa@gmail.com","avatar":"https://avatars.githubusercontent.com/u/136238836?v=4"},"body":"Improve O(n^2) complexity to O(n log n) while building a sorted\n'string_list' by constructing it unsorted then sorting it\nfollowed by removing duplicates.\n\nsparse-checkout deduplicates repeated cone-mode patterns,\nbut this behaviour was previously untested, add tests that\nverify that sparse-checkout file contain each cone\npattern only once and sparse-checkout list reports each pattern\nonly once.\n\nSigned-off-by: Amisha Chhajed <amishhhaaaa@gmail.com>\n---\n builtin/sparse-checkout.c          |  7 +++--\n t/t1091-sparse-checkout-builtin.sh | 48 ++++++++++++++++++++++++++++++\n 2 files changed, 52 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c\nindex 15d51e60a8..7dfb276bf0 100644\n--- a/builtin/sparse-checkout.c\n+++ b/builtin/sparse-checkout.c\n@@ -91,10 +91,11 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix,\n \n \t\thashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) {\n \t\t\t/* pe->pattern starts with \"/\", skip it */\n-\t\t\tstring_list_insert(&sl, pe->pattern + 1);\n+\t\t\tstring_list_append(&sl, pe->pattern + 1);\n \t\t}\n \n \t\tstring_list_sort(&sl);\n+\t\tstring_list_remove_duplicates(&sl, 0);\n \n \t\tfor (i = 0; i < sl.nr; i++) {\n \t\t\tquote_c_style(sl.items[i].string, NULL, stdout, 0);\n@@ -289,7 +290,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstring_list_sort(&sl);\n@@ -311,7 +312,7 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl)\n \t\tif (!hashmap_contains_parent(&pl->recursive_hashmap,\n \t\t\t\t\t     pe->pattern,\n \t\t\t\t\t     &parent_pattern))\n-\t\t\tstring_list_insert(&sl, pe->pattern);\n+\t\t\tstring_list_append(&sl, pe->pattern);\n \t}\n \n \tstrbuf_release(&parent_pattern);\ndiff --git a/t/t1091-sparse-checkout-builtin.sh b/t/t1091-sparse-checkout-builtin.sh\nindex b2da4feaef..cd0aed9975 100755\n--- a/t/t1091-sparse-checkout-builtin.sh\n+++ b/t/t1091-sparse-checkout-builtin.sh\n@@ -817,6 +817,54 @@ test_expect_success 'cone mode clears ignored subdirectories' '\n \ttest_cmp expect out\n '\n \n+test_expect_success 'sparse-checkout deduplicates repeated cone patterns' '\n+\trm -f repo/.git/info/sparse-checkout &&\n+\tgit -C repo sparse-checkout init --cone &&\n+\tgit -C repo sparse-checkout add --stdin <<-\\EOF &&\n+\tfoo/bar/baz\n+\ta/b/c\n+\tfoo/bar/baz\n+\ta/b\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\t/*\n+\t!/*/\n+\t/a/\n+\t!/a/*/\n+\t/foo/\n+\t!/foo/*/\n+\t/foo/bar/\n+\t!/foo/bar/*/\n+\t/a/b/\n+\t/foo/bar/baz/\n+\tEOF\n+\ttest_cmp expect repo/.git/info/sparse-checkout\n+'\n+\n+test_expect_success 'sparse-checkout list deduplicates repeated cone patterns' '\n+\trm -f repo/.git/info/sparse-checkout &&\n+\tgit -C repo sparse-checkout init --cone &&\n+\tcat <<-\\EOF >repo/.git/info/sparse-checkout &&\n+\t/*\n+\t!/*/\n+\t/a/\n+\t!/a/*/\n+\t/foo/\n+\t!/foo/*/\n+\t/foo/bar/\n+\t!/foo/bar/*/\n+\t/a/b/\n+\t/foo/bar/baz/\n+\t/foo/bar/baz/\n+\tEOF\n+\tgit -C repo sparse-checkout list >actual &&\n+\tcat <<-\\EOF >expect &&\n+\ta/b\n+\tfoo/bar/baz\n+\tEOF\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success 'malformed cone-mode patterns' '\n \tgit -C repo sparse-checkout init --cone &&\n \tmkdir -p repo/foo/bar &&\n-- \n2.51.0\n\n"},{"id":"534363","messageId":"615b31c3-a47a-43bc-8dcf-7943ead101a7@gmail.com","threadId":"64804","inReplyTo":"20260121130005.72375-1-amishhhaaaa@gmail.com","subject":"Re: [PATCH v7] sparse-checkout: optimize string_list construction and add tests to verify deduplication.","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-01-21T16:28:06Z","receivedAt":"2026-01-21T16:28:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/21/2026 8:00 AM, Amisha Chhajed wrote:\n> Improve O(n^2) complexity to O(n log n) while building a sorted\n> 'string_list' by constructing it unsorted then sorting it\n> followed by removing duplicates.\n\nThanks for iterating on this. I think v7 is good to go.\n\nThanks,\n-Stolee\n\n"},{"id":"534365","messageId":"xmqqqzrivrh4.fsf@gitster.g","threadId":"64804","inReplyTo":"615b31c3-a47a-43bc-8dcf-7943ead101a7@gmail.com","subject":"Re: [PATCH v7] sparse-checkout: optimize string_list construction and add tests to verify deduplication.","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-01-21T16:51:51Z","receivedAt":"2026-01-21T16:51:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n> On 1/21/2026 8:00 AM, Amisha Chhajed wrote:\n>> Improve O(n^2) complexity to O(n log n) while building a sorted\n>> 'string_list' by constructing it unsorted then sorting it\n>> followed by removing duplicates.\n>\n> Thanks for iterating on this. I think v7 is good to go.\n>\n> Thanks,\n> -Stolee\n\nThanks, both.\n"}]}