Re: [PATCH v3] sparse-checkout: optimize string_list construction

From: René Scharfe <l.s.r@web.de>
Date: Jan 15, 2026, 22:26 UTC
Message-ID: <fc14e0e5-93bc-4805-a20d-d2aa4eb87ddb@web.de>
In-Reply-To: <CAPvEtreX9sGHUn7+Y0kLo_VnK7Y=OYLq-kz-+np3bu1QtoEpnA@mail.gmail.com>

On 1/15/26 2:15 PM, Amisha Chhajed wrote:

Show 6 quoted lines

> 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?

Show 55 quoted lines

> 
> On Thu, 15 Jan 2026 at 18:39, amisha <amishhhaaaa@gmail.com> 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 <amishhhaaaa@gmail.com>
>> ---
>>  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
>>