{"thread":{"id":"64533","subject":"[PATCH] xdiff: optimize patience diff's LCS search","startedAt":"2025-11-26T10:26:00Z","lastAt":"2025-11-27T02:16:10Z","messageCount":4,"participants":["Yee Cheng Chin via GitGitGadget","Junio C Hamano","Yee Cheng Chin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"531287","messageId":"pull.2109.git.git.1764152756908.gitgitgadget@gmail.com","threadId":"64533","inReplyTo":null,"subject":"[PATCH] xdiff: optimize patience diff's LCS search","fromName":"Yee Cheng Chin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-11-26T10:25:56Z","receivedAt":"2025-11-26T10:26:00Z","isPatch":true,"sender":{"key":"ychin.macvim@gmail.com","avatar":null},"body":"From: Yee Cheng Chin \n\nThe find_longest_common_sequence() function in patience diff is\ninefficient as it calls binary_search() for every unique line it\nencounters when deciding where to put it in the sequence. From\ninstrumentation (using xctrace) on popular repositories, binary_search()\ntakes up 50-60% of the run time within patience_diff() when performing a\ndiff.\n\nTo optimize this, add a boundary condition check before binary_search()\nis called to see if the encountered unique line is located after the\nentire currently tracked longest subsequence. If so, skip the\nunnecessary binary search and simply append the entry to the end of\nsequence. Given that most files compared in a diff are usually quite\nsimilar to each other, this condition is very common, and should be hit\nmuch more frequently than the binary search.\n\nBelow are some end-to-end performance results by timing `git log\n--shortstat --oneline -500 --patience` on different repositories with\nthe old and new code. Generally speaking this seems to give at least\n8-10% speed up. The \"binary search hit %\" column describes how often the\nalgorithm enters the binary search path instead of the new faster path.\nEven in the WebKit case we can see that it's quite rare (1.46%).\n\n| Repo | Speed difference | binary search hit % |\n|----------|------------------|---------------------|\n| vim | 1.27x | 0.01% |\n| pytortch | 1.16x | 0.02% |\n| cpython | 1.14x | 0.06% |\n| ripgrep | 1.14x | 0.03% |\n| git | 1.13x | 0.12% |\n| vscode | 1.09x | 0.10% |\n| WebKit | 1.08x | 1.46% |\n\nThe benchmarks were done using hyperfine, on an Apple M1 Max laptop,\nwith git compiled with `-O3 -flto`.\n\nSigned-off-by: Yee Cheng Chin \n---\n xdiff: optimize patience diff's LCS search\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2109%2Fychin%2Fpatience-optimizations-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2109/ychin/patience-optimizations-v1\nPull-Request: https://github.com/git/git/pull/2109\n\n xdiff/xpatience.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex 669b653580..13ab0d591c 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -211,7 +211,10 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res)\n \tfor (entry = map->first; entry; entry = entry->next) {\n \t\tif (!entry->line2 || entry->line2 == NON_UNIQUE)\n \t\t\tcontinue;\n-\t\ti = binary_search(sequence, longest, entry);\n+\t\tif (longest == 0 || entry->line2 > sequence[longest - 1]->line2)\n+\t\t\ti = longest - 1;\n+\t\telse\n+\t\t\ti = binary_search(sequence, longest, entry);\n \t\tentry->previous = i < 0 ? NULL : sequence[i];\n \t\t++i;\n \t\tif (i <= anchor_i)\n\nbase-commit: 6ab38b7e9cc7adafc304f3204616a4debd49c6e9\n-- \ngitgitgadget\n"},{"id":"531322","messageId":"xmqqy0nsmxvt.fsf@gitster.g","threadId":"64533","inReplyTo":"pull.2109.git.git.1764152756908.gitgitgadget@gmail.com","subject":"Re: [PATCH] xdiff: optimize patience diff's LCS search","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-11-26T18:50:30Z","receivedAt":"2025-11-26T18:50:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Yee Cheng Chin via GitGitGadget\" writes:\n\n> The find_longest_common_sequence() function in patience diff is\n> inefficient as it calls binary_search() for every unique line it\n> encounters when deciding where to put it in the sequence. From\n> instrumentation (using xctrace) on popular repositories, binary_search()\n> takes up 50-60% of the run time within patience_diff() when performing a\n> diff.\n>\n> To optimize this, add a boundary condition check before binary_search()\n> is called to see if the encountered unique line is located after the\n> entire currently tracked longest subsequence. If so, skip the\n> unnecessary binary search and simply append the entry to the end of\n> sequence. Given that most files compared in a diff are usually quite\n> similar to each other, this condition is very common, and should be hit\n> much more frequently than the binary search.\n\nThis is a \"stupid and obvious\" optimization that is quite clever ;-)\n\n> diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\n> index 669b653580..13ab0d591c 100644\n> --- a/xdiff/xpatience.c\n> +++ b/xdiff/xpatience.c\n> @@ -211,7 +211,10 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res)\n> \tfor (entry = map->first; entry; entry = entry->next) {\n> \t\tif (!entry->line2 || entry->line2 == NON_UNIQUE)\n> \t\t\tcontinue;\n> -\t\ti = binary_search(sequence, longest, entry);\n> +\t\tif (longest == 0 || entry->line2 > sequence[longest - 1]->line2)\n> +\t\t\ti = longest - 1;\n> +\t\telse\n> +\t\t\ti = binary_search(sequence, longest, entry);\n\nOK. If we have nothing, or if the thing sorts after the existing\nones, then we do not have to run binsearch to find where to insert\nit. We know we want to append.\n\nNice.\n"},{"id":"531332","messageId":"CAHTeOx_4WSLHJDixkshN-e2pqMS6e2qMKnW25x8ed+GOQBvj3g@mail.gmail.com","threadId":"64533","inReplyTo":"xmqqy0nsmxvt.fsf@gitster.g","subject":"Re: [PATCH] xdiff: optimize patience diff's LCS search","fromName":"Yee Cheng Chin","fromEmail":"ychin.git@gmail.com","sentAt":"2025-11-26T20:15:54Z","receivedAt":"2025-11-26T20:16:31Z","isPatch":true,"sender":{"key":"ychin.git@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1217449?v=4"},"body":"Thanks. I was personally surprised how this simple check ends up\nbypassing the slow path almost completely in most situations.\n\nI just noticed I made a typo in the commit message (misspelled\n\"pytorch\"), and will prepare a v2 with the fixed typo.\n"},{"id":"531364","messageId":"pull.2109.v2.git.git.1764209766305.gitgitgadget@gmail.com","threadId":"64533","inReplyTo":"pull.2109.git.git.1764152756908.gitgitgadget@gmail.com","subject":"[PATCH v2] xdiff: optimize patience diff's LCS search","fromName":"Yee Cheng Chin via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-11-27T02:16:06Z","receivedAt":"2025-11-27T02:16:10Z","isPatch":true,"sender":{"key":"ychin.macvim@gmail.com","avatar":null},"body":"From: Yee Cheng Chin \n\nThe find_longest_common_sequence() function in patience diff is\ninefficient as it calls binary_search() for every unique line it\nencounters when deciding where to put it in the sequence. From\ninstrumentation (using xctrace) on popular repositories, binary_search()\ntakes up 50-60% of the run time within patience_diff() when performing a\ndiff.\n\nTo optimize this, add a boundary condition check before binary_search()\nis called to see if the encountered unique line is located after the\nentire currently tracked longest subsequence. If so, skip the\nunnecessary binary search and simply append the entry to the end of\nsequence. Given that most files compared in a diff are usually quite\nsimilar to each other, this condition is very common, and should be hit\nmuch more frequently than the binary search.\n\nBelow are some end-to-end performance results by timing `git log\n--shortstat --oneline -500 --patience` on different repositories with\nthe old and new code. Generally speaking this seems to give at least\n8-10% speed up. The \"binary search hit %\" column describes how often the\nalgorithm enters the binary search path instead of the new faster path.\nEven in the WebKit case we can see that it's quite rare (1.46%).\n\n| Repo | Speed difference | binary search hit % |\n|----------|------------------|---------------------|\n| vim | 1.27x | 0.01% |\n| pytorch | 1.16x | 0.02% |\n| cpython | 1.14x | 0.06% |\n| ripgrep | 1.14x | 0.03% |\n| git | 1.13x | 0.12% |\n| vscode | 1.09x | 0.10% |\n| WebKit | 1.08x | 1.46% |\n\nThe benchmarks were done using hyperfine, on an Apple M1 Max laptop,\nwith git compiled with `-O3 -flto`.\n\nSigned-off-by: Yee Cheng Chin \n---\n xdiff: optimize patience diff's LCS search\n \n Changes since v1:\n \n * Fix typo in commit message for \"pytortch\"\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2109%2Fychin%2Fpatience-optimizations-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2109/ychin/patience-optimizations-v2\nPull-Request: https://github.com/git/git/pull/2109\n\nRange-diff vs v1:\n\n 1: dc6d509b59 ! 1: 0f8a2dd719 xdiff: optimize patience diff's LCS search\n @@ Commit message\n | Repo | Speed difference | binary search hit % |\n |----------|------------------|---------------------|\n | vim | 1.27x | 0.01% |\n - | pytortch | 1.16x | 0.02% |\n + | pytorch | 1.16x | 0.02% |\n | cpython | 1.14x | 0.06% |\n | ripgrep | 1.14x | 0.03% |\n | git | 1.13x | 0.12% |\n\n\n xdiff/xpatience.c | 5 ++++-\n 1 file changed, 4 insertions(+), 1 deletion(-)\n\ndiff --git a/xdiff/xpatience.c b/xdiff/xpatience.c\nindex 669b653580..13ab0d591c 100644\n--- a/xdiff/xpatience.c\n+++ b/xdiff/xpatience.c\n@@ -211,7 +211,10 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res)\n \tfor (entry = map->first; entry; entry = entry->next) {\n \t\tif (!entry->line2 || entry->line2 == NON_UNIQUE)\n \t\t\tcontinue;\n-\t\ti = binary_search(sequence, longest, entry);\n+\t\tif (longest == 0 || entry->line2 > sequence[longest - 1]->line2)\n+\t\t\ti = longest - 1;\n+\t\telse\n+\t\t\ti = binary_search(sequence, longest, entry);\n \t\tentry->previous = i < 0 ? NULL : sequence[i];\n \t\t++i;\n \t\tif (i <= anchor_i)\n\nbase-commit: 6ab38b7e9cc7adafc304f3204616a4debd49c6e9\n-- \ngitgitgadget\n"}]}