{"thread":{"id":"66023","subject":"[PATCH] wt-status: avoid quadratic insertion for untracked paths","startedAt":"2026-07-16T18:51:11Z","lastAt":"2026-07-18T08:38:29Z","messageCount":10,"participants":["Sahitya Chandra","Patrick Steinhardt","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"548446","messageId":"20260716185045.229320-1-sahityajb@gmail.com","threadId":"66023","inReplyTo":null,"subject":"[PATCH] wt-status: avoid quadratic insertion for untracked paths","fromName":"Sahitya Chandra","fromEmail":"sahityajb@gmail.com","sentAt":"2026-07-16T18:50:45Z","receivedAt":"2026-07-16T18:51:11Z","isPatch":true,"body":"wt_status_collect_untracked() copies entries from dir.entries and\ndir.ignored into string_lists using string_list_insert(). That keeps the\ndestination lists sorted and deduplicated, but each insertion may shift\nthe backing array, making construction O(n^2) in the number of paths.\n\nCollect the entries with string_list_append() instead, then sort and\ndeduplicate each list once. This preserves the sorted, duplicate-free\nresult while reducing the construction cost to O(n log n).\n\nSigned-off-by: Sahitya Chandra <sahityajb@gmail.com>\n---\nNotes for reviewers:\n\nfill_directory() currently sorts dir.entries and dir.ignored\nbefore returning, so another possible approach would be to append the\nentries directly and rely on that order, reducing this copy step to O(n).\nThat would require relying on these arrays not containing duplicate\nentries, though, which I have not been able to verify yet. This patch\ntakes the safer approach of preserving the existing duplicate-removal\nbehavior from `string_list_insert()` by sorting and deduplicating once\nafter appending.\n\n wt-status.c | 8 ++++++--\n 1 file changed, 6 insertions(+), 2 deletions(-)\n\ndiff --git a/wt-status.c b/wt-status.c\nindex 58461e02f8..13a7cf7946 100644\n--- a/wt-status.c\n+++ b/wt-status.c\n@@ -832,14 +832,18 @@ static void wt_status_collect_untracked(struct wt_status *s)\n \tfor (i = 0; i < dir.nr; i++) {\n \t\tstruct dir_entry *ent = dir.entries[i];\n \t\tif (index_name_is_other(istate, ent->name, ent->len))\n-\t\t\tstring_list_insert(&s->untracked, ent->name);\n+\t\t\tstring_list_append(&s->untracked, ent->name);\n \t}\n+\tstring_list_sort(&s->untracked);\n+\tstring_list_remove_duplicates(&s->untracked, 0);\n \n \tfor (i = 0; i < dir.ignored_nr; i++) {\n \t\tstruct dir_entry *ent = dir.ignored[i];\n \t\tif (index_name_is_other(istate, ent->name, ent->len))\n-\t\t\tstring_list_insert(&s->ignored, ent->name);\n+\t\t\tstring_list_append(&s->ignored, ent->name);\n \t}\n+\tstring_list_sort(&s->ignored);\n+\tstring_list_remove_duplicates(&s->ignored, 0);\n \n \tdir_clear(&dir);\n \n\nbase-commit: d35c5399e3e54ac277bb391fc2f6be3e816d312b\n-- \n2.43.0\n"},{"id":"548472","messageId":"alnLPSnOt_Sf7cA5@pks.im","threadId":"66023","inReplyTo":"20260716185045.229320-1-sahityajb@gmail.com","subject":"Re: [PATCH] wt-status: avoid quadratic insertion for untracked paths","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-07-17T06:27:09Z","receivedAt":"2026-07-17T06:27:16Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 12:20:45AM +0530, Sahitya Chandra wrote:\n> wt_status_collect_untracked() copies entries from dir.entries and\n> dir.ignored into string_lists using string_list_insert(). That keeps the\n> destination lists sorted and deduplicated, but each insertion may shift\n> the backing array, making construction O(n^2) in the number of paths.\n> \n> Collect the entries with string_list_append() instead, then sort and\n> deduplicate each list once. This preserves the sorted, duplicate-free\n> result while reducing the construction cost to O(n log n).\n> \n> Signed-off-by: Sahitya Chandra <sahityajb@gmail.com>\n> ---\n> Notes for reviewers:\n> \n> fill_directory() currently sorts dir.entries and dir.ignored\n> before returning, so another possible approach would be to append the\n> entries directly and rely on that order, reducing this copy step to O(n).\n> That would require relying on these arrays not containing duplicate\n> entries, though, which I have not been able to verify yet. This patch\n> takes the safer approach of preserving the existing duplicate-removal\n> behavior from `string_list_insert()` by sorting and deduplicating once\n> after appending.\n\nOut of curiosity: is this something that you have encountered in the\nreal world as inefficient, or is this rather a theoretical inefficiency?\nIf the former it would be great to add a small benchmark to the commit\nmessage.\n\n> diff --git a/wt-status.c b/wt-status.c\n> index 58461e02f8..13a7cf7946 100644\n> --- a/wt-status.c\n> +++ b/wt-status.c\n> @@ -832,14 +832,18 @@ static void wt_status_collect_untracked(struct wt_status *s)\n>  \tfor (i = 0; i < dir.nr; i++) {\n>  \t\tstruct dir_entry *ent = dir.entries[i];\n>  \t\tif (index_name_is_other(istate, ent->name, ent->len))\n> -\t\t\tstring_list_insert(&s->untracked, ent->name);\n> +\t\t\tstring_list_append(&s->untracked, ent->name);\n>  \t}\n> +\tstring_list_sort(&s->untracked);\n> +\tstring_list_remove_duplicates(&s->untracked, 0);\n\nInstead of sorting and then deduplicating you can call\n`string_list_sort_u()`. It does the exact same thing as you do here, but\nI guess it makes sense to use that interface anyway.\n\n>  \tfor (i = 0; i < dir.ignored_nr; i++) {\n>  \t\tstruct dir_entry *ent = dir.ignored[i];\n>  \t\tif (index_name_is_other(istate, ent->name, ent->len))\n> -\t\t\tstring_list_insert(&s->ignored, ent->name);\n> +\t\t\tstring_list_append(&s->ignored, ent->name);\n>  \t}\n> +\tstring_list_sort(&s->ignored);\n> +\tstring_list_remove_duplicates(&s->ignored, 0);\n\nLikewise.\n\nOverall this looks like a sensible thing to do though. Thanks!\n\nPatrick\n"},{"id":"548479","messageId":"20260717075449.GA1832790@coredump.intra.peff.net","threadId":"66023","inReplyTo":"alnLPSnOt_Sf7cA5@pks.im","subject":"Re: [PATCH] wt-status: avoid quadratic insertion for untracked paths","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-07-17T07:54:49Z","receivedAt":"2026-07-17T07:54:52Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 08:27:09AM +0200, Patrick Steinhardt wrote:\n\n> > fill_directory() currently sorts dir.entries and dir.ignored\n> > before returning, so another possible approach would be to append the\n> > entries directly and rely on that order, reducing this copy step to O(n).\n> > That would require relying on these arrays not containing duplicate\n> > entries, though, which I have not been able to verify yet. This patch\n> > takes the safer approach of preserving the existing duplicate-removal\n> > behavior from `string_list_insert()` by sorting and deduplicating once\n> > after appending.\n> \n> Out of curiosity: is this something that you have encountered in the\n> real world as inefficient, or is this rather a theoretical inefficiency?\n> If the former it would be great to add a small benchmark to the commit\n> message.\n\nYeah, I had the same question, and tried for a moment to produce an\nexample before realizing that it probably is theoretical. If we are\nfeeding the entries in pre-sorted order then the insert is always O(1).\n\nI think it's still worth doing this, though, as it makes the result much\nmore obvious to analyze. I think it could even be O(n) if the sort\nimplementation is optimized under the hood for pre-sorted inputs.\n\n-Peff\n"},{"id":"548510","messageId":"CAP=WS+tb-HnMmOjH7i+ZY0EBOT0xfDPi4wsTboiH0mRtCCs=ng@mail.gmail.com","threadId":"66023","inReplyTo":"alnLPSnOt_Sf7cA5@pks.im","subject":"Re: [PATCH] wt-status: avoid quadratic insertion for untracked paths","fromName":"Sahitya Chandra","fromEmail":"sahityajb@gmail.com","sentAt":"2026-07-17T14:37:31Z","receivedAt":"2026-07-17T14:37:45Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 11:57 AM Patrick Steinhardt <ps@pks.im> wrote:\n> Out of curiosity: is this something that you have encountered in the\n> real world as inefficient, or is this rather a theoretical inefficiency?\n> If the former it would be great to add a small benchmark to the commit\n> message.\n\nThanks for asking. I do not have a real-world benchmark for this. After\nJeff's reply, I agree that the O(n^2) claim is too strong for the current\ncode path because fill_directory() already returns the entries sorted, so\nstring_list_insert() should usually append at the end.\n\nI have reworded v2 to avoid that performance claim and describe the\nchange as making the collection strategy explicit instead.\n\n> Instead of sorting and then deduplicating you can call\n> `string_list_sort_u()`. It does the exact same thing as you do here, but\n> I guess it makes sense to use that interface anyway.\n\nDone in v2. Thanks.\n"},{"id":"548511","messageId":"CAP=WS+uWJJ3MY9K3JX-PQo_pKimNtyCO_fTdFsA=AXqbzO-bLg@mail.gmail.com","threadId":"66023","inReplyTo":"20260717075449.GA1832790@coredump.intra.peff.net","subject":"Re: [PATCH] wt-status: avoid quadratic insertion for untracked paths","fromName":"Sahitya Chandra","fromEmail":"sahityajb@gmail.com","sentAt":"2026-07-17T14:40:55Z","receivedAt":"2026-07-17T14:41:10Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 1:24 PM Jeff King <peff@peff.net> wrote:\n> Yeah, I had the same question, and tried for a moment to produce an\n> example before realizing that it probably is theoretical. If we are\n> feeding the entries in pre-sorted order then the insert is always O(1).\n>\n> I think it's still worth doing this, though, as it makes the result much\n> more obvious to analyze. I think it could even be O(n) if the sort\n> implementation is optimized under the hood for pre-sorted inputs.\n\nThanks, that makes sense. I updated v2 to avoid claiming this is a\ncurrent O(n^2) problem and instead frame it as making the append, sort,\nand deduplicate steps explicit.\n\nI also switched to string_list_sort_u() as Patrick suggested.\n"},{"id":"548512","messageId":"20260717144620.259031-1-sahityajb@gmail.com","threadId":"66023","inReplyTo":"20260716185045.229320-1-sahityajb@gmail.com","subject":"[PATCH v2] wt-status: avoid repeated insertion for untracked paths","fromName":"Sahitya Chandra","fromEmail":"sahityajb@gmail.com","sentAt":"2026-07-17T14:46:20Z","receivedAt":"2026-07-17T14:46:32Z","isPatch":true,"body":"wt_status_collect_untracked() copies entries from dir.entries and\ndir.ignored into string_lists using string_list_insert(). That keeps the\ndestination lists sorted and deduplicated, but makes the code harder to\nreason about because it rebuilds sorted lists through repeated sorted\ninsertion.\n\nCollect the entries with string_list_append() instead, then sort and\ndeduplicate each list once with string_list_sort_u(). This preserves the\nsorted, duplicate-free result while making the collection strategy explicit.\n\nSigned-off-by: Sahitya Chandra <sahityajb@gmail.com>\n---\nChanges since v1:\n- Use string_list_sort_u() instead of open-coding sort plus deduplication.\n- Reword the subject and commit message to avoid overclaiming an O(n^2)\n  cost when the input from fill_directory() is already sorted.\n\n wt-status.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/wt-status.c b/wt-status.c\nindex 58461e02f8..57772c7501 100644\n--- a/wt-status.c\n+++ b/wt-status.c\n@@ -832,14 +832,16 @@ static void wt_status_collect_untracked(struct wt_status *s)\n \tfor (i = 0; i < dir.nr; i++) {\n \t\tstruct dir_entry *ent = dir.entries[i];\n \t\tif (index_name_is_other(istate, ent->name, ent->len))\n-\t\t\tstring_list_insert(&s->untracked, ent->name);\n+\t\t\tstring_list_append(&s->untracked, ent->name);\n \t}\n+\tstring_list_sort_u(&s->untracked, 0);\n \n \tfor (i = 0; i < dir.ignored_nr; i++) {\n \t\tstruct dir_entry *ent = dir.ignored[i];\n \t\tif (index_name_is_other(istate, ent->name, ent->len))\n-\t\t\tstring_list_insert(&s->ignored, ent->name);\n+\t\t\tstring_list_append(&s->ignored, ent->name);\n \t}\n+\tstring_list_sort_u(&s->ignored, 0);\n \n \tdir_clear(&dir);\n \n\nbase-commit: 44de1520f08d1dfebc3ab2d9f644208eaa5ac925\n-- \n2.43.0\n"},{"id":"548568","messageId":"20260718073135.GA22588@coredump.intra.peff.net","threadId":"66023","inReplyTo":"20260717144620.259031-1-sahityajb@gmail.com","subject":"Re: [PATCH v2] wt-status: avoid repeated insertion for untracked paths","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-07-18T07:31:35Z","receivedAt":"2026-07-18T07:31:42Z","isPatch":true,"body":"On Fri, Jul 17, 2026 at 08:16:20PM +0530, Sahitya Chandra wrote:\n\n> wt_status_collect_untracked() copies entries from dir.entries and\n> dir.ignored into string_lists using string_list_insert(). That keeps the\n> destination lists sorted and deduplicated, but makes the code harder to\n> reason about because it rebuilds sorted lists through repeated sorted\n> insertion.\n> \n> Collect the entries with string_list_append() instead, then sort and\n> deduplicate each list once with string_list_sort_u(). This preserves the\n> sorted, duplicate-free result while making the collection strategy explicit.\n\nThe patch looks good, and I think this explanation is OK-ish. But IMHO\nit is still worth talking about the quadratic issue, because that's\nreally the motivation here (and what the \"harder to reason about\" is\ngetting at).\n\nSo maybe something like:\n\n  wt_status_collect_untracked() copies entries from dir.entries and\n  dir.ignored into string_lists using string_list_insert(). At first\n  glance this seems to be quadratic, because we may shift the backing\n  array, incurring O(n) work for each insert.\n\n  In practice, though, the entries in the dir struct are already sorted,\n  so each we never have to shift the array (and only pay the log-n\n  lookup cost for each insertion). But this is subtle and depends on the\n  behavior of fill_directory().\n\n  Collect the entries[...etc...]\n\n?\n\n-Peff\n"},{"id":"548570","messageId":"CAP=WS+tZuQyodN1_0Z4D7-uD9dpi9CKp8_sWvVTXqM6hWcwx6A@mail.gmail.com","threadId":"66023","inReplyTo":"20260718073135.GA22588@coredump.intra.peff.net","subject":"Re: [PATCH v2] wt-status: avoid repeated insertion for untracked paths","fromName":"Sahitya Chandra","fromEmail":"sahityajb@gmail.com","sentAt":"2026-07-18T08:05:01Z","receivedAt":"2026-07-18T08:05:15Z","isPatch":true,"body":"On Sat, Jul 18, 2026 at 1:01 PM Jeff King <peff@peff.net> wrote:\n> The patch looks good, and I think this explanation is OK-ish. But IMHO\n> it is still worth talking about the quadratic issue, because that's\n> really the motivation here (and what the \"harder to reason about\" is\n> getting at).\n>\n> So maybe something like:\n>\n>   wt_status_collect_untracked() copies entries from dir.entries and\n>   dir.ignored into string_lists using string_list_insert(). At first\n>   glance this seems to be quadratic, because we may shift the backing\n>   array, incurring O(n) work for each insert.\n>\n>   In practice, though, the entries in the dir struct are already sorted,\n>   so each we never have to shift the array (and only pay the log-n\n>   lookup cost for each insertion). But this is subtle and depends on the\n>   behavior of fill_directory().\n>\n>   Collect the entries[...etc...]\n>\n> ?\n\nThanks, that wording makes sense. I will use that structure in v3, and\nsubmit it right away :)\n"},{"id":"548573","messageId":"20260718081449.26747-1-sahityajb@gmail.com","threadId":"66023","inReplyTo":"20260717144620.259031-1-sahityajb@gmail.com","subject":"[PATCH v3] wt-status: avoid repeated insertion for untracked paths","fromName":"Sahitya Chandra","fromEmail":"sahityajb@gmail.com","sentAt":"2026-07-18T08:14:49Z","receivedAt":"2026-07-18T08:15:28Z","isPatch":true,"body":"wt_status_collect_untracked() copies entries from dir.entries and\ndir.ignored into string_lists using string_list_insert(). At first glance\nthis seems quadratic, because inserting into the sorted list may shift the\nbacking array, incurring O(n) work for each insert.\n\nIn practice, though, the entries in the dir struct are already sorted, so\nwe should not have to shift the array and only pay the O(log n) lookup cost\nfor each insertion. But this is subtle and depends on the behavior of\nfill_directory().\n\nCollect the entries with string_list_append() instead, then sort and\ndeduplicate each list once with string_list_sort_u(). This preserves the\nsorted, duplicate-free result while making the collection strategy explicit.\n\nSigned-off-by: Sahitya Chandra <sahityajb@gmail.com>\n---\nChanges since v2:\n- Reword the commit message to explain the quadratic concern while noting\n  that the current sorted input avoids array shifts in practice.\n\n wt-status.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/wt-status.c b/wt-status.c\nindex 58461e02f8..57772c7501 100644\n--- a/wt-status.c\n+++ b/wt-status.c\n@@ -832,14 +832,16 @@ static void wt_status_collect_untracked(struct wt_status *s)\n \tfor (i = 0; i < dir.nr; i++) {\n \t\tstruct dir_entry *ent = dir.entries[i];\n \t\tif (index_name_is_other(istate, ent->name, ent->len))\n-\t\t\tstring_list_insert(&s->untracked, ent->name);\n+\t\t\tstring_list_append(&s->untracked, ent->name);\n \t}\n+\tstring_list_sort_u(&s->untracked, 0);\n \n \tfor (i = 0; i < dir.ignored_nr; i++) {\n \t\tstruct dir_entry *ent = dir.ignored[i];\n \t\tif (index_name_is_other(istate, ent->name, ent->len))\n-\t\t\tstring_list_insert(&s->ignored, ent->name);\n+\t\t\tstring_list_append(&s->ignored, ent->name);\n \t}\n+\tstring_list_sort_u(&s->ignored, 0);\n \n \tdir_clear(&dir);\n \n\nbase-commit: 41365c2a9ba347870b80881c0d67454edd22fd49\n-- \n2.43.0\n"},{"id":"548576","messageId":"20260718083828.GE22588@coredump.intra.peff.net","threadId":"66023","inReplyTo":"20260718081449.26747-1-sahityajb@gmail.com","subject":"Re: [PATCH v3] wt-status: avoid repeated insertion for untracked paths","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2026-07-18T08:38:28Z","receivedAt":"2026-07-18T08:38:29Z","isPatch":true,"body":"On Sat, Jul 18, 2026 at 01:44:49PM +0530, Sahitya Chandra wrote:\n\n> - Reword the commit message to explain the quadratic concern while noting\n>   that the current sorted input avoids array shifts in practice.\n\nLooks good to me. ;)\n\n-Peff\n"}]}