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
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:
>>>>
>> []
>>>&
On Wed, Jun 15, 2011 at 1:08 AM, Johan Corveleyn wrote:
> On Tue, Jun 14, 2011 at 5:33 PM, Stefan Sperling wrote:
>> On Tue, Jun 14, 2011 at 05:21:27PM +0200, Neels J Hofmeyr wrote:
>>> Hi Johan,
>>>
>>> it's been a while and I still haven't sent you my diff wish we briefly
>>> touched on the Sub
On Tue, Jun 14, 2011 at 05:21:27PM +0200, Neels J Hofmeyr wrote:
> Hi Johan,
>
> it's been a while and I still haven't sent you my diff wish we briefly
> touched on the Subversion hackathon.
>
> Here is a fabricated example of why I don't like diff to match empty lines:
> A couple of lines get rep
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 man
On Sun, Jun 12, 2011 at 9:37 PM, Greg Hudson wrote:
> My executive summary of your post is that you want diff3 to try to merge
> related, but not identical, changes occuring between a pair of sync
> points. I'm wary about this for two reasons.
>
> First, the benefit appears to arise chiefly for w
ff_latest, which
is currently not the case. It might be best to add more display
options for the output functions, so an API change might still be
required. Some or all of the output functions would need to be
adjusted to handle these possibilities.
===
If you know of reasons why these changes would be a bad
idea, please provide examples when possible.
Morten Kloster
the output functions would need to be
adjusted to handle these possibilities.
---
If you know of reasons why these changes would be a bad
idea, please provide examples when possible.
Morten Kloster
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 wrote:
> [[[
> Speeds up LCS algorithm for well-separated sections of change
> By exploiting unique matches between the two files, it is possible to
&g
On Mon, Jun 6, 2011 at 3:17 AM, Johan Corveleyn wrote:
> On Wed, Jun 1, 2011 at 5:56 PM, Morten Kloster wrote:
[]
> Hi Morten,
>
> Sorry, it took me a little while longer than expected, but I finally
> got around to it.
>
> I did some more tests, and upon further inves
On Wed, Jun 1, 2011 at 1:35 AM, Johan Corveleyn wrote:
> On Tue, May 31, 2011 at 12:44 PM, Johan Corveleyn wrote:
> ...
[]
> I'll get into some more testing and reviewing tomorrow or the day
> after (unless someone else beats me to it :-)).
>
> Cheers,
> --
> Johan
>
I had trouble getting any re
On Wed, Jun 1, 2011 at 10:28 AM, Johan Corveleyn wrote:
> On Wed, Jun 1, 2011 at 10:04 AM, Philip Martin
> wrote:
>> Stefan Fuhrmann writes:
>>
Updated log message:
[[[
Simpler/faster LCS algorithm in libsvn_diff by elimination of idx.
* subversion/libsvn_diff/lcs.c
On Mon, May 30, 2011 at 12:26 PM, Stefan Sperling wrote:
> On Mon, May 30, 2011 at 08:25:38AM +0200, Markus Schaber wrote:
>> Hi, Morten,
>>
>> > Von: Morten Kloster [mailto:mor...@gmail.com]
>>
>> > I haven't changed the index/count types yet. What&#
Here's a version that resolves conflicts from r1128921.
Index: subversion/libsvn_diff/diff.c
===
--- subversion/libsvn_diff/diff.c (revision 1128966)
+++ subversion/libsvn_diff/diff.c (working copy)
@@ -33,7 +33,39 @@
#i
On Sun, May 29, 2011 at 6:17 PM, Morten Kloster wrote:
> On Sun, May 29, 2011 at 6:00 PM, Bert Huijben wrote:
>>
>>
>>> -Original Message-
>>> From: Morten Kloster [mailto:mor...@gmail.com]
>>> Sent: zondag 29 mei 2011 17:35
>
On Sun, May 29, 2011 at 6:00 PM, Bert Huijben wrote:
>
>
>> -Original Message-----
>> From: Morten Kloster [mailto:mor...@gmail.com]
>> Sent: zondag 29 mei 2011 17:35
>> To: Julian Foad
>> Cc: Mark Phippard; dev@subversion.apache.org
>> Subject: Re: [
On Fri, May 27, 2011 at 7:57 PM, Julian Foad wrote:
> Morten Kloster wrote:
>> On Fri, May 27, 2011 at 4:55 PM, Julian Foad
>> wrote:
>> > Morten Kloster wrote:
>> >> I haven't changed the index/count types yet. What's the right type
>> &
(stefan) wrote:
> Hi Morten,
> Did you activate compiler optimizations (e.g. use the release build in VS)?
> While your patch makes the code easier to read, the GCC output is
> the same as for the unchanged code - except for an additional NOP
> to ensure optiminal branch target alignment.
> -- Stef
Here is an updated version that resolves conflicts with revision 1128852.
Index: subversion/libsvn_diff/lcs.c
===
--- subversion/libsvn_diff/lcs.c(revision 1128868)
+++ subversion/libsvn_diff/lcs.c(working copy)
@@ -48,
On Fri, May 27, 2011 at 8:41 PM, Morten Kloster wrote:
> [[[
> Faster LCS algorithm in libsvn_diff by reworking fp argument
>
> * subversion/libsvn_diff/lcs.c
> (svn_diff__snake): fp and k arguments are added by caller
> ]]]
>
> Calling svn_diff__snake with fp+k as arg
On Sat, May 28, 2011 at 10:18 AM, Johan Corveleyn wrote:
[]
>
> Actually, about the theory behind the algorithm: I think it would be
> quite beneficial if lcs.c would contain more high level documentation
> about how the algorithm works, and why it works. Right now it only
> contains this referenc
[[[
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
[[[
Faster LCS algorithm in libsvn_diff by reworking fp argument
* subversion/libsvn_diff/lcs.c
(svn_diff__snake): fp and k arguments are added by caller
]]]
Calling svn_diff__snake with fp+k as argument instead of both as
separate arguments reduces running time for the lcs algorithm
substantia
[]
>
> I've attached an updated version.
>
And there I go, forgetting the .txt file type again.
HERE is the new version.
Morten
Index: subversion/libsvn_diff/lcs.c
===
--- subversion/libsvn_diff/lcs.c(revision 1128318)
+++
On Fri, May 27, 2011 at 4:55 PM, Julian Foad wrote:
> Morten Kloster wrote:
>> I haven't changed the index/count types yet. What's the right type
>> to use to get signed 32 bit on 32-bit machines and signed 64 bit
>> on 64-bit machines?
>
> "int&
On Fri, May 27, 2011 at 3:13 PM, Julian Foad wrote:
> On Fri, 2011-05-27 at 13:32 +0200, Johan Corveleyn wrote:
>> On Fri, May 27, 2011 at 12:47 PM, Fuhrmann Stefan (ETAS/ESA1)
>> wrote:
>> > Morten Kloster wrote:
>> >
>> >> [[[
>> >> Simp
My bad; I had forgotten to wrap two of the counting loops in NULL
checks. This version fixes it. Thanks again for catching that bug,
Mark.
I've also figured out how to run the test C programs. The new
version passes all libsvn_diff tests.
I haven't changed the index/count types yet. What's the ri
Diff3 seemed to work fine here in preliminary testing. I'll run
more test, but just in case, which version of the patch did
you use? If you somehow got the .patch file that I included
with my original post, which didn't make it to the archive,
that version had a bug (as noted in my 2nd post). It's
On Thu, May 26, 2011 at 6:32 PM, Mark Phippard wrote:
> On Thu, May 26, 2011 at 11:13 AM, Mark Phippard wrote:
>> I applied your patch on OSX and figured I would at least run the tests
>> for you. Builds go OK, but the one of the tests fail and two other
>> tests crash your patch applied. The c
[[[
Simpler/faster LCS algorithm in libsvn_diff by elimination of idx.
* subversion/libsvn_diff/lcs.c
(svn_diff__snake_t): Removed idx parameter (always 0)
(svn_diff__lcs_t): Removed idx variable (always 0) , let d have either
sign, and moved the origo of fp by d. New version no longer choo
On Wed, May 25, 2011 at 1:44 AM, Johan Corveleyn wrote:
> On Tue, May 24, 2011 at 10:46 PM, Stefan Sperling wrote:
>> On Tue, May 24, 2011 at 10:22:58PM +0200, Morten Kloster wrote:
>>> Johan / Stefan - any progress on the reviewing part?
>>
>> I haven't had ti
Johan / Stefan - any progress on the reviewing part?
Only possible error I'm aware of is that I made the indices/counts
32 bit signed/unsigned integers, which means it'll run into trouble
if there are more than ~2 billion different tokens (lines) or more than
~4 billion occurrences of the same tok
Never mind, it looks like it's just my browser messing up things.
On Thu, May 19, 2011 at 2:28 PM, Daniel Shahaf wrote:
> Did they? I have not changed mutt/vim's configuration recently and I've
> sent many patches inline before.
>
> Morten Kloster wrote on Thu, May
Yeah, it was the same problem that I had when I included the patch
directly in the email; the indentations got all messed up on the
archive.
On Thu, May 19, 2011 at 2:07 PM, Daniel Shahaf wrote:
> Morten Kloster wrote on Thu, May 19, 2011 at 13:38:56 +0200:
>> Here is a version wi
011 at 07:31:54PM +0200, Morten Kloster wrote:
>>> >
>>> > I'm attaching a version of the patch re-generated with -x-pw.
>>> >
>>> > [[[
>>> > Index: subversion/libsvn_diff/diff.c
>>> > =
+ new_node->index = tree->node_count++;
*node = *node_ref = new_node;
@@ -168,7 +181,7 @@
/* Create a new position */
position = apr_palloc(pool, sizeof(*position));
position->next = NULL;
- position->node = node;
On Wed, May 18, 2011 at 9:25 PM, Johan Corveleyn wrote:
> On Wed, May 18, 2011 at 9:23 PM, Johan Corveleyn wrote:
>> On Wed, May 18, 2011 at 7:31 PM, Morten Kloster wrote:
>>> Thanks, Daniel.
>>>
>>> Johan:
>>> I've found your notes trunk
t; + current = current->next;
> + }
> + while (current != position_list[3]);
> + }
> +
> /* Get the lcs for original - latest */
> - lcs_ol = svn_diff__lcs(position_list[0], position_list[2], prefix_lines,
> + lcs_ol = svn_diff__lcs(position_list[0], position_list[2],
> +
On Wed, May 18, 2011 at 8:33 AM, Johan Corveleyn wrote:
> On Wed, May 18, 2011 at 1:56 AM, Morten Kloster wrote:
>> Log message:
>>
>> Speed-up of libsvn_diff using token counts
>> By using indices, not node pointers, to refer to tokens, and counting
>> the
, but the changes to svn_diff_diff3 and svn_diff_diff4 are
completely analogous. Tested on a Windows 7 64-bit machine,
TortoiseSVN build script.
Morten Kloster (first patch)
40 matches
Mail list logo
