quaternion multiplication: two years later

Sometime back I wrote (fun fact: it's Google first hit for faster quaternion multiplication) about my favorite commit I did exactly two years ago to Qt :

git show cbc22908
commit cbc229081a9df67a577b4bea61ad6aac52d470cb
Author: Ariya Hidayat 
Date:   Tue Jun 30 11:18:03 2009 +0200

    Faster quaternion multiplications.
    
    Use the known factorization trick to speed-up quaternion multiplication.
    Now we need only 9 floating-point multiplications, instead of 16 (but
    at the cost of extra additions and subtractions).

Ages ago, during my Ph.D research, when I worked with a certain hardware platform (hint: it's not generalized CPU), minimizing the needed number of hardware multipliers with a very little impact in the computation speed makes a huge different. With today's advanced processor architecture armed with vectorized instructions and a really smart optimizing compiler, there is often no need to use the factorized version of the multiplication.

Side note: if you want to like quaternion, see this simple rotatation quiz which can be solved quite easily once you know quaternion.

I try to apply the same trick to PhiloGL, an excellent WebGL framework from Nicolas. Recently, to my delight, he added quaternion support to the accompanying math library in PhiloGL. I think this is a nice chance to try the old trick, as I had the expectation that reducing the number of multiplications from 16 to just 9 could give some slight performance advantage.

It turns out that it is not the case, at least based on the benchmark tests running on modern browsers with very capable JavaScript engine. You can try the test yourself at jsperf.com/quaternion-multiplication. I have no idea whether this is due to JSPerf (very unlikely) or it's simply because the longer construct of the factorized version does not really speed-up anything. If any, seems that the amount of executed instruction matters more than whether addition is much faster than multiplication. And of course, we're talking about modern CPU, the difference is then becoming more subtle.

With the help of Nicolas, I tried various other tricks to help the JavaScript engine, mainly around different ways to prepare the persistent temporary variables: using normal properties, using Array, using Float32Array (at the cost of precision). Nothing leads to any significant improvement.

Of course if you have other tricks in your sleeve, I welcome you to try it with the benchmark. Meanwhile, let's hope that someday some JavaScript engine will run the factorized version faster. It's just a much cooler way to multiply quaternions!

SenchaCon 2010

At the last successful, sold-out Sencha Conference 2010, I did two introductory talks about JavaScript and WebKit, mainly targeted for web application developers. Since a few weeks ago, the videos for these talks have been available for you to watch.

JavaScript Engines: Under the Hood is 10,000-foot overview on how a typical JavaScript engine works. Watch it below or at vimeo.com/18783283, with the accompanying slides at http://slidesha.re/gGx9aA.

The other talk Compiling and Optimizing Your Own Browser with WebKit (vimeo.com/18780399 for the video, http://slidesha.re/fPSvXX for the slide deck), mostly showing few tricks you can leverage to understand how your web applications work. For example, by using QtWebKit and capturing all the drawing commands and the corresponding timestamp, it is very easy to have a slow-motion rendering of your web page. As I showed it in the talk, it is even possible to go back in time, i.e. rendering your web page backwards.

Many other videos from SenchaCon 2010 have been published as well. Make sure you check them out.

Enjoy!

PhantomJS meets CoffeeScript

I did something related to CoffeeScript before, namely simple command-line compiler. For those who are not aware of CoffeeScript, it's basically (from Wikipedia) JavaScript with "syntactic sugar inspired by Ruby and Python".

On the hand, surprisingly PhantomJS generates more interest than I ever imagined before (with over 240 watching its repository), prompting me not to abandon it too soon :) In fact, I decided to dump my tought on its roadmap since more and more people are willing to help.

My secret feature, which is not secret anymore, for the upcoming 1.1 release is to incorporate the CoffeeScript compiler so that PhantomJS scripts can be written in CoffeeScript. Since the intention of PhantomJS is for various scripting purpose utilizing headless QtWebKit, this is a perfect match.

Gone are the curly braces...

color wheel on Canvas

While I played with HSV pie and color wheel before, usually I just use the excellent Qt graphics stack to try out various things. This days, I lean towards using web technologies and for that purpose, HTML Canvas suits me just fine. With PhantomJS, I even got the result rendered as PNG image.

The new example I added to PhantomJS is colorwheel.js which produces the above screenshot. The entire script code is as follows (if some parts look cryptic, read about HSL and HSV color space):

if (phantom.state.length === 0) {
    phantom.state = 1;
    phantom.viewportSize = { width: 400, height : 400 };
    phantom.content = '<html><body><canvas id="surface">' +
        '</canvas></body></html>';
} else {
    var el = document.getElementById('surface'),
        context = el.getContext('2d'),
        width = window.innerWidth,
        height = window.innerHeight,
        cx = width / 2,
        cy = height / 2,
        radius = width  / 2.3,
        imageData,
        pixels,
        hue, sat, value,
        i = 0, x, y, rx, ry, d,
        f, g, p, u, v, w, rgb;

    el.width = width;
    el.height = height;
    imageData = context.createImageData(width, height);
    pixels = imageData.data;

    for (y = 0; y < height; y = y + 1) {
        for (x = 0; x < width; x = x + 1, i = i + 4) {
            rx = x - cx;
            ry = y - cy;
            d = rx * rx + ry * ry;
            if (d < radius * radius) {
                hue = 6 * (Math.atan2(ry, rx) + Math.PI) / (2 * Math.PI);
                sat = Math.sqrt(d) / radius;
                g = Math.floor(hue);
                f = hue - g;
                u = 255 * (1 - sat);
                v = 255 * (1 - sat * f);
                w = 255 * (1 - sat * (1 - f));
                pixels[i] = [255, v, u, u, w, 255, 255][g];
                pixels[i + 1] = [w, 255, 255, v, u, u, w][g];
                pixels[i + 2] = [u, u, w, 255, 255, v, u][g];
                pixels[i + 3] = 255;
            }
        }
    }

    context.putImageData(imageData, 0, 0);
    document.body.style.backgroundColor = 'white';
    document.body.style.margin = '0px';

    phantom.render('colorwheel.png');
    phantom.exit();
}

Beside the above example, there are few other things which you'll get in the upcoming PhantomJS 1.1 release, among others support for Unix shebang, file upload for form submission, disable/enable images loading and plugins, as well as support for QUnit integration.

PhantomJS: minimalistic headless WebKit-based JavaScript-driven tool

PhantomJS is a headless WebKit packaged as a JavaScript-driven tool. It can be used in command-line utilities which requires web stack, or even as the basis for testing rich web application. It uses WebKit in a headless mode, so you get access to the real native and fast implementation (not a simulated environment) of various standards such as DOM, CSS selector, Canvas, SVG, and many others.

The project page contains a bunch of examples, from easy ones to some more complicated uses. Feel free to contribute more examples!

Let's look at one of the examples, the page rasterizer (yes, it's only 16 lines!):

if (phantom.state.length === 0) {
    if (phantom.args.length !== 2) {
        console.log('Usage: rasterize.js URL filename');
        phantom.exit();
    } else {
        var address = phantom.args[0];
        phantom.state = 'rasterize';
        phantom.viewportSize = { width: 600, height: 600 };
        phantom.open(address);
    }
} else {
    var output = phantom.args[1];
    phantom.sleep(200);
    phantom.render(output);
    phantom.exit();
}

If I want to have the famous PostScript tiger from its SVG source, all I have to do is to run:

phantomjs rasterize.js http://ariya.github.com/svg/tiger.svg tiger.png

But static vector graphic is boring. Replacing the above with

phantomjs rasterize.js http://raphaeljs.com/polar-clock.html clock.png

gives me Polar Clock, one notable example from RaphaelJS.

Should you need to deal with JSONP, process XML, and integrate with YQL, that's all easily done. Again, refer to the various service integration examples. Let me show one example, which is actually my favorite:

if (phantom.state.length === 0) {
    var origin, dest;
    if (phantom.args.length < 2) {
        console.log('Usage: direction.js origin destination');
        console.log('Example: direction.js "San Diego" "Palo Alto"');
        phantom.exit(1);
    }
    origin = phantom.args[0];
    dest = phantom.args[1];
    phantom.state = origin + ' to ' + dest;
    phantom.open(encodeURI('http://maps.googleapis.com/maps/api/directions/xml?origin='
        + origin +  '&destination=' + dest + 
        '&units=imperial&mode=driving&sensor=false'));
} else {
    if (phantom.loadStatus === 'fail') {
        console.log('Unable to access network');
    } else {
        var steps;
        steps = phantom.content.match(/<html_instructions>(.*)<\/html_instructions>/ig);
        if (steps == null) {
            console.log('No data available for ' + phantom.state);
        } else {
            steps.forEach(function (ins) {
                ins = ins.replace(/\&lt;/ig, '<').replace(/\&gt;/ig, '>');
                ins = ins.replace(/\<div/ig, '\n<div');
                ins = ins.replace(/<.*?>/g, '');
                console.log(ins);
            });
        }
    }
    phantom.exit();
}

If I run it like the following:

phantomjs direction.js 'Redwood City' 'Sunnyvale'

what I got is the complete driving direction:

Head east on Broadway toward El Camino Real
Take the 1st left onto El Camino Real
Turn right at Whipple Ave
Slight right to merge onto US-101 S toward San Jose
Take exit 398B to merge onto CA-85 S toward Santa Cruz/Cupertino
Take exit 22A to merge onto CA-82 S/E El Camino Real toward Sunnyvale
Destination will be on the right

Map data ©2011 Google

Make sure you check out other examples, such as getting weather forecast conditions, finding pizza in New York, looking up approximate location based on IP address, pulling the list of seasonal food, displaying tweets, and many others.

Headless execution of any web content also enables fast unit testing. Obviously, the goal is not to replace comprehensive, cross-browser framework such as Selenium or Squish for Web. Rather, it serves a quick sanity check just before you check in some changes.

Since this can happen automatically and does not need to launch any browser, even better, you can hook the test so that it executes right before a commit and actually prevents the commit if any of the test fails. It is easily done using git via its hook support. This is something I have written at Sencha blog. It demonstrated precommit hook with Jasmine, but technically it can work with any test framework.

I have been working on and off on PhantomJS for the past few years. You may be already familiar with some of its inspiration (also involving headless WebKit): SVG rasterizer, page capture, visual Google, etc. Finally I managed to overcome my laziness, cleaned up the code, and published it for your pleasure. Obviously it's not a surprise if you find out that PhantomJS uses QtWebKit.

I got a few tasks for next PhantomJS version 1.1. You are encouraged to file bugs and feature requests in the said issue tracker.

Get it while it is hot!