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

[Jeff King <peff@peff.net>]

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

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