{"thread":{"id":"62937","subject":"[GSoC][PATCH] merge-recursive: optimize string_list construction","startedAt":"2025-02-11T19:43:42Z","lastAt":"2025-02-15T08:42:56Z","messageCount":17,"participants":["Meet Soni","Elijah Newren","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"512255","messageId":"20250211194334.20710-1-meetsoni3017@gmail.com","threadId":"62937","inReplyTo":null,"subject":"[GSoC][PATCH] merge-recursive: optimize string_list construction","fromName":"Meet Soni","fromEmail":"meetsoni3017@gmail.com","sentAt":"2025-02-11T19:43:34Z","receivedAt":"2025-02-11T19:43:42Z","isPatch":true,"sender":{"key":"meetsoni3017@gmail.com","avatar":"https://avatars.githubusercontent.com/u/92802561?v=4"},"body":"Avoid O(n^2) complexity when building a sorted `string_list` by\nconstructing it unsorted and sorting it afterward, reducing the\ncomplexity to O(n log n).\n\nSigned-off-by: Meet Soni \n---\n merge-recursive.c | 14 ++++----------\n 1 file changed, 4 insertions(+), 10 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 5dfaf32b2c..c43b79e6ef 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -2757,24 +2757,18 @@ static int process_renames(struct merge_options *opt,\n \tstruct string_list b_by_dst = STRING_LIST_INIT_NODUP;\n \tconst struct rename *sre;\n \n-\t/*\n-\t * FIXME: As string-list.h notes, it's O(n^2) to build a sorted\n-\t * string_list one-by-one, but O(n log n) to build it unsorted and\n-\t * then sort it. Note that as we build the list, we do not need to\n-\t * check if the existing destination path is already in the list,\n-\t * because the structure of diffcore_rename guarantees we won't\n-\t * have duplicates.\n-\t */\n \tfor (i = 0; i < a_renames->nr; i++) {\n \t\tsre = a_renames->items[i].util;\n-\t\tstring_list_insert(&a_by_dst, sre->pair->two->path)->util\n+\t\tstring_list_append(&a_by_dst, sre->pair->two->path)->util\n \t\t\t= (void *)sre;\n \t}\n \tfor (i = 0; i < b_renames->nr; i++) {\n \t\tsre = b_renames->items[i].util;\n-\t\tstring_list_insert(&b_by_dst, sre->pair->two->path)->util\n+\t\tstring_list_append(&b_by_dst, sre->pair->two->path)->util\n \t\t\t= (void *)sre;\n \t}\n+\tstring_list_sort(&a_by_dst);\n+\tstring_list_sort(&b_by_dst);\n \n \tfor (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {\n \t\tstruct string_list *renames1, *renames2Dst;\n\nbase-commit: 9520f7d9985d8879bddd157309928fc0679c8e92\n-- \n2.34.1\n\n"},{"id":"512257","messageId":"CABPp-BHMgTX2J4pRM=DjU-Ye46JtVZJsi95VUqcPHTcrzJgwOg@mail.gmail.com","threadId":"62937","inReplyTo":"20250211194334.20710-1-meetsoni3017@gmail.com","subject":"Re: [GSoC][PATCH] merge-recursive: optimize string_list construction","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-02-11T20:59:26Z","receivedAt":"2025-02-11T20:59:38Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Tue, Feb 11, 2025 at 11:43 AM Meet Soni wrote:\n>\n> Avoid O(n^2) complexity when building a sorted `string_list` by\n> constructing it unsorted and sorting it afterward, reducing the\n> complexity to O(n log n).\n\nI'm tempted to say merge-recursive.[ch] is nearly dead and planned for\nremoval, so there's not much value in messing with it, but...it's not\ndead yet, so I guess this is worthwhile.\n\n> Signed-off-by: Meet Soni \n> ---\n> merge-recursive.c | 14 ++++----------\n> 1 file changed, 4 insertions(+), 10 deletions(-)\n>\n> diff --git a/merge-recursive.c b/merge-recursive.c\n> index 5dfaf32b2c..c43b79e6ef 100644\n> --- a/merge-recursive.c\n> +++ b/merge-recursive.c\n> @@ -2757,24 +2757,18 @@ static int process_renames(struct merge_options *opt,\n> struct string_list b_by_dst = STRING_LIST_INIT_NODUP;\n> const struct rename *sre;\n>\n> - /*\n> - * FIXME: As string-list.h notes, it's O(n^2) to build a sorted\n> - * string_list one-by-one, but O(n log n) to build it unsorted and\n> - * then sort it. Note that as we build the list, we do not need to\n> - * check if the existing destination path is already in the list,\n> - * because the structure of diffcore_rename guarantees we won't\n> - * have duplicates.\n> - */\n> for (i = 0; i < a_renames->nr; i++) {\n> sre = a_renames->items[i].util;\n> - string_list_insert(&a_by_dst, sre->pair->two->path)->util\n> + string_list_append(&a_by_dst, sre->pair->two->path)->util\n> = (void *)sre;\n> }\n> for (i = 0; i < b_renames->nr; i++) {\n> sre = b_renames->items[i].util;\n> - string_list_insert(&b_by_dst, sre->pair->two->path)->util\n> + string_list_append(&b_by_dst, sre->pair->two->path)->util\n> = (void *)sre;\n> }\n> + string_list_sort(&a_by_dst);\n> + string_list_sort(&b_by_dst);\n\nIf the original source had duplicates, this would change behavior (the\ninsert function checks for duplicates while append does not).\nGranted, the comment above the block points out why there aren't\nduplicates, but will that be obvious to future readers now that you've\nremoved the whole comment?\n\nAlso, are the sources already sorted? If so, we can avoid the manual\nsort calls at the end, and drop this from O(n log n) to O(n). Digging\nthrough the code...it appears these are setup in get_renames() and are\nsorted but by pair->one->path rather than pair->two->path, so we do\nneed the sorts here.\n\nOf course, get_renames() itself utilizes string_list_insert() rather\nthan string_list_append. and there are a number of other\nstring_list_insert calls in the code (though some of the others might\nbe hard to restructure) -- perhaps the first line of your commit\nmessage should have a \"in process_renames\" qualifier, since it's only\naddressing one case?\n\nAnyway, other than perhaps tweaking the first line of the commit\nmessage, and not removing the whole comment, the patch looks good to\nme.\n"},{"id":"512350","messageId":"20250213090040.16133-1-meetsoni3017@gmail.com","threadId":"62937","inReplyTo":"20250211194334.20710-1-meetsoni3017@gmail.com","subject":"[RFC PATCH 0/2] merge-recursive: optimize time complexity","fromName":"Meet Soni","fromEmail":"meetsoni3017@gmail.com","sentAt":"2025-02-13T09:00:38Z","receivedAt":"2025-02-13T09:00:47Z","isPatch":true,"sender":{"key":"meetsoni3017@gmail.com","avatar":"https://avatars.githubusercontent.com/u/92802561?v=4"},"body":"changes in this version:\n - Updated comment and commit message as per review.\n - Added another commit implementing optimization logic.\n - added an RFC tag since, if the changes in 2nd commit are\n appropriate, we can apply similar logic in other places as\n well.\n\nMeet Soni (2):\n merge-recursive: optimize time complexity for process_renames\n merge-recursive: optimize time complexity for get_unmerged\n\n merge-recursive.c | 25 ++++++++++++-------------\n 1 file changed, 12 insertions(+), 13 deletions(-)\n\nRange-diff:\n1: ec96e4010e ! 1: c7dca6e971 merge-recursive: optimize string_list construction\n @@ Metadata\n Author: Meet Soni \n \n ## Commit message ##\n - merge-recursive: optimize string_list construction\n + merge-recursive: optimize time complexity for process_renames\n \n - Avoid O(n^2) complexity when building a sorted `string_list` by\n - constructing it unsorted and sorting it afterward, reducing the\n - complexity to O(n log n).\n + Avoid O(n^2) complexity in `process_renames()` when building a sorted\n + `string_list` by constructing it unsorted and sorting it afterward,\n + reducing the complexity to O(n log n).\n \n Signed-off-by: Meet Soni \n \n ## merge-recursive.c ##\n @@ merge-recursive.c: static int process_renames(struct merge_options *opt,\n - \tstruct string_list b_by_dst = STRING_LIST_INIT_NODUP;\n \tconst struct rename *sre;\n \n --\t/*\n + \t/*\n -\t * FIXME: As string-list.h notes, it's O(n^2) to build a sorted\n -\t * string_list one-by-one, but O(n log n) to build it unsorted and\n -\t * then sort it. Note that as we build the list, we do not need to\n -\t * check if the existing destination path is already in the list,\n -\t * because the structure of diffcore_rename guarantees we won't\n -\t * have duplicates.\n --\t */\n ++\t * Note that as we build the list, we do not need to check if the\n ++\t * existing destination path is already in the list, because the\n ++\t * structure of diffcore_rename guarantees we won't have duplicates.\n + \t */\n \tfor (i = 0; i < a_renames->nr; i++) {\n \t\tsre = a_renames->items[i].util;\n -\t\tstring_list_insert(&a_by_dst, sre->pair->two->path)->util\n-: ---------- > 2: 78a007be7d merge-recursive: optimize time complexity for get_unmerged\n-- \n2.34.1\n\n"},{"id":"512351","messageId":"20250213090040.16133-2-meetsoni3017@gmail.com","threadId":"62937","inReplyTo":"20250213090040.16133-1-meetsoni3017@gmail.com","subject":"[RFC PATCH 1/2] merge-recursive: optimize time complexity for process_renames","fromName":"Meet Soni","fromEmail":"meetsoni3017@gmail.com","sentAt":"2025-02-13T09:00:39Z","receivedAt":"2025-02-13T09:00:50Z","isPatch":true,"sender":{"key":"meetsoni3017@gmail.com","avatar":"https://avatars.githubusercontent.com/u/92802561?v=4"},"body":"Avoid O(n^2) complexity in `process_renames()` when building a sorted\n`string_list` by constructing it unsorted and sorting it afterward,\nreducing the complexity to O(n log n).\n\nSigned-off-by: Meet Soni \n---\n merge-recursive.c | 15 +++++++--------\n 1 file changed, 7 insertions(+), 8 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 5dfaf32b2c..884ccf99a5 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -2758,23 +2758,22 @@ static int process_renames(struct merge_options *opt,\n \tconst struct rename *sre;\n \n \t/*\n-\t * FIXME: As string-list.h notes, it's O(n^2) to build a sorted\n-\t * string_list one-by-one, but O(n log n) to build it unsorted and\n-\t * then sort it. Note that as we build the list, we do not need to\n-\t * check if the existing destination path is already in the list,\n-\t * because the structure of diffcore_rename guarantees we won't\n-\t * have duplicates.\n+\t * Note that as we build the list, we do not need to check if the\n+\t * existing destination path is already in the list, because the\n+\t * structure of diffcore_rename guarantees we won't have duplicates.\n \t */\n \tfor (i = 0; i < a_renames->nr; i++) {\n \t\tsre = a_renames->items[i].util;\n-\t\tstring_list_insert(&a_by_dst, sre->pair->two->path)->util\n+\t\tstring_list_append(&a_by_dst, sre->pair->two->path)->util\n \t\t\t= (void *)sre;\n \t}\n \tfor (i = 0; i < b_renames->nr; i++) {\n \t\tsre = b_renames->items[i].util;\n-\t\tstring_list_insert(&b_by_dst, sre->pair->two->path)->util\n+\t\tstring_list_append(&b_by_dst, sre->pair->two->path)->util\n \t\t\t= (void *)sre;\n \t}\n+\tstring_list_sort(&a_by_dst);\n+\tstring_list_sort(&b_by_dst);\n \n \tfor (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {\n \t\tstruct string_list *renames1, *renames2Dst;\n-- \n2.34.1\n\n"},{"id":"512352","messageId":"20250213090040.16133-3-meetsoni3017@gmail.com","threadId":"62937","inReplyTo":"20250213090040.16133-1-meetsoni3017@gmail.com","subject":"[RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged","fromName":"Meet Soni","fromEmail":"meetsoni3017@gmail.com","sentAt":"2025-02-13T09:00:40Z","receivedAt":"2025-02-13T09:00:53Z","isPatch":true,"sender":{"key":"meetsoni3017@gmail.com","avatar":"https://avatars.githubusercontent.com/u/92802561?v=4"},"body":"Previously, `get_unmerged()` used `string_list_insert()`, which has an\nO(n^2) complexity due to shifting elements on each insertion. It also\ncalled `string_list_lookup()` before insertion, which performs a binary\nsearch in O(log n). This combination made insertion costly, especially\nfor large index states, as each new entry required both a search and\npotentially shifting many elements.\n\nReplace `string_list_insert()` with `string_list_append()` to achieve\nO(n) insertion. After all entries are added, sort the list in O(n log n)\nand remove duplicates in O(n), reducing the overall complexity to\nO(n log n). This improves performance significantly for large datasets\nwhile maintaining correctness.\n\nSigned-off-by: Meet Soni \n---\n merge-recursive.c | 10 +++++-----\n 1 file changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 884ccf99a5..6165993429 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -547,15 +547,15 @@ static struct string_list *get_unmerged(struct index_state *istate)\n \t\tif (!ce_stage(ce))\n \t\t\tcontinue;\n \n-\t\titem = string_list_lookup(unmerged, ce->name);\n-\t\tif (!item) {\n-\t\t\titem = string_list_insert(unmerged, ce->name);\n-\t\t\titem->util = xcalloc(1, sizeof(struct stage_data));\n-\t\t}\n+\t\titem = string_list_append(unmerged, ce->name);\n+\t\titem->util = xcalloc(1, sizeof(struct stage_data));\n+\n \t\te = item->util;\n \t\te->stages[ce_stage(ce)].mode = ce->ce_mode;\n \t\toidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid);\n \t}\n+\tstring_list_sort(unmerged);\n+\tstring_list_remove_duplicates(unmerged, 1);\n \n \treturn unmerged;\n }\n-- \n2.34.1\n\n"},{"id":"512359","messageId":"CAPhwyn2-H4F73j+9gMTV__1+5PLRsirFf+11dgPYVyi==-w7Nw@mail.gmail.com","threadId":"62937","inReplyTo":"20250213090040.16133-1-meetsoni3017@gmail.com","subject":"Re: [RFC PATCH 0/2] merge-recursive: optimize time complexity","fromName":"Meet Soni","fromEmail":"meetsoni3017@gmail.com","sentAt":"2025-02-13T11:02:41Z","receivedAt":"2025-02-13T11:02:58Z","isPatch":true,"sender":{"key":"meetsoni3017@gmail.com","avatar":"https://avatars.githubusercontent.com/u/92802561?v=4"},"body":"Hi everyone.\n\nAdding the missing CCs who were unintentionally dropped in my original email.\nPlease refer to the previous message for the patch details.\nLink to the patch:\nhttps://lore.kernel.org/git/20250213090040.16133-1-meetsoni3017@gmail.com/\n\nThanks,\nMeet\n"},{"id":"512367","messageId":"CABPp-BHrbvxGsiS_XHswyP5qPRBa39y38bue3CFGb7R7k4xVBQ@mail.gmail.com","threadId":"62937","inReplyTo":"20250213090040.16133-2-meetsoni3017@gmail.com","subject":"Re: [RFC PATCH 1/2] merge-recursive: optimize time complexity for process_renames","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-02-13T17:06:35Z","receivedAt":"2025-02-13T17:06:48Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Feb 13, 2025 at 1:00 AM Meet Soni wrote:\n>\n> Avoid O(n^2) complexity in `process_renames()` when building a sorted\n> `string_list` by constructing it unsorted and sorting it afterward,\n> reducing the complexity to O(n log n).\n>\n> Signed-off-by: Meet Soni \n> ---\n> merge-recursive.c | 15 +++++++--------\n> 1 file changed, 7 insertions(+), 8 deletions(-)\n>\n> diff --git a/merge-recursive.c b/merge-recursive.c\n> index 5dfaf32b2c..884ccf99a5 100644\n> --- a/merge-recursive.c\n> +++ b/merge-recursive.c\n> @@ -2758,23 +2758,22 @@ static int process_renames(struct merge_options *opt,\n> const struct rename *sre;\n>\n> /*\n> - * FIXME: As string-list.h notes, it's O(n^2) to build a sorted\n> - * string_list one-by-one, but O(n log n) to build it unsorted and\n> - * then sort it. Note that as we build the list, we do not need to\n> - * check if the existing destination path is already in the list,\n> - * because the structure of diffcore_rename guarantees we won't\n> - * have duplicates.\n> + * Note that as we build the list, we do not need to check if the\n> + * existing destination path is already in the list, because the\n> + * structure of diffcore_rename guarantees we won't have duplicates.\n> */\n> for (i = 0; i < a_renames->nr; i++) {\n> sre = a_renames->items[i].util;\n> - string_list_insert(&a_by_dst, sre->pair->two->path)->util\n> + string_list_append(&a_by_dst, sre->pair->two->path)->util\n> = (void *)sre;\n> }\n> for (i = 0; i < b_renames->nr; i++) {\n> sre = b_renames->items[i].util;\n> - string_list_insert(&b_by_dst, sre->pair->two->path)->util\n> + string_list_append(&b_by_dst, sre->pair->two->path)->util\n> = (void *)sre;\n> }\n> + string_list_sort(&a_by_dst);\n> + string_list_sort(&b_by_dst);\n>\n> for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {\n> struct string_list *renames1, *renames2Dst;\n> --\n> 2.34.1\n\nThis version looks good to me.\n"},{"id":"512368","messageId":"CABPp-BGqihkPq3o4jnqp2aGdqw12F8a8nOModuAB-5N7BQ1t0w@mail.gmail.com","threadId":"62937","inReplyTo":"20250213090040.16133-3-meetsoni3017@gmail.com","subject":"Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-02-13T17:11:33Z","receivedAt":"2025-02-13T17:11:45Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Feb 13, 2025 at 1:01 AM Meet Soni wrote:\n>\n> Previously, `get_unmerged()` used `string_list_insert()`, which has an\n> O(n^2) complexity due to shifting elements on each insertion. It also\n> called `string_list_lookup()` before insertion, which performs a binary\n> search in O(log n).\n\nOkay.\n\n> This combination made insertion costly, especially\n> for large index states, as each new entry required both a search and\n> potentially shifting many elements.\n\nWhy does the combination make it costly? O(log n) + O(n^2) is still\nO(n^2), so I don't see why it matters to mention the combination.\nCould you clarify?\n\nAlso, does it actually make it costly, or do you only suspect that it\ndoes? O(n^2) worst case sometimes behaves O(n) or O(n log n) in some\ncases. Since your commit message says \"made insertion costly\" instead\nof \"might make insertion costly\", I think that would suggest you have\nsome performance numbers to back this up on some interesting real\nworld repository. Do you? Can you share them?\n\n> Replace `string_list_insert()` with `string_list_append()` to achieve\n> O(n) insertion. After all entries are added, sort the list in O(n log n)\n> and remove duplicates in O(n), reducing the overall complexity to\n> O(n log n).\n\nOkay.\n\n> This improves performance significantly for large datasets\n\nThat's a big claim; it may be true, but without evidence I don't\nbelieve it for three reasons : (1) n here is the number of conflicts,\nnot the number of files in the repo or the number of lines being\nmerged. Thus, n is typically small. (2) Other O(n^2) behavior in\nmerge-recursive likely drowns this particular codepath out, so any\ngains here just aren't going to be noticed, (3) After looking at the\ncode and knowing the specialized structure of the index, I think that\nwhile string_list_insert() for n items in general is going to be\nO(n^2), it will likely functionally be O(n log n) for this particular\ncode path, meaning you haven't actually improved the performance.\n\n> while maintaining correctness.\n\nMore on that below.\n\n\n> Signed-off-by: Meet Soni \n> ---\n> merge-recursive.c | 10 +++++-----\n> 1 file changed, 5 insertions(+), 5 deletions(-)\n>\n> diff --git a/merge-recursive.c b/merge-recursive.c\n> index 884ccf99a5..6165993429 100644\n> --- a/merge-recursive.c\n> +++ b/merge-recursive.c\n> @@ -547,15 +547,15 @@ static struct string_list *get_unmerged(struct index_state *istate)\n> if (!ce_stage(ce))\n> continue;\n>\n> - item = string_list_lookup(unmerged, ce->name);\n> - if (!item) {\n> - item = string_list_insert(unmerged, ce->name);\n> - item->util = xcalloc(1, sizeof(struct stage_data));\n> - }\n> + item = string_list_append(unmerged, ce->name);\n> + item->util = xcalloc(1, sizeof(struct stage_data));\n> +\n> e = item->util;\n> e->stages[ce_stage(ce)].mode = ce->ce_mode;\n> oidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid);\n\nDid you run any tests? I'm not sure you maintained correctness here.\n\n> }\n> + string_list_sort(unmerged);\n> + string_list_remove_duplicates(unmerged, 1);\n>\n> return unmerged;\n> }\n> --\n> 2.34.1\n\n(As a side note, due to the specialized structure of the input, I\nsuspect this code could be modified to run in O(n), i.e. we could skip\nthe string_list_lookup and the string_list_sort and the\nstring_list_remove_duplicates... But, it'd make the code trickier, so\nit'd need to be carefully commented, the change would need to be\njustified, and it'd need to be carefully tested. Even if we weren't\nplanning to delete this entire file, I suspect it's not possible to\nfind a case justifying such a change without optimizing several other\nthings in merge-recursive first, but optimizing those things probably\nresults in a significant rewrite...which we've already done with\nmerge-ort.)\n"},{"id":"512371","messageId":"xmqqwmdtofxh.fsf@gitster.g","threadId":"62937","inReplyTo":"CABPp-BGqihkPq3o4jnqp2aGdqw12F8a8nOModuAB-5N7BQ1t0w@mail.gmail.com","subject":"Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-02-13T18:30:50Z","receivedAt":"2025-02-13T18:30:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> (As a side note, due to the specialized structure of the input, I\n> suspect this code could be modified to run in O(n), i.e. we could skip\n> the string_list_lookup and the string_list_sort and the\n> string_list_remove_duplicates...\n\nAre you talking about the input being already sorted so we can just\nwalk the multiple input and merge them into a single stream? In the\ncost analysis you did earlier in the message I am responding to,\nbeing able to go down to O(n) sounds really like a great thing ;-)\n\n> But, it'd make the code trickier, so\n> it'd need to be carefully commented, the change would need to be\n> justified, and it'd need to be carefully tested. \n\n... and measured.\n\n> Even if we weren't\n> planning to delete this entire file, I suspect it's not possible to\n> find a case justifying such a change without optimizing several other\n> things in merge-recursive first, but optimizing those things probably\n> results in a significant rewrite...which we've already done with\n> merge-ort.)\n\nSounds like unless the performance issues are shared between the\ntwo, it may not be worth to spend too much brain cycles only on the\n\"recursive\" one?\n\nThanks.\n"},{"id":"512372","messageId":"CABPp-BEC3UVQcJfXLia6+XrmNCnozNdHtGhGOTUr4A9J=Xo1Ow@mail.gmail.com","threadId":"62937","inReplyTo":"20250213090040.16133-1-meetsoni3017@gmail.com","subject":"Re: [RFC PATCH 0/2] merge-recursive: optimize time complexity","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-02-13T18:30:55Z","receivedAt":"2025-02-13T18:31:08Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"Hi,\n\nOn Thu, Feb 13, 2025 at 1:01 AM Meet Soni wrote:\n>\n> changes in this version:\n> - Updated comment and commit message as per review.\n> - Added another commit implementing optimization logic.\n> - added an RFC tag since, if the changes in 2nd commit are\n> appropriate, we can apply similar logic in other places as\n> well.\n\nThe 1st patch looks good. The 2nd appears to have some problems, as\nper comments I left on it -- it might be easier to drop the second\npatch and just apply the first. I don't think merge-recursive is\nworth putting much effort into (there's value in providing feedback on\npatches by new contributors, because new contributors are valuable,\nbut there's really not much value in tweaking this particular file),\nso I'd advise against adding more patches to this series that\ntransform more of merge-recursive.\n"},{"id":"512377","messageId":"CABPp-BGkWsq9tKk1ytHfP=GP6z90dioqDVgKuDB+N2EzjtWfDA@mail.gmail.com","threadId":"62937","inReplyTo":"xmqqwmdtofxh.fsf@gitster.g","subject":"Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-02-13T18:45:26Z","receivedAt":"2025-02-13T18:45:38Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Feb 13, 2025 at 10:30 AM Junio C Hamano wrote:\n>\n> Elijah Newren writes:\n>\n> > (As a side note, due to the specialized structure of the input, I\n> > suspect this code could be modified to run in O(n), i.e. we could skip\n> > the string_list_lookup and the string_list_sort and the\n> > string_list_remove_duplicates...\n>\n> Are you talking about the input being already sorted so we can just\n> walk the multiple input and merge them into a single stream? In the\n\nI'm not sure what you mean by \"merge them into a single stream\". I\nthink you have the right idea that we are creating a string list of\ninformation about unmerged entries, and since we're taking information\nfrom the index which is already sorted, we can just either modify the\nlast entry in the list if it matches or append a new entry to it; no\nneed to walk, insert, or binary search the list at all.\n\n> cost analysis you did earlier in the message I am responding to,\n> being able to go down to O(n) sounds really like a great thing ;-)\n\nNote first that we aren't going from O(n^2) -> O(n), we're only going\nfrom O(n log n) -> O(n). That's still great, but:\n\n * n is typically pretty small (number of unmerged files)\n * there's things in merge-recursive that are O(m^2), where typically\nm >> n (number of files in repo, or number of lines in big files in\nthe repo)\n * merge-recursive is used by almost no one\n * we are planning to delete merge-recursive\n\nSo, although O(n) is great....\n\n> > But, it'd make the code trickier, so\n> > it'd need to be carefully commented, the change would need to be\n> > justified, and it'd need to be carefully tested.\n>\n> ... and measured.\n\n+1\n\n> > Even if we weren't\n> > planning to delete this entire file, I suspect it's not possible to\n> > find a case justifying such a change without optimizing several other\n> > things in merge-recursive first, but optimizing those things probably\n> > results in a significant rewrite...which we've already done with\n> > merge-ort.)\n>\n> Sounds like unless the performance issues are shared between the\n> two, it may not be worth to spend too much brain cycles only on the\n> \"recursive\" one?\n\n...yep, exactly, and this is not a performance issue shared with the\nort backend; it's unique to the recursive one.\n"},{"id":"512393","messageId":"CAPhwyn0hz16mZ-UoVAczC4qDLx2i0LwfFhhDjdTahe0=4TO57g@mail.gmail.com","threadId":"62937","inReplyTo":"CABPp-BGqihkPq3o4jnqp2aGdqw12F8a8nOModuAB-5N7BQ1t0w@mail.gmail.com","subject":"Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged","fromName":"Meet Soni","fromEmail":"meetsoni3017@gmail.com","sentAt":"2025-02-14T04:28:28Z","receivedAt":"2025-02-14T04:28:41Z","isPatch":true,"sender":{"key":"meetsoni3017@gmail.com","avatar":"https://avatars.githubusercontent.com/u/92802561?v=4"},"body":"On Thu, 13 Feb 2025 at 22:41, Elijah Newren wrote:\n>\n> On Thu, Feb 13, 2025 at 1:01 AM Meet Soni wrote:\n> >\n> > Previously, `get_unmerged()` used `string_list_insert()`, which has an\n> > O(n^2) complexity due to shifting elements on each insertion. It also\n> > called `string_list_lookup()` before insertion, which performs a binary\n> > search in O(log n).\n>\n> Okay.\n>\n> > This combination made insertion costly, especially\n> > for large index states, as each new entry required both a search and\n> > potentially shifting many elements.\n>\n> Why does the combination make it costly? O(log n) + O(n^2) is still\n> O(n^2), so I don't see why it matters to mention the combination.\n> Could you clarify?\n>\n> Also, does it actually make it costly, or do you only suspect that it\n> does? O(n^2) worst case sometimes behaves O(n) or O(n log n) in some\n> cases. Since your commit message says \"made insertion costly\" instead\n> of \"might make insertion costly\", I think that would suggest you have\n> some performance numbers to back this up on some interesting real\n> world repository. Do you? Can you share them?\n>\nSorry, I should've specified, this patch is purely theoretical, I was\naiming for a trial\nand error kind of approach.\n\n> > Replace `string_list_insert()` with `string_list_append()` to achieve\n> > O(n) insertion. After all entries are added, sort the list in O(n log n)\n> > and remove duplicates in O(n), reducing the overall complexity to\n> > O(n log n).\n>\n> Okay.\n>\n> > This improves performance significantly for large datasets\n>\n> That's a big claim; it may be true, but without evidence I don't\n> believe it for three reasons : (1) n here is the number of conflicts,\n> not the number of files in the repo or the number of lines being\n> merged. Thus, n is typically small. (2) Other O(n^2) behavior in\n> merge-recursive likely drowns this particular codepath out, so any\n> gains here just aren't going to be noticed, (3) After looking at the\n> code and knowing the specialized structure of the index, I think that\n> while string_list_insert() for n items in general is going to be\n> O(n^2), it will likely functionally be O(n log n) for this particular\n> code path, meaning you haven't actually improved the performance.\n>\n> > while maintaining correctness.\n>\n> More on that below.\n>\n>\n> > Signed-off-by: Meet Soni \n> > ---\n> > merge-recursive.c | 10 +++++-----\n> > 1 file changed, 5 insertions(+), 5 deletions(-)\n> >\n> > diff --git a/merge-recursive.c b/merge-recursive.c\n> > index 884ccf99a5..6165993429 100644\n> > --- a/merge-recursive.c\n> > +++ b/merge-recursive.c\n> > @@ -547,15 +547,15 @@ static struct string_list *get_unmerged(struct index_state *istate)\n> > if (!ce_stage(ce))\n> > continue;\n> >\n> > - item = string_list_lookup(unmerged, ce->name);\n> > - if (!item) {\n> > - item = string_list_insert(unmerged, ce->name);\n> > - item->util = xcalloc(1, sizeof(struct stage_data));\n> > - }\n> > + item = string_list_append(unmerged, ce->name);\n> > + item->util = xcalloc(1, sizeof(struct stage_data));\n> > +\n> > e = item->util;\n> > e->stages[ce_stage(ce)].mode = ce->ce_mode;\n> > oidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid);\n>\n> Did you run any tests? I'm not sure you maintained correctness here.\n\nI didn't run any tests -- I wanted to, but I wasn’t sure how to do it\nfor this change. Since you suggested dropping this patch from the\nseries, I’ll do that. But for similar changes in the future, how should I go\nabout testing them?\n>\n> > }\n> > + string_list_sort(unmerged);\n> > + string_list_remove_duplicates(unmerged, 1);\n> >\n> > return unmerged;\n> > }\n> > --\n> > 2.34.1\n>\n> (As a side note, due to the specialized structure of the input, I\n> suspect this code could be modified to run in O(n), i.e. we could skip\n> the string_list_lookup and the string_list_sort and the\n> string_list_remove_duplicates... But, it'd make the code trickier, so\n> it'd need to be carefully commented, the change would need to be\n> justified, and it'd need to be carefully tested. Even if we weren't\n> planning to delete this entire file, I suspect it's not possible to\n> find a case justifying such a change without optimizing several other\n> things in merge-recursive first, but optimizing those things probably\n> results in a significant rewrite...which we've already done with\n> merge-ort.)\nMakes sense.\n\nThankyou for reviewing,\nMeet\n"},{"id":"512394","messageId":"20250214044129.15282-1-meetsoni3017@gmail.com","threadId":"62937","inReplyTo":"20250213090040.16133-1-meetsoni3017@gmail.com","subject":"[GSoC][PATCH v2] merge-recursive: optimize time complexity for process_renames","fromName":"Meet Soni","fromEmail":"meetsoni3017@gmail.com","sentAt":"2025-02-14T04:41:29Z","receivedAt":"2025-02-14T04:41:38Z","isPatch":true,"sender":{"key":"meetsoni3017@gmail.com","avatar":"https://avatars.githubusercontent.com/u/92802561?v=4"},"body":"Avoid O(n^2) complexity in `process_renames()` when building a sorted\n`string_list` by constructing it unsorted and sorting it afterward,\nreducing the complexity to O(n log n).\n\nSigned-off-by: Meet Soni \n---\nRange-diff against v1:\n1: c7dca6e971 = 1: c7dca6e971 merge-recursive: optimize time complexity for process_renames\n2: 78a007be7d < -: ---------- merge-recursive: optimize time complexity for get_unmerged\n\n merge-recursive.c | 15 +++++++--------\n 1 file changed, 7 insertions(+), 8 deletions(-)\n\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 5dfaf32b2c..884ccf99a5 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -2758,23 +2758,22 @@ static int process_renames(struct merge_options *opt,\n \tconst struct rename *sre;\n \n \t/*\n-\t * FIXME: As string-list.h notes, it's O(n^2) to build a sorted\n-\t * string_list one-by-one, but O(n log n) to build it unsorted and\n-\t * then sort it. Note that as we build the list, we do not need to\n-\t * check if the existing destination path is already in the list,\n-\t * because the structure of diffcore_rename guarantees we won't\n-\t * have duplicates.\n+\t * Note that as we build the list, we do not need to check if the\n+\t * existing destination path is already in the list, because the\n+\t * structure of diffcore_rename guarantees we won't have duplicates.\n \t */\n \tfor (i = 0; i < a_renames->nr; i++) {\n \t\tsre = a_renames->items[i].util;\n-\t\tstring_list_insert(&a_by_dst, sre->pair->two->path)->util\n+\t\tstring_list_append(&a_by_dst, sre->pair->two->path)->util\n \t\t\t= (void *)sre;\n \t}\n \tfor (i = 0; i < b_renames->nr; i++) {\n \t\tsre = b_renames->items[i].util;\n-\t\tstring_list_insert(&b_by_dst, sre->pair->two->path)->util\n+\t\tstring_list_append(&b_by_dst, sre->pair->two->path)->util\n \t\t\t= (void *)sre;\n \t}\n+\tstring_list_sort(&a_by_dst);\n+\tstring_list_sort(&b_by_dst);\n \n \tfor (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {\n \t\tstruct string_list *renames1, *renames2Dst;\n-- \n2.34.1\n\n"},{"id":"512407","messageId":"CABPp-BGq-x9Z98scXRtEnqz7BCmPn9ONHd6wDnnm9jL4YeDHxQ@mail.gmail.com","threadId":"62937","inReplyTo":"CAPhwyn0hz16mZ-UoVAczC4qDLx2i0LwfFhhDjdTahe0=4TO57g@mail.gmail.com","subject":"Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-02-14T06:04:50Z","receivedAt":"2025-02-14T06:05:02Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Feb 13, 2025 at 8:28 PM Meet Soni wrote:\n>\n> On Thu, 13 Feb 2025 at 22:41, Elijah Newren wrote:\n> >\n> > On Thu, Feb 13, 2025 at 1:01 AM Meet Soni wrote:\n...\n> > > diff --git a/merge-recursive.c b/merge-recursive.c\n> > > index 884ccf99a5..6165993429 100644\n> > > --- a/merge-recursive.c\n> > > +++ b/merge-recursive.c\n> > > @@ -547,15 +547,15 @@ static struct string_list *get_unmerged(struct index_state *istate)\n> > > if (!ce_stage(ce))\n> > > continue;\n> > >\n> > > - item = string_list_lookup(unmerged, ce->name);\n> > > - if (!item) {\n> > > - item = string_list_insert(unmerged, ce->name);\n> > > - item->util = xcalloc(1, sizeof(struct stage_data));\n> > > - }\n> > > + item = string_list_append(unmerged, ce->name);\n> > > + item->util = xcalloc(1, sizeof(struct stage_data));\n> > > +\n> > > e = item->util;\n> > > e->stages[ce_stage(ce)].mode = ce->ce_mode;\n> > > oidcpy(&e->stages[ce_stage(ce)].oid, &ce->oid);\n> >\n> > Did you run any tests? I'm not sure you maintained correctness here.\n>\n> I didn't run any tests -- I wanted to, but I wasn’t sure how to do it\n> for this change. Since you suggested dropping this patch from the\n> series, I’ll do that. But for similar changes in the future, how should I go\n> about testing them?\n\nAs per Documentation/CodingGuidelines: \"After any code change, make\nsure that the entire test suite passes.\" You can do that by running:\n cd t && make\n(You probably want to also run that before making any changes, just to\nverify that they all pass for you. Then, if any test fails after you\nmake changes, you know it's because of your changes rather than\nbecause you missed something in building or setting up the tests.)\n\n\nAnd although it doesn't matter since we're dropping this patch, the\nissue I noticed was that if there were, say, three unmerged entries\nwith the same path, the original code would create one entry in the\nstring list and modify it 3 times (each with a different ce_stage(ce).\nYour modification would create three different entries (each with only\ninformation from one stage) and drop two of them, meaning we no longer\nhave a single string_list_item that contains information from all 3\nunmerged entries for the same path. I'm pretty sure running the\nexisting tests would catch that kind of bug, which is what raised the\nquestion.\n"},{"id":"512408","messageId":"CAPhwyn1oXRy5BFQBvuFsmhfVhkW8+D6Xz6OYB8LpP0O+jH1TFQ@mail.gmail.com","threadId":"62937","inReplyTo":"CABPp-BGq-x9Z98scXRtEnqz7BCmPn9ONHd6wDnnm9jL4YeDHxQ@mail.gmail.com","subject":"Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged","fromName":"Meet Soni","fromEmail":"meetsoni3017@gmail.com","sentAt":"2025-02-14T08:24:32Z","receivedAt":"2025-02-14T08:24:46Z","isPatch":true,"sender":{"key":"meetsoni3017@gmail.com","avatar":"https://avatars.githubusercontent.com/u/92802561?v=4"},"body":"On Fri, 14 Feb 2025 at 11:35, Elijah Newren wrote:\n>\n> > > Did you run any tests? I'm not sure you maintained correctness here.\n> >\n> > I didn't run any tests -- I wanted to, but I wasn’t sure how to do it\n> > for this change. Since you suggested dropping this patch from the\n> > series, I’ll do that. But for similar changes in the future, how should I go\n> > about testing them?\n>\n> As per Documentation/CodingGuidelines: \"After any code change, make\n> sure that the entire test suite passes.\" You can do that by running:\n> cd t && make\n> (You probably want to also run that before making any changes, just to\n> verify that they all pass for you. Then, if any test fails after you\n> make changes, you know it's because of your changes rather than\n> because you missed something in building or setting up the tests.)\n>\n>\n> And although it doesn't matter since we're dropping this patch, the\n> issue I noticed was that if there were, say, three unmerged entries\n> with the same path, the original code would create one entry in the\n> string list and modify it 3 times (each with a different ce_stage(ce).\n> Your modification would create three different entries (each with only\n> information from one stage) and drop two of them, meaning we no longer\n> have a single string_list_item that contains information from all 3\n> unmerged entries for the same path. I'm pretty sure running the\n> existing tests would catch that kind of bug, which is what raised the\n> question.\n\nThat's the thing -- I did run make in the t/ directory, and it passed. I was\njust wondering if there's any other way to test this in isolation, in case\nI want to verify such changes more directly in the future.\n\nThanks for the clarification!\nMeet\n"},{"id":"512434","messageId":"CABPp-BGOeAJ-e0P7kALLMnA7wCzbJx6WEYwmCmsq9qK46DYdVw@mail.gmail.com","threadId":"62937","inReplyTo":"CAPhwyn1oXRy5BFQBvuFsmhfVhkW8+D6Xz6OYB8LpP0O+jH1TFQ@mail.gmail.com","subject":"Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-02-14T19:00:09Z","receivedAt":"2025-02-14T19:00:21Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Feb 14, 2025 at 12:24 AM Meet Soni wrote:\n>\n> On Fri, 14 Feb 2025 at 11:35, Elijah Newren wrote:\n> >\n> > > > Did you run any tests? I'm not sure you maintained correctness here.\n> > >\n> > > I didn't run any tests -- I wanted to, but I wasn’t sure how to do it\n> > > for this change. Since you suggested dropping this patch from the\n> > > series, I’ll do that. But for similar changes in the future, how should I go\n> > > about testing them?\n> >\n> > As per Documentation/CodingGuidelines: \"After any code change, make\n> > sure that the entire test suite passes.\" You can do that by running:\n> > cd t && make\n> > (You probably want to also run that before making any changes, just to\n> > verify that they all pass for you. Then, if any test fails after you\n> > make changes, you know it's because of your changes rather than\n> > because you missed something in building or setting up the tests.)\n> >\n> >\n> > And although it doesn't matter since we're dropping this patch, the\n> > issue I noticed was that if there were, say, three unmerged entries\n> > with the same path, the original code would create one entry in the\n> > string list and modify it 3 times (each with a different ce_stage(ce).\n> > Your modification would create three different entries (each with only\n> > information from one stage) and drop two of them, meaning we no longer\n> > have a single string_list_item that contains information from all 3\n> > unmerged entries for the same path. I'm pretty sure running the\n> > existing tests would catch that kind of bug, which is what raised the\n> > question.\n>\n> That's the thing -- I did run make in the t/ directory, and it passed. I was\n> just wondering if there's any other way to test this in isolation, in case\n> I want to verify such changes more directly in the future.\n\nReally? Did you rebuild the code, after making your changes? You may\nhave been running with a pre-changes version of the code.\n\nI just applied your changes and ran the tests. I see it fail as soon\nas it gets to t1004.\n\n$ cd t && make test\n[... lots of output snipped ...]\n*** t1004-read-tree-m-u-wf.sh ***\nok 1 - two-way setup\nok 2 - two-way not clobbering\nok 3 - two-way with incorrect --exclude-per-directory (1)\nok 4 - two-way with incorrect --exclude-per-directory (2)\nok 5 - two-way clobbering a ignored file\nok 6 - three-way not complaining on an untracked path in both\nok 7 - three-way not clobbering a working tree file\nok 8 - three-way not complaining on an untracked file\nok 9 - 3-way not overwriting local changes (setup)\nok 10 - 3-way not overwriting local changes (our side)\nok 11 - 3-way not overwriting local changes (their side)\nok 12 - funny symlink in work tree\nok 13 - funny symlink in work tree, un-unlink-able\nok 14 - D/F setup\nok 15 - D/F\nok 16 - D/F resolve\nnot ok 17 - D/F recursive\n#\n#\n# git reset --hard &&\n# git checkout side-b &&\n# git merge-recursive branch-point -- side-b side-a\n#\n#\n# failed 1 among 17 test(s)\n1..17\nmake[1]: *** [Makefile:77: t1004-read-tree-m-u-wf.sh] Error 1\nmake[1]: Leaving directory '/home/newren/floss/git/t'\nmake: *** [Makefile:63: test] Error 2\n\n\n...and if go to the toplevel directory and run under prove so I can\nsee all the failures (and run the test suites in parallel), I see:\n\n$ cd .. && make DEFAULT_TEST_TARGET=prove GIT_PROVE_OPTS='--timer\n--state failed,slow,save --jobs 12' test\n[... lots of output snipped ...]\nTest Summary Report\n-------------------\nt3424-rebase-empty.sh (Wstat: 256 Tests: 20\nFailed: 18)\n Failed tests: 3-20\n Non-zero exit status: 1\nt3436-rebase-more-options.sh (Wstat: 256 Tests: 19\nFailed: 17)\n Failed tests: 2-18\n Non-zero exit status: 1\nt4151-am-abort.sh (Wstat: 256 Tests: 20\nFailed: 12)\n Failed tests: 5-9, 12-16, 19-20\n Non-zero exit status: 1\nt3407-rebase-abort.sh (Wstat: 256 Tests: 17\nFailed: 8)\n Failed tests: 2-9\n Non-zero exit status: 1\nt3428-rebase-signoff.sh (Wstat: 256 Tests: 7 Failed: 5)\n Failed tests: 2, 4-7\n Non-zero exit status: 1\nt6409-merge-subtree.sh (Wstat: 256 Tests: 12\nFailed: 5)\n Failed tests: 2-6\n Non-zero exit status: 1\nt7102-reset.sh (Wstat: 256 Tests: 38\nFailed: 7)\n Failed tests: 14-20\n Non-zero exit status: 1\nt6432-merge-recursive-space-options.sh (Wstat: 256 Tests: 11\nFailed: 4)\n Failed tests: 2, 7-8, 11\n Non-zero exit status: 1\nt6430-merge-recursive.sh (Wstat: 256 Tests: 37\nFailed: 15)\n Failed tests: 10-11, 13-20, 22-24, 28-29\n Non-zero exit status: 1\nt3406-rebase-message.sh (Wstat: 256 Tests: 32\nFailed: 8)\n Failed tests: 22, 24-27, 29-31\n Non-zero exit status: 1\nt4200-rerere.sh (Wstat: 256 Tests: 36\nFailed: 5)\n Failed tests: 24-28\n Non-zero exit status: 1\nt7201-co.sh (Wstat: 256 Tests: 46\nFailed: 5)\n Failed tests: 5-9\n Non-zero exit status: 1\nt3418-rebase-continue.sh (Wstat: 256 Tests: 29\nFailed: 7)\n Failed tests: 4, 6, 10-12, 26-27\n Non-zero exit status: 1\nt3403-rebase-skip.sh (Wstat: 256 Tests: 20\nFailed: 3)\n Failed tests: 2, 4, 9\n Non-zero exit status: 1\nt4253-am-keep-cr-dos.sh (Wstat: 256 Tests: 7 Failed: 2)\n Failed tests: 6-7\n Non-zero exit status: 1\nt9903-bash-prompt.sh (Wstat: 256 Tests: 67\nFailed: 39)\n Failed tests: 16-31, 33-35, 37, 40-44, 46-52, 55-58, 60\n 62, 67\n Non-zero exit status: 1\nt3503-cherry-pick-root.sh (Wstat: 256 Tests: 6 Failed: 2)\n Failed tests: 5-6\n Non-zero exit status: 1\nt3401-rebase-and-am-rename.sh (Wstat: 256 Tests: 10\nFailed: 2)\n Failed tests: 4, 10\n Non-zero exit status: 1\nt2407-worktree-heads.sh (Wstat: 256 Tests: 12\nFailed: 2)\n Failed tests: 4-5\n Non-zero exit status: 1\nt5407-post-rewrite-hook.sh (Wstat: 256 Tests: 17\nFailed: 3)\n Failed tests: 4-6\n Non-zero exit status: 1\nt2500-untracked-overwriting.sh (Wstat: 256 Tests: 10\nFailed: 2)\n Failed tests: 9-10\n Non-zero exit status: 1\nt4153-am-resume-override-opts.sh (Wstat: 256 Tests: 6 Failed: 1)\n Failed test: 3\n Non-zero exit status: 1\nt1015-read-index-unmerged.sh (Wstat: 256 Tests: 6 Failed: 1)\n Failed test: 6\n Non-zero exit status: 1\nt3509-cherry-pick-merge-df.sh (Wstat: 256 Tests: 9 Failed: 1)\n Failed test: 9\n Non-zero exit status: 1\nt2023-checkout-m.sh (Wstat: 256 Tests: 5 Failed: 1)\n Failed test: 5\n Non-zero exit status: 1\nt7615-diff-algo-with-mergy-operations.sh (Wstat: 256 Tests: 7 Failed: 1)\n Failed test: 2\n Non-zero exit status: 1\nt6427-diff3-conflict-markers.sh (Wstat: 256 Tests: 9 Failed: 1)\n Failed test: 8\n Non-zero exit status: 1\nt1004-read-tree-m-u-wf.sh (Wstat: 256 Tests: 17\nFailed: 1)\n Failed test: 17\n Non-zero exit status: 1\nt3420-rebase-autostash.sh (Wstat: 256 Tests: 52\nFailed: 10)\n Failed tests: 11-17, 21-23\n Non-zero exit status: 1\nt4150-am.sh (Wstat: 256 Tests: 87\nFailed: 33)\n Failed tests: 34-40, 42-46, 48, 50-54, 57-62, 64-65, 67-71\n 75, 87\n Non-zero exit status: 1\nt7512-status-help.sh (Wstat: 256 Tests: 46\nFailed: 3)\n Failed tests: 5-6, 29\n Non-zero exit status: 1\nt3400-rebase.sh (Wstat: 256 Tests: 39\nFailed: 1)\n Failed test: 30\n Non-zero exit status: 1\nt3404-rebase-interactive.sh (Wstat: 256 Tests:\n131 Failed: 1)\n Failed test: 80\n Non-zero exit status: 1\nFiles=1031, Tests=30662, 70 wallclock secs ( 8.33 usr 2.13 sys +\n248.60 cusr 516.60 csys = 775.66 CPU)\nResult: FAIL\nmake[1]: *** [Makefile:73: prove] Error 1\nmake[1]: Leaving directory '/home/newren/floss/git/t'\nmake: *** [Makefile:3237: test] Error 2\n\nI suspect this is a case where it was testing a version of git that\nyou built before making the changes.\n"},{"id":"512457","messageId":"CAPhwyn0JGxqQcKjz58F9AQ5caPeXms_qPksxJ=JRrxPufUFZWg@mail.gmail.com","threadId":"62937","inReplyTo":"CABPp-BGOeAJ-e0P7kALLMnA7wCzbJx6WEYwmCmsq9qK46DYdVw@mail.gmail.com","subject":"Re: [RFC PATCH 2/2] merge-recursive: optimize time complexity for get_unmerged","fromName":"Meet Soni","fromEmail":"meetsoni3017@gmail.com","sentAt":"2025-02-15T08:42:42Z","receivedAt":"2025-02-15T08:42:56Z","isPatch":true,"sender":{"key":"meetsoni3017@gmail.com","avatar":"https://avatars.githubusercontent.com/u/92802561?v=4"},"body":"On Sat, 15 Feb 2025 at 00:30, Elijah Newren wrote:\n>\n> On Fri, Feb 14, 2025 at 12:24 AM Meet Soni wrote:\n> > That's the thing -- I did run make in the t/ directory, and it passed. I was\n> > just wondering if there's any other way to test this in isolation, in case\n> > I want to verify such changes more directly in the future.\n>\n> Really? Did you rebuild the code, after making your changes? You may\n> have been running with a pre-changes version of the code.\n>\n> I just applied your changes and ran the tests. I see it fail as soon\n> as it gets to t1004.\n>\n> $ cd t && make test\n> [... lots of output snipped ...]\n> *** t1004-read-tree-m-u-wf.sh ***\n> ok 1 - two-way setup\n> ok 2 - two-way not clobbering\n> ok 3 - two-way with incorrect --exclude-per-directory (1)\n> ok 4 - two-way with incorrect --exclude-per-directory (2)\n> ok 5 - two-way clobbering a ignored file\n> ok 6 - three-way not complaining on an untracked path in both\n> ok 7 - three-way not clobbering a working tree file\n> ok 8 - three-way not complaining on an untracked file\n> ok 9 - 3-way not overwriting local changes (setup)\n> ok 10 - 3-way not overwriting local changes (our side)\n> ok 11 - 3-way not overwriting local changes (their side)\n> ok 12 - funny symlink in work tree\n> ok 13 - funny symlink in work tree, un-unlink-able\n> ok 14 - D/F setup\n> ok 15 - D/F\n> ok 16 - D/F resolve\n> not ok 17 - D/F recursive\n> #\n> #\n> # git reset --hard &&\n> # git checkout side-b &&\n> # git merge-recursive branch-point -- side-b side-a\n> #\n> #\n> # failed 1 among 17 test(s)\n> 1..17\n> make[1]: *** [Makefile:77: t1004-read-tree-m-u-wf.sh] Error 1\n> make[1]: Leaving directory '/home/newren/floss/git/t'\n> make: *** [Makefile:63: test] Error 2\n>\n>\n> ...and if go to the toplevel directory and run under prove so I can\n> see all the failures (and run the test suites in parallel), I see:\n>\n> $ cd .. && make DEFAULT_TEST_TARGET=prove GIT_PROVE_OPTS='--timer\n> --state failed,slow,save --jobs 12' test\n> [... lots of output snipped ...]\n> Test Summary Report\n> -------------------\n> t3424-rebase-empty.sh (Wstat: 256 Tests: 20\n> Failed: 18)\n> Failed tests: 3-20\n> Non-zero exit status: 1\n> t3436-rebase-more-options.sh (Wstat: 256 Tests: 19\n> Failed: 17)\n> Failed tests: 2-18\n> Non-zero exit status: 1\n> t4151-am-abort.sh (Wstat: 256 Tests: 20\n> Failed: 12)\n> Failed tests: 5-9, 12-16, 19-20\n> Non-zero exit status: 1\n> t3407-rebase-abort.sh (Wstat: 256 Tests: 17\n> Failed: 8)\n> Failed tests: 2-9\n> Non-zero exit status: 1\n> t3428-rebase-signoff.sh (Wstat: 256 Tests: 7 Failed: 5)\n> Failed tests: 2, 4-7\n> Non-zero exit status: 1\n> t6409-merge-subtree.sh (Wstat: 256 Tests: 12\n> Failed: 5)\n> Failed tests: 2-6\n> Non-zero exit status: 1\n> t7102-reset.sh (Wstat: 256 Tests: 38\n> Failed: 7)\n> Failed tests: 14-20\n> Non-zero exit status: 1\n> t6432-merge-recursive-space-options.sh (Wstat: 256 Tests: 11\n> Failed: 4)\n> Failed tests: 2, 7-8, 11\n> Non-zero exit status: 1\n> t6430-merge-recursive.sh (Wstat: 256 Tests: 37\n> Failed: 15)\n> Failed tests: 10-11, 13-20, 22-24, 28-29\n> Non-zero exit status: 1\n> t3406-rebase-message.sh (Wstat: 256 Tests: 32\n> Failed: 8)\n> Failed tests: 22, 24-27, 29-31\n> Non-zero exit status: 1\n> t4200-rerere.sh (Wstat: 256 Tests: 36\n> Failed: 5)\n> Failed tests: 24-28\n> Non-zero exit status: 1\n> t7201-co.sh (Wstat: 256 Tests: 46\n> Failed: 5)\n> Failed tests: 5-9\n> Non-zero exit status: 1\n> t3418-rebase-continue.sh (Wstat: 256 Tests: 29\n> Failed: 7)\n> Failed tests: 4, 6, 10-12, 26-27\n> Non-zero exit status: 1\n> t3403-rebase-skip.sh (Wstat: 256 Tests: 20\n> Failed: 3)\n> Failed tests: 2, 4, 9\n> Non-zero exit status: 1\n> t4253-am-keep-cr-dos.sh (Wstat: 256 Tests: 7 Failed: 2)\n> Failed tests: 6-7\n> Non-zero exit status: 1\n> t9903-bash-prompt.sh (Wstat: 256 Tests: 67\n> Failed: 39)\n> Failed tests: 16-31, 33-35, 37, 40-44, 46-52, 55-58, 60\n> 62, 67\n> Non-zero exit status: 1\n> t3503-cherry-pick-root.sh (Wstat: 256 Tests: 6 Failed: 2)\n> Failed tests: 5-6\n> Non-zero exit status: 1\n> t3401-rebase-and-am-rename.sh (Wstat: 256 Tests: 10\n> Failed: 2)\n> Failed tests: 4, 10\n> Non-zero exit status: 1\n> t2407-worktree-heads.sh (Wstat: 256 Tests: 12\n> Failed: 2)\n> Failed tests: 4-5\n> Non-zero exit status: 1\n> t5407-post-rewrite-hook.sh (Wstat: 256 Tests: 17\n> Failed: 3)\n> Failed tests: 4-6\n> Non-zero exit status: 1\n> t2500-untracked-overwriting.sh (Wstat: 256 Tests: 10\n> Failed: 2)\n> Failed tests: 9-10\n> Non-zero exit status: 1\n> t4153-am-resume-override-opts.sh (Wstat: 256 Tests: 6 Failed: 1)\n> Failed test: 3\n> Non-zero exit status: 1\n> t1015-read-index-unmerged.sh (Wstat: 256 Tests: 6 Failed: 1)\n> Failed test: 6\n> Non-zero exit status: 1\n> t3509-cherry-pick-merge-df.sh (Wstat: 256 Tests: 9 Failed: 1)\n> Failed test: 9\n> Non-zero exit status: 1\n> t2023-checkout-m.sh (Wstat: 256 Tests: 5 Failed: 1)\n> Failed test: 5\n> Non-zero exit status: 1\n> t7615-diff-algo-with-mergy-operations.sh (Wstat: 256 Tests: 7 Failed: 1)\n> Failed test: 2\n> Non-zero exit status: 1\n> t6427-diff3-conflict-markers.sh (Wstat: 256 Tests: 9 Failed: 1)\n> Failed test: 8\n> Non-zero exit status: 1\n> t1004-read-tree-m-u-wf.sh (Wstat: 256 Tests: 17\n> Failed: 1)\n> Failed test: 17\n> Non-zero exit status: 1\n> t3420-rebase-autostash.sh (Wstat: 256 Tests: 52\n> Failed: 10)\n> Failed tests: 11-17, 21-23\n> Non-zero exit status: 1\n> t4150-am.sh (Wstat: 256 Tests: 87\n> Failed: 33)\n> Failed tests: 34-40, 42-46, 48, 50-54, 57-62, 64-65, 67-71\n> 75, 87\n> Non-zero exit status: 1\n> t7512-status-help.sh (Wstat: 256 Tests: 46\n> Failed: 3)\n> Failed tests: 5-6, 29\n> Non-zero exit status: 1\n> t3400-rebase.sh (Wstat: 256 Tests: 39\n> Failed: 1)\n> Failed test: 30\n> Non-zero exit status: 1\n> t3404-rebase-interactive.sh (Wstat: 256 Tests:\n> 131 Failed: 1)\n> Failed test: 80\n> Non-zero exit status: 1\n> Files=1031, Tests=30662, 70 wallclock secs ( 8.33 usr 2.13 sys +\n> 248.60 cusr 516.60 csys = 775.66 CPU)\n> Result: FAIL\n> make[1]: *** [Makefile:73: prove] Error 1\n> make[1]: Leaving directory '/home/newren/floss/git/t'\n> make: *** [Makefile:3237: test] Error 2\n>\n> I suspect this is a case where it was testing a version of git that\n> you built before making the changes.\n\nThanks! You're right. I ran the tests before running make. After\nrunning make and testing again, it failed.\n\nMeet\n"}]}