NV path rendering

A while ago NVIDIA released drivers with their NV_path_rendering extension. GL_NV_path_rendering is a relatively new OpenGL extension which allows rendering of stroked and filled paths on the GPU.

 I've heard about it before but lately I've been too busy with other stuff to look at, well, anything.

 I've decided to spend a few seconds looking at the videos NVIDIA posted on their site. They were comparing the NV_path_rendering, Skia, Cairo and Qt. Pretty neat. Some of the demos were using huge paths, clipped by another weird path and using perspective transforms. Qt was very slow. It was time for me to abandon my dream of teaching my imaginary hamster how to drive a stick shift and once again look at path rendering.

You see, I wrote the path rendering code so many times that one of my favorite pastimes was creating ridicules paths that no one would ever think about rendering and seeing how fast I could render them. Qt's OpenGL code was always unbelievably good at rendering paths no one would ever render. Clearly these people were trying to outcrazy me.

Fortunately there's an SDK posted on the NVIDIA site and it's really well done. It even compiles and works on GNU/Linux. Probably the best demo code for a new extension that I've ever seen. The extension itself is very well done as well. It's very robust, ultimately though it's the implementation that I care about. I have just one workstation with an NVIDIA card in it, a measly Quadro 600, running on a dual processor xeon e5405, but it was enough to play with it.

 The parts using Qt were using the raster engine though. I've looked at the code and decided to write something that would render the same thing but using just Qt. The results were a little surprising. Qt OpenGL could render tiger.svg scaling and rotating it at about 270fps, while the NV_path_rendering was running at about 72fps. Here's both of them running side by side:

 (numbers lower for both on account of them running at the same time of course). As you can see Qt is almost 4x faster. I've figured it might be related to the different SVG implementations and rendering techniques used, so I quickly hacked the demo NVIDIA posted to open a brand new window (you need to click on it to start rendering) and render to QGLPixelBuffer but using the same SVG and rendering code as their NV_path_rendering demo code. The results were basically the same.

I posted the code for the Qt demo and the patch to nvpr_svg on github: https://github.com/zackr/qt_svg

The patch is larger than it should be because it also changed the file encoding on the saved files from DOS to Unix but you shouldn't have any issues applying it.

So from a quick glance it doesn't seem like there are any performance benefits to using NV_path_rendering, in fact Qt would likely be quite a bit slower with it. Having said that NVIDIA's implementation looks very robust and a lot more numerically stable. I've spent a little bit of time looking at the individual pixels and came away very impressed.

In general the extension is in a little bit of a weird situation. On one hand, unlike OpenVG which creates a whole new API, it's the proper way of introducing GPU path rendering, on the other hand pretty much every vector graphics toolkit out there already implements GPU based path rendering. Obviously the implementations differ and some might profit from the extension but for Qt the question is whether that quality matters more than the performance. Specifically whether the quality improves enough to justify the performance hit.

I think the extension's success will largely depend on whether it's promoted to, at least an EXT or, ideally an ARB, meaning all the drivers support it. Using it would make the implementations of path rendering in toolkits/vector graphics libs a lot simpler and give driver developer a central place to optimize a pretty crucial  part of the modern graphics stack. Unfortunately if you still need to maintain the non NV_path_rendering paths then it doesn't make a whole lot of sense. Mesa3D implementation would be trivial simply because I've already implemented path rendering for OpenVG using the Gallium3D interface, so it'd be a matter of moving that code but I'm just not sure if anyone will be actually using this extension. All in all, it's a very well done extension but it might be a little too late.

2D musings

If you've been following graphics developments in the 2D world over the last few years you've probably seen a number of blogs and articles complaining about performance. In particular about how slow 2D is on GPUs. Have you ever wondered why it's possible to make this completely smooth but your desktop still sometimes feels sluggish?

Bad model

For some weird reason ("neglect" being one of them) 2D rendering model hasn't evolved at all in the last few years. That is if it has evolved at all since the very first "draw line" became a function call. Draw line, draw rectangle, draw image, blit this, were simply joined by fill path, stroke path, few extra composition modes and such. At its very core the model remained the same though, meaning lots of calls to draw an equally large number of small primitives.

This worked well because technically zero, or almost zero, setup code was necessary to start rendering. Then GPUs became prevalent and they could do amazing things but to get them to do anything you had to upload the data and the commands that would tell them what to do. With time more and more data had to be sent to the GPU to describe the increasingly complex and larger scenes. It made sense to optimize the process of uploads (I keep calling them "uploads" but "GPU downloads" is closer to the true meaning) by allowing to upload an entire resource once and then refer to it via a handle. Buffers, shaders, addition of new shading stages (tessellation, geometry) all meant to reduce the size of data that had to be uploaded to the GPU before every rendering.

At least for games and well designed 3D software. 2D stuck to its old model of "make GPU download everything on every draw request". It worked ok because most of the user interface was static and rather boring so the performance was never much of an issue. Plus in many cases the huge setup costs are offset by the fact that the Graphics Processing Units are really good at processing graphics.

Each application is composed of multiple widgets each widget draws itself using multiple primitives (pixmaps, rectangles, lines, paths) and each primitive needs to first upload the data needed by the GPU to render it. It's like that because from the 2D api perspective there's no object persistence. The api has no idea that you keep re-rendering the same button over and over again. All the api sees is another "draw rectangle" or "draw path" call which it will complete.

On each frame the same data is being copied to the GPU over and over again. It's not very efficient, is it? There's a limited number of optimizations you can do in this model. Some of the more obvious ones include:

adding unique identifiers to the pixmaps/surfaces and using those as identifiers as keys in a texture cache which allows you to create a texture for every pixmap/surface only once,

collecting data from each draw call in a temporary buffer and copying it all at once (e.g. in SkOSWindow::afterChildren, QWindowSurface::endPaint or such),

creating a shader cache for different types of fills and composition modes

But the real problem is that you keep making the GPU download the same data every frame and unfortunately that is really hard to fix in this model.

Fixing the model

It all boils down to creating some kind of a store where lifetime of an object/model is known. This way the scene knows exactly what objects are being rendered and before rendering begins it can initialize and upload all the data the items need to be renderer. Then rendering is just that - rendering. Data transfers are limited to object addition/removal or significant changes to their properties and then further limited by the fact that a lot of the state can always be reused. Note that trivial things like changing the texture (e.g. on hover/push) don't require any additional transfers and things like translations can be limited to just two floats (translation in x and y) and they're usually shared for multiple primitives (e.g. in a pushbutton it would be used by the background texture and the label texture/glyphs)

It would seem like the addition of QGraphicsView was a good time to change the 2D model, but that wasn't really possible because people like their QPainter. No one likes when a tool they have been using for a while and are fairly familiar with is suddenly taken away. Completely changing a model required a more drastic move.

QML and scene-graph

QML fundamentally changes the way we create interfaces and it's very neat. From the api perspective it's not much different from JavaFX and one could argue which one is neater/better but QML allows us to almost completely get rid of the old 2D rendering model and that's why I love it! A side-effect of moving to QML is likely the most significant change we've done to accelerated 2D in a long time. The new Qt scene graph is a very important project that can make a huge difference to the performance, look and feel of 2D interfaces.

Give it a try. If you don't have OpenGL working, no worries it will work fine with Mesa3D on top of llvmpipe.

A nice project would be doing the same in web engines. We have all the info there but we decompose it into the draw line, draw path, draw rectangle, draw image calls. Short of the canvas object which needs the old style painters, everything is there to make accelerated web engines a lot better at rendering the content.

Geometry Processing - A love story

It's still early in the year but I feel like this is the favorite for the "best computer science related blog title of 2010". I'd include 2009 in that as well, but realistically speaking I probably wrote something equally stupid last year and I don't have the kind of time required to read what I write.

Last week I've merged the new geometry processing pipeline and hooked it into our new software driver, llvmpipe. It actually went smoother than I thought it would, i.e. it just worked. I celebrated by visiting ER, a harsh reminder that my lasting fascination with martial arts will be the end of me (it will pay dividends once llvmpipe becomes self-aware though).

The codepaths are part of the Gallium3D Draw module. It's fairly simple once you get to it. At a draw call we generate the optimal vertex pipeline for the currently set state. LLVM makes this stuff a lot easier. First of all we get the human-readable LLVM IR which is a lot easier than assembly to go over if something goes wrong. Running LLVM optimization passes over a fairly significant amount of code is a lot easier than having to hand-optimize assembly code-generation. Part of it is that geometry processing is composed of a few fairly distinct phases (e.g. fetch, shade, clip, assemble, emit) and given that they all can and will change depending on the currently set state makes it difficult to code-generate optimal code by hand. That is unless you have a compiler framework like LLVM. Then you don't care and hope LLVM will bail you out in cases where you end up doing something stupid for the sake of code-simplicity.

A good example of that is our usage of alloca's for all variables. Initially all variables were in registers but I switched the code to use alloca's for a very simple reason: doing flow control in SOA mode when everything was in registers was tough, it meant keeping track of the PHI nodes. Not to mention that we had no good way of doing indirect addressing in that scheme. Using alloca's makes our code a lot simpler. In the end, thanks to LLVM optimization passes (mem2reg in this case), virtually every usage of allocas is eliminated and replaced with direct register access.

Anyway, with the new geometry paths the improvements are quite substantial. For vertex processing dominated tests (like geartrain which went from 35fps to 110fps) the improvements are between 2x to about 6x, for cases which are dominated by fragment processing it's obviously a lot less (e.g. openarena went from about 25fps to about 32fps). All in all llvmpipe is looking real good.

The software renderer

There's a number of great software renderers out there. SwiftShader and DirectX WARP being the two widely known ones. Unfortunately GNU/Linux, and Free Software in general, didn't have a modern software renderer. That's about to change thanks to a project started by José Fonseca. The project is known as the llvmpipe (obviously a development name). José decided that the way forward is writing a driver for Gallium which would code-generate at run-time the rendering paths from the currently set state. LLVM is used to code-generate and optimize the code.

Besides the idea itself, my favorite part of the driver is the software rasterizer. Keith Whitwell, Brian Paul and José implemented a threaded, tiled rasterizer which performs very nicely and scales pretty well with the number of cores. I'm sure one of them will write more about it when they'll have a bit of spare time.

Currently the entire fragment pipeline is code-generated. Over the last two weeks I've been implementing the vertex pipeline, which I'm hoping to merge soon (hence the light smile). Code generating the entire vertex pipeline isn't exactly trivial, but one can divide it into individual pieces and that makes it a bit easier. Start with the vertex shader, then go back and do the fetch and translate, then again move forward and do the emit, then go back and do the viewport transformations and clipping and so on, finally combine all the pieces together.

In between working on the vertex pipeline I've been filling in some missing pieces in the shader compilation. In particular the control-flow. We use the SOA layout which always make control flow a bit tricky. I've just committed support for loops and the only thing left is support for subroutines in shaders so I think we're in a pretty good shape. We can't rock the speedos quite yet, but we're getting there. It's my new measurment for software quality - could it pull off the speedos look? There's few things on this world that can.

Keeping in mind that we haven't even started optimizing it yet, as we're still implementing features, the driver, on my Xeon E5405 runs the anholt.dm_68 OpenArena demo at 25fps (albeit with some artifacts) which is quite frankly pretty impressive, especially if you compare it to the old Mesa3D software renderer that runs the same demo, on the same machine at 3.5 fps.

Accelerating X with Gallium

Spring is coming. I'm certain of it because I know for a fact that it's not Spring right now and seasons have a tendency to wrap around. Obviously that means I need to work a bit on the acceleration code for X11. It's just like going to a doctor, sure, it sucks, but at the back of your mind you know you need to do it.

So what's different about this code? Well, it's not an acceleration architecture. We're reusing Exa. It's the implementation.

Currently if you want to accelerate X11, or more precisely Xrender, you implement some acceleration architecture in your X11 driver. It may be Exa, Uxa, Xaa or something else (surely also with an X and A in the name because that seems to be a requirement here). Xrender is a bit too complicated for any 2D engine out there, which means that any code which accelerates Xrender will use the same paths OpenGL acceleration does. In turn this means that if we had an interface which exposed how hardware works we could put OpenGL and Xrender acceleration on top of the same driver. One driver, accelerating multiple APIs.

That's exactly what Gallium is all about so it shouldn't be a big surprise that this is what we're doing. We're simply writing an Xorg state tracker for Gallium in which Exa is implemented through the Gallium interface.

So with a Gallium driver, besides OpenGL, OpenGL ES and OpenVG you'll get X11 acceleration. I'm specifically saying here X11 because after implementing Exa we'll move to accelerating Xv, which will give us a nice set of ops which are accelerated in a typical X application.

More 2D in KDE

An interesting question is: if the raster engine is faster at gross majority of graphics and Qt X11 engine falls back on quite a few features anyway why shouldn't we make raster the default until OpenGL implementations/engine are stable enough.

There are two technical reasons for that. Actually that's not quite true, there's more but these two are the ones that will bother a lot of people.

The first is that we'd kill KDE performance over network. So everyone who uses X/KDE over network would suddenly realize that their setup became unusable. Their sessions would suddenly send images for absolutely everything all the time... As you can imagine institutions/schools/companies who use KDE exactly in this way wouldn't be particularly impressed if suddenly updating their installations would render them unusable.

The second reason is that I kinda like being able to read and sometimes even write text. Text tends to be pretty helpful during the process of reading. Especially things like emails and web browsing get a lot easier with text. I think a lot of people shares that opinion with me. To render text we need fonts, in turn those are composed of glyphs. To make text rendering efficient, we need to cache the glyphs. When running with the X11 engine we render the text using Xrender, which means that there's a central process that can technically manage all the glyphs used by applications running on a desktop. That process is the Xserver. With the raster engine we take Xserver out of the equation and suddenly every single application on the desktop needs to cache the glyphs for all the fonts they're using. This implies that every application suddenly uses megs and megs of extra memory. They all need to individually cache all the glyphs even if all of them use the same font. It tends to work ok for languages with a few glyphs e.g. 40+ for english (26 letters + 10 digits + a few punctuation marks). It doesn't work at all for languages with more. So unless it will be decided that KDE can only be used by people with languages whose alphabets contain about 30 letters or less, then I'd hold off with making raster engine the default.

While the latter problem could be solved with some clever shared memory usage or forcing Xrender on top of raster engine (actually I shouldn't state that as a fact, I haven't looked at font rendering in raster engine in a while and maybe that was implemented lately), it's worth noting that X11 engine is simply fast enough to not bother over a few frames in this way or another. Those few frames that you'd gain would mean unusable KDE for others.

And if you think that neither of the above two points bothers you and you'd still want to use raster engine by default you'll have to understand that I just won't post instructions on how to do that here. If you're a developer, you already know how to do it and if not there are trivial ways of finding that out from the Qt sources. If you're not a developer then you really should stick globally to the defaults and can simply test the applications with the -graphicssystem switches.

2D in KDE

So it seems a lot of people is wondering about this. By this I mean why dwarfs always have beards. Underground big ears would be probably a better evolutionary trait, but elfs got dibs on those.

Qt, and therefore KDE, deals with 3 predominant ways of rendering graphics. I don't feel like bothering with transitions today, so find your own way from beards and dwarfs to Qt/KDE graphics. Those three ways are:

• On the CPU with no help from the GPU using the raster engine
• Using X11/Xrender with the X11 engine
• Using OpenGL with the OpenGL engine

There's a couple of ways in which the decision about which one of those engines is being used is made.

First there's the default global engine. This is what you get when you open a QPainter on a QWidget and its derivatives. So whenever you have code like

void MyWidget::paintEvent(QPaintEvent *)
{
QPainter p(this);
...
}

you know the default engine is being used. The rules for that are as follows:

• GNU/Linux : X11 engine is being used
• Windows : Raster engine is being used
• Application has been started with -graphicssystem= option :
  
  • -graphicssystem=native the rules above apply
  • -graphicssystem=raster the raster engine is being used by default
  • -graphicssystem=opengl the OpenGL engine is being used by default

Furthermore depending on which QPaintDevice is being used, different engines will be selected. The rules for that are as follows:

• QWidget the default engine is being used (picked as described above)
• QPixmap the default engine is being used (picked as described above)
• QImage the raster engine is being used (always, it doesn't matter what engine has been selected as the default)
• QGLWidget, QGLFramebufferObject, QGLPixelBuffer the OpenGL engine is being used (always, it doesn't matter what engine has been selected as the default)

Now here's where things get tricky: if the engine doesn't support certain features it will have to fallback to one engine that is sure to work on all platforms and have all the features required by the QPainter api - that is the raster engine. This was done to assure that all engines have the same feature set.

While OpenGL engine should in general never fallback, that is not the case for X11 and there are fallbacks. One of the biggest immediate optimizations you can do to make your application run faster is to assure that you don't have fallbacks. A good way to check for that is to export QT_PAINT_FALLBACK_OVERLAY and run your application against a debug build of Qt, this way the region which caused a fallback will be highlighted (the other method is to gdb break in QPainter::draw_helper). Unfortunately this will only detect fallbacks in Qt.

All of those engines also use drastically different methods of rendering primitives.
The raster engine rasterizes primitives directly.
The X11 engine tessellates primitives into trapezoids, that's because Xrender composites trapezoids.
The GL engine either uses the stencil method (described in this blog a long time ago) or shaders to decompose the primitives and the rest is handled by the normal GL rasterization rules.

Tessellation is a fairly complicated process (also described a long ago in this blog). To handle degenerate cases the first step of this algorithm is to find intersections of the primitive. In the simplest form think about rendering figure 8. There's no way of testing whether the given primitive is self-intersecting without actually running the algorithm.
To render with anti-aliasing on the X11 engine we have to tessellate. We have to tessellate because Xrender requires trapezoids to render anti-aliased primitives. So if the X11 engine is being used and the rendering is anti-aliased whether you're rendering a line, heart or a moose we have to tessellate.

Someone was worried that it's a O(n^2) process which is of course completely incorrect. We're not using a brute force algorithm here. The process is obviously O(nlogn). O(nlogn) complexity on the cpu side is something that both the raster and X11 engines need to deal with. The question is what happens next and what happens in the subsequent calls.

While the raster engine can deal with all of it while rasterizing, the X11 engine can't. It has to tessellate, send the results to the server and hope for the best. If the X11 driver doesn't implement composition of trapezoids (which realistically speaking most of them doesn't) this operation is done by Pixman. In the raster engine the sheer spatial locality almost forces better cache utilization than what could be realistically achieved by the "application tessellate->server rasterization" process that the X11 engine has to deal with. So without all out acceleration in this case X11 engine can't compete with the raster engine. While simplifying a lot it's worth remembering that in terms of cycles register access is most likely smaller or equal to 1 cycle, access to L1 data cache is likely about 3 cycles, L2 is probably about 14 cycles, while the main memory is about 240 cycles. So for CPU based graphics efficient memory utilization is one of the most crucial undertakings.

With that in mind, this is also the reason why a heavily optimized purely software based OpenGL implementation would be a lot faster than raster engine is at 2D graphics. In terms of memory usage OpenGL pipeline is simply a lot better at handling memory than the API QPainter provides.

So what you should take away from this is that if you're living in the perfect world, the GL engine is so much better than absolutely anything else Qt/KDE have it's not even funny, X11 follows it and the raster engine trails far behind.

The reality with which you're dealing with is that when using the X11 engine, due to the fallback you will be also using the raster engine (either on the application side with Qt raster engine or the server side with Pixman) and unfortunately in this case "the more the better" doesn't apply and you will suffer tremendously. Our X11 drivers don't accelerate chunks of Xrender, the applications don't have good means of testing what is accelerated, so what Qt does is simply doesn't use many of its features. So even if the driver would accelerate for example gradient fills and source picture transformations it wouldn't help you because Qt simply doesn't use them and always falls back to the raster engine. It's a bit of a chicken and an egg problem - Qt doesn't use it because it's slow, it's slow because no one uses it.

The best solution to that conundrum is to try running your applications with -graphicssystem=opengl and report any problems you see to both Qt software and the Mesa3D/DRI bugzillas because the only way out is to make sure that both our OpenGL implementations and OpenGL usage in the rendering code on the applications side are working efficiently and correctly. The quicker we get the rendering stack to work on top of OpenGL the better off we'll be.

Fast graphics

Instead of highly popular pictures of llamas today I'll post a few numbers. Not related to llamas at all. Zero llamas. These will be Qt/KDE related numbers. And there's no llamas in KDE. There's a dragon, but he doesn't hang around with llamas at all. I know what you're thinking: KDE is a multi-coltural project surely someone must be chilling with llamas. I said it before and I'll say it again, what an avarage KDE developer, two llamas, one hamster and five chickens do in a privacy of their own home is none of your business.

Lets take a simple application, called qgears2, based on David Reveman cairogears and see how it performs with different rendering backends. Pay attention to zero relation to llamas or any other animals. The application takes a few options, -image: to render using a CPU based raster engine, -render: to render using X11's Xrender and -gl to render using OpenGL (-llama option is not accepted). It has three basic tests, "GEARSFANCY" which renders a few basic paths with a linear gradient alpha blended on top, TEXT that tests some very simple text rendering and COMPO which is just compostion and scaling of images.



The numbers come from two different machines. One is my laptop which is running Xorg server version 1.4.2. Exa is 2.2.0. Intel driver 2.3.2. GPU is 965GM, CPU is T8300 at 2.4GHz running on Debian Unstable's kernel 2.6.26-1.
The second machine is running GeForce 6600 (NV43 rev a2), NVIDIA proprietary driver version G01-173.14.09, Xorg version 7.3, kernel 2.6.25.11, CPU is Q6600 @ 2.40GHz (thanks to Kevin Ottens for those numbers, as I don't have NVIDIA machine at the moment).

The results for each test are as follows:

GEARSFANCY

	I965	NVIDIA
Xrender	35.37	44.743
Raster	63.41	41.999
OpenGL	131.41	156.250

TEXT

	I965	NVIDIA
Xrender	13.389	40.683
Raster	(incorrect results)	(incorrect results)
OpenGL	36.496	202.840

COMPO

	I965	NVIDIA
Xrender	67.751	66.313
Raster	81.833	70.472
OpenGL	411.523	436.681

COMPO test isn't really fair because as I mentioned Qt doesn't use server side picture transformations with Xrender but it shows that OpenGL is certainly not slow at it.

So what these results show is that GL backend, which hasn't been optimized at all, is between 2 to 6 times faster than anything out there and that pure CPU based Raster engine is faster than the Xrender engine.

So if you're on an Intel GPU, or NVIDIA GPU rendering using GL will immediately make your application a number times faster. If you're running on a system with no capable GPU then using raster engine will make your application faster as well.
Switching Qt to use GL backend by default would result in all applications running a magnitude times faster. The quality would suffer though (unless HighQualityAntialiasing mode would be used in Qt in which case it would be the same). This certainly would fix our graphics performance woes and as a side-effect allow using GL shaders right on the widgets for some nifty effects.
On systems with no GPU raster engine is a great choice, on everything else GL is clearly the best option.

Accelerating desktops

In general I'm extremely good at ignoring emails and blog posts. Next to head-butting it is one of the primary skills I've developed while working on Free Software. Today I will respond to a few recent posts (all at once, I'm a mass-market responder) about accelerating graphics.

Some kernel developers released a statement saying that binary blobs are simply not a good idea. I don't think anyone can argue that. But this statement prompted a discussion about graphics acceleration, or more specifically a certain vendor who is, allegedly, doing a terrible job at it.

First of all the whole discussion is based on a fallacy rendering even the most elaborate conclusions void. It's assumed that in our graphics stack there's a straight forward way between accelerating an api and fast graphics. That's simply not the case.

I don't think it's a secret that I'm not a fan of XRender. Actually "not a fan" is an understatement I flat out don't like it. You'd think that the fact that 8 years after its introduction we still don't have any driver that is actually real good at accelerating that "simple API" would be a sign of something... anything. When we were making Qt use more of the XRender api the only way we could do that is by having Lars and I go and rewrite the parts of XRender that we were using. So what happened was that instead of depending on XRender being reasonably fast we rewrote the parts that we really needed (which is realistically just the SourceOver blending) and did everything else client side (meaning not using XRender)

Now going back to benchmarking XRender. Some people pointed out an application I wrote a while back to benchmark XRender: please do not use it to test a performance of anything. It will not respond to any real workloads. (also if you're taking something I wrote to prove some arbitrary point, it'd be likely a good idea to ping me and ask about it. You know on account of writing it, I just might have some insight into it). The thing about XRender is that there's a large amount of permutations for every operation. Each graphics framework which uses XRender uses specific, defined paths. For example Qt doesn't use server-side transformations (they were just pathetically slow and we didn't feel it would be in the best interest of our users to make Qt a lot slower), Cairo does. Accelerating server side transformations would make Cairo a lot faster, and would have absolutely no effect on Qt. So whether those tests pass with 20ms or 20hours has 0 (zero) effect on Qt performance.

What I wanted to do with the XRender performance benchmarking application is basically have a list of operations that need to be implemented in driver to make Qt, Cairo or anything else using XRender fast. "To make KDE fast look at the following results:" type of thing. So the bottom line is that if one driver has for example result of 20ms for Source and SourceOver and 26 hours for everything else and there's second driver that has 100ms for all operations, it doesn't mean that on average driver two is a lot better for running KDE, in fact it likely means that running KDE will be five times faster on driver one.

Closed sourced drivers are a terrible thing and there's a lot of reasons why vendors would profit immensely from having open drivers (which is possibly a topic for another post). Unfortunately I don't think that blaming driver writers for not accelerating graphics stack which we went out of our way to make as difficult to accelerate as possible is just a good way of bringing that point forward.

Constant state objects

I know you wither away, like a leaf in the darkness of the chilly, Autumn night, without my posts. I've been depriving you for too long of the sunshine that is me. Writing an interesting post explaining the new way one is doing register allocation or how the code generation has changed to benefit the drivers is a little difficult and I didn't feel like it would interest anyone. Especially that I know that if I write a blog about a little demo app I wrote in half an hour to showcase some technology I get 50 comments but when I blog about the process of creating that new technology I get two comments with one of them being "What?". On top of that I was lacking those new nude photos (it's art you pig!) of myself that I've promised you and which you yearn for so much.

Lately I've been working on the Gallium3D i965 driver. I had to read up some documentation because, as it turned out, being a "graphics ninja" did not give me intrinsic knowledge of all graphics hardware ever built. I know! I was as shocked as you are right now.

It started with the fact that I wanted to experiment with the layout of vectors in shaders for the code generation using LLVM facilities.

To experiment with different layouts I've decided to write i965 driver for Gallium3D and experiment with LLVM code generation for i965 in that driver. Keith Whitwell and I have been hacking on it and it's going pretty well. It's amazing how much code we've removed from the old i965 driver while porting it to Gallium3D. It was a rather nice feeling to see so much of the complexity of the driver disappear.

The great thing about writing a Gallium3D driver is that a lot of the complexity of the high level API goes away, as it's being moved to "state tracker". State tracker is responsible for all API specific state handling and tricky conversions. The driver never sees the state tracker, it implements a very thin interface, which corresponds rather closely to the way modern hardware works.

One of my favorite changes is the new way we handle state changes. It used to be that the driver had to check whether any of its state changed and if it did upload it before drawing anything. It turned out to be a rather serious bottleneck and it made reading our driver a little painful.

In Gallium3D we went away from that. Now we use similar semantics to what Direct3D10 and OpenGL3 (will) use. Which is that states are largely immutable objects. Their usage follows the

• create from a template
• bind the state to make it active for subsequent rendering calls
• delete when not needed anymore

pattern. This way the driver can do all of its conversion on creation (which ideally happens only once) and then on bind calls (which we have multiple off) it can just reference the id of this state to have it used instead of having to do a full conversion from the Mesa state and upload of the converted state.
When I wrote the constant state objects code I ported our simple i915 driver and, even though on i915 we don't have hardware state caching just doing the state conversions in create calls improved the performance in simple examples by about 15fps. For more complicated examples where the state changes are more frequent it will be a lot more. Not even mentioning drivers which will do full state caching in the hardware where this is going to fly like Superman with diarrhea.

Less complexity in the driver and faster code, is what I think love is all about. Granted that my idea of love might be a smidge skewed on account of me being crazy and all but no one can argue with the "simpler/faster" being 'awesome'.

And to really top this graphics talk off, a picture of me naked:

In retrospect not my best day. The lighting was all wrong...

Gallium3D LLVM

I've seen the future. The blurry outlines sketched by such briliant audio-visual feasts as Terminator came to fruition as in the future the world is ruled by self-aware software.
That's the bad news. The good news is that we haven't noticed.
We're too busy due to the fact that we're all playing the visually stunning "The Good Guy Kills the Bad Guys 2" on Playstation 22. It really captured the essence of the first. The theaters are ruled by "Animals - Did they exist?" documentary with some stunning CG of a horse, although I could have sworn that horses had 4, not 3 legs but then again I'm no nature expert.
What everyone was wrong about though is which program became self-aware and exerted its iron-fist like dominance upon the unsuspecting humans and the last few, very suspicious cockroaches. It wasn't a military mistake. It was a 3D framework that evolved.

But lets start from the beginning. First there was Mesa, the Open Source implementation of the OpenGL specification. Then there came Gallium3D, a new architecture for building 3D graphics drivers. Gallium3D modeled what modern graphics hardware was doing. Which meant that the framework was fully programmable and was actually code-generating its own pipeline. Every operation in Gallium3D was a combination of a vertex and a fragment shader. Internally Gallium3D was using a language called TGSI - a graphics dedicated intermediate representation.

Gallium3D was generating vertex and fragment shaders at run-time to describe what it was about to do. After that system was working, some engineers decided that it would make sense to teach Gallium3D to self-optimize the vertex/fragment programs that it, itself, was creating. LLVM was used for that purpose. It was used because it was an incredible compiler framework with a wonderful community. The decision proved to be the right one as Gallium3D with LLVM proved to be a match made in heaven. It was pure love. I'm not talking about the "roll over onto your stomach, take a deep breath, relax and lets experiment" kind of love, just pure and beautiful love.

So lets take a simple example to see what was happening. Lets deal with triangles, because they're magical.
Now to produce this example Gallium3D was creating two small programs. One that was run for every vertex in the triangle and calculated its position - it was really just multiplying the vertex by the current modelview matrix - that was the vertex shader. The other program was run on every fragment in this figure to produce the resulting pixels - that was the fragment shader. To execute these two programs they were being compiled into LLVM IR, LLVM optimization passes were run on them and LLVM code generators were used to produce executable code. People working on Gallium3D quickly noticed that, even though, their code wasn't optimized at all and it was doing terribly expensive conversions all the time, it was up to 10x faster with LLVM on some demos. They knew it was good.

So Gallium3D was in essence, at run-time, creating and optimizing itself. Which lead many Free Software enthusiast to create, wear and rarely even wash shirts with a slogan "We might not have a billion dollar budget but our graphics framework is smarter than all the people in your company together".

Then in the year 2113 Gallium3D got bored with just creating graphics and took control of the entire world. Which realistically speaking wasn't hard to do because we were willingly immersing ourselves in the worlds it was creating for us anyway.

But that's still many, many years away from our boring present. So for now, while you wait for sex robots, dinners in a tube and world without insects (or for that matter absolutely any animals at all) you can just go, get and play with Gallium3D where LLVM is used. At the moment only in the software cases, but the fifth of November is going to mark the first day in which work on code-generating directly for GPU's using LLVM is going to start.

Remember, remember the fifth of November... (oh, come on that's one heck of an ending)

Quasar

Does working on the 3D stack make me look fat? Give it to me straight. I promised myself I won't cry no matter what the answer is. As I mentioned in my last blog I'll be getting awfully kinky with our 3D stack and people wondered whether my work on it affects Quasar. Well, just as me moving didn't affect my habits with regards to taking showers (which I do frequently, i.e. every christmas or so), smoking (never ever), being awake (at least once per day) it also didn't affect my spare time habits (except the "starving" thing which was one of my favorite past-times in Norway). Since Quasar was always my spare time project, my move affected it as much as me buying new sneakers affects temperature in Japan (which it doesn't, assuming of course that the folks in Japan won't find the vision of me in the new sneakers so insanely hot to increase the temperature of the whole country).

Aaaanyway, so what is Quasar? Besides being a word that starts with a Q, has some other letters in the middle and sounds funky. It's a dynamic rendering framework, which in turn begs the question "what the hell is that?" ("the hell" being an optional part of this sentence).

Let me lead you through the evolution of Quasar and hopefully at end of this trip we'll be on the same page with regards to what we really need in terms of a graphical framework on the desktop.

Quasar started as a pretty basic image manipulation framework. I wanted to make sure that people can chain filters e.g. read-image->scale image->blur image->render image. It was a linear pipeline. The thing that made it important to me was that it was focused on hardware acceleration. This is a very important point which I want to underline.

I'm not interested in software based effects. This is not to say that the software versions of all of them shouldn't work, I just refuse to bother. It's 2007, even phones come out with some kind of gpu in them, worrying about software based graphical effects does to your time what listening to financial advises from blogs of Open Source engineers does to your money - wastes it (which reminds me, I also have some financial tips for you. Well, tip, just one. It's not the quantity but quality as they say. Invest money in winning lottery tickets. Note that I said "winning", buying any other kind would be silly. You're welcome). With the work we're doing right now at Tungsten Graphics our graphics stack will be extremely good at it.

When I was a kid we didn't have fancy graphics. We had crackheads, alcoholics, pimps, thugs and plenty of other shady characters none of which, I'm fairly certain, did computer graphics (childhood memories warm your heart, don't they?). If my years of working on a vector graphics framework taught me anything (besides how to write a vector graphics framework) it's that the most fundamental part of a high level graphics framework isn't the framework at all. It's the way in which you let people design their applications, their interfaces. What use are blurred perspective transformations if two people know how to use them? What's the point of 20 composition modes if people can't be bothered to understand the basic 2.

So I started seeing effects as a step, a very crucial one, on the way to very appealing interfaces, but not my ultimate goal. In a desktop world we're dealing with graphics on a fairly abstract level, because we're doing graphics for non-graphics people. Good effects framework is not one that has every possible effect ever invented but one that makes it possible to quickly add those effects to ones application/interface and end up with something usable and pretty.

Finally inherent complexity of graphics bothered me. Maybe not even the complexity itself (especially since it's where my job security stems from), but the fact that it takes a lot of knowledge to understand and know the fast paths. The knowledge necessary to extract that logic can be easily abstracted in a graph like structure. That's what I started doing in Quasar.

Quasar is a dynamic graph. One that can rearrange itself to produce the output in the fastest possible way.
Those are the three basic tenants of Quasar, to rehash, they are:
- hardware accelerated,
- easy to incorporate and produce good looking results,
- smart enough to produce the results in the quickest possible way, no matter how little knowledge its users posses.

The way it works is that one creates the rendering in a graphical builder (which at the moment looks very much like Quartz Composer), loads it up in application and, well, that's it.

Of course, the graph can be created or modified at run-time just well. It follows the "tell me what you'd like and I'll give you that in the best way possible" principle.
Having said that Quasar is still far from complete but I just posted where to get it from on the relevant KDE list (if you don't know which one, trust me you want to wait a little bit longer before trying it out). Oh, and of course Quasar will support full effects pipelines on top of movies (integrated with Phonon).

Small steps

I was on vacations last week but I'm being all jealous of my luggage. It got a free trip around the world. During my last 8 flights my luggage has been lost 5 times. Is that a record? Confetti anyone? It's a celebration. If you're going to meet me during any of the upcoming conferences I'll be the outgoing and highly sarcastic naked guy with a sign on my chest saying "for my face look this way" and an arrow pointing up.

I neglected to mention that, as Simon said, QtWebKit is working on Windows. Simon did an amazing job of porting all the quirks of the build system but "amazing" is the default state for all of his code so it's not a surprise at all. While he was doing that I've sat down and ported XML tokenizer to QXmlStream from LibXML. If you never wrote a web rendering tokenizer (and unless you're crazy, the chances of that are pretty high, and if you did you're crazy and won't remember doing it anyway) you know that "fragile" is a term that nicely describes it. After it was ported Lars and I sat down to fix the regressions and they didn't even know what hit them (ha! ninja reference).

In other news I've merged in FreeType2 rasterization algorithm patches in Qt. Our raster engine, uses the beauty that is FreeType's rasterizer, with a few patches on top. Because they break BC in FreeType's public interfaces we can't merge them back at the moment. In any case the patches improve rendering speed in general antialiased paths of the raster engine (meaning on Windows, Qtopia Core and in general whenever rendering to a QImage) by about 10% which is gangsta awesome ("gangsta awesome" is a very high level of awesomeness, at least judging from MTV).

I've also optimized the path clipping code. Andreas uses the path clipping code in GraphicsView for collision detection, so when I say "path clipping code" you should read "path clipping and GraphicsView collision detection". A lot of the time in that algorithm has been spent on vertex allocation for tested paths. I've used a few tricks to speed it up by about 15%. The code for that algorithm is the number two reason why baby seals die (the first is still undisputed). It's not even the algorithm itself but the inherent complexity of the problem. I'm a big fan of computational geometry in computer graphics because it makes grown man cry, except me and I like feeling like the lean, mean, killing machine that I am. My favorite part of the path clipping problem is that there are two ways of solving the precision problems and neither of them really works. The trick is that paths operate in double coordinate system, efficient snap-rounding implementations that I've seen operate in fixed-point coordinate system which falls apart in this case because of absolutely random distribution of vertices across the full double spectrum. Tessellation and clipping itself can be done in a screen coordinate system, which makes it possible to consistently represent your coordinates with fixed-point representation. That doesn't work for paths because, e.g. boolean operations on paths need to be done in native path coordinates not screen coordinates. So the algorithm forces an absolutely crazy mix of dynamic fixed-point size, reduced-predicates, magic and good-will to work. Aren't you happy that I'm doing it for you? You better be.

Yours(1) Latino(2) Lover(3)

1) Not really "yours", more "community". I love "you" but "you" need to realize that I need to be seeing other people.
2) Not really "Latino". Unless of course my Spanish or Brazilian friends would like to name me an "honorary Latino" or "Latino by association". I'd be definitely down with that. The only food I can make that is eatable and doesn't force the fire department to evacuate the building before are nachos. I'm a definition of grace in the kitchen. "Whatever you have in the kitchen I will make it burn" is my motto. Plus I'm sporting quite an attitude to boot. "Make Zack a Latino" campaign. We can make it work!
3) Not really "lover". More "no feelings haver". Though technically I've worked on software for so long that hate is, next to sarcasm, my primary export.

Browsers, performance and interventions

This week I beat WebKit Qt's rendering into shape. I rewrote the theming and canvas code.
It works so nicely that I'm actually pretty happy with it. The rewrite helped me fix issues with statically positioned elements (which just didn't work on a scrollview/canvas combination I did before). Due to which my blog finally looks and behaves correctly as seen on the screenshot above. That plus scrolling is about 10x faster and you never see gray areas on scrolling as you did before.
This week George Staikos has been here in Oslo to work with us on the networking code. George and I have been friends for five or six years and he has this nasty habit that forces me to start an intervention and try to get him off it. What I'm referring to is the fact that George has been Canadian for, well his entire life, and it is my professional opinion (but I'm not a doctor) that he needs to move on. I'm not sure in which culture it is customary to bring Snapple ice-tea to your friends when you come to see them but we need to change him to that because he definitely didn't bring me any this time and that's just rude.
Going back to work, I'm sure Lars will blog about the networking magic they did so I'll keep my mouth shut. Once the code they were working on will be ready (which should happen within next week or two) and we'll start using in WebKit, we'll make the transition and start using WebKit Qt based browser on a daily basis. So we're close which is pretty exciting.

We have also started optimization run for Qt 4.3. My grand plan is to make sure Qt 4.3 is 2x faster in general rendering code than Qt 4.2 was. I have a list of algorithms to shave and rewrite over the next few weeks which will be rather challenging.
By the way of performance some people noticed that Qt OpenGL in recent snapshots with Antialiasing turned on is actually slower than it was in Qt 4.2. It's because of an experiment that we're trying on. We're now using GLSL to antialias primitives. Of course it's a lot slower than the old code but produces very high quality results. I don't really like it though because the performance hit is just too big.