On Mon, Sep 20, 2010 at 11:52 AM, Branko Čibej <br...@xbc.nu> wrote: > On 15.09.2010 14:20, Johan Corveleyn wrote: >> Some update on this: I have implemented this for svn_diff (excluding >> the identical prefix and suffix of both files, and only then starting >> to fill up the token tree and let the lcs-agorithm to its thing). It >> makes a *huge* difference. On my bigfile.xml (1.5 Mb) with only one >> line changed, the call to svn_diff_diff is ~10 times faster (15-20 ms >> vs. 150-170 ms). > > > Hmmm ... looks to me like test data tailored to the optimization. :)
Nope, that's real data from a real repository, with a normal kind of change that happens here every day. Of course this optimization is most effective if there are a lot of common prefix/suffix lines. If there is a single change in the first line, and a single change in the last one, this optimization will do nothing but introduce a little bit of extra overhead. And it will obviously make the most impact on large files (in fact it's just relative to the ratio of the "number of common prefix/suffix lines" to the "number of lines in between"). I'm sorry it takes me longer than expected to post a version of this to the list, but I'm still having some problems with a couple of edge conditions (I'm learning C as I go, and I'm struggling with a couple of pointer calculations/comparisons). I plan to post something during this week... Cheers, -- Johan