From: Sahitya Chandra <sahityajb@gmail.com>
Date: Sat, 18 Jul 2026 08:05:01 GMT
Subject: Re: [PATCH v2] wt-status: avoid repeated insertion for untracked paths
Message-ID: <CAP=WS+tZuQyodN1_0Z4D7-uD9dpi9CKp8_sWvVTXqM6hWcwx6A@mail.gmail.com>
In-Reply-To: <20260718073135.GA22588@coredump.intra.peff.net>

On Sat, Jul 18, 2026 at 1:01 PM Jeff King <peff@peff.net> wrote:
> 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...]
>
> ?

Thanks, that wording makes sense. I will use that structure in v3, and
submit it right away :)