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

From: Junio C Hamano <gitster@pobox.com>
Date: Jan 19, 2026, 19:06 UTC
Message-ID: <xmqqy0lt4e36.fsf@gitster.g>
In-Reply-To: <20260119053251.GA1991605@coredump.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 14 quoted lines

> On Fri, Jan 16, 2026 at 11:11:16AM -0800, Junio C Hamano wrote:
>
>> > Improve O(n^2) complexity to O(n log n) while building a sorted
>> > 'string_list' by constructing it unsorted then sorting it
>> > followed by removing duplicates.
>> 
>> By the way, do we have t/perf/ that substanticates the performance
>> claim here (in other words, how much improvement are we expecting in
>> practice)?
>
> IMHO it is not that big a deal to demonstrate the perf improvement in
> the test suite.
> ... a one-off hyperfine output in the commit message would be
> enough.

Thanks, I agree with this conclusion; I didn't expect a huge difference from this change unless N is meaningfully large anyway.