HTML5 Canvas: performance and optimization. Part 2: going deeper

Last time we were talking about JavaScript optimization, we used some basic optimization techniques to achieve better performance of Flood Fill algorithm on HTML5 Canvas. Today we’re going to go deeper.

We discussed results internally and came out with several low-level fixes. Here they go:

Minimize created objects count

First of all we thought about enormous number of objects we created during execution of our algorithm. As you probably remember, we’d applied fix named ‘Temp object creation’, when we tried to minimize number of performed arithmetic operations. It had negative effect on performance because of increased memory allocation and garbage collector overhead. So, the less objects you created – the better performance you get. It is not hard to notice that most of objects in our code are created here:
What if we don’t create new objects here at all? Let’s store in stack individual coordinates instead of creating wrapper objects. Sure, it makes code more complicated and unreadable, but performance is our main goal today. So, we came out with this:
Results follows:

Please note, we removed two bad fixes from the previous article. We’ve got nice results in all browsers, but in Safari results were really amazing: about 45% performance boost. If we remember bad “Temp object” fix from the previous article we notice that Safari was dramatically slower than other browsers after that fix, so such result is logical consequence of some issues Safari has with objects allocation and/or garbage collection.

Inline functions

Let’s go deeper. Most modern compilers do function inlining automatically or provide you with ability to mark function with some kind of inline attribute (think C’s inline keyword or AggressiveInliningAttribute from .NET 4.5). JavaScript don’t allow you to do that. Although function inlining might have dramatic performance effect in case you call function very often. We call isSameColor about 2 million times and setPixelColor about 700K times. Let’s try to inline them manually:
Again, it makes our code less readable and understandable, but we really want better performance, so we don’t care about code readability here.

Isn’t it amazing? Absolutely incredible results: we’ve got 70% boost on Firefox, 56% on IE and 36% on Safari. And what about Chrome? Surprisingly it is 9% slower. It seems that Google already implemented automatic function inlining in V8 optimizer and our manual fix is worse than theirs. Another interesting thing: with that fix Firefox is almost two times faster than Chrome, previous leader.

Optimize CPU cache utilization

There are one thing we never thought before in context of such a high-level language as JavaScript: CPU cache utilization. It is quite an interesting topic and it deserves separate article. As for now you can read more about it here, for example.
ImageData array has two dimensions that are packed into one dimensional array line by line. So, 3x3 pixel matrix with coordinates (x;y), is basically stored in memory like that:

Let’s look at the following lines in our code:
Let’s think about the order we access neighbor pixels if we are in (1;1):

So, we’re going left, then once again left, then right, then again right. According to best practices of cache utilization optimization it is better to access memory sequentially, because it minimizes a chance to have cache miss. So, what we need is something like that:

Let’s rewrite our dx,dy arrays:

Here is what we’ve got:

Well, the only browser reacted significantly was Chrome: we’ve got about 10% better performance with it. Other browsers were up to 3% faster which is in the area of statistical error. Anyway, this is interesting result that means we should pay attention even to such low-level optimizations when we write code on JavaScript – they are still important.

Fixing own bug – reorder if statements

Those of you who read inlined code carefully might already noticed that we actually did a mistake there:

We check pixel color and only then make sure that we don’t go outside array bounds. In statically typed language we’d got some kind of IndexOutOfBoundsException or Access Violation error here. But in JavaScript arrays are basically hash tables, so noting prevents you from accessing negative index here. But due to the cost of array element access operation it makes sense to check array bounds before checking colors:

Results are surprising:

Most of the browsers results were in the area of statistical error, but Chrome was more than two times faster and got its crown of fastest browser back in our benchmark! It is hard to tell what the reason of such a dramatic difference is. Maybe other browsers use instruction reordering and already applied that optimization by themselves, but it looks strange Chrome don’t do it. There also may be some hidden optimization heuristics in Chrome that help it understand that stack is used as simple array, not hash-table and it makes some significant optimization based on that fact.

Conclusions

Low-level optimizations matter even if you write your code in high-level language such as JavaScript. Code is still executed on same hardware as if you write it on C++.
Each JavaScript engine is different. You can have significant performance boost in one browser, but at the same time your fix may make your code slower in another browser. Test your code in all browsers your application must work with.
Keep the balance between code readability and performance considerations. Sometimes it makes sense to inline function even if it makes your code less readable. But always make sure that it brings you desired value: it doesn’t make sense to sacrifice code readability for 2 ms performance boost for code that is already fast enough.
Think about object allocation, memory usage and cache utilization, especially if you work with memory intensive algorithms such as Flood Fill.

You can find all the results with exact numbers at Google Spreadsheets: https://docs.google.com/open?id=0B1Umejl6sE1raW9iRkpDSXNyckU
You can check our demo code at GitHub: https://github.com/eleks/canvasPaint
You can play with app, deployed on S3: https://s3.amazonaws.com/rnd-demo/canvasPaint/index.html
Thanks to Yuriy Guts for proposed low-level fixes.
Stay tuned!

HTML5 Canvas: performance and optimization

It's no doubt that HTML5 is going to be next big platform for software development. Some people say it could even kill traditional operating systems and all applications in future will be written with HTML5 and JavaScript. Others say HTML5 apps will have their market share, but never replace native applications completely. One of the main reasons is poor JavaScript performance, they say. But wait, browser vendors say they did lots of optimizations and JavaScript is fast as it was never before! Isn't it true?
Well, simple answer is yes... and no. Modern JavaScript engines such as Google's V8 have impressive performance in case you compare them with their predecessors five-ten years ago. Although, their results are not so impressive if you compare them with statically typed languages such as Java or C#. And of course it will be absolutely unfair competition if we compare JavaScript with native code written with C++.
But how one can determine if their application could be written in JavaScript or should they choose native tools?
Recently we had a chance to make such kind of decision. We were working on proposal for tablet application that should include Paint-like control where user can draw images using standard drawing tools like Pencil and Fill. Target platforms were Android, Windows 8 and iOS, so cross-platform development tools had to be taken into consideration. From the very beginning there was a concern that HTML5 canvas could be too slow for such task. We implemented simple demo application to test canvas performance and prove if it is applicable in that case. Leaping ahead, let us point out that we have mixed fillings about gathered results. On the one hand canvas was fast enough on simple functions like pencil drawing due to native implementation of basic drawing methods. On the other hand, when we implemented classic Flood Fill algorithm using Pixel Manipulation API we found that it is too slow for that class of algorithms. During that research we applied set of performance optimizations to our Flood Fill implementation. We measured their effect on several browsers and want to share them with you.

Initial implementation 

Our very first Flood Fill implementation was very simple:

We tested it with 3 desktop browsers running on Core i5 (3.2 GHz) and 3rd generation iPad with iOS 6. We got following results with that implementation:

Surprisingly, IE 10 is even slower than Safari on iPad. Chrome proved that it is still fastest browser in the world.

Optimize pixel manipulation 

Let's take a look at getPixelColor function:
Code looks little bit ugly, so let's cache result of ((y * (img.width * 4)) + (x * 4)) expression (pixel offset) in variable. Also it makes sense to cache img.data reference into another variable. WE also applied similar optimizations to setPixelColor function:

At least code looks more readable. And what about performance?

Impressive, we got 40-50% performance gain on desktop browsers and about 30% on Safari for iOS. IE 10 now has comparable performance to mobile Safari. It seems that Safari's JavaScript compiler already applied some of optimization we did, so effect was less dramatic for it.

Optimize color comparison 

Let's take a look at getPixelColor function again. We mostly use it in if statement to determine if pixel already was filled with new color: getPixelColor(img, cur.x + dx[i], cur.y + dy[i]) != hitColor. As far as you probably know, HTML5 canvas API provide access to individual color components of each pixel. We use this components to get whole color in RGB format, but here we actually don't need to do it. Let's implement special function to compare pixel color with given color:
Here we use standard behavior of || operator: it doesn't execute right part of the expression if left part returns true. This optimization allows us to minimize array reads and arithmetic operations count. Let's take look at its effect:

Almost no effect: 5-6% faster on Chrome and IE and 2-3% slower on FF and Safari. So, problem must be somewhere else. We left this fix in our code because the code is little bit faster in average with it than without.

Temp object for inner loop

As you probably noticed, our code in main flood fill loop looks little bit ugly because of duplicated arithmetic operations:

Let's rewrite it using temp object for new point we work with:
And test effect:

Results are discouraging. It seems that side-effect of such fix is higher garbage collector load and as a result overall slowness of the application. We tried to replace it with two variables for coordinates, defined in outer scope but it didn't help at all. Logical decision is to revert that code, what we actually did.

Visited pixels cache

Let's think again about pixel visiting in Flood Fill algorithm. It is obvious that we should visit each pixel only once. We guarantee such behavior by comparing colors of neighbor pixels with hit pixel color, which must be slow operation. In fact, we can mark pixels as visited and compare colors only if pixel is not visited. Let's do it:
So, what are results? Well, here they go:

Again, absolutely unexpected results: IE 10 is 10% faster with that fix, but other browsers are dramatically slower! Safari is even slower than initial implementation. It is hard to tell what is the main reason of such behavior, but we can suppose that it could be garbage collector. It also makes sense to apply it in case you don't target mobile Safari and want to have maximum performance in worst case (Sorry IE, it is you. As usual).

Conclusions

We tried to make some more optimizations but it didn't help. Worst thing about JavaScript optimizations is that it is hard to predict their effect, mainly because of implementation differences. Remember, there are two basic rules when you optimize JavaScript code:

• benchmark results after each optimization step 
• test in each browser you want your application work with 

HTML5 is cool, but still much slower than native platforms. You should think twice before choosing it as a platform for any compute-intensive application. In other words, there will be no pure HTML5 Photoshop for a long time. Probably you can move some calculations to server-side, but sometimes it is not an option.
You can check our demo code at GitHub: https://github.com/eleks/canvasPaint 
You can play with app, deployed on S3: https://s3.amazonaws.com/rnd-demo/canvasPaint/index.html 
Stay tuned!

UPD: Part 2: going deeper!