<div dir="auto"><div>Hi all,</div><div dir="auto"><br></div><div dir="auto">This is a recap mail from 8 years ago for<br><a href="https://invent.kde.org/utilities/kate/-/merge_requests/737">https://invent.kde.org/utilities/kate/-/merge_requests/737</a></div><div dir="auto"><br></div><div dir="auto">Just in case it's useful...</div><div dir="auto"><br></div><div dir="auto">Best regards</div><div dir="auto">Dominik</div><div dir="auto"><br></div><div dir="auto"><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">---------- Forwarded message ---------<br>Von: <strong class="gmail_sendername" dir="auto">Michal Humpula</strong> <span dir="auto"><<a href="mailto:michal.humpula@seznam.cz">michal.humpula@seznam.cz</a>></span><br>Date: Fr., 17. Jan. 2014, 13:12<br>Subject: Re: using google-diff-match-patch<br>To: Dominik Haumann <<a href="mailto:dhaumann@kde.org">dhaumann@kde.org</a>><br>Cc:  <<a href="mailto:kwrite-devel@kde.org">kwrite-devel@kde.org</a>><br></div><br><br>And here comes the update<br>
<br>
With the little tweaks to cpp code, I was able to push down the execution time <br>
for my test example from 8s to 4s (diff binary is able to execute in 0.5s).<br>
<br>
After this, it seems that most of the time is spent converting from QByteArray <br>
to QString and back and creating temporary QStrings. IMHO this could be speed <br>
up considerably by switching to const QByteArray altogether and just working <br>
with references.<br>
<br>
The whole output of the diff process is escaped with <br>
QByteArray::toPercentEncoding, which currently takes half of the execution <br>
time. But I have no idea, why is that necessary.<br>
<br>
For comparison, I've run the same test with python and lua version:<br>
<br>
Python: 13s<br>
Lua: 18s<br>
Java: 23s<br>
<br>
Seems like general problem with algorithm to me.<br>
<br>
On Wednesday 15 of January 2014 13:34:07 Dominik Haumann wrote:<br>
> On Wednesday, January 15, 2014 12:11:24 Michal Humpula wrote:<br>
> > did a quick speed test. Compiled with -O2, Qt4.8.6 (no _FAST_ switches).<br>
> > Testing just diff_main routine<br>
> > <br>
> > Two 3,6k lines cpp files (one kate source file) took 4ms per diff.<br>
> > Two ~11MB cpp files (100 concatenation off above files) took 3,9s per<br>
> > diff.<br>
> > <br>
> > The numbers are correct, I've checked that twice. Seems like it doesn't<br>
> > scale in linear time. Just for compare, the "diff" program can generate<br>
> > output for the second run in 400ms, so there is definitely a space for<br>
> > improvement.<br>
> <br>
> Run it through `valgrind --tool=callgrind <app>` and analyze the output file<br>
> with kcachegrind.<br>
> <br>
> Or with perf record <app> and then perf report.<br>
> <br>
> Maybe there is some Qt class or similar ill used?<br>
> <br>
> Greetings,<br>
> Dominik<br>
> <br>
> > On Tuesday 14 of January 2014 10:57:27 Neil Fraser wrote:<br>
> > > I have absolutely no objections to any open source use of diff match<br>
> > > patch.<br>
> > > <br>
> > > That said, before you invest too heavily in this library, please<br>
> > > verify that the C++/Qt version of diff match patch meets your<br>
> > > performance needs.  I've never been happy with this port, in my tests<br>
> > > it has performed slower than the JavaScript version.  One of these<br>
> > > days I'd like to replace it with a pure C version.<br>
> > > <br>
> > > On 14 January 2014 05:48, Dominik Haumann <<a href="mailto:dhaumann@kde.org" target="_blank" rel="noreferrer">dhaumann@kde.org</a>> wrote:<br>
> > > > Dear Neil,<br>
> > > > <br>
> > > > I am writing to you on behalf of the KDE/Kate project [1]. Kate is an<br>
> > > > advanced text editor under KDE with lots of features for programmers.<br>
> > > > <br>
> > > > One feature is showing a diff. For instance, if a file changed on<br>
> > > > disk,<br>
> > > > we<br>
> > > > currently launch the external `diff` process to get the diff of the<br>
> > > > text<br>
> > > > buffer and the file on disk, and then show it graphically.<br>
> > > > However, this is not portable and to some degree slow.<br>
> > > > <br>
> > > > Therefore, we are looking for a C++/Qt solution we can use to generate<br>
> > > > the<br>
> > > > diff. Since google-diff-match-patch has a C++/Qt interface, it looks<br>
> > > > like<br>
> > > > the perfect match. However, Kate is licensed under "LGPL version 2 or<br>
> > > > later".<br>
> > > > <br>
> > > > Is there any chance we are allowed to use google-diff-match-patch?<br>
> > > > As far as we know, the Apache 2 license is incompatible with LGPLv2.<br>
> > > > <br>
> > > > Would it be possible to put google-diff-match-patch into a library,<br>
> > > > and<br>
> > > > then dynamically link the text editor to this library? Or would that<br>
> > > > still violate licensing?<br>
> > > > <br>
> > > > We're very much interested in finding a solution and clarifying<br>
> > > > possible<br>
> > > > licensing conflicts.<br>
> > > > <br>
> > > > CC for reference: <a href="mailto:kwrite-devel@kde.org" target="_blank" rel="noreferrer">kwrite-devel@kde.org</a><br>
> > > > <br>
> > > > Thanks in advance,<br>
> > > > Dominik & Kate developers<br>
> > > > <br>
> > > > [1] <a href="http://kate-editor.org/" rel="noreferrer noreferrer" target="_blank">http://kate-editor.org/</a><br>
> > <br>
> > _______________________________________________<br>
> > KWrite-Devel mailing list<br>
> > <a href="mailto:KWrite-Devel@kde.org" target="_blank" rel="noreferrer">KWrite-Devel@kde.org</a><br>
> > <a href="https://mail.kde.org/mailman/listinfo/kwrite-devel" rel="noreferrer noreferrer" target="_blank">https://mail.kde.org/mailman/listinfo/kwrite-devel</a><br>
<br>
</div></div></div>