Fwd: using google-diff-match-patch

Hi all,

This is a recap mail from 8 years ago for
https://invent.kde.org/utilities/kate/-/merge_requests/737

Just in case it's useful...

Best regards
Dominik


---------- Forwarded message ---------
Von: Michal Humpula <[email protected]>
Date: Fr., 17. Jan. 2014, 13:12
Subject: Re: using google-diff-match-patch
To: Dominik Haumann <[email protected]>
Cc: <[email protected]>


And here comes the update

With the little tweaks to cpp code, I was able to push down the execution
time
for my test example from 8s to 4s (diff binary is able to execute in 0.5s).

After this, it seems that most of the time is spent converting from
QByteArray
to QString and back and creating temporary QStrings. IMHO this could be
speed
up considerably by switching to const QByteArray altogether and just
working
with references.

The whole output of the diff process is escaped with
QByteArray::toPercentEncoding, which currently takes half of the execution
time. But I have no idea, why is that necessary.

For comparison, I've run the same test with python and lua version:

Python: 13s
Lua: 18s
Java: 23s

Seems like general problem with algorithm to me.

On Wednesday 15 of January 2014 13:34:07 Dominik Haumann wrote:
> On Wednesday, January 15, 2014 12:11:24 Michal Humpula wrote:
> > did a quick speed test. Compiled with -O2, Qt4.8.6 (no _FAST_ switches).
> > Testing just diff_main routine
> >
> > Two 3,6k lines cpp files (one kate source file) took 4ms per diff.
> > Two ~11MB cpp files (100 concatenation off above files) took 3,9s per
> > diff.
> >
> > The numbers are correct, I've checked that twice. Seems like it doesn't
> > scale in linear time. Just for compare, the "diff" program can generate
> > output for the second run in 400ms, so there is definitely a space for
> > improvement.
>
> Run it through `valgrind --tool=callgrind <app>` and analyze the output
file
> with kcachegrind.
>
> Or with perf record <app> and then perf report.
>
> Maybe there is some Qt class or similar ill used?
>
> Greetings,
> Dominik
>
> > On Tuesday 14 of January 2014 10:57:27 Neil Fraser wrote:
> > > I have absolutely no objections to any open source use of diff match
> > > patch.
> > >
> > > That said, before you invest too heavily in this library, please
> > > verify that the C++/Qt version of diff match patch meets your
> > > performance needs.  I've never been happy with this port, in my tests
> > > it has performed slower than the JavaScript version.  One of these
> > > days I'd like to replace it with a pure C version.
> > >
> > > On 14 January 2014 05:48, Dominik Haumann <[email protected]> wrote:
> > > > Dear Neil,
> > > >
> > > > I am writing to you on behalf of the KDE/Kate project [1]. Kate is
an
> > > > advanced text editor under KDE with lots of features for
programmers.
> > > >
> > > > One feature is showing a diff. For instance, if a file changed on
> > > > disk,
> > > > we
> > > > currently launch the external `diff` process to get the diff of the
> > > > text
> > > > buffer and the file on disk, and then show it graphically.
> > > > However, this is not portable and to some degree slow.
> > > >
> > > > Therefore, we are looking for a C++/Qt solution we can use to
generate
> > > > the
> > > > diff. Since google-diff-match-patch has a C++/Qt interface, it looks
> > > > like
> > > > the perfect match. However, Kate is licensed under "LGPL version 2
or
> > > > later".
> > > >
> > > > Is there any chance we are allowed to use google-diff-match-patch?
> > > > As far as we know, the Apache 2 license is incompatible with LGPLv2.
> > > >
> > > > Would it be possible to put google-diff-match-patch into a library,
> > > > and
> > > > then dynamically link the text editor to this library? Or would that
> > > > still violate licensing?
> > > >
> > > > We're very much interested in finding a solution and clarifying
> > > > possible
> > > > licensing conflicts.
> > > >
> > > > CC for reference: [email protected]
> > > >
> > > > Thanks in advance,
> > > > Dominik & Kate developers
> > > >
> > > > [1] http://kate-editor.org/
> >
> > _______________________________________________
> > KWrite-Devel mailing list
> > [email protected]
> > https://mail.kde.org/mailman/listinfo/kwrite-devel