show_menu logo_rd

HTML5 Canvas: Performance and Optimization

1

It’s no doubt that HTML5 is going to be the next big platform for software development. Some 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 in 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 a proposal for a 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 a 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 feelings 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 a 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:

// The CanvasPixelArray object indicates the color components of each pixel of an image, 
// first for each of its three RGB values in order (0-255) and then its alpha component (0-255), 
// proceeding from left-to-right, for each row (rows are top to bottom).
// That's why we have to assign each color component separately. 
function getPixelColor(img, x, y) {
    var result = img.data[((y * (img.width * 4)) + (x * 4)) + 0] << 24; // r
    result |= img.data[((y * (img.width * 4)) + (x * 4)) + 1] << 16; // g
    result |= img.data[((y * (img.width * 4)) + (x * 4)) + 2] << 8; // b
    return result;
}
 
function setPixelColor(img, x, y, color) {
    img.data[((y * (img.width * 4)) + (x * 4)) + 0] = (color >> 24) & 0xFF;
    img.data[((y * (img.width * 4)) + (x * 4)) + 1] = (color >> 16) & 0xFF;
    img.data[((y * (img.width * 4)) + (x * 4)) + 2] = (color >>  8) & 0xFF;
}
 
// flood fill tool
function toolFiller() {
    var dx = [-1, 0, +1, 0];
    var dy = [0, -1, 0, +1];
 
    this.touchstart = this.mousedown = function (ev) {
        // measure execution time
        var stopWatch = new StopWatch();
        stopWatch.start('global');
 
        var canvas = document.getElementById('myCanvas');
        var context = canvas.getContext('2d');
        var pos = findPos(this); // get cursor hit point position
        var x = ev.pageX - pos.x;
        var y = ev.pageY - pos.y;
        var img = context.getImageData(0, 0, W, H);
        
        var hitColor = getPixelColor(img, x, y);
        var stack = [];
        stack.push({ x: x, y: y });
        var newColor = (intval('red') << 24) | (intval('green') << 16) | (intval('blue') << 8);
        setPixelColor(img, x, y, newColor);
        while (stack.length > 0) {
            var cur = stack.pop();
 
            for (var i = 0; i < 4; i++) {
                if (cur.x + dx[i] < 0 || cur.y + dy[i] < 0 || cur.x + dx[i] >= W || cur.y + dy[i] >= H || getPixelColor(img, cur.x + dx[i], cur.y + dy[i]) != hitColor) {
                    continue;
                }
                setPixelColor(img, cur.x + dx[i], cur.y + dy[i], newColor);
                stack.push({ x: cur.x + dx[i], y: cur.y + dy[i]});
            }
        }
 
        context.putImageData(img, 0, 0);
 
        // measure execution time
        var time = stopWatch.stop('global');
        log('Total fill execution time: ' + time.delta() + " ms");
    };
}

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:

function getPixelColor(img, x, y) {
    var result = img.data[((y * (img.width * 4)) + (x * 4)) + 0] << 24; // r
    result |= img.data[((y * (img.width * 4)) + (x * 4)) + 1] << 16; // g
    result |= img.data[((y * (img.width * 4)) + (x * 4)) + 2] << 8; // b
    return result;
}

The code looks a little bit ugly, so let’s cache the 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:

function getPixelColor(img, x, y) {
    var data = img.data;
    var offset = ((y * (img.width * 4)) + (x * 4));
    var result = data[offset + 0] << 24; // r
    result |= data[offset + 1] << 16; // g
    result |= data[offset + 2] << 8; // b
    return result;
}
 
function setPixelColor(img, x, y, color) {
    var data = img.data;
    var offset = ((y * (img.width * 4)) + (x * 4));
    data[offset + 0] = (color >> 24) & 0xFF;
    data[offset + 1] = (color >> 16) & 0xFF;
    data[offset + 2] = (color >>  8) & 0xFF;
}

At least the 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 the if statement to determine if pixel already was filled with the new color: getPixelColor(img, cur.x + dx[i], cur.y + dy[i]) != hitColor. As far as you probably know, HTML5 canvas API provides 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 a special function to compare pixel color with given color:

function isSameColor(img, x, y, color) {
    var data = img.data;
    var offset = ((y * (img.width * 4)) + (x * 4));
    if ((data[offset + 0]) != ((color >> 24) & 0xFF)
      || (data[offset + 1]) != ((color >> 16) & 0xFF)
      || (data[offset + 2]) != ((color >> 8) & 0xFF)) {
        return false;
    }
    return true;
}

Here we use the standard behavior of || operator: it doesn’t execute the right part of the expression if the left part evaluates to 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, the 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 a little bit ugly because of duplicated arithmetic operations:

for (var i = 0; i < 4; i++) {
    if (cur.x + dx[i] < 0 || cur.y + dy[i] < 0 || cur.x + dx[i] >= W || cur.y + dy[i] >= H || getPixelColor(img, cur.x + dx[i], cur.y + dy[i]) != hitColor) {
        continue;
    }
    setPixelColor(img, cur.x + dx[i], cur.y + dy[i], newColor);
    stack.push({ x: cur.x + dx[i], y: cur.y + dy[i]});
}

Let’s rewrite it using temp object for new point we work with:

for (var i = 0; i < 4; i++) {
    var p = { x: cur.x + dx[i], y: cur.y + dy[i]};
    if (p.x < 0 || p.y < 0 || p.x >= W || p.y >= H || !isSameColor(img, p.x, p.y, hitColor)) {
        continue;
    }
    setPixelColor(img, p.x, p.y, newColor);
    stack.push(p);
}

And test the effect:

The results are discouraging. It seems that the 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. A logical decision is to revert that code, which 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 a slow operation. In fact, we can mark the pixels as visited and compare the colors only if the pixel is not visited. Let’s do it:

var visited = new Array(W * H); // visited pixels map
 
var hitColor = getPixelColor(img, x, y);
var stack = [];
stack.push({ x: x, y: y });
var newColor = (intval('red') << 24) | (intval('green') << 16) | (intval('blue') << 8);
setPixelColor(img, x, y, newColor);
visited[x*W + y] = true; // mark as visited
while (stack.length > 0) {
    var cur = stack.pop();
 
    for (var i = 0; i < 4; i++) {
        var pixelHash = (cur.x + dx[i])*W + cur.y + dy[i];
        if (cur.x + dx[i] < 0 || cur.y + dy[i] < 0 || cur.x + dx[i] >= W || cur.y + dy[i] >= H || visited[pixelHash] || !isSameColor(img, cur.x + dx[i], cur.y + dy[i], hitColor)) {
            continue;
        }
        setPixelColor(img, cur.x + dx[i], cur.y + dy[i], newColor);
        visited[pixelHash] = true; // mark as visited
        stack.push({ x: cur.x + dx[i], y: cur.y + dy[i]});
    }
}

So, what are the 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

The 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:

  1. Benchmark the results after each optimization step.
  2. Test in every browser you want your application to 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 also play with the app, deployed on S3: https://s3.amazonaws.com/rnd-demo/canvasPaint/index.html

Stay tuned!

UPD: Part 2: Going Deeper!

Victor Haydin

Victor Haydin is the Head of R&D at ELEKS where he leads the company towards technical innovations. He likes experimenting with cutting-edge technology and creating amusing projects. Formerly an avid participant of programming contests like ACM ICPC, TopCoder and Google AI Challenge, now Victor enjoys photographing, playing guitar, travelling and reading. Lately, Victor’s main project was parenting. Due to his inborn graphomania, Victor is the most active ELEKS Labs author, writing about HPC, cloud, wearables and other cutting-edge technology topics.

tags

Comments: 1