From: Jeff King <peff@peff.net>
Date: Mon, 19 Jan 2026 05:32:51 GMT
Subject: Re: [PATCH] sparse-checkout: optimize string_list construction
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:

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