From: Miklos Vajna Date: Fri, 30 Oct 2026 20:09:11 GMT Subject: [PATCH v4 5/6] log: speed up --follow following renames for non-linear history Message-ID: <072d90b865c9c046f7c0dd00a265eb11bc9b48a2.1793298331.git.vmiklos@collabora.com> In-Reply-To: Test the performance of 'git log --stat --follow -- include/linux/rsc_table.h' on linux.git, it used to take about 28 seconds, and since commit 304812ed33 (log: improve --follow following renames for non-linear history, 2026-06-22), it takes 6m43s. What happens is that log_tree_diff() diffs each merge against all of its parents with rename following. diff_tree_oid() only does the expensive rename detection when the path is added relative to a parent, but that is common for merges, e.g. when a branch forked before the path was created merges mainline, and this slows down 'git log --follow'. Fix the problem by diffing the merge against its parents in two passes: - First pass: diff against the parents without rename following. If the path is unchanged against a parent, then just follow that history in all parents. - Except when an other parent doesn't have the path, the merge has it and a merge base of the two parents also has it, i.e. the path was renamed or removed on that side: still do the rename following against such a parent, otherwise the history on that side would be lost. The merge base is only computed in this rare case, and back-merges where the path was created after the other side forked still skip the expensive rename detection. - Second pass: only do the rename following against each parent if the path changed relative to all parents. Given that this way a parent may be asked to follow a path that it doesn't have, also adjust remember_follow_pathspec(): if children disagree on what should be the path for a commit, then prefer the path that exists in that commit. Now the above use case takes 36s, somewhat close to the original cost. Helped-by: SZEDER Gábor Signed-off-by: Miklos Vajna --- log-tree.c | 96 +++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 91 insertions(+), 5 deletions(-) diff --git a/log-tree.c b/log-tree.c index 0aa27fb210..0dc71be61e 100644 --- a/log-tree.c +++ b/log-tree.c @@ -31,6 +31,7 @@ #include "range-diff.h" #include "strmap.h" #include "tree.h" +#include "tree-walk.h" #include "wildmatch.h" #include "write-or-die.h" #include "pager.h" @@ -1110,6 +1111,17 @@ static void set_pathspec_to_single_path(struct pathspec *ps, const char *path) PATHSPEC_LITERAL_PATH, "", paths); } +static int commit_has_path(struct rev_info *opt, struct commit *c, + const char *path) +{ + struct object_id oid; + unsigned short mode; + + parse_commit_or_die(c); + return !get_tree_entry(opt->diffopt.repo, get_commit_tree_oid(c), path, + &oid, &mode); +} + static void remember_follow_pathspec(struct rev_info *opt, struct commit *c, const char *path) { @@ -1122,8 +1134,12 @@ static void remember_follow_pathspec(struct rev_info *opt, init_follow_pathspec_slab(opt->follow_pathspec_slab); } slot = follow_pathspec_slab_at(opt->follow_pathspec_slab, c); - if (*slot && !strcmp(*slot, path)) - return; + /* If children of 'c' disagree on the path, prefer the one 'c' has. */ + if (*slot) { + if (!strcmp(*slot, path) || commit_has_path(opt, c, *slot) || + !commit_has_path(opt, c, path)) + return; + } free(*slot); *slot = xstrdup(path); } @@ -1153,6 +1169,29 @@ void release_follow_pathspec_slab(struct rev_info *opt) FREE_AND_NULL(opt->follow_pathspec_slab); } +/* + * When the path in a merge is the same as in 'same', does the path still need + * renames to be followed in 'parent'? Only if the merge has the path, 'parent' + * doesn't have it, but its fork point with 'same' had it, e.g. 'parent' + * renamed the path. + */ +static int follow_needs_renames(struct rev_info *opt, struct commit *parent, + struct commit *same, const char *path) +{ + struct commit_list *bases = NULL, *base; + int ret = 0; + + if (commit_has_path(opt, parent, path) || + !commit_has_path(opt, same, path)) + return 0; + if (repo_get_merge_bases(opt->diffopt.repo, parent, same, &bases) < 0) + exit(128); + for (base = bases; base && !ret; base = base->next) + ret = commit_has_path(opt, base->item, path); + commit_list_free(bases); + return ret; +} + /* Show the remerge or combined diff of a merge commit */ static int log_tree_merge_diff(struct rev_info *opt, struct commit *commit, struct commit_list *parents, @@ -1181,7 +1220,7 @@ static int log_tree_merge_diff(struct rev_info *opt, struct commit *commit, static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log_info *log) { int showed_log; - struct commit_list *parents, *all_parents; + struct commit_list *parents, *all_parents, *rename_parents = NULL; struct object_id *oid; int is_merge; int all_need_diff = opt->diff || opt->diffopt.flags.exit_with_status; @@ -1235,15 +1274,25 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log path = xstrdup_or_null( pathspec_single_path(&opt->diffopt.pathspec)); + if (follow_only) { + /* + * First look for a parent where the path is unchanged, without + * the expensive rename detection. + */ + opt->diffopt.flags.follow_renames = 0; + } + showed_log = 0; all_parents = parents; for (;;) { struct commit *parent = parents->item; + int changed = 1; parse_commit_or_die(parent); diff_tree_oid(get_commit_tree_oid(parent), oid, "", &opt->diffopt); if (follow_only) { + changed = diff_queued_diff.nr; diff_queue_clear(&diff_queued_diff); opt->diffopt.found_follow = 0; } else { @@ -1252,20 +1301,54 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log showed_log |= !opt->loginfo; + if (!changed) { + /* + * Same as in this parent, follow that history, but + * still look for renames in parents that had the path + * at the fork point. + */ + struct commit_list **tail = &rename_parents; + + for (parents = all_parents; parents; + parents = parents->next) { + if (parents->item != parent && + follow_needs_renames(opt, parents->item, + parent, path)) + tail = &commit_list_insert(parents->item, + tail)->next; + else + remember_follow_pathspec(opt, + parents->item, + path); + } + if (!rename_parents) + break; + opt->diffopt.flags.follow_renames = 1; + parents = rename_parents; + continue; + } + /* The diff updated the pathspec in case of a rename */ - if (path) + if (path && opt->diffopt.flags.follow_renames) remember_follow_pathspec(opt, parent, pathspec_single_path(&opt->diffopt.pathspec)); /* Set up the log info for the next parent, if any.. */ parents = parents->next; + if (!parents && follow_only && + !opt->diffopt.flags.follow_renames) { + /* The path changed in all parents, look for renames. */ + opt->diffopt.flags.follow_renames = 1; + parents = all_parents; + } if (!parents) break; - if (opt->first_parent_merges) { + if (opt->first_parent_merges && !follow_only) { if (!path || opt->first_parent_only) break; /* Only find the path to follow in the other parents */ follow_only = 1; + opt->diffopt.flags.follow_renames = 0; } if (path) set_pathspec_to_single_path(&opt->diffopt.pathspec, @@ -1275,6 +1358,8 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log log->parent = parents->item; opt->loginfo = log; } + if (follow_only) + opt->diffopt.flags.follow_renames = 1; if (follow_only && (opt->remerge_diff || opt->combine_merges)) { /* Show the merge diff with the path of this commit */ if (path) @@ -1282,6 +1367,7 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log path); showed_log = log_tree_merge_diff(opt, commit, all_parents, oid); } + commit_list_free(rename_parents); free(path); return showed_log; } -- 2.56.0