Performance vs Responsiveness —or— How I Made the Parser Twice As Fast in One Day
Since we [launched Ubiquity 0.5][1], the issue of Parser 2 performance has been brought up [over][2] and [over][3] within the community. By virtue of having a [more flexible and localizable design][4], Parser 2 was expected to be slower than our original parser, but its current implementation felt noticeably—perhaps unnecessarily—slow compared to Parser 1. Parser 2 performance has been identified as [one of the blockers][5] for pushing Ubiquity 0.5+ to all of our 0.1.x users, and has thus been one of my recent foci.
The short story:
Inspired by some comments by [Blair][6], yesterday I was able to make significant (roughly 100%) performance gains in Parser 2, resulting in 40-60% faster parses, depending on the query. This change [has been committed][7] and will be released as part of our forthcoming minor update, Ubiquity 0.5.4. Yay!
The long story: asynchronous parsing
Given that parsing in Ubiquity, combined with the post-parse of displaying suggestions, takes a good few dozen milliseconds, it is important to make sure it doesn’t block the main execution thread in order for the UI to stay responsive throughout. In other words, we needed to make it asynchronous.[^1]
When we began work on Parser 2 a few months ago, [Blair][6] stepped up to the plate to make it run asynchronously. For various reasons, the parser doesn’t run in a Worker thread for truer threading. Instead, what we did was to put the parser’s steps into a [generator][8] called _yieldingParse. The keyword yield is scattered in points throughout this generator.
function _yieldingParse(...) {
// step 1
...
yield true;</p>
// step 2
...
{
...
yield true;
}
...
}
</pre>
We then iterate over a _yieldingParse object in a function called doAsyncParse. Each time we go invoke doAsyncParse, it invokes next which advances from the last yield point of the parse to the next one. doAsyncParse checks after each step whether we should keepworking or not and then asynchronously advances to the next step by calling itself with a setTimeout. (Note the code below is a simplification.)
var parseGenerator = _yieldingParse();</p>
function doAsyncParse() {
var ok = parseGenerator.next();
if (ok && keepworking)
Utils.setTimeout(doAsyncParse,0);
}
// get this party started
Utils.setTimeout(doAsyncParse,0);
</pre>
The more often we yield, the more responsive the UI would be. However, there is a certain overhead to yielding each time due to the setTimeouts we call. This point hit home when Blair told me the other day that the parser was much faster without any of the setTimeouts. Indeed, in my own testing running queries completely synchronously (replacing out all the setTimeouts), parses would run in roughly half the original time. However, by virtue of being completely synchronous, the parser would then completely lock up the UI.
I thus set out to strike a balance between performance and responsiveness by taking out and moving some of the yields in our _yieldingParse (#856).
Tests, tests, tests
Keeping this in mind, I ran a number of tests as I proceeded with my “refactoring.”
Here are some final parse time results:
Four different queries (“hello to span”, “goo hello”, “22.7”, “tw as test” with a selection context of “hello world”) were run using each algorithm. The blue bar is the performance of the algorithm prior to adjustment of setTimeouts—that of Ubiquity 0.5.3. The gold bar is the time from a completely synchronous parse where all the setTimeouts were replaced. This algorithm completely locks up the UI, but is clearly the fastest, and should be seen as a baseline for all other yielding optimizations. The green bar is our new algorithm. As you can see, the parser is now roughly twice as fast.
Moreover, the average time difference between yields went from 0.7ms to 3.9ms which still should be no problem in terms of responsiveness.
Cancellability
This doAsyncParse is also the key for cancellability of the query. When a user changes the input or closes Ubiquity while a query is in progress, we want to cancel that query as soon as possible so the user and UI can advance. keepworking is set to false when the query is cancelled, so making sure that we yield early enough and often enough in the parse are important for issues like keystrokes being lost when typing too fast.
While the parser was indeed yielding often enough (in fact, more often than necessary) before, I noticed that our first yield was often 15-20 ms into the parse. This was because step 1 of our parse derivation was happening outside of the doAsyncParse loop. By moving this into that loop, I was able to bring this initial synchronous time down to around 10 ms. Of course, setting up the parse generator itself takes a little overhead, so this can never go down to 0, but perhaps this will improve the keystroke issue as well. I’d love to get anecdotal feedback on whether this update improves the disappearing keystrokes issue from 0.5.4 users.
This is analogous to a recent discussion of the asynchronous AwesomeBar.
A note on methodology: the Parser 2 Playpen (chrome://ubiquity/content/playpen.html) was used for all testing and timing. All tests were in Firefox 3.5 on Mac OS X Leopard. My machine is a 2.4 GHz Intel Core 2 Duo MacBook Pro. No other (non-OS/daemon) apps were running. No other tabs were open and no other add-ons were installed.
[1]: http://labs.mozilla.com/2009/07/ubiquity-0-5/
[2]: http://groups.google.com/group/ubiquity-firefox/browse_thread/thread/b0dfa649dda77a2c#
[3]: http://groups.google.com/group/ubiquity-firefox/browse_thread/thread/13bc9ade35c8b708#
[4]: https://wiki.mozilla.org/Labs/Ubiquity/Parser_2
[5]: https://wiki.mozilla.org/Labs/Ubiquity/Meetings/2009-08-05_Weekly_Meeting#Notes
[6]: http://theunfocused.net
[7]: https://ubiquity.mozilla.com/hg/ubiquity-firefox/rev/77156d689b26
[8]: https://developer.mozilla.org/en/New_in_JavaScript_1.7#Generators_and_iterators