From: Jeff King Date: Fri, 17 Jul 2026 07:54:49 GMT Subject: Re: [PATCH] wt-status: avoid quadratic insertion for untracked paths Message-ID: <20260717075449.GA1832790@coredump.intra.peff.net> In-Reply-To: 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