Language Plugin Parsers / KDevelop-PG-Qt Performance

Milian Wolff mail at
Sun Oct 25 01:08:50 UTC 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 

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 

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 
- if index is too low, use upper half of remaining list, continue from 
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 

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
Milian Wolff
mail at
-------------- 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: <>

More information about the KDevelop-devel mailing list