KDevelop-PG-Location-Table::positionAt updated with new combined relative/binary algorithm

[Milian Wolff]

Hey guys,

just wanted to notify you that I updated the algorithm that is used in the 
KDevelop-PG-Qt LocationTable::positionAt method. The old linear algorithm was 
of course pretty bad for huge files (i.e. our phpfunctions.php with its 80k 
lines).

In release mode the new algorithm is fast, no matter if we use linear or 
random access:

********* Start testing of KDevPG::Benchmarks *********                                                                                                           
Config: Using QTest library 4.5.2, Qt 4.5.2                                                                                                                       
PASS   : KDevPG::Benchmarks::initTestCase()                                                                                                                       
RESULT : KDevPG::Benchmarks::positionAt():"initial, linear":                                                                                                      
     1,184.0 msec per iteration (total: 11840, iterations: 10)                                                                                                    
RESULT : KDevPG::Benchmarks::positionAt():"initial, random":                                                                                                      
     1,008.5 msec per iteration (total: 10085, iterations: 10)                                                                                                    
RESULT : KDevPG::Benchmarks::positionAt():"relative, linear":                                                                                                     
     1.3 msec per iteration (total: 14, iterations: 10)                                                                                                           
RESULT : KDevPG::Benchmarks::positionAt():"relative, random":                                                                                                     
     1,185.0 msec per iteration (total: 11850, iterations: 10)                                                                                                    
RESULT : KDevPG::Benchmarks::positionAt():"binary, linear":                                                                                                       
     31.1 msec per iteration (total: 312, iterations: 10)                                                                                                         
RESULT : KDevPG::Benchmarks::positionAt():"binary, random":                                                                                                       
     39.2 msec per iteration (total: 392, iterations: 10)                                                                                                         
RESULT : KDevPG::Benchmarks::positionAt():"binary & relative, linear":                                                                                            
     0.8 msec per iteration (total: 8, iterations: 10)                                                                                                            
RESULT : KDevPG::Benchmarks::positionAt():"binary & relative, random":                                                                                            
     40.2 msec per iteration (total: 402, iterations: 10)                                                                                                         
PASS   : KDevPG::Benchmarks::positionAt()                                                                                                                         
PASS   : KDevPG::Benchmarks::cleanupTestCase()                                                                                                                    
Totals: 3 passed, 0 failed, 0 skipped                                                                                                                             
********* Finished testing of KDevPG::Benchmarks *********

I've also profiled the former implementations (i.e. all but the one I 
committed), but I'll also profile the committed implementation to proof that 
it is the best :)

If you are interested in the callgrind output (esp. for with the new 
algorithms applied to find new bottlenecks) visit:

http://users.physik.fu-berlin.de/~milianw/kdevelop_profiling_26_10.tar.bz2

Cya
-- 
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/20091026/80fc81e7/attachment.sig>