Re: [PATCH] wt-status: avoid quadratic insertion for untracked paths

From: Jeff King <peff@peff.net>
Date: Jul 17, 2026, 07:54 UTC
Message-ID: <20260717075449.GA1832790@coredump.intra.peff.net>
In-Reply-To: <alnLPSnOt_Sf7cA5@pks.im>

On Fri, Jul 17, 2026 at 08:27:09AM +0200, Patrick Steinhardt wrote:

Show 13 quoted lines

> > fill_directory() currently sorts dir.entries and dir.ignored
> > before returning, so another possible approach would be to append the
> > entries directly and rely on that order, reducing this copy step to O(n).
> > That would require relying on these arrays not containing duplicate
> > entries, though, which I have not been able to verify yet. This patch
> > takes the safer approach of preserving the existing duplicate-removal
> > behavior from `string_list_insert()` by sorting and deduplicating once
> > after appending.
> 
> Out of curiosity: is this something that you have encountered in the
> real world as inefficient, or is this rather a theoretical inefficiency?
> If the former it would be great to add a small benchmark to the commit
> message.

Yeah, I had the same question, and tried for a moment to produce an example before realizing that it probably is theoretical. If we are feeding the entries in pre-sorted order then the insert is always O(1).

I think it's still worth doing this, though, as it makes the result much more obvious to analyze. I think it could even be O(n) if the sort implementation is optimized under the hood for pre-sorted inputs.

-Peff