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

From: Jeff King <peff@peff.net>
Date: Jan 19, 2026, 05:32 UTC
Message-ID: <20260119053251.GA1991605@coredump.intra.peff.net>
In-Reply-To: <xmqqqzrp74q3.fsf@gitster.g>

On Fri, Jan 16, 2026 at 11:11:16AM -0800, Junio C Hamano wrote:

Show 7 quoted lines

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

Probably you could feed a very long list of unique names to "git sparse-checkout add --stdin" to trigger it. But a list long enough to cause annoying quadratic behavior is getting far enough from the real world that I'm not sure it is worth adding to the (already expensive) perf suite.

And swapping append+sort for sorted insertion is a common and simple improvement. We probably don't need to prove its performance at all, but if we do, a one-off hyperfine output in the commit message would be enough.

-Peff