linear/relative or binary search algorithm?

[Milian Wolff]

On Sunday 25 October 2009 02:08:50 Milian Wolff wrote:
> 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 now implemented my two ideas, i.e. a relative search (relative to the 
last search) and a binary search. Of course the latter is faster for random 
access, while the former is faster for linear access.

To decide which one to use I'm now running callgrind on each of the three 
(i.e. also the initial algorithm) on the huge phpfunctions.php file.

Thank god I have access to always-on machines at my university :)

So far I'd say: Implement binary search as it's always fast. I doubt the 
additional speed in the linear/relative algorithm is significant together with 
the other stuff going on during a declaration build.

I'll publish the results tomorrow (lets hope it finishes in ~12h ;-) ). Maybe 
we can find some more bottlenecks this way :)

Oh and please review my implementation of the binary search algorithm, you can 
find it here:

http://websvn.kde.org/trunk/playground/devtools/kdevelop-pg-
qt/tests/benchmarks.cpp?revision=HEAD&view=markup

Note that I never wrote such an algorithm before, hence feedback is much 
appreciated. Esp. the part where I increase/decrease the iterator by 
float(upperBound - lowerBound)/2. Is that OK?

As you can see in the benchmarks, I've added some tests to verify that all 
algorithms return the same results.

I'd be also interested in testing whether it's significantly slower (if not 
even faster!) to use e.g. QVector or QList together with qBinaryFind, or a 
std::vector with a binary_search. Of course that would mean I'd have to 
benchmark _filling_ the lookup table as well.

So, cya tomorrow!
-- 
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/5de5a548/attachment.sig>