The RunnerManager interface in libplasma which powers KRunner (among other interfaces) was designed to allow plugins a-plenty so that one search term could be matched in "real time" by several different components, each one looking for answers in different ways or places. This isn't a particularly unique design by any means, and the concept can be seen in many search interfaces out there.
A "run command" app faces a challenge with this sort of design: in usage, one expects the interface to appear "instantly" when called up and remain responsive during use. This isn't the web where pages can take significant fractions of a second without anyone caring or where we can stack dozens/hundreds/thousands of servers behind your queries to offer mindcrushing amounts of compute power to chew through whatever gets thrown at it. No, we have to be fast with limited resources while looking in all kinds of places. Basically, KRunner has to be as responsive as the KDE 3 minicli while doing orders of magnitude more processing. Interesting problem.
To address the problem we made the query plugins, or "runners", multi-threaded even when we only had 2 of them. This ended up involving lots of queue management, but Threadweaver made that as easy as possible. We got rid of many locks as development went on, improving interactivity, and eventually ended up introducing the concept of a query "session". In KRunner, a session starts when the user interface is shown and ends when it is hidden. Runners are given the opportunity to set what they need during searching up at that point. Later, when the session is over, they can tear down all of that allowing us to conserve resources and not wake up KRunner every time a window twitches. This also helped speed up querying in some cases as it meant moving initialization routines that were being run in some cases on every keystroke to once-per-session.
The prep and teardown for sessions is not multithreaded, however. Or rather, the signals that a session is about to begin and end are not. This gives runners some comforting guarantees as to their ability to manipulate pixmaps or x.org information (things that can not be safely done from outside the main application thread) as well as to the order of events: prep, querying, teardown is a guaranteed order.
The new issue that query sessions brought was that some runners have grown time consuming code that is run during session preparation. There were a handful of runners that were taking 20-80 milliseconds each every time the user interface was to be shown. That may not seem like much, but it quickly added up to over 150ms on my dual core 2Ghz laptop which is very noticeable to the human eye. Since this code was running in the main application thread, popping up the KRunner window felt really slow. The question was: which runners were responsible for this and why? Some profiling was in order!
So I popped a small three-line patch into libplasma that measured how long each runner was taking during session preparation. The problem plugins were immediately highlighted. So I went through each of those and did some profiling to see where they were spending their time and pushed code around until the prep time was more reasonable. Most of the work was taking synchronous operations and making them asynchronous. At this point, none of the runners on my system take more than 1-2 milliseconds to prep, which means instead of waiting 0.15 seconds for something to happen after I press Alt+F2, it appears almost immediately. The difference is very noticeable and very pleasing.
What's interesting is that, with one exception, none of the runners are doing any less processing. In fact, in a couple cases they are doing a little more (though nothing to write home about), but the result is something that feels much smoother and more pleasant to use.
I backported the results after testing to the KDE SC 4.4 branch. I don't think the improvements will make it into 4.4.0 (it's already tagged and being packaged) but should be in the 4.4.1 release at the latest. So if you have been finding KRunner sluggish to appear and build from sources, try updating kdebase/workspace/plasma/generic/runners/ and kdeplasma-addons/runners/ and see if things improve after a restart of KRunner.