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

From: Jeff King <peff@peff.net>
Date: Jul 18, 2026, 07:31 UTC
Message-ID: <20260718073135.GA22588@coredump.intra.peff.net>
In-Reply-To: <20260717144620.259031-1-sahityajb@gmail.com>

On Fri, Jul 17, 2026 at 08:16:20PM +0530, Sahitya Chandra wrote:

Show 9 quoted lines

> wt_status_collect_untracked() copies entries from dir.entries and
> dir.ignored into string_lists using string_list_insert(). That keeps the
> destination lists sorted and deduplicated, but makes the code harder to
> reason about because it rebuilds sorted lists through repeated sorted
> insertion.
> 
> Collect the entries with string_list_append() instead, then sort and
> deduplicate each list once with string_list_sort_u(). This preserves the
> sorted, duplicate-free result while making the collection strategy explicit.

The patch looks good, and I think this explanation is OK-ish. But IMHO it is still worth talking about the quadratic issue, because that's really the motivation here (and what the "harder to reason about" is getting at).

So maybe something like:

  wt_status_collect_untracked() copies entries from dir.entries and
  dir.ignored into string_lists using string_list_insert(). At first
  glance this seems to be quadratic, because we may shift the backing
  array, incurring O(n) work for each insert.

  In practice, though, the entries in the dir struct are already sorted,
  so each we never have to shift the array (and only pay the log-n
  lookup cost for each insertion). But this is subtle and depends on the
  behavior of fill_directory().

  Collect the entries[...etc...]

-Peff