Re: [PATCH 2/2] line-log: avoid unnecessary full tree diffs

[Derrick Stolee <stolee@gmail.com>]

On 8/21/2019 7:04 AM, SZEDER Gábor wrote:
> With rename detection enabled the line-level log is able to trace the
> evolution of line ranges across whole-file renames [1].  Alas, to
> achieve that it uses the diff machinery very inefficiently, making the
> operation very slow [2].  And since rename detection is enabled by
> default, the line-level log is very slow by default.
> 
> When the line-level log processes a commit with rename detection
> enabled, it currently does the following (see queue_diffs()):
> 
>   1. Computes a full tree diff between the commit and (one of) its
>      parent(s), i.e. invokes diff_tree_oid() with an empty
>      'diffopt->pathspec'.
>   2. Checks whether any paths in the line ranges were modified.
>   3. Checks whether any modified paths in the line ranges are missing
>      in the parent commit's tree.
>   4. If there is such a missing path, then calls diffcore_std() to
>      figure out whether the path was indeed renamed based on the
>      previously computed full tree diff.
>   5. Continues doing stuff that are unrelated to the slowness.
> 
> So basically the line-level log computes a full tree diff for each
> commit-parent pair in step (1) to be used for rename detection in step
> (4) in the off chance that an interesting path is missing from the
> parent.
> 
> Avoid these expensive and mostly unnecessary full tree diffs by
> limiting the diffs to paths in the line ranges.  This is much cheaper,
> and makes step (2) unnecessary.  If it turns out that an interesting
> path is missing from the parent, then fall back and compute a full
> tree diff, so the rename detection will still work.

I applied your patches and tried them on our VFS-enabled version of Git
(see [1]). Unfortunately, the new logic is still triggering rename
detection, as measured by the number of objects being downloaded.

[1] https://github.com/microsoft/git/pull/182

My *guess* is that the repo has a lot of merge commits, and for many
of those, the file does not exist in the first parent. Since we are
essentially doing a --full-history, this means that edge tries a
rename detection. If we used the file-history simplification route of
traveling along a treesame edge instead of caring about both parents,
then maybe this would be avoided.

I could also be completely wrong about how this line-log code works
with regards to --full-history.

> Care must be taken when to update the pathspec used to limit the diff
> in case of renames.  A path might be renamed on one branch and
> modified on several parallel running branches, and while processing
> commits on these branches the line-level log might have to alternate
> between looking at a path's new and old name.  However, at any one
> time there is only a single 'diffopt->pathspec'.
> 
> So add a step (0) to the above to ensure that the paths in the
> pathspec match the paths in the line ranges associated with the
> currently processed commit, and re-parse the pathspec from the paths
> in the line ranges if they differ.
> 
> The new test cases include a specially crafted piece of history with
> two merged branches and two files, where each branch modifies both
> files, renames on of them, and then modifies both again.  Then two
> separate 'git log -L' invocations check the line-level log of each of
> those two files, which ensures that at least one of those invocations
> have to do that back-and-forth between the file's old and new name (no
> matter which branch is traversed first).  't/t4211-line-log.sh'
> already contains two tests involving renames, they don't don't trigger
> this back-and-forth.
> 
> Avoiding these unnecessary full tree diffs can have huge impact on
> performance, especially in big repositories with big trees and mergy
> history.  Tracing the evolution of a function through the whole
> history:
> 
>   # git.git
>   $ time git --no-pager log -L:read_alternate_refs:sha1-file.c v2.23.0
> 
>   Before:
> 
>     real    0m8.874s
>     user    0m8.816s
>     sys     0m0.057s
> 
>   After:
> 
>     real    0m2.516s
>     user    0m2.456s
>     sys     0m0.060s
> 
>   # linux.git
>   $ time ~/src/git/git --no-pager log \
>     -L:build_restore_work_registers:arch/mips/mm/tlbex.c v5.2
> 
>   Before:
> 
>     real    3m50.033s
>     user    3m48.041s
>     sys     0m0.300s
> 
>   After:
> 
>     real    0m2.599s
>     user    0m2.466s
>     sys     0m0.157s
> 
> That's just over 88x speedup.

These performance numbers are great! Please don't let my complaints of
"it doesn't work for my particularly bad example" be a deterrent to this
change. If I figure out what is going on in my case, then I can create
an update on top of your changes.

> diff --git a/line-log.c b/line-log.c
> index fddd91f060..9010e00950 100644
> --- a/line-log.c
> +++ b/line-log.c
> @@ -737,6 +737,22 @@ static struct line_log_data *lookup_line_range(struct rev_info *revs,
>  	return ret;
>  }
>  
> +static int same_paths_in_pathspec_and_range(struct pathspec *pathspec,
> +					    struct line_log_data *range)
> +{
> +	int i;
> +	struct line_log_data *r;
> +
> +	for (i = 0, r = range; i < pathspec->nr && r; i++, r = r->next)
> +		if (strcmp(pathspec->items[i].match, r->path))
> +			return 0;
> +	if (i < pathspec->nr || r)
> +		/* different number of pathspec items and ranges */
> +		return 0;
> +
> +	return 1;
> +}

This method is easy to digest. Looks correct.

> @@ -762,8 +778,7 @@ void line_log_init(struct rev_info *rev, const char *prefix, struct string_list
>  	range = parse_lines(rev->diffopt.repo, commit, prefix, args);
>  	add_line_range(rev, commit, range);
>  
> -	if (!rev->diffopt.detect_rename)
> -		parse_pathspec_from_ranges(&rev->diffopt.pathspec, range);
> +	parse_pathspec_from_ranges(&rev->diffopt.pathspec, range);
>  }

So we always parse the pathspec, even if we don't do detect renames.

> @@ -821,15 +836,29 @@ static void queue_diffs(struct line_log_data *range,
>  			struct diff_queue_struct *queue,
>  			struct commit *commit, struct commit *parent)
>  {
> +	struct object_id *tree_oid, *parent_tree_oid;
> +
>  	assert(commit);
>  
> +	tree_oid = get_commit_tree_oid(commit);
> +	parent_tree_oid = parent ? get_commit_tree_oid(parent) : NULL;
> +
> +	if (opt->detect_rename &&
> +	    !same_paths_in_pathspec_and_range(&opt->pathspec, range)) {
> +		clear_pathspec(&opt->pathspec);
> +		parse_pathspec_from_ranges(&opt->pathspec, range);
> +	}

If we are detecting renames and our pathspec is not up-to-date with the
range, then clear the pathspec and reparse. Makes sense.

>  	DIFF_QUEUE_CLEAR(&diff_queued_diff);
> -	diff_tree_oid(parent ? get_commit_tree_oid(parent) : NULL,
> -		      get_commit_tree_oid(commit), "", opt);
> +	diff_tree_oid(parent_tree_oid, tree_oid, "", opt);

(I rearranged a pair of -/+ lines in the diff to highlight this change.)

Makes sense, parent_tree_oid above was set using the same conditional.

> -	if (opt->detect_rename) {
> +	if (opt->detect_rename && diff_might_be_rename()) {

Here is the crux of the matter: diff_might_be_rename() can prevent
the full tree diff.

> +		/* must look at the full tree diff to detect renames */
> +		clear_pathspec(&opt->pathspec);
> +		DIFF_QUEUE_CLEAR(&diff_queued_diff);
> +
> +		diff_tree_oid(parent_tree_oid, tree_oid, "", opt);
> +
>  		filter_diffs_for_paths(range, 1);
> -		if (diff_might_be_rename())
> -			diffcore_std(opt);
> +		diffcore_std(opt);
>  		filter_diffs_for_paths(range, 0);
>  	}

So before, diff_might_be_rename() already prevented diffcore_std(), but
now it also prevents clearing the pathspec. diff_might_be_rename() has
a simple implementation:

static inline int diff_might_be_rename(void)
{
        int i;
        for (i = 0; i < diff_queued_diff.nr; i++)
                if (!DIFF_FILE_VALID(diff_queued_diff.queue[i]->one)) {
                        /* fprintf(stderr, "diff_might_be_rename found creation of: %s\n", */
                        /*      diff_queued_diff.queue[i]->two->path); */
                        return 1;
                }
        return 0;
}

So yes, it is triggered by any path appearing in the child but not
a parent.

>  	move_diff_queue(queue, &diff_queued_diff);
> diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh
> index 1db7bd0f59..8319163744 100755
> --- a/t/t4211-line-log.sh
> +++ b/t/t4211-line-log.sh
> @@ -132,4 +132,86 @@ test_expect_success '--raw is forbidden' '
>  	test_must_fail git log -L1,24:b.c --raw
>  '
>  
> +test_expect_success 'setup for checking fancy rename following' '
> +	git checkout --orphan moves-start &&
> +	git reset --hard &&
> +
> +	printf "%s\n"    12 13 14 15      b c d e   >file-1 &&
> +	printf "%s\n"    22 23 24 25      B C D E   >file-2 &&
> +	git add file-1 file-2 &&
> +	test_tick &&
> +	git commit -m "Add file-1 and file-2" &&
> +	oid_add_f1_f2=$(git rev-parse --short HEAD) &&
> +
> +	git checkout -b moves-main &&
> +	printf "%s\n" 11 12 13 14 15      b c d e   >file-1 &&
> +	git commit -a -m "Modify file-1 on main" &&
> +	oid_mod_f1_main=$(git rev-parse --short HEAD) &&
> +
> +	printf "%s\n" 21 22 23 24 25      B C D E   >file-2 &&
> +	git commit -a -m "Modify file-2 on main #1" &&
> +	oid_mod_f2_main_1=$(git rev-parse --short HEAD) &&
> +
> +	git mv file-1 renamed-1 &&
> +	git commit -m "Rename file-1 to renamed-1 on main" &&
> +
> +	printf "%s\n" 11 12 13 14 15      b c d e f >renamed-1 &&
> +	git commit -a -m "Modify renamed-1 on main" &&
> +	oid_mod_r1_main=$(git rev-parse --short HEAD) &&
> +
> +	printf "%s\n" 21 22 23 24 25      B C D E F >file-2 &&
> +	git commit -a -m "Modify file-2 on main #2" &&
> +	oid_mod_f2_main_2=$(git rev-parse --short HEAD) &&
> +
> +	git checkout -b moves-side moves-start &&
> +	printf "%s\n"    12 13 14 15 16   b c d e   >file-1 &&
> +	git commit -a -m "Modify file-1 on side #1" &&
> +	oid_mod_f1_side_1=$(git rev-parse --short HEAD) &&
> +
> +	printf "%s\n"    22 23 24 25 26   B C D E   >file-2 &&
> +	git commit -a -m "Modify file-2 on side" &&
> +	oid_mod_f2_side=$(git rev-parse --short HEAD) &&
> +
> +	git mv file-2 renamed-2 &&
> +	git commit -m "Rename file-2 to renamed-2 on side" &&
> +
> +	printf "%s\n"    12 13 14 15 16 a b c d e   >file-1 &&
> +	git commit -a -m "Modify file-1 on side #2" &&
> +	oid_mod_f1_side_2=$(git rev-parse --short HEAD) &&
> +
> +	printf "%s\n"    22 23 24 25 26 A B C D E   >renamed-2 &&
> +	git commit -a -m "Modify renamed-2 on side" &&
> +	oid_mod_r2_side=$(git rev-parse --short HEAD) &&
> +
> +	git checkout moves-main &&
> +	git merge moves-side &&
> +	oid_merge=$(git rev-parse --short HEAD)
> +'
> +
> +test_expect_success 'fancy rename following #1' '
> +	cat >expect <<-EOF &&
> +	$oid_merge Merge branch '\''moves-side'\'' into moves-main
> +	$oid_mod_f1_side_2 Modify file-1 on side #2
> +	$oid_mod_f1_side_1 Modify file-1 on side #1
> +	$oid_mod_r1_main Modify renamed-1 on main
> +	$oid_mod_f1_main Modify file-1 on main
> +	$oid_add_f1_f2 Add file-1 and file-2
> +	EOF
> +	git log -L1:renamed-1 --oneline --no-patch >actual &&
> +	test_cmp expect actual
> +'
> +
> +test_expect_success 'fancy rename following #2' '
> +	cat >expect <<-EOF &&
> +	$oid_merge Merge branch '\''moves-side'\'' into moves-main
> +	$oid_mod_r2_side Modify renamed-2 on side
> +	$oid_mod_f2_side Modify file-2 on side
> +	$oid_mod_f2_main_2 Modify file-2 on main #2
> +	$oid_mod_f2_main_1 Modify file-2 on main #1
> +	$oid_add_f1_f2 Add file-1 and file-2
> +	EOF
> +	git log -L1:renamed-2 --oneline --no-patch >actual &&
> +	test_cmp expect actual
> +'

These look to be suitably interesting test cases. Thanks!

Looking at your patch, I can mostly follow the logic, but my
unfamiliarity with the code is keeping me from being confident
in full understanding. I hope someone who is familiar can
chime in, because I really like the direction here.

Hopefully I will have time in the next few weeks to revisit
this and work to resolve my abnormal case.

-Stolee