Language Plugin Parsers / KDevelop-PG-Qt Performance

[Milian Wolff]

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.

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/35f3b6e5/attachment.sig>