Language Plugin Parsers / KDevelop-PG-Qt Performance

[Carlos Licea]

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.

Carlos