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!

chunks inside PNG

Here is a few minutes of hack which would hopefully help someone else:

pngchunks logo.png
File size: 5967 byte(s)

Offset    Chunk    Size
      8    IHDR      13
     33    iCCP    2627
   2672    IDAT    3271
   5955    IEND       0

Useful to quickly find out if we can further strip unnecessary chunks from the PNG image. Or even as a warming up before you fire your favorite hex viewer/editor.

It's pure, stand-alone, self-contained C code (i.e. compile using gcc -o pngchunks pngchunks.c), available at the usual X2 repository, find it under graphics/pngchunks.

morphing clock revisited

If you can't see the clock below, visit the stand alone demo.

Technically, I had wanted to wait till it can display the actual time and perhaps ask some designer to polish it. But rather than keeping this lunch-break hack in a safe deposit box forever, let me just release this ugly clock transition (since everyone is on the animation frenzy). So far it works only if you use latest version of Safari, Chrome, Opera, Firefox. Canvas and/or VML fallback (which sadly will require JavaScript) for other browser are in the pipeline.

Basically it is another version of my previous morphing clock attempt (see the video). The principle is the same, except now I modified that C++ program to also output an HTML which renders the clock as above.

Also it morphs only once. Reload the page to enjoy the morphing once more. Maybe I'll find the time (in another lunch break) to toggle the two clock modes. Update: morphing from/to both analog and digital mode is implemented.

Like I said, it's a creepy, machine-generated, ugly looking clock. You've been warned, but feel free to write me anything (should you need to vent your anger).

yet another command-line JavaScript beautifier (based on V8)

While we're still on the topic of JavaScript, I took the afternoon break to create a command-line runner for jsbeautifier.org . In case you miss it, I did the similar thing using Qt Script module. This time however, the command-line tool uses and exploits Google V8 instead.

If you update your clone of js-beautify repository, check out the fresh v8 subdirectory. I also mirror the code in the usual X2 repository, under the javascript/jsbeautify8 subdirectory. Also, grok the included README.txt first.

Update: I added --overwrite option which (surprise!) will overwrite the original source file (and thus, use it with care). This is useful if you invoke the beautifier tool from your text editor. Nicolas also implemented various settings support so you can specify the indentation level, braces placement, etc.

This is probably the last thing the world needs now, but hey, it was a fun break.

color inversion for web pages

Something I worked on during my last few weeks with Qualcomm was color inversion for the web browser in Android. The patch was then integrated by Enrico (see the diff) because I switched job.

Later on this feature was also pulled into CyanogenMod. Thus, if you are running CyanogenMod 6 on your shiny Android device, you can try this feature already! In the web browser, just pick the Settings menu and then scroll a bit until you see a checkbox for Invert Color. You should get something like the captured screens below:

The idea behind this is to reduce the power consumption of Organic LED display, because on mostly-white web page, it hungrily grabs to 3x more power compared to LCD. This is similar to Jeff's trick of applying color filter in SurfaceFlinger.

Doing it at the user-space level gives one advantage: we can keep the embedded images non-inverted. Blindly inverting the entire screen would result in web pages look rather funky, especially those new sites with photos to accompany the articles. Of course, this hackish approach will not work 100%, (hint: double XOR?) since the web designer likely never intend the page to be color inverted. However it seems to work most of the time, at least with pages which do not have ueberartistic look-and-feel.

Faithful followers of my blog know that I already played with the color inversion ages ago, in the form of giving night mode appearance for QWebView. Thus, it happened that in one afternoon break I played with QtWebKit to do something similar to this selective color inversion.

Now, in the case of Android WebKit, the effect was rather easy to achieve. This is because Skia's SkCanvas is basically an interface which can be subclassed easily, while none of the functions in QPainter is virtual. The trick using Skia was to use a proxy canvas (a slight variation of Skia's built-in SkProxyCanvas) which I invented for this purpose but somehow also useful for another feature.

For QtWebKit however, we need to tweak it with some QPaintEngine voodoo. Check out the code at the usual X2 repository, find it under webkit/nightcapture (it still has some rooms for improvement, left as exercises for the adventurous readers). For simplicity, I made it as capturing tool so you need to pass a URL and the output filename. Unless you do something wrong, expect to get something like this:

The trick is the same as my approach for the Android patch: invert the colors of each image before drawing it, at the end invert the entire viewport. This seems like slow, but it's the best compromise I found out working with most sites. Note how we skip inverting any brush pixmap as usually brush is for the tiled background (and thus we want to keep it that way, i.e. not inverted). You can do some fancy magic with clipping and whatnot, but I doubt the end result is much better. Again, this whole stuff is a hack anyway and there will be always corner cases which will not work, no matter what approach you pick, thus there is no need to make it more complicated that it should be.

Just like they say, we code for life, i.e. the battery life.

the art of blurring the shadow

In the recent weeks, sporadically I have been working on QtWebKit to fix the missing blur support for Canvas and CSS shadow (see the tracking bug 34479). This brings some good memory; before I left Nokia, I was involved in prototyping the special effect stuff, both for the low-level (non-public) QPixmapFilter and the high-level QGraphicsEffect.

Usually blurring drop shadow for a shape is a very typical: grab the alpha channel of the shape, apply the blur filter, and finally tint it with the intended shadow color. The last step is trivial using the SourceIn composition mode. The blur filter is supposed to follow the SVG specification on feGaussianBlur. The said specification mentions one possible way to approximate the perfect Gaussian blur: three successive box blurs.

Since QPixmapFilter is private anyway and QGraphicsEffect is not suitable for this task, an attempt to implement what the specification outlines became my hobby for a few evenings. This is basically what emerges as the shadow blur implementation in QtWebKit. For the sake of code reuse, I pushed the implementation to the X2 repository under the graphics/shadowblur subdirectory. The shadowBlur() function itself is BSD licensed, there is a demo program included for your pleasure:

Performance-wise, the code is as satisfactory (for such a portable implementation). Another good approach is to use stack blur, adopted among others by AGG. KHTML notably uses stack blur for its Canvas shadow blur support. Exponential blur is known to be very fast, although quality-wise it deviates farther from a true Gaussian one. The portable, raster version of QGraphicsDropShadowEffect (via QPixmapFilter) is using this algorithm.

For this particular use-case, namely blurring the shadow (as opposed to generic blur filter), I'm surprised that the Gaussian blur approximation is not necessary slower than KHTML's stack blur approach or even QGraphicsDropShadowEffect's exponential blur. I did a quick benchmark, measuring the time spent creating the shadow for two images (horizontal 149x13 and vertical 13x149) for different radii (small 4px and medium 17px), on a Core i7 machine. The outcome is shown in the following bar chart. The result was from several runs, with the overall confidence level observed to make sure it was statistically sound. Still, take it with a pinch of salt.

With a very large blur radius, e.g. 50, stack blur performance deteriorates quickly, probably because the pre-loop initial setup. Exponential blur is pretty much radius-agnostic, although I can't find cases where it wins against my shadow blur code (which is BTW only 60 lines). Larger source images would highlight the performance difference even more. Maybe I am doing something wrong, or maybe that's how it is. In any case, I insert a low-priority entry in my (already infinite) TODO list: spend some quality evenings with callgrind and examine those blur implementations.

On mobile devices however the situation is reversed. The approximated Gaussian blur is consistently slower, around 10%, compared to exponential or stack blur, when tested on 600 MHz Cortex A8-powered Nokia N900. Due to slower memory speed and smaller cache, the repetitive memory access for the successive box blurs cancels its fast processing benefit. Hopefully the 1 GHz generation CPU (like in Nokia N8) and improved memory bus will eliminate this minor slow down.

Anyway, in all cases, just like Andreas mentioned, now you can enjoy the fancy Parcycle demo in its full glory:

Sencha Touch and N900

Being part of the awesome Sencha Team, I did shoot a quick attempt to run Sencha Touch, more precisely its Kitchen Sink demo, on Maemo-powered Nokia N900. Since Sencha Touch targets WebKit but Maemo default browser is Gecko/Firefox-based, I crafted a mini launcher which wraps Sencha Touch in QtWebKit. The screenshots below serve as the proof:

Most of the stuff works just fine. There are some minor issues and performance problems, but I worry not. With the amazing amount of optimizations Qt+Nokia put in place for Qt 4.7 and QtWebKit 2.x, writing applications for Maemo/MeeGo will be fun (again).

var Adam = new Child(Ariya);

> Adam.prototype
Human
> Adam.timestamp
1279148700
> Adam.length
50.17
> Adam.weight
3.4
> Adam.health
Checking.... Good
> Adam.mother.health
Checking... Good
> Adam.father.status
"Happy"

faster quaternion multiplication

Sweet memories, it was fun to derive it.

Faster here however must be taken with a grain of salt as the new code is not always guaranteed to be better pipelined.

And of course, it's trivial to beat this generic C code with architecture-specific hand-rolled assembly.

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).
    
    Callgrind shows that the function now takes 299 instructions instead of
    318 instructions, which is not a big win. However I assume the speed-up
    has a better effect for mobile CPU, where multiplications are more
    expensive.
    
    Reviewed-by: Rhys Weatherley

diff --git a/src/gui/math3d/qquaternion.h b/src/gui/math3d/qquaternion.h
index 55c871d..9a1b590 100644
--- a/src/gui/math3d/qquaternion.h
+++ b/src/gui/math3d/qquaternion.h
@@ -198,24 +198,17 @@ inline QQuaternion &QQuaternion::operator*=(qreal factor)
 
 inline const QQuaternion operator*(const QQuaternion &q1, const QQuaternion& q2)
 {
-    // Algorithm from:
-    // http://www.j3d.org/matrix_faq/matrfaq_latest.html#Q53
-    float x = q1.wp * q2.xp +
-                    q1.xp * q2.wp +
-                    q1.yp * q2.zp -
-                    q1.zp * q2.yp;
-    float y = q1.wp * q2.yp +
-                    q1.yp * q2.wp +
-                    q1.zp * q2.xp -
-                    q1.xp * q2.zp;
-    float z = q1.wp * q2.zp +
-                    q1.zp * q2.wp +
-                    q1.xp * q2.yp -
-                    q1.yp * q2.xp;
-    float w = q1.wp * q2.wp -
-                    q1.xp * q2.xp -
-                    q1.yp * q2.yp -
-                    q1.zp * q2.zp;
+    float ww = (q1.zp + q1.xp) * (q2.xp + q2.yp);
+    float yy = (q1.wp - q1.yp) * (q2.wp + q2.zp);
+    float zz = (q1.wp + q1.yp) * (q2.wp - q2.zp);
+    float xx = ww + yy + zz;
+    float qq = 0.5 * (xx + (q1.zp - q1.xp) * (q2.xp - q2.yp));
+
+    float w = qq - ww + (q1.zp - q1.yp) * (q2.yp - q2.zp);
+    float x = qq - xx + (q1.xp + q1.wp) * (q2.xp + q2.wp);
+    float y = qq - yy + (q1.wp - q1.xp) * (q2.yp + q2.zp);
+    float z = qq - zz + (q1.zp + q1.yp) * (q2.wp - q2.xp);
+
     return QQuaternion(w, x, y, z, 1);
 }

proxy server with filtering feature

Beside exploring San Diego, I had done some coding intermittently only. My apology if I do not update X2 with fresh new examples often enough.

Having said that, here is one network-related example: a minor tweak to the previous example of Qt-based proxy server. Basically it adds a minimalistic URL filtering support, in the form of blacklisting certain URLs which start with some predefined strings. The code is available in the usual place, X2 repository, under the directory network/filterproxy.

While major browsers support some variants of content blocking, be it via an extension like AdBlock or as a feature built-in into the browser itself, this new filterproxy should work with any browser that supports proxy. Alas, I did not bother to implement an AdBlock-compatible rule system because it would complicate the code. Again, consider this is a proof of concept only. A challenging exercise would be to fully support the most known subscription filters.

It is unheard that content filtering can dramatically improve your browsing experience. Because it cuts the bandwidth usage, it does translate to lower cost for those who are not lucky enough to get unlimited data plan. But most importantly, throwing garbage out of the web pages definitely speeds up the page loading. For this filterproxy example, I did a very unscientific benchmark and test it with Detik.com news site (now you get the answer why the included blacklist.txt contains only some basic advertisement-laden sites). The screenshots below (click to enlarge) show the unfiltered version (left) and the filtered version (right). Notice also the whopping 40% of bandwith saving!

My promise was to post two variations from that simple proxy example. This counts as one of them, and when the time allows me to clean-up to the other, you'll know it. Stay tuned and happy proxying!

QNetworkAccessManager, tracenet, Speed Tracer

Just like Rich's trick with QNetworkAccessManager, I have done something similar which I call tracenet (around 150 lines of code). Though I have committed this example to X2 some time ago, only now I have the chance to blog about it.

The idea is to subclass QNetworkAccessManager and reimplement its createRequest method so that we can keep track all the network responses and replies. This is useful for your network-based application, or even for e.g. QtWebKit. As a matter of fact, the tracenet example captures the network traffic as you load a URL into a web page.

Now, the next step is how to visualize the result. While it's certainly possible to craft a Qt-based fancy GUI for this (maybe using Qt Quick?), let's think outside the box. Unless you live in a cave, I am sure you are aware that there is this nice tool called Speed Tracer, part of GWT, an extension for Google Chrome or Chromium. For this purpose, we won't use the live profiling feature of Speed Tracer, but rather its ability to visualize network requests and replies (with nice timeline and so on). All we have to do is to carefully spit some JSON-formatted data that match the Speed Tracer data dump format. And that is exactly what tracenet does!

The screenshot below gives an exemplary result from running tracenet on my Nokia N900 when it accesses New York Times front website, a notoriously complicated web page. All I did was to execute "tracenet > nytimes.htm", transfer back the HTML file to the laptop and then open it with Chromium on OpenSUSE, click on "Network (resources)" line, and voila! You can click on each entry to get detailed timing info, use zoom in/out, and many other features of Speed Tracer. Refer to some tutorials if you are new to Speed Tracer.

If you want some follow-up and challenging exercise, try to split Speed Tracer code so that the pure GWT-part can run on any browser. Then you can just package it with QtWebKit and use it to show the outcome of all your network sniffing. Have fun!

simple http proxy server in 100 lines

I guess a simple proxy server should have been an example in Qt Network module. What I mean of course a real proxy server based on Qt, not about using a proxy server via QNetworkProxy class. After all, there are other more complex examples like the torrent client and Google suggest (yeah, blame me for the latter). As a matter of fact, there are e.g. a gazillion proxy servers written in Python.

Look no more. I posted an example in the X2 repository, under the directory network/webproxy. The code is written for clarity and not for performance. In fact, fancy error handling is even omitted (minimalism rulez!). There is no support for pipelining, or in-memory cache, or per-connection thread, or even secure connection via https. I leave them as exercises for the curious readers.

If we focus on things which work, here they are: asynchronous socket handling, different request methods (GET/PUT/POST/HEAD), persistent connection aka keep alive, and even Flash and HTML 5 video streaming. Yes, you can still watch YouTube or Vimeo if you hook your browser into this little proxy. For a few hours of hacking and 92 lines of code (as reported by sloccount) and certain ways to abuse QObject, I could not be more happier.

There will be two other offspring examples based on this one. So stay tuned. Meanwhile let's just hope nobody would ask me for a colorful UML diagram for this snippet...

PS: Special thanks to Jan Erik for his feedback and review.

morphing clock

As I promised before, here is a fresh X2 example. Those who attended Bossa Conference 10 and followed my talk are lucky to have seen it for the first time there. In fact, this example is ridiculously simple that I am not surprised at all if somebody has done this ages ago.

Let's start with a screen capture, or two:

Basically the above shows an analog and digital clock running on my Nokia N900, hardly a shock. However, the fun part is when you switch the clock from analog to digital and vice versa. Check out this video, or watch directly on YouTube, courtesy of Signor Portale from Nokia/Qt, showing the morphing on Nokia 5800:

The trick is simple. Actually it's not even generic enough, meaning that you can't morph from an arbitrary path to another arbitrary path. However, for this clock use-case, the gross approximation is good enough. First, we need to convert the path into a polygon, which is done easily via QPainterPath::toFillPolygon() function. Then any line segment in the polygon longer than a certain tolerance is further split into smaller segments. As I claimed above, the result is not perfect, i.e. it does not approximate the original path into line segments with equal length. But hey, it is good enough for this animation purpose (unless your user has ueberhuman eyes).

The target path needs to be sliced into segments as well. Since we have only two types, circle (for the analog clock frame) and solid block (for the hour and minute hands), it is easier to special-case both. The secret is to have the same number of segments as the source path. The following figure shows the digit '7' and a circle, each splitted to 28 line segments. Small dots indicate the start and end points of those segments. The animation is now a matter of doing tweening, or linear interpolation, between each segment.

The flaw of this trick is when the source path contains holes inside it, e.g. for digits like 0, 4, 6, 8, and 9. Again, we are cheating here for the sake of keeping the code simple, so I leave the code as it is. Doing a more advanced, better handling for those cases is left as a motivational exercise for the perfectionist readers. Another bonus puzzle: find out why 503 ms is the morphing time (hint: find the same number in Qt source tree).

The code is in the X2 repository, check the sub-directory widget/morphingclock. You need Qt 4.5 or later. It is not long at all (surprise!), sloccount reports 191 lines of code. A morphing-clock plasmoid is also underway, just be patient.

For the sake of completeness, let me mentioned Dali Clock (even in Canvas and JavaScript version) from the famous Jamie Zawinski (jwz). It is similar, however Dali Clock just morphs the digits of the digital clock.

Also, if you just prefer a normal (but old-fashioned!) digital clock with the flipping effect, check the digiflip example I did back then. You already have it if you install Qt 4.6 for Symbian.

Last but not least, I'd like to mention my "special thanks to Delta Airlines for such a long (but safe) flight to Brazil so I had the chance to write this example while I was bored", but then I was told by the Trolls that this kind of intro line can't be funny anymore.

graphics dojo in 2009: wrap-up

That is, 2009 is coming to its end. Some parts in Central Europe already enjoy the snow although Oslo still has a touch of autumn feeling.

Here is a list of biweekly Graphics Dojo examples that I managed to pull off this year. Most of them are available for Qt/C++ and PyQt.

Note that although the examples are categorized (for your convenience), often it does not strictly belong to one category, e.g. night mode is both a graphics and WebKit example. Also, all S60 examples are designed with S60 mind but they still run well on the desktop, too.

S60

• Wolfenstein-like ray casting in your pocket.
• Maps solution using OpenStreetMap, of course running on the phone, too.
• Flight tracking utility, useful to check the status and time.
• Weather info on your pocket.
• Still about kinetic scrolling, now with a Flickable interface that works smooth also on a phone.
• Suitable for your S60 phone: flipping digital clock.

Graphics

• Reborn/recycled parallax effect for the home screen.
• Simplified magnifying glass trick.
• A simple trick to get the night-mode vision, just like in some navigation system.
• DragMove charm to allow widget moving by dragging
• simple timeline demo along with a custom S-shape curve
• thumbnail preview via a fast cheat-scaling trick.
• cheap trick to half-scale ARGB32 image very fast.

WebKit

• Doing a talk? Use a presentation tool purely based on web technologies.
• Magnifying glass trick with Google Maps.
• Make your QWebView transparent to achieve some interesting effect.
• snap-scrolling in QWebView, useful for small-screen browser.
• Need to do a visual web scraping? This little weather applet, which scraps the Google-provided page, might be a good start.
• Use jQuery, enjoy selector goodies with QtWebKit
• simple example to integrate Google Suggest
• WYSIWYG HTML Editor using QtWebKit
• Google chat client made in 15 minutes
• web capture, a tool to take a snapshot of web pages.

JavaScript

• Run Monster Evolution demo with Qt and V8 (the JavaScript engine behind Google Chrome)
• Still about Monster, but now with JavaScriptCore of QtWebKit
• Or, just run this cool Monster Evolution demo with QtScript
• simple bar chart using QtScript.

Need more goodies? See also last year (2008) graphics dojo wrap-up.

Until next time.

kinetic scrolling: the state machine

Some of the slides from last Maemo Summit in Amsterdam have been made online. Here is the one from the Cross Platform with Qt talk that I held. It does not give much, though, since mostly what counts is the real live demo. Let us hope that at some point in time, the recorded videos will be online as well. Of course, there are also other interesting slides such as Harmattan highlights and its architecture, Web Runtime, Quake3, and many others.

Cross Platform Qt

View more documents from Nokia, Qt Development Frameworks.

While I am there, if you check the slides from my talk above, page 9 shows the secret behind kinetic scrolling code, which I featured before as Flick Charm or Flickable interface. Or, in another version as follows (click to enlarge):

Of course, it is the simplified version and ignore some details, but that should be a good start to really digest the code. Since it was hacked in the old 4.4/4.5 time, I did not have the luxury of using the new state machine framework in Qt 4.6. As an exercise for you, the brave readers, convert the code to use the framework. In addition, it does not support yet bouncing-on-edge feature, something which can serve as another exercise, too.

Have fun with scrolling :)

Chromium on OpenSUSE

Though Google Chrome for Linux is not yet officially announced, people have been working to make Chromium, the open-source version thereof, available for different popular distributions. I wrote before about CrossOver Chromium, but not only this is just a hack, it is also not up-to-date at all. The easiest way for OpenSUSE 11.1 users is to use the package from Contrib.

Though for veteran OpenSUSE fans, the steps to install Chromium are obvious, here I write down the idiot-proof version. Go to http://software.opensuse.org/search, type Chromium and click the Search button, wait for a moment, find the entry from openSUSE:Factory:Contrib/openSUSE_11.1, then well, click on the 1-Click Install button there. Follow the usual installation guides (mostly just agreeing and confirming some stuff), then in few minutes you will get:

Who says installing software in Linux is difficult? :)

Qt Developer Days 2009 - Live

Like I mentioned before, now I am in Munich for Qt Developer Days 2009. The training sessions started yesterday already, the plenary was initiated this morning as we had the keynotes from Sebastian, Lars, Walter, and Matthias. We are now in the middle of lunch break, the technical track will start very soon.

This is the biggest Qt Developer Days so far, we have over 650 participants (last year it was only around 400). Can you imagine now what happens during the lunch break? Hint: the queue. As a nice touch, we even show a coffee machine running Qt:

I will have two talks tomorrow (Day 2) for the Innovate track: Special FX with Graphics View and Copy Your Favourite Nokia App with Qt. See you there!

SVG: parsing and content optimization

A few weeks ago, just for a change (between the usual QtWebKit bug-fixing and patches juggling), I did take a look at our QtSvg module. According to some internal reports, QtSvg is not fast enough when parsing a large and complicated SVG. Of course, slow is relative, slow to what. And arguably, parsing time is not as important as rendering time. But if you stash your user-interface elements in some sort of SVG theme, loading time becomes a factor (caching the pixmaps whenever possible also helps). Of course, reduced size served in a web server can decrease the bandwidth as well (think of all the SVGs in Wikipedia).

Still, I decided to have a look, just in case there are low-hanging fruits I can grab. And I was right, far from being an SVG expert, with just two days of work I managed to squeeze its performance a bit, which you'd enjoy already in the recent 4.6 preview.

The chart above - shorter is better - represents the comparison of the time spent in QSvgRenderer::load(), measured using CPU tick counter (in millions of ticks), comparing Qt 4.5 and 4.6. I also tested some other files as well, see the bigger bar charts. In all measurements, the 95% confidence intervals were well below 1%. In-house Theme refers to an internal SVG that unfortunately I can't share. Tiger is the SVG version of the famous head in PostScript (taken from GNU GhostScript), something I have shown before. Imperial Coat of Arms of France is another complex SVG, from Wikipedia Commons. World Map is the public domain blank grayscale world map from Wikipedia. There are a bunch of other test files I used, they mostly show the same improvements.

As you can see, Qt 4.6 would enjoy a bit of speed-up (in some cases up to 1.4x) when loading and parsing SVG.

However, I did not stop there. For the fun of it, I quickly hacked a Qt-based, command line SVG minifier, dubbed SVGMin. More about it can be read in the detailed Quick Start, but basically it tries to eliminate redundant garbages which have no effect whatsoever in the final rendering.

What follows is the chart showing the same type of measurement but I added the result with the minified SVG (see also the full comparison chart). The result should speak for itself:

I plan some more improvements to the SVG minifier, for example collapsing a single grouped element (<g><path ...></g> makes no sense), group a bunch of nodes with similar attributes (no need to duplicate the same fill colors over 100 circles), remove useless attributes (why there is fill-* for fill:none?), and many others. Hold your breath.

wanna curve away? it's such a perfect day

If you were at my Special F/X talk, Desktop Summit in Las Palmas, or if you watched the recorded video (135 MB Ogg), you might notice the tongue-in-cheek gratitudes to Lufthansa dan SpanAir I expressed at the beginning of the talk. The story goes as follows. As all of us, the Trolls, left Oslo to fly to Las Palmas, our flight got delayed twice, in Oslo (by Lufthansa) and Madrid (by SpanAir). Like every other dedicated (read: foolish) hackers, I took advantage of the delay to fulfill my dream (read: obsession): writing my own presentation tool. Hence, the special thanks.

Of course, like every other dedicated hackers, I cheated (after all, great artists steal). Inspired from the previous discussion with Simon (and Holger), I just took S5 and wrapped it with QtWebKit. The result is something I called s5runner. The 200-lines Qt/C++ code (and PyQt, thanks to David) is best demonstrated by watching the following short screencast:

Few extra features added on top S5 are screen blanking (white or black), night mode (just for the fun of it), syntax highlighting (useful for code snippet), countdown timer (because my laptop has 100x computing power vs my wristwatch), and (my favorite) live editing.

I will definitely reuse this for my upcoming talks.

(again) the map of my world gets smaller as I sit here

I always wanted to help Marble, but I am guilty because until now I can't afford any time to play with it. All these years, I used to compile bleeding-edge Marble from time and time, use it, and basically that is it. Although since a long time ago I promised Torsten that I was willing to help Marble, actually only right after Gran Canaria Desktop Summit finally I devoted some time to study its code. The three of us, Torsten, Andrew and I also had a short but fascinating discussion during the summit.

Now, I still don't manage to contribute anything to Marble yet, but I already have something in my pipeline. You will likely hear from me in the coming weeks, so stay tuned.

Since I reckon I enter the wonderful territory of mapping world, I thought, well, let's familiarize myself a bit with the technology. I took a look at the interesting experimental Google Maps API v3 (which BTW does not require an API key). Using QtWebKit, I wrote a simple 300-lines example that shows a magnifying glass over the map (see the screencast). Of course, the area under is the zoomed version of the map.

Since I am flirting with Qt for S60 these days, I thought about bringing that example to the phone. However, instead of relying on Google Maps, I decided to leave the dark side and jumped to use OpenStreetMap instead. The result is effectively an example of how to render the tiles from OpenStreetMap using Qt, which also runs on S60. It does even have the night-mode feature.

Video, you asked? Thanks to Alessandro, here is the 52-second videocast that demonstrates it (or watch on YouTube), running on Nokia 5800: