[PATCH] wt-status: avoid quadratic insertion for untracked paths
- From
Sahitya Chandra <sahityajb@gmail.com>
- Date
- Jul 16, 2026, 18:50 UTC
- Message-ID
- <20260716185045.229320-1-sahityajb@gmail.com>
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