Milian Wolff

Good news everyone :)

Documentation

After years of pretty much no documentation (except looking at the sources…), The_User aka. Jonathan Schmidt-Dominé started documenting the parser generator that is used for most KDevelop language plugins (java, python, php, …). You can find it here: http://techbase.kde.org/Development/KDevelop-PG-Qt_Introduction

It has to be improved and more examples have to be put in there, but it’s already a huge improvement over the situation before…

Performance

In related news I did some profiling on the parsing of the quite big file that includes all internal PHP declarations (i.e. all functions, classes, definitions,…). It drops in at a whopping 1.9M, with ~80k lines. Well, turns out that this showed a pretty easy to fix bottleneck in KDevelop-PG’s LocationTable, which used to use a linear lookup algorithm. Profiling showed that nearly 75% was spent in that function. But I used the past tense for a reason:

I replaced it with an algorithm that combines a relative search (i.e. relative to the last lookup) with a binary search fallback. That’s comparatively blazingly fast. I added some benchmarks to KDevelop-PG-Qt that proofs that (benchmark below run with release mode build):

********* 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 *********

In our “realworld” phpfunctions.php example the DUChain building process got twice as fast (in debug mode though, but still).

We should probably get lost of the LocationTable altogether and use an existing container (QList, QVector, QLinkedList,… or any STL variant of them). But this would mean more profiling, and well, lets see when we get to it… But just got a reply on the KDevelop list showing interest on this, so maybe someone does that eventually!

Profiling rocks, and KCacheGrind is such a great application. I love such visualization. Well done! And the QTestLib benchmark utilities are also very solid, nice!

PS: KDevelop beta6 is in the pipelines and we’ll release a beta1 of the PHP plugin together with it. Packagers and users rejoice :)