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

2011-06-27 Thread Morten Kloster
On Mon, Jun 27, 2011 at 12:14 AM, Johan Corveleyn 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 experime

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

2011-06-26 Thread Johan Corveleyn
On Sun, Jun 26, 2011 at 11:23 AM, Morten Kloster wrote: > On Tue, Jun 14, 2011 at 11:12 PM, Johan Corveleyn wrote: >> On Tue, Jun 14, 2011 at 7:32 PM, Morten Kloster wrote: >>> On Tue, Jun 14, 2011 at 2:49 AM, Johan Corveleyn wrote: On Tue, Jun 7, 2011 at 10:16 PM, Morten Kloster wrote: >

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

2011-06-26 Thread Morten Kloster
On Tue, Jun 14, 2011 at 11:12 PM, Johan Corveleyn wrote: > On Tue, Jun 14, 2011 at 7:32 PM, Morten Kloster wrote: >> On Tue, Jun 14, 2011 at 2:49 AM, Johan Corveleyn wrote: >>> On Tue, Jun 7, 2011 at 10:16 PM, Morten Kloster wrote: >> [] Here's an updated patch based on the current HE

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

2011-06-14 Thread Johan Corveleyn
On Tue, Jun 14, 2011 at 7:32 PM, Morten Kloster wrote: > On Tue, Jun 14, 2011 at 2:49 AM, Johan Corveleyn wrote: >> On Tue, Jun 7, 2011 at 10:16 PM, Morten Kloster wrote: >>> > [] >>> Here's an updated patch based on the current HEAD, and with >>> one or two minor improvements. While, as stated,

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

2011-06-14 Thread Morten Kloster
On Tue, Jun 14, 2011 at 2:49 AM, Johan Corveleyn wrote: > On Tue, Jun 7, 2011 at 10:16 PM, Morten Kloster 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

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

2011-06-13 Thread Johan Corveleyn
On Tue, Jun 7, 2011 at 10:16 PM, Morten Kloster wrote: > On Fri, May 27, 2011 at 11:00 PM, Morten Kloster 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 tim

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

2011-06-07 Thread Morten Kloster
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 sys

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

2011-05-27 Thread Morten Kloster
[[[ 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 u