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

From: Derrick Stolee <stolee@gmail.com>
Date: Jan 18, 2026, 02:39 UTC
Message-ID: <9394755a-18db-4efd-b7c8-ce38eab57f04@gmail.com>
In-Reply-To: <20260114213551.GC1010080@coredump.intra.peff.net>

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.

...

Show 14 quoted lines

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