Re: [PATCH] xdiff: optimize patience diff's LCS search

[Junio C Hamano <gitster@pobox.com>]

"Yee Cheng Chin via GitGitGadget" <gitgitgadget@gmail.com> writes:

> The find_longest_common_sequence() function in patience diff is
> inefficient as it calls binary_search() for every unique line it
> encounters when deciding where to put it in the sequence. From
> instrumentation (using xctrace) on popular repositories, binary_search()
> takes up 50-60% of the run time within patience_diff() when performing a
> diff.
>
> To optimize this, add a boundary condition check before binary_search()
> is called to see if the encountered unique line is located after the
> entire currently tracked longest subsequence. If so, skip the
> unnecessary binary search and simply append the entry to the end of
> sequence. Given that most files compared in a diff are usually quite
> similar to each other, this condition is very common, and should be hit
> much more frequently than the binary search.

This is a "stupid and obvious" optimization that is quite clever ;-)

> diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c
> index 669b653580..13ab0d591c 100644
> --- a/xdiff/xpatience.c
> +++ b/xdiff/xpatience.c
> @@ -211,7 +211,10 @@ static int find_longest_common_sequence(struct hashmap *map, struct entry **res)
>  	for (entry = map->first; entry; entry = entry->next) {
>  		if (!entry->line2 || entry->line2 == NON_UNIQUE)
>  			continue;
> -		i = binary_search(sequence, longest, entry);
> +		if (longest == 0 || entry->line2 > sequence[longest - 1]->line2)
> +			i = longest - 1;
> +		else
> +			i = binary_search(sequence, longest, entry);

OK.  If we have nothing, or if the thing sorts after the existing
ones, then we do not have to run binsearch to find where to insert
it.  We know we want to append.

Nice.