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

> 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.

> 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);