Language Plugin Parsers / KDevelop-PG-Qt Performance

[Milian Wolff]

On Sunday 25 October 2009 05:15:01 Carlos Licea wrote:
> On Sábado 24 Octubre 2009 20:45:43 Milian Wolff escribió:
> > Milian Wolff, 25.10.2009:
> > > Hey guys,
> > >
> > > after waiting quite a bit for my benchmark to finish in callgrind I
> > > just aborted it and looked at the data it produced in the meantime. And
> > > boy was I surprised!
> > >
> > > 75.67% of the time was spent in KDevPG::LocationTable::positionAt() !
> > >
> > > I think the problem is that my test file is very large, it has 79929
> > > lines, and the function above goes everytime from 0 to X where X is the
> > > line that has a proper index...
> > >
> > > I have several ideas how to improve the situation:
> > >
> > > 1) store last looked up line + index and make the search relative to
> > > that: assuming that, during declaration building, the search is always
> > > incremental, or at least we lookup stuff near to each other, this
> > > should greatly increase performance.
> >
> > I couldn't really sleep since I spotted this, so I implemented at least
> > my first idea. See my attached patch for a benchmark. In the benchmark I
> > assume linear access to a quite big location table (12500 lines of approx
> > 80 chars). The results are:
> >
> > Original algorithm:
> > 7,690 msec per iteration (total: 7690, iterations: 1)
> > My algorithm:
> > 4.8 msec per iteration (total: 39, iterations: 8)
> >
> > Looks pretty good already :) There's also a method to verify that the new
> > algorithm is correct.
> >
> >
> > I'll also add the second idea tomorrow, amilcar also told me that the
> > algorithm I describe is called "bisection". Nice, thanks.
> 
> It sounds like a binary search algorithm to me:
> 
> http://en.wikipedia.org/wiki/Binary_search_algorithm
> 
> It also can get tricky to get the *most* efficient method. Are you sure
>  that you can't use qBinaryFind()? if you are using a Qt container (a list,
>  a vector,…) I'd very much recommend you to use the already implemented
>  (and likely tweaked) Qt function.

True, but I'm not the one who wrote the parser. I assumed he wrote the lookup 
table in the way it is specifically because other approaches were insufficient.

To make sure I'll probably have a look how the current implementation (with my 
binary search) performs against a simple QVector or QList basec approach with 
qBinaryFind. Thanks for the heads up!

-- 
Milian Wolff
mail at milianw.de
http://milianw.de
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.kde.org/pipermail/kdevelop-devel/attachments/20091025/c90ecdb7/attachment.sig>