From: Junio C Hamano <gitster@pobox.com>
Date: Tue, 03 Jul 2018 18:14:26 GMT
Subject: Re: [PATCH] xdiff: reduce indent heuristic overhead
Message-ID: <xmqq1sckrxtp.fsf@gitster-ct.c.googlers.com>
In-Reply-To: <72ac1ac2-f567-f241-41d6-d0f83072e0b3@alum.mit.edu>

Michael Haggerty <mhagger@alum.mit.edu> writes:

> So if `N ≫ M`, there is necessarily a lot of repetition among the `N +
> M` lines that the hunk could possibly overlay. Specifically, it must
> consist of `floor((N + M)/M)` identical copies of the hunk, plus
> possibly a few leftover lines constituting the start of another repetition.
>
> Given this large amount of repetition, it seems to me that there is
> never a need to scan more than the bottom `M + 1` possible positions [1]
> plus the highest possible position [2] to be sure of finding the very
> best one. In the pathological case that you described above, where `M`
> is 1, only three positions have to be evaluated, not 100.

Nicely analysed.