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

From: Derrick Stolee <[email-masked]>
Date: Sat, 17 Jan 2026 21:39:27 -0500

On 1/14/26 4:35 PM, Jeff King wrote:
> On Thu, Jan 15, 2026 at 12:58:03AM +0530, 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.
...
>>   		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);
> 
> Since we already sort here, I was quite curious how this came about.  It
> looks like the _insert() call and the _sort() were both added together
> in de11951b03 (sparse-checkout: list directories in cone mode,
> 2019-12-30).
> 
> I'd guess it was just a typo/brain-o to mix up append and insert.

This is exactly the case.

> Doesn't the same issue exist in write_cone_to_file(), too (in two
> separate spots)?

It would make sense that such a pattern could reappear in other areas
in this file. I see that you have caught a few more in v3.

Thanks,
-Stolee