Language Plugin Parsers / KDevelop-PG-Qt Performance

[Milian Wolff]

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.

> 2) dunno, if the following algorithm has a name (I bet it does), but it
>  would work like this:
> - look at index of line in the middle of the list
> - if index is good, finish
> - if index is too high, use lower half of remaining list, continue from
> beginning
> - if index is too low, use upper half of remaining list, continue from
> beginning
> This should at least reduce the number of iterations required. If I'm not
> mistaken it would take log_2(total number of lines) to find the correct
>  index, in my case a maximum of 17. Of course the code would become much
>  more complicated, as we don't want to copy lists, but always operate on
>  the base list...
> 
> I think I'll implement both tomorrow and see what I get. Both somehow
>  interest me :) Do you have any other ideas? I bet you "real" computer
>  science guys have learned such stuff in school and can solve it easily? Is
>  there maybe something already available in algorithm.h or the Qt
>  equivalent?
> 
> You can download the data (highly compressed) from
> http://milianw.de/files/kdevelop/callgrind_data.7z
> 


-- 
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: 197 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.kde.org/pipermail/kdevelop-devel/attachments/20091025/fcdc33ab/attachment.sig>