Skip to contentSkip to conversation

wt-status: avoid quadratic insertion for untracked paths

PATCH Superseded Sahitya Chandra 3 participants 10 messages Jul 16 – Jul 18

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 wt-status: avoid quadratic insertion for untracked paths

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).

---
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(-)
wt-status.c +6 -2
index 58461e02f8..13a7cf7946 100644
@@ -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

Signature · 1 line
2.43.0
#1 lore raw
Quoted 13 lines · 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).

---
Notes for reviewers:

Quoted 8 lines

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.

wt-status.c static void wt_status_collect_untracked(struct wt_status *s) · line 838

Quoted 13 lines
wt-status.c +3 -1
index 58461e02f8..13a7cf7946 100644
@@ -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.

wt-status.c static void wt_status_collect_untracked(struct wt_status *s) · line 846

Quoted 8 lines
wt-status.c +3 -1
 	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

#2 lore raw
Quoted 9 lines · Patrick Steinhardt
Quoted 8 lines

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.

Quoted 4 lines

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

#3 lore raw
Quoted 7 lines · Jeff King

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.

Thanks, that makes sense. I updated v2 to avoid claiming this is a current O(n^2) problem and instead frame it as making the append, sort, and deduplicate steps explicit.

I also switched to string_list_sort_u() as Patrick suggested.

#4 lore raw
In reply to Patrick Steinhardt
Quoted 4 lines · Patrick Steinhardt

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.

Thanks for asking. I do not have a real-world benchmark for this. After Jeff's reply, I agree that the O(n^2) claim is too strong for the current code path because fill_directory() already returns the entries sorted, so string_list_insert() should usually append at the end.

I have reworded v2 to avoid that performance claim and describe the change as making the collection strategy explicit instead.

Quoted 3 lines

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.

Done in v2. Thanks.

#5 lore raw

PATCH v2 1/1 wt-status: avoid repeated insertion for untracked paths

In reply to 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 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.

---
Changes since v1:
- Use string_list_sort_u() instead of open-coding sort plus deduplication.
- Reword the subject and commit message to avoid overclaiming an O(n^2) cost when the input from fill_directory() is already sorted.

 wt-status.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
wt-status.c +4 -2
index 58461e02f8..57772c7501 100644
@@ -832,14 +832,16 @@ 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_u(&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_u(&s->ignored, 0);
 
 	dir_clear(&dir);
 

base-commit: 44de1520f08d1dfebc3ab2d9f644208eaa5ac925

Signature · 1 line
2.43.0
#6 lore raw

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

Quoted 9 lines · 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 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

#7 lore raw

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

Quoted 12 lines · Jeff King

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.

Quoted 8 lines

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 :)

#8 lore raw

PATCH v3 1/1 wt-status: avoid repeated insertion for untracked paths

In reply to Sahitya Chandra

wt_status_collect_untracked() copies entries from dir.entries and dir.ignored into string_lists using string_list_insert(). At first glance this seems quadratic, because inserting into the sorted list 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 we should not have to shift the array and only pay the O(log n) lookup cost for each insertion. But this is subtle and depends on the behavior of fill_directory().

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.

---
Changes since v2:
- Reword the commit message to explain the quadratic concern while noting that the current sorted input avoids array shifts in practice.

 wt-status.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)
wt-status.c +4 -2
index 58461e02f8..57772c7501 100644
@@ -832,14 +832,16 @@ 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_u(&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_u(&s->ignored, 0);
 
 	dir_clear(&dir);
 

base-commit: 41365c2a9ba347870b80881c0d67454edd22fd49

Signature · 1 line
2.43.0
#9 lore raw

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

Quoted 2 lines · Sahitya Chandra

- Reword the commit message to explain the quadratic concern while noting that the current sorted input avoids array shifts in practice.

Looks good to me. ;)

-Peff