Re: [PATCH] Speed-up of libsvn_diff by restarts of LCS algorithm

[Morten Kloster <mo...@gmail.com>]

Here's an updated patch based on the current HEAD, and with
one or two minor improvements. While, as stated, the patch
can give many-fold speed increases for ideal cases, it also slows
down the LCS algorithm significantly for poorly matching files; I
got about 18% increase in running time on my system for files
that were very poor matches but had no lines unique to either file.

On Fri, May 27, 2011 at 11:00 PM, Morten Kloster <mo...@gmail.com> wrote:
> [[[
> Speeds up LCS algorithm for well-separated sections of change
> �By exploiting unique matches between the two files, it is possible to
> �"restart" the LCS algorithm at times and reset the buildup of square
> �computational complexity.
>
> * subversion/libsvn_diff/lcs.c
> �(svn_diff__snake_t): Added uniquematchcount member.
> �(svn_diff__snake): Increments uniquematchcount each time
> � a matching token occurs only once in each file.
> �(clear_fp): New method that removes nonviable states.
> �(svn_diff__lcs): Restarts LCS algorithm from p=0 if the number
> � of unique matches exceeds the number of mismatches, using
> � the first state where that occurs as the new start state.
> ]]]
>
> This patch is a partial implementation of a possible enhancement to
> the LCS algorithm. The patch builds on the patch in the thread
> "[PATCH] Speed-up of libsvn_diff using token counts". I have only
> included the lcs.c file in this patch; the other files in that other patch
> must already be patched.
>
>
> Theory behind the enhancement:
> If the number of unique matches - tokens that only occur once in each
> file - so far found exceeds the number of mismatches so far, and this
> is the FIRST time that happens, then we are guaranteed that that
> state is part of the true LCS, since eliminating some number of the
> mismatches will necessarily add more new mismatches among the
> current unique matches. We can thus "start over" from the current
> state and thus stop the build-up of computational complexity
> represented by the 'p' variable. By resetting also the number
> of unique matches found to 0, we can repeat this process many
> times.
>
> This implementation is partial in the sense that it does not reach the
> full potential of the enhancement. It will still scan at least 'd' states
> for each value of 'p', whereas an optimal implementation would
> interrupt the scan if there's a mismatch for what would have been
> a unique match (since this always make the potential LCS worse,
> regardless of whether the change is an insertion or a deletion).
> However, a full implementation will be significantly more complicated,
> as far as I can see.
>
> The current implementation can reduce the average computational
> complexity from O((p_max + d)*p_max) to O(sum((p_n + d)*p_n)),
> while an optimal implementation would be O(sum((p_n + d_n)*p_n)).
> p_max is here the total number of mismatches in the shorter file,
> while p_n and d_n are the lesser number of mismatches and the
> length difference between the files within each area of difference that
> is separated from other areas of difference by a large number of
> (not necessarily contiguous) unique matches. The current version
> is only really useful if there is a similar number of mismatches in
> each file, i.e. if there is a similar number of insertions and deletions
> (not counting tokens that are unique to one of the files).
>
> Johan: I initially thought it would be easiest to give unique matches
> higher weight in the diff algorithm. This would have meant a change
> in the definition of the optimal diff - rather than asking for simply the
> largest number of matching tokes, we would prefer diffs with slightly
> fewer total matches but more unique matches. It would not be a
> heuristic, since we would still be a guaranteed optimal diff given the
> new optimality criterion, but it would no longer be an LCS.
> However, it turned out to be easier to keep the same weights.
>
>
> The patch will need significant changes to integrate with the idx
> patch (also libsvn_diff speed-up). The current version doesn't give
> much speed improvement for most of my tests so far, but can
> give very large improvements for "ideal" cases (many small areas
> of non-unique changes that are separated by many unique matches,
> and where the files are of equal length).
>
> I'm not sure whether or not the current version (integrated with idx)
> is worthwhile or not. I'll look into making a full implementation of the
> enhancement.
>
>
> Morten
>

Re: [PATCH] Speed-up of libsvn_diff by restarts of LCS algorithm

[Morten Kloster <mo...@gmail.com>]

On Mon, Jun 27, 2011 at 12:14 AM, Johan Corveleyn <jc...@gmail.com> wrote:
[]
>
> Hi Morten,
>
> Thanks for explaining.
>
> Maybe you can start a feature branch for this optimization (and maybe
> other further LCS/diff-optimizations). That would give it some more
> visibility, and would allow for some more experimentation and
> discussion. Now that you have your account with (partial) commit
> access...
>
> Speaking of which: have you added your name to the COMMITTERS file
> yet? You should probably do that first.
>
> --
> Johan
>

I've just committed an updated version to the new diff-improvements branch.
The updated version eliminates the potential problem of slow-downs due
to too much clearing in clear_fp.

---
Morten

Re: [PATCH] Speed-up of libsvn_diff by restarts of LCS algorithm

[Johan Corveleyn <jc...@gmail.com>]

On Sun, Jun 26, 2011 at 11:23 AM, Morten Kloster <mo...@gmail.com> wrote:
> On Tue, Jun 14, 2011 at 11:12 PM, Johan Corveleyn <jc...@gmail.com> wrote:
>> On Tue, Jun 14, 2011 at 7:32 PM, Morten Kloster <mo...@gmail.com> wrote:
>>> On Tue, Jun 14, 2011 at 2:49 AM, Johan Corveleyn <jc...@gmail.com> wrote:
>>>> On Tue, Jun 7, 2011 at 10:16 PM, Morten Kloster <mo...@gmail.com> wrote:
>>>>>
>>> []
>>>>> Here's an updated patch based on the current HEAD, and with
>>>>> one or two minor improvements. While, as stated, the patch
>>>>> can give many-fold speed increases for ideal cases, it also slows
>>>>> down the LCS algorithm significantly for poorly matching files; I
>>>>> got about 18% increase in running time on my system for files
>>>>> that were very poor matches but had no lines unique to either file.
>>>>
>>>> Hi Morten,
>>>>
>>>> Hmmm, that sounds like a lot of overhead in some cases (I actually
>>>> wonder why -- I haven't fully understood the implementation, but on
>>>> first sight it doesn't seem that computationally intensive). But the
>>>> most important question that's bugging me: do those "ideal cases"
>>>> occur often in real-world examples?
>>>>
>>>
>>> It's not surprising to get that kind of speed reduction, since it uses
>>> an extra test within the loops that take the bulk of the time when
>>> the files don't match.
>>
>> Indeed, that might be it :-). Just wondering though: it isn't by any
>> chance the case that, worst case, clear_fp is called too often (more
>> often than is useful, each time resetting the LCS run for only
>> marginal gain)?
>>
>> Can you verify that those 18% are spent because of those extra
>> comparisons, and not because of calls to clear_fp? IIUC, with those
>> poorly-matching files, there should never be a call to clear_fp,
>> because the unique-matching optimization never kicks in, right?
>>
>
> As you say, clear_fp is never called in this case. But there is
> actually a risk of slowdown for well-matching files due to
> calls to clear_fp (during the loop over k for p=0; clear_fp will
> clear more than it really needs to). It shouldn't be too hard
> to avoid that, though.
>
>> Also, those 18% you measured: is that the increase in
>> svn_diff_file_diff time, or in lcs time? Or is that approximately the
>> same, because the lcs time dominates because of the poor matching?
>>
>
> They are essentially the same in this case.
>
>>
>> I have two more, possibly stupid, questions on the implementation in the patch:
>>
>> - You mentioned in your theoretical explanation that you still have to
>> scan the entire d-range for every p, even after you've found a "reset
>> point". But can't you just "break" from the for-loops, whenever you
>> encounter a reset point?
>>
>
> No, I don't have to scan after I find a reset point (the loops
> just continue in post-reset mode; there's no waste there). The
> issue is that svn_diff__lcs still looks for a p=0 solution even after
> a unique possible match has failed, which clearly is no longer
> possible (it's not restricted to p=0, that's just the simplest case).
>
>> - You calculated 'limit' as:
>>        limit = (d >= 0 ? 2 * p + d : 2 * p - d);
>> and made the "reset condition" be:
>>        if (fp[k].uniquematchcount > limit + k)  /* with k < 0 */
>> or:
>>        if (fp[k].uniquematchcount > limit - k)  /* with k >= 0 */
>>
>> I don't fully understand. Can you explain a bit more why this is the
>> right value for 'limit', and how this is the correct "reset
>> condition"?
>>
>
> Those limits are actually overkill. The correct condition is that the
> number of unique matches must be larger than (or equal to, I guess)
> the number of mismatches that could conceivably be corrected by
> matching the files otherwise. I have here used the total number of
> mismatches in BOTH files, but the larger number of mismatches in
> one file would be sufficient.

Hi Morten,

Thanks for explaining.

Maybe you can start a feature branch for this optimization (and maybe
other further LCS/diff-optimizations). That would give it some more
visibility, and would allow for some more experimentation and
discussion. Now that you have your account with (partial) commit
access...

Speaking of which: have you added your name to the COMMITTERS file
yet? You should probably do that first.

-- 
Johan

Re: [PATCH] Speed-up of libsvn_diff by restarts of LCS algorithm

[Morten Kloster <mo...@gmail.com>]

On Tue, Jun 14, 2011 at 11:12 PM, Johan Corveleyn <jc...@gmail.com> wrote:
> On Tue, Jun 14, 2011 at 7:32 PM, Morten Kloster <mo...@gmail.com> wrote:
>> On Tue, Jun 14, 2011 at 2:49 AM, Johan Corveleyn <jc...@gmail.com> wrote:
>>> On Tue, Jun 7, 2011 at 10:16 PM, Morten Kloster <mo...@gmail.com> wrote:
>>>>
>> []
>>>> Here's an updated patch based on the current HEAD, and with
>>>> one or two minor improvements. While, as stated, the patch
>>>> can give many-fold speed increases for ideal cases, it also slows
>>>> down the LCS algorithm significantly for poorly matching files; I
>>>> got about 18% increase in running time on my system for files
>>>> that were very poor matches but had no lines unique to either file.
>>>
>>> Hi Morten,
>>>
>>> Hmmm, that sounds like a lot of overhead in some cases (I actually
>>> wonder why -- I haven't fully understood the implementation, but on
>>> first sight it doesn't seem that computationally intensive). But the
>>> most important question that's bugging me: do those "ideal cases"
>>> occur often in real-world examples?
>>>
>>
>> It's not surprising to get that kind of speed reduction, since it uses
>> an extra test within the loops that take the bulk of the time when
>> the files don't match.
>
> Indeed, that might be it :-). Just wondering though: it isn't by any
> chance the case that, worst case, clear_fp is called too often (more
> often than is useful, each time resetting the LCS run for only
> marginal gain)?
>
> Can you verify that those 18% are spent because of those extra
> comparisons, and not because of calls to clear_fp? IIUC, with those
> poorly-matching files, there should never be a call to clear_fp,
> because the unique-matching optimization never kicks in, right?
>

As you say, clear_fp is never called in this case. But there is
actually a risk of slowdown for well-matching files due to
calls to clear_fp (during the loop over k for p=0; clear_fp will
clear more than it really needs to). It shouldn't be too hard
to avoid that, though.

> Also, those 18% you measured: is that the increase in
> svn_diff_file_diff time, or in lcs time? Or is that approximately the
> same, because the lcs time dominates because of the poor matching?
>

They are essentially the same in this case.

>
> I have two more, possibly stupid, questions on the implementation in the patch:
>
> - You mentioned in your theoretical explanation that you still have to
> scan the entire d-range for every p, even after you've found a "reset
> point". But can't you just "break" from the for-loops, whenever you
> encounter a reset point?
>

No, I don't have to scan after I find a reset point (the loops
just continue in post-reset mode; there's no waste there). The
issue is that svn_diff__lcs still looks for a p=0 solution even after
a unique possible match has failed, which clearly is no longer
possible (it's not restricted to p=0, that's just the simplest case).

> - You calculated 'limit' as:
>        limit = (d >= 0 ? 2 * p + d : 2 * p - d);
> and made the "reset condition" be:
>        if (fp[k].uniquematchcount > limit + k)  /* with k < 0 */
> or:
>        if (fp[k].uniquematchcount > limit - k)  /* with k >= 0 */
>
> I don't fully understand. Can you explain a bit more why this is the
> right value for 'limit', and how this is the correct "reset
> condition"?
>

Those limits are actually overkill. The correct condition is that the
number of unique matches must be larger than (or equal to, I guess)
the number of mismatches that could conceivably be corrected by
matching the files otherwise. I have here used the total number of
mismatches in BOTH files, but the larger number of mismatches in
one file would be sufficient.

>>> I'm sure you could craft good examples, but how likely am I to have a
>>> benefit of this in my average repository (given all of the other
>>> optimizations taking away already a lot of the work (prefix/suffix
>>> elimination; elimination of non-matching lines due to token-counting;
>>> ...))?
>>>
>>> Can you give examples from subversion's own repository, or other
>>> public repositories, where it can have a big impact?
>>>
>>
>> I ran it on merge.c (in libsvn_client), between revisions 1127198 (HEAD,
>> or close enough) and 1036419 (semi-randomly chosen to have about
>> the right fraction of changes from 1127198 - it was the first one I looked
>> at, and seemed reasonable for the test). When running all of
>> svn_diff_file_diff, the patch was about 15% faster, however, the LCS
>> algorithm itself was about 3.5 times faster; most of the time was
>> spent reading the tokens from file.
>
> That's quite neat! It's a lot more than I expected in an average case.
> Maybe some more testing should be done (not saying you have to do this
> per say, just in general) to see how average this is :-). But for now
> it's already great to see a single real-world example like the one you
> just gave.
>
>> The "problem" is that the files have to be quite big before the LCS
>> algorithm itself dominates the running time even when the files still
>> match reasonably well, whereas it is much easier for the LCS
>> algorithm to dominate the running time when the files don't match
>> at all, in which case this patch degrades performance.
>
> Yeah, I know :-). The token-scanning/hashing phase is still quite a
> heavy factor in the diff performance (especially when the matching of
> the files is reasonably good (yielding a fast LCS-run), which is
> typically the case with changes in source code).
>
> Stefan Fuhrmann (stefan2) has some great ideas for optimizing the
> token-scanning phase, which could help a lot for that. We had some
> nice discussions about it during the Berlin Hackathon last month (but
> I didn't have the chance yet to dig into it further). But that's all
> definitely 1.8 or later stuff.
>
> Also, in the same vein, I think this current patch will have to wait
> for post-1.7. I like the idea a lot, and would definitely like to see
> it in svn one day, but it's not such a trivial change. With 1.7 just
> around the corner, we're trying to avoid changes that are not directly
> related to getting 1.7 (finally) out the door :-).
>
>> It is quite easy to do a quick heuristic test for whether this patch
>> would help or not, so we could have alternate versions of the LCS
>> algorithm depending on whether that test checks out. That would
>> make the code somewhat harder to maintain, of course.
>
> That might be a good idea, to get really the best of both worlds.
> Though I think it would also be acceptable to optimize for the common
> case (reasonably matching files (modulo all the "non-matching
> lines")), at a slight cost for the rare case (files that are matching
> terribly bad, even with "skipping all the non-matching lines"). Not
> sure right now, I guess it depends on the cost of the added code
> complexity.
>
> Definitely something to look at post-1.7 :-).
>
>>> Or are you looking at this for some specific purpose, some repository
>>> where this situation occurs regularly and has a big impact (huge
>>> LCS'es ...)?
>>>
>>
>> Nope, I just like to optimize stuff, and since we were already
>> looking at diff optimization I thought I might as well point out the
>> possibility.
>
> Cool :-). Me too.
>
> --
> Johan
>

Re: [PATCH] Speed-up of libsvn_diff by restarts of LCS algorithm

[Johan Corveleyn <jc...@gmail.com>]

On Tue, Jun 14, 2011 at 7:32 PM, Morten Kloster <mo...@gmail.com> wrote:
> On Tue, Jun 14, 2011 at 2:49 AM, Johan Corveleyn <jc...@gmail.com> wrote:
>> On Tue, Jun 7, 2011 at 10:16 PM, Morten Kloster <mo...@gmail.com> wrote:
>>>
> []
>>> Here's an updated patch based on the current HEAD, and with
>>> one or two minor improvements. While, as stated, the patch
>>> can give many-fold speed increases for ideal cases, it also slows
>>> down the LCS algorithm significantly for poorly matching files; I
>>> got about 18% increase in running time on my system for files
>>> that were very poor matches but had no lines unique to either file.
>>
>> Hi Morten,
>>
>> Hmmm, that sounds like a lot of overhead in some cases (I actually
>> wonder why -- I haven't fully understood the implementation, but on
>> first sight it doesn't seem that computationally intensive). But the
>> most important question that's bugging me: do those "ideal cases"
>> occur often in real-world examples?
>>
>
> It's not surprising to get that kind of speed reduction, since it uses
> an extra test within the loops that take the bulk of the time when
> the files don't match.

Indeed, that might be it :-). Just wondering though: it isn't by any
chance the case that, worst case, clear_fp is called too often (more
often than is useful, each time resetting the LCS run for only
marginal gain)?

Can you verify that those 18% are spent because of those extra
comparisons, and not because of calls to clear_fp? IIUC, with those
poorly-matching files, there should never be a call to clear_fp,
because the unique-matching optimization never kicks in, right?

Also, those 18% you measured: is that the increase in
svn_diff_file_diff time, or in lcs time? Or is that approximately the
same, because the lcs time dominates because of the poor matching?


I have two more, possibly stupid, questions on the implementation in the patch:

- You mentioned in your theoretical explanation that you still have to
scan the entire d-range for every p, even after you've found a "reset
point". But can't you just "break" from the for-loops, whenever you
encounter a reset point?

- You calculated 'limit' as:
        limit = (d >= 0 ? 2 * p + d : 2 * p - d);
and made the "reset condition" be:
        if (fp[k].uniquematchcount > limit + k)  /* with k < 0 */
or:
        if (fp[k].uniquematchcount > limit - k)  /* with k >= 0 */

I don't fully understand. Can you explain a bit more why this is the
right value for 'limit', and how this is the correct "reset
condition"?

>> I'm sure you could craft good examples, but how likely am I to have a
>> benefit of this in my average repository (given all of the other
>> optimizations taking away already a lot of the work (prefix/suffix
>> elimination; elimination of non-matching lines due to token-counting;
>> ...))?
>>
>> Can you give examples from subversion's own repository, or other
>> public repositories, where it can have a big impact?
>>
>
> I ran it on merge.c (in libsvn_client), between revisions 1127198 (HEAD,
> or close enough) and 1036419 (semi-randomly chosen to have about
> the right fraction of changes from 1127198 - it was the first one I looked
> at, and seemed reasonable for the test). When running all of
> svn_diff_file_diff, the patch was about 15% faster, however, the LCS
> algorithm itself was about 3.5 times faster; most of the time was
> spent reading the tokens from file.

That's quite neat! It's a lot more than I expected in an average case.
Maybe some more testing should be done (not saying you have to do this
per say, just in general) to see how average this is :-). But for now
it's already great to see a single real-world example like the one you
just gave.

> The "problem" is that the files have to be quite big before the LCS
> algorithm itself dominates the running time even when the files still
> match reasonably well, whereas it is much easier for the LCS
> algorithm to dominate the running time when the files don't match
> at all, in which case this patch degrades performance.

Yeah, I know :-). The token-scanning/hashing phase is still quite a
heavy factor in the diff performance (especially when the matching of
the files is reasonably good (yielding a fast LCS-run), which is
typically the case with changes in source code).

Stefan Fuhrmann (stefan2) has some great ideas for optimizing the
token-scanning phase, which could help a lot for that. We had some
nice discussions about it during the Berlin Hackathon last month (but
I didn't have the chance yet to dig into it further). But that's all
definitely 1.8 or later stuff.

Also, in the same vein, I think this current patch will have to wait
for post-1.7. I like the idea a lot, and would definitely like to see
it in svn one day, but it's not such a trivial change. With 1.7 just
around the corner, we're trying to avoid changes that are not directly
related to getting 1.7 (finally) out the door :-).

> It is quite easy to do a quick heuristic test for whether this patch
> would help or not, so we could have alternate versions of the LCS
> algorithm depending on whether that test checks out. That would
> make the code somewhat harder to maintain, of course.

That might be a good idea, to get really the best of both worlds.
Though I think it would also be acceptable to optimize for the common
case (reasonably matching files (modulo all the "non-matching
lines")), at a slight cost for the rare case (files that are matching
terribly bad, even with "skipping all the non-matching lines"). Not
sure right now, I guess it depends on the cost of the added code
complexity.

Definitely something to look at post-1.7 :-).

>> Or are you looking at this for some specific purpose, some repository
>> where this situation occurs regularly and has a big impact (huge
>> LCS'es ...)?
>>
>
> Nope, I just like to optimize stuff, and since we were already
> looking at diff optimization I thought I might as well point out the
> possibility.

Cool :-). Me too.

-- 
Johan

Re: [PATCH] Speed-up of libsvn_diff by restarts of LCS algorithm

[Morten Kloster <mo...@gmail.com>]

On Tue, Jun 14, 2011 at 2:49 AM, Johan Corveleyn <jc...@gmail.com> wrote:
> On Tue, Jun 7, 2011 at 10:16 PM, Morten Kloster <mo...@gmail.com> wrote:
>>
[]
>> Here's an updated patch based on the current HEAD, and with
>> one or two minor improvements. While, as stated, the patch
>> can give many-fold speed increases for ideal cases, it also slows
>> down the LCS algorithm significantly for poorly matching files; I
>> got about 18% increase in running time on my system for files
>> that were very poor matches but had no lines unique to either file.
>
> Hi Morten,
>
> Hmmm, that sounds like a lot of overhead in some cases (I actually
> wonder why -- I haven't fully understood the implementation, but on
> first sight it doesn't seem that computationally intensive). But the
> most important question that's bugging me: do those "ideal cases"
> occur often in real-world examples?
>

It's not surprising to get that kind of speed reduction, since it uses
an extra test within the loops that take the bulk of the time when
the files don't match.

> I'm sure you could craft good examples, but how likely am I to have a
> benefit of this in my average repository (given all of the other
> optimizations taking away already a lot of the work (prefix/suffix
> elimination; elimination of non-matching lines due to token-counting;
> ...))?
>
> Can you give examples from subversion's own repository, or other
> public repositories, where it can have a big impact?
>

I ran it on merge.c (in libsvn_client), between revisions 1127198 (HEAD,
or close enough) and 1036419 (semi-randomly chosen to have about
the right fraction of changes from 1127198 - it was the first one I looked
at, and seemed reasonable for the test). When running all of
svn_diff_file_diff, the patch was about 15% faster, however, the LCS
algorithm itself was about 3.5 times faster; most of the time was
spent reading the tokens from file.

The "problem" is that the files have to be quite big before the LCS
algorithm itself dominates the running time even when the files still
match reasonably well, whereas it is much easier for the LCS
algorithm to dominate the running time when the files don't match
at all, in which case this patch degrades performance.

It is quite easy to do a quick heuristic test for whether this patch
would help or not, so we could have alternate versions of the LCS
algorithm depending on whether that test checks out. That would
make the code somewhat harder to maintain, of course.

> Or are you looking at this for some specific purpose, some repository
> where this situation occurs regularly and has a big impact (huge
> LCS'es ...)?
>

Nope, I just like to optimize stuff, and since we were already
looking at diff optimization I thought I might as well point out the
possibility.

> --
> Johan
>

Re: [PATCH] Speed-up of libsvn_diff by restarts of LCS algorithm

[Johan Corveleyn <jc...@gmail.com>]

On Tue, Jun 7, 2011 at 10:16 PM, Morten Kloster <mo...@gmail.com> wrote:
> On Fri, May 27, 2011 at 11:00 PM, Morten Kloster <mo...@gmail.com> wrote:
>> [[[
>> Speeds up LCS algorithm for well-separated sections of change
>>  By exploiting unique matches between the two files, it is possible to
>>  "restart" the LCS algorithm at times and reset the buildup of square
>>  computational complexity.
>>
>> * subversion/libsvn_diff/lcs.c
>>  (svn_diff__snake_t): Added uniquematchcount member.
>>  (svn_diff__snake): Increments uniquematchcount each time
>>   a matching token occurs only once in each file.
>>  (clear_fp): New method that removes nonviable states.
>>  (svn_diff__lcs): Restarts LCS algorithm from p=0 if the number
>>   of unique matches exceeds the number of mismatches, using
>>   the first state where that occurs as the new start state.
>> ]]]
>>
>> This patch is a partial implementation of a possible enhancement to
>> the LCS algorithm. The patch builds on the patch in the thread
>> "[PATCH] Speed-up of libsvn_diff using token counts". I have only
>> included the lcs.c file in this patch; the other files in that other patch
>> must already be patched.
>>
>>
>> Theory behind the enhancement:
>> If the number of unique matches - tokens that only occur once in each
>> file - so far found exceeds the number of mismatches so far, and this
>> is the FIRST time that happens, then we are guaranteed that that
>> state is part of the true LCS, since eliminating some number of the
>> mismatches will necessarily add more new mismatches among the
>> current unique matches. We can thus "start over" from the current
>> state and thus stop the build-up of computational complexity
>> represented by the 'p' variable. By resetting also the number
>> of unique matches found to 0, we can repeat this process many
>> times.
>>
>> This implementation is partial in the sense that it does not reach the
>> full potential of the enhancement. It will still scan at least 'd' states
>> for each value of 'p', whereas an optimal implementation would
>> interrupt the scan if there's a mismatch for what would have been
>> a unique match (since this always make the potential LCS worse,
>> regardless of whether the change is an insertion or a deletion).
>> However, a full implementation will be significantly more complicated,
>> as far as I can see.
>>
>> The current implementation can reduce the average computational
>> complexity from O((p_max + d)*p_max) to O(sum((p_n + d)*p_n)),
>> while an optimal implementation would be O(sum((p_n + d_n)*p_n)).
>> p_max is here the total number of mismatches in the shorter file,
>> while p_n and d_n are the lesser number of mismatches and the
>> length difference between the files within each area of difference that
>> is separated from other areas of difference by a large number of
>> (not necessarily contiguous) unique matches. The current version
>> is only really useful if there is a similar number of mismatches in
>> each file, i.e. if there is a similar number of insertions and deletions
>> (not counting tokens that are unique to one of the files).
>>
>> Johan: I initially thought it would be easiest to give unique matches
>> higher weight in the diff algorithm. This would have meant a change
>> in the definition of the optimal diff - rather than asking for simply the
>> largest number of matching tokes, we would prefer diffs with slightly
>> fewer total matches but more unique matches. It would not be a
>> heuristic, since we would still be a guaranteed optimal diff given the
>> new optimality criterion, but it would no longer be an LCS.
>> However, it turned out to be easier to keep the same weights.
>>
>>
>> The patch will need significant changes to integrate with the idx
>> patch (also libsvn_diff speed-up). The current version doesn't give
>> much speed improvement for most of my tests so far, but can
>> give very large improvements for "ideal" cases (many small areas
>> of non-unique changes that are separated by many unique matches,
>> and where the files are of equal length).
>>
>> I'm not sure whether or not the current version (integrated with idx)
>> is worthwhile or not. I'll look into making a full implementation of the
>> enhancement.
>>
>>
>> Morten
>>
> Here's an updated patch based on the current HEAD, and with
> one or two minor improvements. While, as stated, the patch
> can give many-fold speed increases for ideal cases, it also slows
> down the LCS algorithm significantly for poorly matching files; I
> got about 18% increase in running time on my system for files
> that were very poor matches but had no lines unique to either file.

Hi Morten,

Hmmm, that sounds like a lot of overhead in some cases (I actually
wonder why -- I haven't fully understood the implementation, but on
first sight it doesn't seem that computationally intensive). But the
most important question that's bugging me: do those "ideal cases"
occur often in real-world examples?

I'm sure you could craft good examples, but how likely am I to have a
benefit of this in my average repository (given all of the other
optimizations taking away already a lot of the work (prefix/suffix
elimination; elimination of non-matching lines due to token-counting;
...))?

Can you give examples from subversion's own repository, or other
public repositories, where it can have a big impact?

Or are you looking at this for some specific purpose, some repository
where this situation occurs regularly and has a big impact (huge
LCS'es ...)?

-- 
Johan