{"thread":{"id":"51702","subject":"[PATCH 0/2] line-log: avoid unnecessary full tree diffs","startedAt":"2019-08-21T11:04:37Z","lastAt":"2019-08-23T10:04:52Z","messageCount":13,"participants":["SZEDER Gábor","Derrick Stolee","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"380879","messageId":"20190821110424.18184-1-szeder.dev@gmail.com","threadId":"51702","inReplyTo":null,"subject":"[PATCH 0/2] line-log: avoid unnecessary full tree diffs","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-08-21T11:04:22Z","receivedAt":"2019-08-21T11:04:37Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"Line-level log can be very slow with rename detection enabled (and its\nenabled by default), which is caused by it using the diff machinery\nvery inefficiently.  The second patch fixes the issue and make it much\nfaster, especially in large repositories.\n\nThis patch series is independent from my other patch series making\nline-level log incremental [1].  The two can be merged easily, as the\nchanges to 'line-log.c' don't overlap, and the conflict in\n't4211-line-log.sh' is trivial (both series add new tests at the end\nof that test script).\n\n\n[1] https://public-inbox.org/git/6a576e13-79e6-43be-c4a8-065e7a8310ea@gmail.com/T/\n\nSZEDER Gábor (2):\n  line-log: extract pathspec parsing from line ranges into a helper\n    function\n  line-log: avoid unnecessary full tree diffs\n\n line-log.c          | 71 ++++++++++++++++++++++++++++-----------\n t/t4211-line-log.sh | 82 +++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 134 insertions(+), 19 deletions(-)\n\n-- \n2.23.0.352.gebb2b55eae\n\n"},{"id":"380880","messageId":"20190821110424.18184-2-szeder.dev@gmail.com","threadId":"51702","inReplyTo":"20190821110424.18184-1-szeder.dev@gmail.com","subject":"[PATCH 1/2] line-log: extract pathspec parsing from line ranges into a helper function","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-08-21T11:04:23Z","receivedAt":"2019-08-21T11:04:39Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"A helper function to parse the paths involved in the line ranges and\nto turn them into a pathspec will be useful in the next patch.\n\nSigned-off-by: SZEDER Gábor <szeder.dev@gmail.com>\n---\n line-log.c | 32 ++++++++++++++++++--------------\n 1 file changed, 18 insertions(+), 14 deletions(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex 3aff1849e7..fddd91f060 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -737,6 +737,22 @@ static struct line_log_data *lookup_line_range(struct rev_info *revs,\n \treturn ret;\n }\n \n+static void parse_pathspec_from_ranges(struct pathspec *pathspec,\n+\t\t\t\t       struct line_log_data *range)\n+{\n+\tstruct line_log_data *r;\n+\tstruct argv_array array = ARGV_ARRAY_INIT;\n+\tconst char **paths;\n+\n+\tfor (r = range; r; r = r->next)\n+\t\targv_array_push(&array, r->path);\n+\tpaths = argv_array_detach(&array);\n+\n+\tparse_pathspec(pathspec, 0, PATHSPEC_PREFER_FULL, \"\", paths);\n+\t/* strings are now owned by pathspec */\n+\tfree(paths);\n+}\n+\n void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args)\n {\n \tstruct commit *commit = NULL;\n@@ -746,20 +762,8 @@ void line_log_init(struct rev_info *rev, const char *prefix, struct string_list\n \trange = parse_lines(rev->diffopt.repo, commit, prefix, args);\n \tadd_line_range(rev, commit, range);\n \n-\tif (!rev->diffopt.detect_rename) {\n-\t\tstruct line_log_data *r;\n-\t\tstruct argv_array array = ARGV_ARRAY_INIT;\n-\t\tconst char **paths;\n-\n-\t\tfor (r = range; r; r = r->next)\n-\t\t\targv_array_push(&array, r->path);\n-\t\tpaths = argv_array_detach(&array);\n-\n-\t\tparse_pathspec(&rev->diffopt.pathspec, 0,\n-\t\t\t       PATHSPEC_PREFER_FULL, \"\", paths);\n-\t\t/* strings are now owned by pathspec */\n-\t\tfree(paths);\n-\t}\n+\tif (!rev->diffopt.detect_rename)\n+\t\tparse_pathspec_from_ranges(&rev->diffopt.pathspec, range);\n }\n \n static void move_diff_queue(struct diff_queue_struct *dst,\n-- \n2.23.0.352.gebb2b55eae\n\n"},{"id":"380881","messageId":"20190821110424.18184-3-szeder.dev@gmail.com","threadId":"51702","inReplyTo":"20190821110424.18184-1-szeder.dev@gmail.com","subject":"[PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-08-21T11:04:24Z","receivedAt":"2019-08-21T11:04:40Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"With rename detection enabled the line-level log is able to trace the\nevolution of line ranges across whole-file renames [1].  Alas, to\nachieve that it uses the diff machinery very inefficiently, making the\noperation very slow [2].  And since rename detection is enabled by\ndefault, the line-level log is very slow by default.\n\nWhen the line-level log processes a commit with rename detection\nenabled, it currently does the following (see queue_diffs()):\n\n  1. Computes a full tree diff between the commit and (one of) its\n     parent(s), i.e. invokes diff_tree_oid() with an empty\n     'diffopt->pathspec'.\n  2. Checks whether any paths in the line ranges were modified.\n  3. Checks whether any modified paths in the line ranges are missing\n     in the parent commit's tree.\n  4. If there is such a missing path, then calls diffcore_std() to\n     figure out whether the path was indeed renamed based on the\n     previously computed full tree diff.\n  5. Continues doing stuff that are unrelated to the slowness.\n\nSo basically the line-level log computes a full tree diff for each\ncommit-parent pair in step (1) to be used for rename detection in step\n(4) in the off chance that an interesting path is missing from the\nparent.\n\nAvoid these expensive and mostly unnecessary full tree diffs by\nlimiting the diffs to paths in the line ranges.  This is much cheaper,\nand makes step (2) unnecessary.  If it turns out that an interesting\npath is missing from the parent, then fall back and compute a full\ntree diff, so the rename detection will still work.\n\nCare must be taken when to update the pathspec used to limit the diff\nin case of renames.  A path might be renamed on one branch and\nmodified on several parallel running branches, and while processing\ncommits on these branches the line-level log might have to alternate\nbetween looking at a path's new and old name.  However, at any one\ntime there is only a single 'diffopt->pathspec'.\n\nSo add a step (0) to the above to ensure that the paths in the\npathspec match the paths in the line ranges associated with the\ncurrently processed commit, and re-parse the pathspec from the paths\nin the line ranges if they differ.\n\nThe new test cases include a specially crafted piece of history with\ntwo merged branches and two files, where each branch modifies both\nfiles, renames on of them, and then modifies both again.  Then two\nseparate 'git log -L' invocations check the line-level log of each of\nthose two files, which ensures that at least one of those invocations\nhave to do that back-and-forth between the file's old and new name (no\nmatter which branch is traversed first).  't/t4211-line-log.sh'\nalready contains two tests involving renames, they don't don't trigger\nthis back-and-forth.\n\nAvoiding these unnecessary full tree diffs can have huge impact on\nperformance, especially in big repositories with big trees and mergy\nhistory.  Tracing the evolution of a function through the whole\nhistory:\n\n  # git.git\n  $ time git --no-pager log -L:read_alternate_refs:sha1-file.c v2.23.0\n\n  Before:\n\n    real    0m8.874s\n    user    0m8.816s\n    sys     0m0.057s\n\n  After:\n\n    real    0m2.516s\n    user    0m2.456s\n    sys     0m0.060s\n\n  # linux.git\n  $ time ~/src/git/git --no-pager log \\\n    -L:build_restore_work_registers:arch/mips/mm/tlbex.c v5.2\n\n  Before:\n\n    real    3m50.033s\n    user    3m48.041s\n    sys     0m0.300s\n\n  After:\n\n    real    0m2.599s\n    user    0m2.466s\n    sys     0m0.157s\n\nThat's just over 88x speedup.\n\n[1] Line-level log's rename following is quite similar to 'git log\n    --follow path', with the notable differences that it does handle\n    multiple paths at once as well, and that it doesn't show the\n    commit performing the rename if it's an exact rename.\n\n[2] This slowness might not have been apparent initially, because back\n    when the line-level log feature was introduced rename detection\n    was not yet enabled by default; 12da1d1f6f (Implement line-history\n    search (git log -L), 2013-03-28) and 5404c116aa (diff: activate\n    diff.renames by default, 2016-02-25).\n\nSigned-off-by: SZEDER Gábor <szeder.dev@gmail.com>\n---\n line-log.c          | 43 ++++++++++++++++++++----\n t/t4211-line-log.sh | 82 +++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 118 insertions(+), 7 deletions(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex fddd91f060..9010e00950 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -737,6 +737,22 @@ static struct line_log_data *lookup_line_range(struct rev_info *revs,\n \treturn ret;\n }\n \n+static int same_paths_in_pathspec_and_range(struct pathspec *pathspec,\n+\t\t\t\t\t    struct line_log_data *range)\n+{\n+\tint i;\n+\tstruct line_log_data *r;\n+\n+\tfor (i = 0, r = range; i < pathspec->nr && r; i++, r = r->next)\n+\t\tif (strcmp(pathspec->items[i].match, r->path))\n+\t\t\treturn 0;\n+\tif (i < pathspec->nr || r)\n+\t\t/* different number of pathspec items and ranges */\n+\t\treturn 0;\n+\n+\treturn 1;\n+}\n+\n static void parse_pathspec_from_ranges(struct pathspec *pathspec,\n \t\t\t\t       struct line_log_data *range)\n {\n@@ -762,8 +778,7 @@ void line_log_init(struct rev_info *rev, const char *prefix, struct string_list\n \trange = parse_lines(rev->diffopt.repo, commit, prefix, args);\n \tadd_line_range(rev, commit, range);\n \n-\tif (!rev->diffopt.detect_rename)\n-\t\tparse_pathspec_from_ranges(&rev->diffopt.pathspec, range);\n+\tparse_pathspec_from_ranges(&rev->diffopt.pathspec, range);\n }\n \n static void move_diff_queue(struct diff_queue_struct *dst,\n@@ -821,15 +836,29 @@ static void queue_diffs(struct line_log_data *range,\n \t\t\tstruct diff_queue_struct *queue,\n \t\t\tstruct commit *commit, struct commit *parent)\n {\n+\tstruct object_id *tree_oid, *parent_tree_oid;\n+\n \tassert(commit);\n \n+\ttree_oid = get_commit_tree_oid(commit);\n+\tparent_tree_oid = parent ? get_commit_tree_oid(parent) : NULL;\n+\n+\tif (opt->detect_rename &&\n+\t    !same_paths_in_pathspec_and_range(&opt->pathspec, range)) {\n+\t\tclear_pathspec(&opt->pathspec);\n+\t\tparse_pathspec_from_ranges(&opt->pathspec, range);\n+\t}\n \tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n-\tdiff_tree_oid(parent ? get_commit_tree_oid(parent) : NULL,\n-\t\t      get_commit_tree_oid(commit), \"\", opt);\n-\tif (opt->detect_rename) {\n+\tdiff_tree_oid(parent_tree_oid, tree_oid, \"\", opt);\n+\tif (opt->detect_rename && diff_might_be_rename()) {\n+\t\t/* must look at the full tree diff to detect renames */\n+\t\tclear_pathspec(&opt->pathspec);\n+\t\tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n+\n+\t\tdiff_tree_oid(parent_tree_oid, tree_oid, \"\", opt);\n+\n \t\tfilter_diffs_for_paths(range, 1);\n-\t\tif (diff_might_be_rename())\n-\t\t\tdiffcore_std(opt);\n+\t\tdiffcore_std(opt);\n \t\tfilter_diffs_for_paths(range, 0);\n \t}\n \tmove_diff_queue(queue, &diff_queued_diff);\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex 1db7bd0f59..8319163744 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -132,4 +132,86 @@ test_expect_success '--raw is forbidden' '\n \ttest_must_fail git log -L1,24:b.c --raw\n '\n \n+test_expect_success 'setup for checking fancy rename following' '\n+\tgit checkout --orphan moves-start &&\n+\tgit reset --hard &&\n+\n+\tprintf \"%s\\n\"    12 13 14 15      b c d e   >file-1 &&\n+\tprintf \"%s\\n\"    22 23 24 25      B C D E   >file-2 &&\n+\tgit add file-1 file-2 &&\n+\ttest_tick &&\n+\tgit commit -m \"Add file-1 and file-2\" &&\n+\toid_add_f1_f2=$(git rev-parse --short HEAD) &&\n+\n+\tgit checkout -b moves-main &&\n+\tprintf \"%s\\n\" 11 12 13 14 15      b c d e   >file-1 &&\n+\tgit commit -a -m \"Modify file-1 on main\" &&\n+\toid_mod_f1_main=$(git rev-parse --short HEAD) &&\n+\n+\tprintf \"%s\\n\" 21 22 23 24 25      B C D E   >file-2 &&\n+\tgit commit -a -m \"Modify file-2 on main #1\" &&\n+\toid_mod_f2_main_1=$(git rev-parse --short HEAD) &&\n+\n+\tgit mv file-1 renamed-1 &&\n+\tgit commit -m \"Rename file-1 to renamed-1 on main\" &&\n+\n+\tprintf \"%s\\n\" 11 12 13 14 15      b c d e f >renamed-1 &&\n+\tgit commit -a -m \"Modify renamed-1 on main\" &&\n+\toid_mod_r1_main=$(git rev-parse --short HEAD) &&\n+\n+\tprintf \"%s\\n\" 21 22 23 24 25      B C D E F >file-2 &&\n+\tgit commit -a -m \"Modify file-2 on main #2\" &&\n+\toid_mod_f2_main_2=$(git rev-parse --short HEAD) &&\n+\n+\tgit checkout -b moves-side moves-start &&\n+\tprintf \"%s\\n\"    12 13 14 15 16   b c d e   >file-1 &&\n+\tgit commit -a -m \"Modify file-1 on side #1\" &&\n+\toid_mod_f1_side_1=$(git rev-parse --short HEAD) &&\n+\n+\tprintf \"%s\\n\"    22 23 24 25 26   B C D E   >file-2 &&\n+\tgit commit -a -m \"Modify file-2 on side\" &&\n+\toid_mod_f2_side=$(git rev-parse --short HEAD) &&\n+\n+\tgit mv file-2 renamed-2 &&\n+\tgit commit -m \"Rename file-2 to renamed-2 on side\" &&\n+\n+\tprintf \"%s\\n\"    12 13 14 15 16 a b c d e   >file-1 &&\n+\tgit commit -a -m \"Modify file-1 on side #2\" &&\n+\toid_mod_f1_side_2=$(git rev-parse --short HEAD) &&\n+\n+\tprintf \"%s\\n\"    22 23 24 25 26 A B C D E   >renamed-2 &&\n+\tgit commit -a -m \"Modify renamed-2 on side\" &&\n+\toid_mod_r2_side=$(git rev-parse --short HEAD) &&\n+\n+\tgit checkout moves-main &&\n+\tgit merge moves-side &&\n+\toid_merge=$(git rev-parse --short HEAD)\n+'\n+\n+test_expect_success 'fancy rename following #1' '\n+\tcat >expect <<-EOF &&\n+\t$oid_merge Merge branch '\\''moves-side'\\'' into moves-main\n+\t$oid_mod_f1_side_2 Modify file-1 on side #2\n+\t$oid_mod_f1_side_1 Modify file-1 on side #1\n+\t$oid_mod_r1_main Modify renamed-1 on main\n+\t$oid_mod_f1_main Modify file-1 on main\n+\t$oid_add_f1_f2 Add file-1 and file-2\n+\tEOF\n+\tgit log -L1:renamed-1 --oneline --no-patch >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'fancy rename following #2' '\n+\tcat >expect <<-EOF &&\n+\t$oid_merge Merge branch '\\''moves-side'\\'' into moves-main\n+\t$oid_mod_r2_side Modify renamed-2 on side\n+\t$oid_mod_f2_side Modify file-2 on side\n+\t$oid_mod_f2_main_2 Modify file-2 on main #2\n+\t$oid_mod_f2_main_1 Modify file-2 on main #1\n+\t$oid_add_f1_f2 Add file-1 and file-2\n+\tEOF\n+\tgit log -L1:renamed-2 --oneline --no-patch >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.23.0.352.gebb2b55eae\n\n"},{"id":"380891","messageId":"e52e867b-af17-d239-11b5-e0c6353acc2f@gmail.com","threadId":"51702","inReplyTo":"20190821110424.18184-3-szeder.dev@gmail.com","subject":"Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-08-21T15:53:28Z","receivedAt":"2019-08-21T15:53:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/21/2019 7:04 AM, SZEDER Gábor wrote:\n> With rename detection enabled the line-level log is able to trace the\n> evolution of line ranges across whole-file renames [1].  Alas, to\n> achieve that it uses the diff machinery very inefficiently, making the\n> operation very slow [2].  And since rename detection is enabled by\n> default, the line-level log is very slow by default.\n> \n> When the line-level log processes a commit with rename detection\n> enabled, it currently does the following (see queue_diffs()):\n> \n>   1. Computes a full tree diff between the commit and (one of) its\n>      parent(s), i.e. invokes diff_tree_oid() with an empty\n>      'diffopt->pathspec'.\n>   2. Checks whether any paths in the line ranges were modified.\n>   3. Checks whether any modified paths in the line ranges are missing\n>      in the parent commit's tree.\n>   4. If there is such a missing path, then calls diffcore_std() to\n>      figure out whether the path was indeed renamed based on the\n>      previously computed full tree diff.\n>   5. Continues doing stuff that are unrelated to the slowness.\n> \n> So basically the line-level log computes a full tree diff for each\n> commit-parent pair in step (1) to be used for rename detection in step\n> (4) in the off chance that an interesting path is missing from the\n> parent.\n> \n> Avoid these expensive and mostly unnecessary full tree diffs by\n> limiting the diffs to paths in the line ranges.  This is much cheaper,\n> and makes step (2) unnecessary.  If it turns out that an interesting\n> path is missing from the parent, then fall back and compute a full\n> tree diff, so the rename detection will still work.\n\nI applied your patches and tried them on our VFS-enabled version of Git\n(see [1]). Unfortunately, the new logic is still triggering rename\ndetection, as measured by the number of objects being downloaded.\n\n[1] https://github.com/microsoft/git/pull/182\n\nMy *guess* is that the repo has a lot of merge commits, and for many\nof those, the file does not exist in the first parent. Since we are\nessentially doing a --full-history, this means that edge tries a\nrename detection. If we used the file-history simplification route of\ntraveling along a treesame edge instead of caring about both parents,\nthen maybe this would be avoided.\n\nI could also be completely wrong about how this line-log code works\nwith regards to --full-history.\n\n> Care must be taken when to update the pathspec used to limit the diff\n> in case of renames.  A path might be renamed on one branch and\n> modified on several parallel running branches, and while processing\n> commits on these branches the line-level log might have to alternate\n> between looking at a path's new and old name.  However, at any one\n> time there is only a single 'diffopt->pathspec'.\n> \n> So add a step (0) to the above to ensure that the paths in the\n> pathspec match the paths in the line ranges associated with the\n> currently processed commit, and re-parse the pathspec from the paths\n> in the line ranges if they differ.\n> \n> The new test cases include a specially crafted piece of history with\n> two merged branches and two files, where each branch modifies both\n> files, renames on of them, and then modifies both again.  Then two\n> separate 'git log -L' invocations check the line-level log of each of\n> those two files, which ensures that at least one of those invocations\n> have to do that back-and-forth between the file's old and new name (no\n> matter which branch is traversed first).  't/t4211-line-log.sh'\n> already contains two tests involving renames, they don't don't trigger\n> this back-and-forth.\n> \n> Avoiding these unnecessary full tree diffs can have huge impact on\n> performance, especially in big repositories with big trees and mergy\n> history.  Tracing the evolution of a function through the whole\n> history:\n> \n>   # git.git\n>   $ time git --no-pager log -L:read_alternate_refs:sha1-file.c v2.23.0\n> \n>   Before:\n> \n>     real    0m8.874s\n>     user    0m8.816s\n>     sys     0m0.057s\n> \n>   After:\n> \n>     real    0m2.516s\n>     user    0m2.456s\n>     sys     0m0.060s\n> \n>   # linux.git\n>   $ time ~/src/git/git --no-pager log \\\n>     -L:build_restore_work_registers:arch/mips/mm/tlbex.c v5.2\n> \n>   Before:\n> \n>     real    3m50.033s\n>     user    3m48.041s\n>     sys     0m0.300s\n> \n>   After:\n> \n>     real    0m2.599s\n>     user    0m2.466s\n>     sys     0m0.157s\n> \n> That's just over 88x speedup.\n\nThese performance numbers are great! Please don't let my complaints of\n\"it doesn't work for my particularly bad example\" be a deterrent to this\nchange. If I figure out what is going on in my case, then I can create\nan update on top of your changes.\n\n> diff --git a/line-log.c b/line-log.c\n> index fddd91f060..9010e00950 100644\n> --- a/line-log.c\n> +++ b/line-log.c\n> @@ -737,6 +737,22 @@ static struct line_log_data *lookup_line_range(struct rev_info *revs,\n>  \treturn ret;\n>  }\n>  \n> +static int same_paths_in_pathspec_and_range(struct pathspec *pathspec,\n> +\t\t\t\t\t    struct line_log_data *range)\n> +{\n> +\tint i;\n> +\tstruct line_log_data *r;\n> +\n> +\tfor (i = 0, r = range; i < pathspec->nr && r; i++, r = r->next)\n> +\t\tif (strcmp(pathspec->items[i].match, r->path))\n> +\t\t\treturn 0;\n> +\tif (i < pathspec->nr || r)\n> +\t\t/* different number of pathspec items and ranges */\n> +\t\treturn 0;\n> +\n> +\treturn 1;\n> +}\n\nThis method is easy to digest. Looks correct.\n\n> @@ -762,8 +778,7 @@ void line_log_init(struct rev_info *rev, const char *prefix, struct string_list\n>  \trange = parse_lines(rev->diffopt.repo, commit, prefix, args);\n>  \tadd_line_range(rev, commit, range);\n>  \n> -\tif (!rev->diffopt.detect_rename)\n> -\t\tparse_pathspec_from_ranges(&rev->diffopt.pathspec, range);\n> +\tparse_pathspec_from_ranges(&rev->diffopt.pathspec, range);\n>  }\n\nSo we always parse the pathspec, even if we don't do detect renames.\n\n> @@ -821,15 +836,29 @@ static void queue_diffs(struct line_log_data *range,\n>  \t\t\tstruct diff_queue_struct *queue,\n>  \t\t\tstruct commit *commit, struct commit *parent)\n>  {\n> +\tstruct object_id *tree_oid, *parent_tree_oid;\n> +\n>  \tassert(commit);\n>  \n> +\ttree_oid = get_commit_tree_oid(commit);\n> +\tparent_tree_oid = parent ? get_commit_tree_oid(parent) : NULL;\n> +\n> +\tif (opt->detect_rename &&\n> +\t    !same_paths_in_pathspec_and_range(&opt->pathspec, range)) {\n> +\t\tclear_pathspec(&opt->pathspec);\n> +\t\tparse_pathspec_from_ranges(&opt->pathspec, range);\n> +\t}\n\nIf we are detecting renames and our pathspec is not up-to-date with the\nrange, then clear the pathspec and reparse. Makes sense.\n\n>  \tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n> -\tdiff_tree_oid(parent ? get_commit_tree_oid(parent) : NULL,\n> -\t\t      get_commit_tree_oid(commit), \"\", opt);\n> +\tdiff_tree_oid(parent_tree_oid, tree_oid, \"\", opt);\n\n(I rearranged a pair of -/+ lines in the diff to highlight this change.)\n\nMakes sense, parent_tree_oid above was set using the same conditional.\n\n> -\tif (opt->detect_rename) {\n> +\tif (opt->detect_rename && diff_might_be_rename()) {\n\nHere is the crux of the matter: diff_might_be_rename() can prevent\nthe full tree diff.\n\n> +\t\t/* must look at the full tree diff to detect renames */\n> +\t\tclear_pathspec(&opt->pathspec);\n> +\t\tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n> +\n> +\t\tdiff_tree_oid(parent_tree_oid, tree_oid, \"\", opt);\n> +\n>  \t\tfilter_diffs_for_paths(range, 1);\n> -\t\tif (diff_might_be_rename())\n> -\t\t\tdiffcore_std(opt);\n> +\t\tdiffcore_std(opt);\n>  \t\tfilter_diffs_for_paths(range, 0);\n>  \t}\n\nSo before, diff_might_be_rename() already prevented diffcore_std(), but\nnow it also prevents clearing the pathspec. diff_might_be_rename() has\na simple implementation:\n\nstatic inline int diff_might_be_rename(void)\n{\n        int i;\n        for (i = 0; i < diff_queued_diff.nr; i++)\n                if (!DIFF_FILE_VALID(diff_queued_diff.queue[i]->one)) {\n                        /* fprintf(stderr, \"diff_might_be_rename found creation of: %s\\n\", */\n                        /*      diff_queued_diff.queue[i]->two->path); */\n                        return 1;\n                }\n        return 0;\n}\n\nSo yes, it is triggered by any path appearing in the child but not\na parent.\n\n>  \tmove_diff_queue(queue, &diff_queued_diff);\n> diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\n> index 1db7bd0f59..8319163744 100755\n> --- a/t/t4211-line-log.sh\n> +++ b/t/t4211-line-log.sh\n> @@ -132,4 +132,86 @@ test_expect_success '--raw is forbidden' '\n>  \ttest_must_fail git log -L1,24:b.c --raw\n>  '\n>  \n> +test_expect_success 'setup for checking fancy rename following' '\n> +\tgit checkout --orphan moves-start &&\n> +\tgit reset --hard &&\n> +\n> +\tprintf \"%s\\n\"    12 13 14 15      b c d e   >file-1 &&\n> +\tprintf \"%s\\n\"    22 23 24 25      B C D E   >file-2 &&\n> +\tgit add file-1 file-2 &&\n> +\ttest_tick &&\n> +\tgit commit -m \"Add file-1 and file-2\" &&\n> +\toid_add_f1_f2=$(git rev-parse --short HEAD) &&\n> +\n> +\tgit checkout -b moves-main &&\n> +\tprintf \"%s\\n\" 11 12 13 14 15      b c d e   >file-1 &&\n> +\tgit commit -a -m \"Modify file-1 on main\" &&\n> +\toid_mod_f1_main=$(git rev-parse --short HEAD) &&\n> +\n> +\tprintf \"%s\\n\" 21 22 23 24 25      B C D E   >file-2 &&\n> +\tgit commit -a -m \"Modify file-2 on main #1\" &&\n> +\toid_mod_f2_main_1=$(git rev-parse --short HEAD) &&\n> +\n> +\tgit mv file-1 renamed-1 &&\n> +\tgit commit -m \"Rename file-1 to renamed-1 on main\" &&\n> +\n> +\tprintf \"%s\\n\" 11 12 13 14 15      b c d e f >renamed-1 &&\n> +\tgit commit -a -m \"Modify renamed-1 on main\" &&\n> +\toid_mod_r1_main=$(git rev-parse --short HEAD) &&\n> +\n> +\tprintf \"%s\\n\" 21 22 23 24 25      B C D E F >file-2 &&\n> +\tgit commit -a -m \"Modify file-2 on main #2\" &&\n> +\toid_mod_f2_main_2=$(git rev-parse --short HEAD) &&\n> +\n> +\tgit checkout -b moves-side moves-start &&\n> +\tprintf \"%s\\n\"    12 13 14 15 16   b c d e   >file-1 &&\n> +\tgit commit -a -m \"Modify file-1 on side #1\" &&\n> +\toid_mod_f1_side_1=$(git rev-parse --short HEAD) &&\n> +\n> +\tprintf \"%s\\n\"    22 23 24 25 26   B C D E   >file-2 &&\n> +\tgit commit -a -m \"Modify file-2 on side\" &&\n> +\toid_mod_f2_side=$(git rev-parse --short HEAD) &&\n> +\n> +\tgit mv file-2 renamed-2 &&\n> +\tgit commit -m \"Rename file-2 to renamed-2 on side\" &&\n> +\n> +\tprintf \"%s\\n\"    12 13 14 15 16 a b c d e   >file-1 &&\n> +\tgit commit -a -m \"Modify file-1 on side #2\" &&\n> +\toid_mod_f1_side_2=$(git rev-parse --short HEAD) &&\n> +\n> +\tprintf \"%s\\n\"    22 23 24 25 26 A B C D E   >renamed-2 &&\n> +\tgit commit -a -m \"Modify renamed-2 on side\" &&\n> +\toid_mod_r2_side=$(git rev-parse --short HEAD) &&\n> +\n> +\tgit checkout moves-main &&\n> +\tgit merge moves-side &&\n> +\toid_merge=$(git rev-parse --short HEAD)\n> +'\n> +\n> +test_expect_success 'fancy rename following #1' '\n> +\tcat >expect <<-EOF &&\n> +\t$oid_merge Merge branch '\\''moves-side'\\'' into moves-main\n> +\t$oid_mod_f1_side_2 Modify file-1 on side #2\n> +\t$oid_mod_f1_side_1 Modify file-1 on side #1\n> +\t$oid_mod_r1_main Modify renamed-1 on main\n> +\t$oid_mod_f1_main Modify file-1 on main\n> +\t$oid_add_f1_f2 Add file-1 and file-2\n> +\tEOF\n> +\tgit log -L1:renamed-1 --oneline --no-patch >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n> +test_expect_success 'fancy rename following #2' '\n> +\tcat >expect <<-EOF &&\n> +\t$oid_merge Merge branch '\\''moves-side'\\'' into moves-main\n> +\t$oid_mod_r2_side Modify renamed-2 on side\n> +\t$oid_mod_f2_side Modify file-2 on side\n> +\t$oid_mod_f2_main_2 Modify file-2 on main #2\n> +\t$oid_mod_f2_main_1 Modify file-2 on main #1\n> +\t$oid_add_f1_f2 Add file-1 and file-2\n> +\tEOF\n> +\tgit log -L1:renamed-2 --oneline --no-patch >actual &&\n> +\ttest_cmp expect actual\n> +'\n\nThese look to be suitably interesting test cases. Thanks!\n\nLooking at your patch, I can mostly follow the logic, but my\nunfamiliarity with the code is keeping me from being confident\nin full understanding. I hope someone who is familiar can\nchime in, because I really like the direction here.\n\nHopefully I will have time in the next few weeks to revisit\nthis and work to resolve my abnormal case.\n\n-Stolee\n"},{"id":"380894","messageId":"xmqqtvaas9zs.fsf@gitster-ct.c.googlers.com","threadId":"51702","inReplyTo":"20190821110424.18184-3-szeder.dev@gmail.com","subject":"Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-08-21T17:29:11Z","receivedAt":"2019-08-21T17:29:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"SZEDER Gábor <szeder.dev@gmail.com> writes:\n\n> So basically the line-level log computes a full tree diff for each\n> commit-parent pair in step (1) to be used for rename detection in step\n> (4) in the off chance that an interesting path is missing from the\n> parent.\n\nGood explanation.  As we are not supporting swapping of two (or\nmore) files, we only need rename processing when a path we have been\ninspecting disappears, at which point it is worth spending cycles to\nsee where the path used to be in the parent commit.\n\n> [1] Line-level log's rename following is quite similar to 'git log\n>     --follow path', with the notable differences that it does handle\n>     multiple paths at once as well, and that it doesn't show the\n>     commit performing the rename if it's an exact rename.\n\nYeah, it's one of the reasons why \"log --follow\" is not (yet) a\nserious \"feature\" but merely a \"checkbox item\".\n\n> [2] This slowness might not have been apparent initially, because back\n>     when the line-level log feature was introduced rename detection\n\ns/introduced/&,/\n\n>     was not yet enabled by default; 12da1d1f6f (Implement line-history\n>     search (git log -L), 2013-03-28) and 5404c116aa (diff: activate\n>     diff.renames by default, 2016-02-25).\n\ns/\\.$/ are about 3 years apart&/ or something like that to make what\nfollows the semicolon a full sentence?\n\n"},{"id":"380895","messageId":"20190821173515.GY20404@szeder.dev","threadId":"51702","inReplyTo":"e52e867b-af17-d239-11b5-e0c6353acc2f@gmail.com","subject":"Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-08-21T17:35:15Z","receivedAt":"2019-08-21T17:35:22Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Wed, Aug 21, 2019 at 11:53:28AM -0400, Derrick Stolee wrote:\n> On 8/21/2019 7:04 AM, SZEDER Gábor wrote:\n> > With rename detection enabled the line-level log is able to trace the\n> > evolution of line ranges across whole-file renames [1].  Alas, to\n> > achieve that it uses the diff machinery very inefficiently, making the\n> > operation very slow [2].  And since rename detection is enabled by\n> > default, the line-level log is very slow by default.\n> > \n> > When the line-level log processes a commit with rename detection\n> > enabled, it currently does the following (see queue_diffs()):\n> > \n> >   1. Computes a full tree diff between the commit and (one of) its\n> >      parent(s), i.e. invokes diff_tree_oid() with an empty\n> >      'diffopt->pathspec'.\n> >   2. Checks whether any paths in the line ranges were modified.\n> >   3. Checks whether any modified paths in the line ranges are missing\n> >      in the parent commit's tree.\n> >   4. If there is such a missing path, then calls diffcore_std() to\n> >      figure out whether the path was indeed renamed based on the\n> >      previously computed full tree diff.\n> >   5. Continues doing stuff that are unrelated to the slowness.\n> > \n> > So basically the line-level log computes a full tree diff for each\n> > commit-parent pair in step (1) to be used for rename detection in step\n> > (4) in the off chance that an interesting path is missing from the\n> > parent.\n> > \n> > Avoid these expensive and mostly unnecessary full tree diffs by\n> > limiting the diffs to paths in the line ranges.  This is much cheaper,\n> > and makes step (2) unnecessary.  If it turns out that an interesting\n> > path is missing from the parent, then fall back and compute a full\n> > tree diff, so the rename detection will still work.\n> \n> I applied your patches and tried them on our VFS-enabled version of Git\n> (see [1]). Unfortunately, the new logic is still triggering rename\n> detection, as measured by the number of objects being downloaded.\n\nWell, the goal of this patch was to avoid full tree diffs if possible,\nnot to avoid rename detection :)\n\nAnyway, I wonder how does 'git log -L1:your-evil-path --no-renames'\nfare as a baseline?\n\n> My *guess* is that the repo has a lot of merge commits, and for many\n> of those, the file does not exist in the first parent.\n\nYeah, actual renames are only one of the possible causes that trigger\nrename detection.  Surprisingly (well, to me, at least), in git.git\nrename detection in line-level log is most often triggered by the\nsubtree merges of gitk and git-gui, not by actual renames.\n\n> Since we are\n> essentially doing a --full-history, this means that edge tries a\n> rename detection. If we used the file-history simplification route of\n> traveling along a treesame edge instead of caring about both parents,\n> then maybe this would be avoided.\n> \n> I could also be completely wrong about how this line-log code works\n> with regards to --full-history.\n\nLine-level log doesn't do '--full-history', though it does seem to\ncompute more diffs than a simple 'git log -- path'.\n\nI applied the following diff on current master to add a bit of ad-hoc\ntracing to see how many and which commit-parent diffs are computed:\n\ndiff --git a/line-log.c b/line-log.c\nindex 9010e00950..64f2c4d216 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -839,6 +839,8 @@ static void queue_diffs(struct line_log_data *range,\n \tstruct object_id *tree_oid, *parent_tree_oid;\n \n \tassert(commit);\n+\tfprintf(stderr, \"%s %s\\n\", oid_to_hex(&commit->object.oid),\n+\t\tparent ? oid_to_hex(&parent->object.oid) : \"-\");\n \n \ttree_oid = get_commit_tree_oid(commit);\n \tparent_tree_oid = parent ? get_commit_tree_oid(parent) : NULL;\ndiff --git a/revision.c b/revision.c\nindex 07412297f0..3f2182e32a 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -627,6 +627,8 @@ static int rev_compare_tree(struct rev_info *revs,\n \tstruct tree *t1 = get_commit_tree(parent);\n \tstruct tree *t2 = get_commit_tree(commit);\n \n+\tfprintf(stderr, \"%s %s\\n\", oid_to_hex(&commit->object.oid),\n+\t\tparent ? oid_to_hex(&parent->object.oid) : \"-\");\n \tif (!t1)\n \t\treturn REV_TREE_NEW;\n \tif (!t2)\n\n\n  $ ./git log v2.23.0 -- builtin/rev-list.c >/dev/null 2>P\n  $ ./git log --full-history v2.23.0 -- builtin/rev-list.c >/dev/null 2>FH\n  $ ./git log -L1:builtin/rev-list.c v2.23.0 >/dev/null 2>LL\n  $ wc -l P FH LL\n    17230 P\n    70842 FH\n    25995 LL\n   114067 total\n\nSo line-level log clearly computes a lot less diffs than\n'--full-history', though still about 50% more than a regular\npathspec-limited history traversal.  Looking at the commit-parent\npairs in the output, it appears that the difference comes mostly from\nmerge commits, because line-level log compares a merge commit with all\nof its parents.\n\nThe number of processed commits is close enough, though:\n\n  $ cut -d' ' -f1 P |sort -u |wc -l\n  17164\n  $ cut -d' ' -f1 LL |sort -u |wc -l\n  17894\n\nIt seems there is still more room for improvements by avoiding\ncommit-non_first_parent diffs when the first parent is TREESAME, and\ndoing so could hopefully avoid triggering rename detection in those\nsubtree merges or in case of your evil path.\n\n\n> > @@ -762,8 +778,7 @@ void line_log_init(struct rev_info *rev, const char *prefix, struct string_list\n> >  \trange = parse_lines(rev->diffopt.repo, commit, prefix, args);\n> >  \tadd_line_range(rev, commit, range);\n> >  \n> > -\tif (!rev->diffopt.detect_rename)\n> > -\t\tparse_pathspec_from_ranges(&rev->diffopt.pathspec, range);\n> > +\tparse_pathspec_from_ranges(&rev->diffopt.pathspec, range);\n> >  }\n> \n> So we always parse the pathspec, even if we don't do detect renames.\n\nErm, no: we always parse the pathspec, even if we DO detect renames.\n\nThis condition made 'git log -L... --no-renames' fast.\n\n> > @@ -821,15 +836,29 @@ static void queue_diffs(struct line_log_data *range,\n> >  \t\t\tstruct diff_queue_struct *queue,\n> >  \t\t\tstruct commit *commit, struct commit *parent)\n> >  {\n> > +\tstruct object_id *tree_oid, *parent_tree_oid;\n> > +\n> >  \tassert(commit);\n> >  \n> > +\ttree_oid = get_commit_tree_oid(commit);\n> > +\tparent_tree_oid = parent ? get_commit_tree_oid(parent) : NULL;\n> > +\n> > +\tif (opt->detect_rename &&\n> > +\t    !same_paths_in_pathspec_and_range(&opt->pathspec, range)) {\n> > +\t\tclear_pathspec(&opt->pathspec);\n> > +\t\tparse_pathspec_from_ranges(&opt->pathspec, range);\n> > +\t}\n> \n> If we are detecting renames and our pathspec is not up-to-date with the\n> range, then clear the pathspec and reparse. Makes sense.\n\nRenames (and subtree merges, etc.) are rare, so the paths rarely\nchange, and clearing and parsing pathspecs involves 2-3 memory\nallocations and frees per path, so it's worth checking first.  It had\na slight but measurable performance impact, about 2% in the Linux\nrepository.\n\n"},{"id":"380897","messageId":"284c3d2a-860a-fc46-bb1a-56c6707de724@gmail.com","threadId":"51702","inReplyTo":"20190821173515.GY20404@szeder.dev","subject":"Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-08-21T18:12:36Z","receivedAt":"2019-08-21T18:12:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/21/2019 1:35 PM, SZEDER Gábor wrote:\n> On Wed, Aug 21, 2019 at 11:53:28AM -0400, Derrick Stolee wrote:\n>> On 8/21/2019 7:04 AM, SZEDER Gábor wrote:\n>>> With rename detection enabled the line-level log is able to trace the\n>>> evolution of line ranges across whole-file renames [1].  Alas, to\n>>> achieve that it uses the diff machinery very inefficiently, making the\n>>> operation very slow [2].  And since rename detection is enabled by\n>>> default, the line-level log is very slow by default.\n>>>\n>>> When the line-level log processes a commit with rename detection\n>>> enabled, it currently does the following (see queue_diffs()):\n>>>\n>>>   1. Computes a full tree diff between the commit and (one of) its\n>>>      parent(s), i.e. invokes diff_tree_oid() with an empty\n>>>      'diffopt->pathspec'.\n>>>   2. Checks whether any paths in the line ranges were modified.\n>>>   3. Checks whether any modified paths in the line ranges are missing\n>>>      in the parent commit's tree.\n>>>   4. If there is such a missing path, then calls diffcore_std() to\n>>>      figure out whether the path was indeed renamed based on the\n>>>      previously computed full tree diff.\n>>>   5. Continues doing stuff that are unrelated to the slowness.\n>>>\n>>> So basically the line-level log computes a full tree diff for each\n>>> commit-parent pair in step (1) to be used for rename detection in step\n>>> (4) in the off chance that an interesting path is missing from the\n>>> parent.\n>>>\n>>> Avoid these expensive and mostly unnecessary full tree diffs by\n>>> limiting the diffs to paths in the line ranges.  This is much cheaper,\n>>> and makes step (2) unnecessary.  If it turns out that an interesting\n>>> path is missing from the parent, then fall back and compute a full\n>>> tree diff, so the rename detection will still work.\n>>\n>> I applied your patches and tried them on our VFS-enabled version of Git\n>> (see [1]). Unfortunately, the new logic is still triggering rename\n>> detection, as measured by the number of objects being downloaded.\n> \n> Well, the goal of this patch was to avoid full tree diffs if possible,\n> not to avoid rename detection :)\n> \n> Anyway, I wonder how does 'git log -L1:your-evil-path --no-renames'\n> fare as a baseline?\n\nYeah, adding --no-renames does really well, comparatively. Perhaps I'll\njust recommend to users to use that flag for now.\n\nThanks,\n-Stolee\n\n"},{"id":"380924","messageId":"20190822084158.GC20404@szeder.dev","threadId":"51702","inReplyTo":"20190821173515.GY20404@szeder.dev","subject":"Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-08-22T08:41:58Z","receivedAt":"2019-08-22T08:42:06Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Wed, Aug 21, 2019 at 07:35:15PM +0200, SZEDER Gábor wrote:\n> So line-level log clearly computes a lot less diffs than\n> '--full-history', though still about 50% more than a regular\n> pathspec-limited history traversal.  Looking at the commit-parent\n> pairs in the output, it appears that the difference comes mostly from\n> merge commits, because line-level log compares a merge commit with all\n> of its parents.\n\n> It seems there is still more room for improvements by avoiding\n> commit-non_first_parent diffs when the first parent is TREESAME, and\n> doing so could hopefully avoid triggering rename detection in those\n> subtree merges or in case of your evil path.\n\nWell, that fruit hung much lower than I though, just look at the size\nof the WIP patch below.  I just hope that there are no unexpected\nsurprises, but FWIW it produces the exact same output for all files up\nto 't/t5515' in v2.23.0 as the previous patch.\n\nCan't wait to see how it fares with that evil Windows path :)\n\n  --- >8 ---\n\nSubject: [PATCH 3/2] WIP line-log: stop diff-ing after first TREESAME merge parent\n\n  # git.git, ~25% of all commits are merges\n  $ time git --no-pager log -L:read_alternate_refs:sha1-file.c v2.23.0\n\n  Before:\n\n    real    0m2.516s\n    user    0m2.456s\n    sys     0m0.060s\n\n  After:\n\n    real    0m1.132s\n    user    0m1.096s\n    sys     0m0.036s\n\n  # linux.git, ~7% of all commits are merges\n  $ time ~/src/git/git --no-pager log \\\n    -L:build_restore_work_registers:arch/mips/mm/tlbex.c v5.2\n\n  Before:\n\n    real    0m2.599s\n    user    0m2.466s\n    sys     0m0.157s\n\n  After:\n\n    real    0m1.976s\n    user    0m1.856s\n    sys     0m0.121s\n\n[TODO: get rid of unnecessary arrays, tests?, write commit message...]\n---\n line-log.c | 6 ++----\n 1 file changed, 2 insertions(+), 4 deletions(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex 9010e00950..a4b032f83a 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -1184,13 +1184,11 @@ static int process_ranges_merge_commit(struct rev_info *rev, struct commit *comm\n \n \tp = commit->parents;\n \tfor (i = 0; i < nparents; i++) {\n+\t\tint changed;\n \t\tparents[i] = p->item;\n \t\tp = p->next;\n \t\tqueue_diffs(range, &rev->diffopt, &diffqueues[i], commit, parents[i]);\n-\t}\n \n-\tfor (i = 0; i < nparents; i++) {\n-\t\tint changed;\n \t\tcand[i] = NULL;\n \t\tchanged = process_all_files(&cand[i], rev, &diffqueues[i], range);\n \t\tif (!changed) {\n@@ -1203,7 +1201,7 @@ static int process_ranges_merge_commit(struct rev_info *rev, struct commit *comm\n \t\t\tcommit_list_append(parents[i], &commit->parents);\n \t\t\tfree(parents);\n \t\t\tfree(cand);\n-\t\t\tfree_diffqueues(nparents, diffqueues);\n+\t\t\tfree_diffqueues(i, diffqueues);\n \t\t\t/* NEEDSWORK leaking like a sieve */\n \t\t\treturn 0;\n \t\t}\n-- \n2.23.0.352.gebb2b55eae\n\n"},{"id":"380937","messageId":"5261a122-cdcb-dab5-dffa-75976c607017@gmail.com","threadId":"51702","inReplyTo":"20190822084158.GC20404@szeder.dev","subject":"Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-08-22T14:53:13Z","receivedAt":"2019-08-22T14:53:17Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/22/2019 4:41 AM, SZEDER Gábor wrote:\n> On Wed, Aug 21, 2019 at 07:35:15PM +0200, SZEDER Gábor wrote:\n>> So line-level log clearly computes a lot less diffs than\n>> '--full-history', though still about 50% more than a regular\n>> pathspec-limited history traversal.  Looking at the commit-parent\n>> pairs in the output, it appears that the difference comes mostly from\n>> merge commits, because line-level log compares a merge commit with all\n>> of its parents.\n> \n>> It seems there is still more room for improvements by avoiding\n>> commit-non_first_parent diffs when the first parent is TREESAME, and\n>> doing so could hopefully avoid triggering rename detection in those\n>> subtree merges or in case of your evil path.\n> \n> Well, that fruit hung much lower than I though, just look at the size\n> of the WIP patch below.  I just hope that there are no unexpected\n> surprises, but FWIW it produces the exact same output for all files up\n> to 't/t5515' in v2.23.0 as the previous patch.\n> \n> Can't wait to see how it fares with that evil Windows path :)\n\nThanks for this! With this patch, we finally have the time down to ~20s.\n\nThis is a HUGE improvement, especially considering there is only one result\nfor the particular section, so the entire history is explored in that time.\n \n>   --- >8 ---\n> \n> Subject: [PATCH 3/2] WIP line-log: stop diff-ing after first TREESAME merge parent\n> \n>   # git.git, ~25% of all commits are merges\n>   $ time git --no-pager log -L:read_alternate_refs:sha1-file.c v2.23.0\n> \n>   Before:\n> \n>     real    0m2.516s\n>     user    0m2.456s\n>     sys     0m0.060s\n> \n>   After:\n> \n>     real    0m1.132s\n>     user    0m1.096s\n>     sys     0m0.036s\n> \n>   # linux.git, ~7% of all commits are merges\n>   $ time ~/src/git/git --no-pager log \\\n>     -L:build_restore_work_registers:arch/mips/mm/tlbex.c v5.2\n> \n>   Before:\n> \n>     real    0m2.599s\n>     user    0m2.466s\n>     sys     0m0.157s\n> \n>   After:\n> \n>     real    0m1.976s\n>     user    0m1.856s\n>     sys     0m0.121s\n> \n> [TODO: get rid of unnecessary arrays, tests?, write commit message...]\n> ---\n>  line-log.c | 6 ++----\n>  1 file changed, 2 insertions(+), 4 deletions(-)\n> \n> diff --git a/line-log.c b/line-log.c\n> index 9010e00950..a4b032f83a 100644\n> --- a/line-log.c\n> +++ b/line-log.c\n> @@ -1184,13 +1184,11 @@ static int process_ranges_merge_commit(struct rev_info *rev, struct commit *comm\n>  \n>  \tp = commit->parents;\n>  \tfor (i = 0; i < nparents; i++) {\n> +\t\tint changed;\n>  \t\tparents[i] = p->item;\n>  \t\tp = p->next;\n>  \t\tqueue_diffs(range, &rev->diffopt, &diffqueues[i], commit, parents[i]);\n> -\t}\n>  \n> -\tfor (i = 0; i < nparents; i++) {\n> -\t\tint changed;\n>  \t\tcand[i] = NULL;\n>  \t\tchanged = process_all_files(&cand[i], rev, &diffqueues[i], range);\n>  \t\tif (!changed) {\n\nInteresting. The old logic computed ALL the diffs, then started navigating.\n\nBy navigating before computing all the diffs, we are now avoiding the rename logic\non the SECOND parent, and there will be a lot of second parents that do not include\nthe file (depending on the number of parallel topics being merged independently).\nThat's why git.git has a better performance difference than linux.git.\n\n> @@ -1203,7 +1201,7 @@ static int process_ranges_merge_commit(struct rev_info *rev, struct commit *comm\n>  \t\t\tcommit_list_append(parents[i], &commit->parents);\n>  \t\t\tfree(parents);\n>  \t\t\tfree(cand);\n> -\t\t\tfree_diffqueues(nparents, diffqueues);\n> +\t\t\tfree_diffqueues(i, diffqueues);\n\nGood point here, as we haven't initialized all of the queues.\n\nThanks,\n-Stolee\n\n"},{"id":"380941","messageId":"xmqq7e75qjdj.fsf@gitster-ct.c.googlers.com","threadId":"51702","inReplyTo":"20190822084158.GC20404@szeder.dev","subject":"Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-08-22T16:01:44Z","receivedAt":"2019-08-22T16:01:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"SZEDER Gábor <szeder.dev@gmail.com> writes:\n\n> Well, that fruit hung much lower than I though, just look at the size\n> of the WIP patch below.  I just hope that there are no unexpected\n> surprises, but FWIW it produces the exact same output for all files up\n> to 't/t5515' in v2.23.0 as the previous patch.\n>\n> Can't wait to see how it fares with that evil Windows path :)\n>\n>   --- >8 ---\n>\n> Subject: [PATCH 3/2] WIP line-log: stop diff-ing after first TREESAME merge parent\n\nA quick question.  That we need \"stop diffing after first treesame\"\npatch in the first place means we have always been attempting to\nfollow all the parents of a merge?  I'd expect that to happen when\n\"--full-history\" was given to \"git log -L...\" invocation.  When we\nare simplifying side branches without \"--full-history\", I agree that\nwe should see if any parent is treesame with respect to the paths we\nare interested in, and if so ignore all other parents.\n\nOr am I misunderstanding the issue here?\n"},{"id":"380947","messageId":"20190822162656.GE20404@szeder.dev","threadId":"51702","inReplyTo":"xmqq7e75qjdj.fsf@gitster-ct.c.googlers.com","subject":"Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-08-22T16:26:56Z","receivedAt":"2019-08-22T16:27:03Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Thu, Aug 22, 2019 at 09:01:44AM -0700, Junio C Hamano wrote:\n> SZEDER Gábor <szeder.dev@gmail.com> writes:\n> \n> > Well, that fruit hung much lower than I though, just look at the size\n> > of the WIP patch below.  I just hope that there are no unexpected\n> > surprises, but FWIW it produces the exact same output for all files up\n> > to 't/t5515' in v2.23.0 as the previous patch.\n> >\n> > Can't wait to see how it fares with that evil Windows path :)\n> >\n> >   --- >8 ---\n> >\n> > Subject: [PATCH 3/2] WIP line-log: stop diff-ing after first TREESAME merge parent\n> \n> A quick question.  That we need \"stop diffing after first treesame\"\n> patch in the first place means we have always been attempting to\n> follow all the parents of a merge?\n\nTo follow, no.\n\nBut there are two subsequent loops: the first loop computed the diffs\nbetween the merge and each of its parents, while the second processed\nthose diffs, and returned as soon as it found a treesame parent,\nwithout following the others.\n\nThis patch unified those two loops so it computes the diff with the\nfirst parent, and then processes that diff right away, and returns if\ntreesame, thereby avoding diffing the remaining parents.\n\n>  I'd expect that to happen when\n> \"--full-history\" was given to \"git log -L...\" invocation.\n\nOh, right, I didn't consider '--full-history'.  In that case it should\nnot stop at the first parent.\n\nHmm, looking into this, it seems that line-level log doesn't work with\n'--full-history' to begin with:\n\n  # Each commit does what the subject says.\n  $ git log --oneline --graph\n  *   f9bf557 (HEAD -> master) Merge branch 'branch'\n  |\\  \n  | * 1b573fb (branch) Revert \"Modify file\"\n  | * 3634cf3 Modify file\n  |/  \n  * 8842c18 Add file\n  $ git log --oneline file\n  8842c18 Add file\n  $ git log --oneline --full-history file\n  1b573fb (branch) Revert \"Modify file\"\n  3634cf3 Modify file\n  8842c18 Add file\n  $ ~/src/git/BUILDS/v2.23.0/bin/git log -L1:file --oneline --no-patch\n  8842c18 Add file\n  $ ~/src/git/BUILDS/v2.23.0/bin/git log -L1:file --oneline --no-patch --full-history\n  8842c18 Add file\n\n"},{"id":"380952","messageId":"09b86c6c-234e-f6e9-c0c7-a810b8214bcf@gmail.com","threadId":"51702","inReplyTo":"20190822162656.GE20404@szeder.dev","subject":"Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2019-08-22T16:51:46Z","receivedAt":"2019-08-22T16:51:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/22/2019 12:26 PM, SZEDER Gábor wrote:\n> On Thu, Aug 22, 2019 at 09:01:44AM -0700, Junio C Hamano wrote:\n>> SZEDER Gábor <szeder.dev@gmail.com> writes:\n>>\n>>> Well, that fruit hung much lower than I though, just look at the size\n>>> of the WIP patch below.  I just hope that there are no unexpected\n>>> surprises, but FWIW it produces the exact same output for all files up\n>>> to 't/t5515' in v2.23.0 as the previous patch.\n>>>\n>>> Can't wait to see how it fares with that evil Windows path :)\n>>>\n>>>   --- >8 ---\n>>>\n>>> Subject: [PATCH 3/2] WIP line-log: stop diff-ing after first TREESAME merge parent\n>>\n>> A quick question.  That we need \"stop diffing after first treesame\"\n>> patch in the first place means we have always been attempting to\n>> follow all the parents of a merge?\n> \n> To follow, no.\n> \n> But there are two subsequent loops: the first loop computed the diffs\n> between the merge and each of its parents, while the second processed\n> those diffs, and returned as soon as it found a treesame parent,\n> without following the others.\n> \n> This patch unified those two loops so it computes the diff with the\n> first parent, and then processes that diff right away, and returns if\n> treesame, thereby avoding diffing the remaining parents.\n\nThe change you've proposed could be made a bit better in the following\nway: first look for a treesame parent by computing the diffs without\nrename detection. Re-enable rename detection only if no treesame parent\nis found.\n\nThat would be sure to avoid the rename detection even if the merge has\na treesame second parent.\n\nThanks,\n-Stolee\n\n"},{"id":"381006","messageId":"20190823100446.GI20404@szeder.dev","threadId":"51702","inReplyTo":"20190822084158.GC20404@szeder.dev","subject":"Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2019-08-23T10:04:46Z","receivedAt":"2019-08-23T10:04:52Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Thu, Aug 22, 2019 at 10:41:58AM +0200, SZEDER Gábor wrote:\n> On Wed, Aug 21, 2019 at 07:35:15PM +0200, SZEDER Gábor wrote:\n> Subject: [PATCH 3/2] WIP line-log: stop diff-ing after first TREESAME merge parent\n\n>   # linux.git, ~7% of all commits are merges\n>   $ time ~/src/git/git --no-pager log \\\n>     -L:build_restore_work_registers:arch/mips/mm/tlbex.c v5.2\n> \n>   Before:\n> \n>     real    0m2.599s\n>     user    0m2.466s\n>     sys     0m0.157s\n> \n>   After:\n> \n>     real    0m1.976s\n>     user    0m1.856s\n>     sys     0m0.121s\n\nSo, to recap, the above command follows the given line range through\nthe whole history, and the timings were done with these three patches\non top of v2.23.0 and with a commit-graph file present and used.\n\nWhen merged with my more responsive line-level log series, the same\ncommand takes about 12% longer:\n\n  real    0m2.216s\n  user    0m2.108s\n  sys     0m0.109s\n\nLooking at the flame graphs generated from the perf profiles I notice\nthe following:\n\n  - (line_log_)process_ranges_arbitrary_commit(), i.e. the function\n    responsible for processing all commits for the line-level log,\n    shows up in 2408 samples before the merge and in 2387 samples\n    after the merge.  I'm inclined to write it off as noise.\n\n  - Before the merge limit_list() and sort_in_topological_order(), the\n    two functions responsible for topo-ordering without generation\n    numbers, show up in 2484 and 707 samples, respectively, which is\n    3191 samples combined.\n\n  - After the merge expand_topo_walk() alone shows up in 4341 samples,\n    with next_topo_commit() in 72 samples.\n    \nSo it appears that the generation numbers-based topo-ordering is\nalmost 40% slower than \"traditional\" topo-ordering.  It came as a\nsurprise to me, but perhaps to you it's expected?\n\nAnyway, the time to show the first commit is still much better with\ngenerarion numbers, so overall I think it more than offsets this ~10%\ndifference.\n\n"}]}