Adblock Plus and (a little) more
Thoughts on using asm.js for performance bottlenecks in browser extensions · 2013-06-26 13:55 by Wladimir Palant
asm.js is big news right now, and for a good reason. Firefox 22 can run some JavaScript code with performance similar to that of a compiled C/C++ application — this is huge. And it got me interested: maybe asm.js can be used to improve the performance of Adblock Plus? So I spent an evening looking into asm.js and Emscripten. This post merely summarizes my thoughts for far, it isn’t meant to be an extensive overview and some of my conclusions might be wrong.
Adblock Plus has well-known performance bottlenecks that I was unable to deal with so far. What’s worse, the same code is responsible for a significant memory usage. C++ should be able to process and store the same data much more efficiently. So at some point in the past I even considered implementing a native library to take over performance-critical tasks but that would create a big mess: that library would need to be compiled for all major platforms targeted by Firefox (currently Windows x86, Windows x64, Linux x86, Linux x64 and OS X), the extension package would need to contain the builds for each platform which would increase its size significantly, and identical JavaScript code as fallback for platforms not covered would still be required. In addition, that effort wouldn’t help Adblock Plus performance in Chrome — it would require yet another solution, maybe PNaCl.
The advent of asm.js seems to make these considerations obsolete. That C++ library can be compiled with Emscripten into asm.js. The same code could then run on any platform and would be fast in both Firefox and Chrome. And the best of it: it would still run fine in older Firefox versions, just not quite as fast. So far the theory, now it’s time to dive into the gory details.
Trying out Emscripten
On the first glance, Emscripten is a collection of Python scripts that can be “installed” simply by checking out the repository. Unfortunately, the requirements listing goes on listing several other packages that need to be installed: LLVM, Clang and node.js. Installing these on Linux is simple enough but the versions available for my Linux distribution were too old. Not a big issue for me of course but enforcing these requirements to build Adblock Plus is a certain way to have no contributors.
Running emcc -O2 -s ASM_JS=1 test.cpp generates rather big files, at least 60 kB even for trivial code. A quick glance shows that most of it is boilerplate code, including lots of code to adapt to various environments: node.js, web page, web worker, shell. Can’t the target environment (shell is probably most appropriate for extension code) be specified at compile time? I couldn’t find any setting to do that.
As soon as you touch functionality provided by C++ the code size balloons up. In particular, doing anything with std::string generates more than 500 kB of code. This probably means that the standard library is off-limits for most extensions, the extension package will otherwise simply grow too big. Unfortunately, this makes the entire solution significantly less convenient.
Next I had to figure out how other extension code can communicate with the asm.js code. Emscripten documentation lists two options: the less convenient approach via Method.cwrap() and the more convenient embind approach. The former doesn’t allow mapping classes into JavaScript but the latter unfortunately has a hefty code size price (100 kB even if no functions are exported). So a flat API it is — unless there is a good reason to go for more convenience.
The important question for me was: how do you pass in a string into the compiled code? Turned out that the string parameter type is somewhat counter-intuitively mapped to char* in C++ rather than wchar_t*. A few experiments explained it: all strings are converted to UTF-8. This means that the string length passed in from JavaScript isn’t usable in C++ without decoding UTF-8 first (it refers to Unicode characters, not to bytes in the UTF-8 encoding), this makes working with the strings without an additional conversion a rather complicated affair.
But maybe the performance is good enough to compensate two conversions — to UTF-8 and back? I implemented a simple rolling hash function, once in C++ (with UTF-8 decoding) and once in JavaScript. When I tested both in the current Firefox Nightly the regular JavaScript version was around 10% faster. Of course, this might be an indication that my UTF-8 decoder wasn’t efficient enough. The decoding algorithm I implemented definitely wasn’t the slowest however. And given that the performance bottlenecks in Adblock Plus are manipulating strings, losing that much performance in conversion will likely mean that the performance gain won’t be too significant.
A look at the raw asm.js
At the moment it seems that Emscripten doesn’t really meet my needs: it’s primarily meant to port large legacy codebases rather than speed up relatively small portions of JavaScript code. But what about hand-writing asm.js code? After all, it’s not too different from regular JavaScript code, you merely have to respect a few rules and the validator will tell you if you don’t. For small code portions that could be acceptable.
Looking into the specification, the biggest challenge here seems to be working with the heap. Variables in asm.js can only use primitive integer and floating point types. Anything beyond that (arrays, structured types, strings) needs to be allocated in the typed array representing the heap. And “allocation” means manual memory management, you essentially have to reimplement the malloc() function.
The other gotcha: heap size is fixed. asm.js code has to get along with a single buffer and cannot change its size (that affects Emscripten-generated code as well of course). Problem with that: I have no way of telling how much memory Adblock Plus will need, it depends largely on the user settings. It might be possible to automatically create new asm.js modules with different heaps if the memory in the original module runs low — coordinating between different modules handling the same data won’t be easy however.
Finally, something that might not be a big deal for other people but is one for Adblock Plus: there are no hash tables. Not using them in Adblock Plus is impossible, they are an essential part of the algorithms. This means however that hash tables need to be reimplemented in asm.js. And I definitely wouldn’t consider that fun.
What now?
All in all, making asm.js work to speed up extensions seems to be a complicated task. It’s hard to imagine that Emscripten will find much use in extensions at the moment, the generated code is simply way too large and the string conversion costs too much performance. What I would rather expect to work would be a compiler for a relatively simple superset of asm.js, breaking it down to regular asm.js. Not much is needed to make asm.js usable in hand-written code: type declarators for variables, structured types and namespaces/objects seem to be the most important omissions. A few generic helpers to manage the heap automatically and use hash tables should allow usable code to be produced then. Still, not being able to allocate additional memory is something that I see as a critical issue that needs to be addressed in the standard.
Comment [3]
Commenting is closed for this article.
Jesse Ruderman · 2013-07-03 04:00 · #
I think a lot of asm.js’s speed boost comes from distinguishing between numeric types (int vs double) and letting the JS engine forget about GC for a while. So I’m not sure a hypothetical extension that supports strings would really solve your problems.
I converted some numeric JS code (mersenne twister PRNG) to be more asm-like, and it got much faster, even before I added the “use asm” line.
Reply from Wladimir Palant:
Yes, that was my impression as well – the “use asm” line isn’t too important if you write your code in a particular way. That’s a nice side-effect of asm.js, it finally shows what kind of code the JS engines are optimized for. In my case, using typed arrays to store strings might actually be a significant improvement, for once because of the more efficient memory storage, but also because character access with typed arrays should be significantly faster (this can allow for a more efficient multi-string search algorithm). Still, manual memory management and self-implemented hash tables required so it will need quite some effort – meaning that we need to verify first whether it is actually worth pursuing.
Jesse Ruderman · 2013-07-03 04:01 · #
You should submit a pure JS benchmark to be included in arewefastyet runs. Then SpiderMonkey developers will be able to optimize for it and spot regressions. It might even get included in a future Kraken-like benchmark suite, in which case all JS engines will compete on being fast on it.
Use the shell function dateNow() in your benchmark. Luke can add it to the “assorted tests” set on arewefastyet.
SpiderMonkey developers might also have suggestions for making your code get along better with the engine.
Mr. Anonymous · 2013-07-03 17:29 · #
Have you thought about trying C with a lightweight hash table functionality like uthash? (http://troydhanson.github.io/uthash/)
Reply from Wladimir Palant:
Sure, using something less heavy than STL is an option, I didn’t really mean that reinventing the wheel is the only way. It does introduce an additional maintenance disadvantage however, our code here will be radically different than C++ code in libadblockplus for example (using STL heavily there). And the generated code will likely still be rather large. But this requires further investigation, so far I only had the time for a brief look.