From: Patrick Steinhardt <ps@pks.im>
Date: Fri, 17 Jul 2026 06:27:09 GMT
Subject: Re: [PATCH] wt-status: avoid quadratic insertion for untracked paths
Message-ID: <alnLPSnOt_Sf7cA5@pks.im>
In-Reply-To: <20260716185045.229320-1-sahityajb@gmail.com>

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