From: René Scharfe Date: Thu, 15 Jan 2026 22:26:49 GMT Subject: Re: [PATCH v3] sparse-checkout: optimize string_list construction Message-ID: In-Reply-To: On 1/15/26 2:15 PM, Amisha Chhajed wrote: > Made the changes for other 2 places as well! > > I was also very curious about the presence of > string_list_remove_duplicates in the original code, from my > understanding string_list_insert already removed duplicates and > string_list_remove_duplicates was still present with it. So the string_list_remove_duplicates() calls were unnecessary with string_list_insert(), but why is it safe to remove them now that you use string_list_append() instead, which doesn't check for duplicates? > > On Thu, 15 Jan 2026 at 18:39, amisha wrote: >> >> Improve O(n^2) complexity to O(n log n) while building a sorted 'string_list' >> by constructing it unsorted and sorting it afterwards. >> >> Signed-off-by: Amisha Chhajed >> --- >> builtin/sparse-checkout.c | 8 +++----- >> 1 file changed, 3 insertions(+), 5 deletions(-) >> >> diff --git a/builtin/sparse-checkout.c b/builtin/sparse-checkout.c >> index 15d51e60a8..edabe7cbd9 100644 >> --- a/builtin/sparse-checkout.c >> +++ b/builtin/sparse-checkout.c >> @@ -91,7 +91,7 @@ static int sparse_checkout_list(int argc, const char **argv, const char *prefix, >> >> hashmap_for_each_entry(&pl.recursive_hashmap, &iter, pe, ent) { >> /* pe->pattern starts with "/", skip it */ >> - string_list_insert(&sl, pe->pattern + 1); >> + string_list_append(&sl, pe->pattern + 1); >> } >> >> string_list_sort(&sl); >> @@ -289,11 +289,10 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl) >> if (!hashmap_contains_parent(&pl->recursive_hashmap, >> pe->pattern, >> &parent_pattern)) >> - string_list_insert(&sl, pe->pattern); >> + string_list_append(&sl, pe->pattern); >> } >> >> string_list_sort(&sl); >> - string_list_remove_duplicates(&sl, 0); >> >> fprintf(fp, "/*\n!/*/\n"); >> >> @@ -311,13 +310,12 @@ static void write_cone_to_file(FILE *fp, struct pattern_list *pl) >> if (!hashmap_contains_parent(&pl->recursive_hashmap, >> pe->pattern, >> &parent_pattern)) >> - string_list_insert(&sl, pe->pattern); >> + string_list_append(&sl, pe->pattern); >> } >> >> strbuf_release(&parent_pattern); >> >> string_list_sort(&sl); >> - string_list_remove_duplicates(&sl, 0); >> >> for (i = 0; i < sl.nr; i++) { >> char *pattern = escaped_pattern(sl.items[i].string); >> -- >> 2.51.0 >>