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

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

[Sahitya Chandra]

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 each insertion may shift
the backing array, making construction O(n^2) in the number of paths.

Collect the entries with string_list_append() instead, then sort and
deduplicate each list once. This preserves the sorted, duplicate-free
result while reducing the construction cost to O(n log n).

Signed-off-by: Sahitya Chandra <sahityajb@gmail.com>
---
Notes for reviewers:

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.

 wt-status.c | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/wt-status.c b/wt-status.c
index 58461e02f8..13a7cf7946 100644
--- a/wt-status.c
+++ b/wt-status.c
@@ -832,14 +832,18 @@ static void wt_status_collect_untracked(struct wt_status *s)
 	for (i = 0; i < dir.nr; i++) {
 		struct dir_entry *ent = dir.entries[i];
 		if (index_name_is_other(istate, ent->name, ent->len))
-			string_list_insert(&s->untracked, ent->name);
+			string_list_append(&s->untracked, ent->name);
 	}
+	string_list_sort(&s->untracked);
+	string_list_remove_duplicates(&s->untracked, 0);
 
 	for (i = 0; i < dir.ignored_nr; i++) {
 		struct dir_entry *ent = dir.ignored[i];
 		if (index_name_is_other(istate, ent->name, ent->len))
-			string_list_insert(&s->ignored, ent->name);
+			string_list_append(&s->ignored, ent->name);
 	}
+	string_list_sort(&s->ignored);
+	string_list_remove_duplicates(&s->ignored, 0);
 
 	dir_clear(&dir);
 

base-commit: d35c5399e3e54ac277bb391fc2f6be3e816d312b
-- 
2.43.0

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

[Patrick Steinhardt]

On Fri, Jul 17, 2026 at 12:20:45AM +0530, Sahitya Chandra wrote:
> 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 each insertion may shift
> the backing array, making construction O(n^2) in the number of paths.
> 
> Collect the entries with string_list_append() instead, then sort and
> deduplicate each list once. This preserves the sorted, duplicate-free
> result while reducing the construction cost to O(n log n).
> 
> Signed-off-by: Sahitya Chandra <sahityajb@gmail.com>
> ---
> Notes for reviewers:
> 
> 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.

> diff --git a/wt-status.c b/wt-status.c
> index 58461e02f8..13a7cf7946 100644
> --- a/wt-status.c
> +++ b/wt-status.c
> @@ -832,14 +832,18 @@ static void wt_status_collect_untracked(struct wt_status *s)
>  	for (i = 0; i < dir.nr; i++) {
>  		struct dir_entry *ent = dir.entries[i];
>  		if (index_name_is_other(istate, ent->name, ent->len))
> -			string_list_insert(&s->untracked, ent->name);
> +			string_list_append(&s->untracked, ent->name);
>  	}
> +	string_list_sort(&s->untracked);
> +	string_list_remove_duplicates(&s->untracked, 0);

Instead of sorting and then deduplicating you can call
`string_list_sort_u()`. It does the exact same thing as you do here, but
I guess it makes sense to use that interface anyway.

>  	for (i = 0; i < dir.ignored_nr; i++) {
>  		struct dir_entry *ent = dir.ignored[i];
>  		if (index_name_is_other(istate, ent->name, ent->len))
> -			string_list_insert(&s->ignored, ent->name);
> +			string_list_append(&s->ignored, ent->name);
>  	}
> +	string_list_sort(&s->ignored);
> +	string_list_remove_duplicates(&s->ignored, 0);

Likewise.

Overall this looks like a sensible thing to do though. Thanks!

Patrick

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

[Jeff King]

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