The colorful balls bounce away from the cursor and that's lots of fun I suppose, unless you're a geek and you notice that OMG this stupid little animation is taking 100% of my CPU time running at no more than 10 frames per second! And that comes from the same company whose product happily announces that it has found more than a billion results in 0.25 seconds. I know, not a fair comparison, but still -- I wonder how many millennia would the search engine need to find a billion matches had it been running on Javascript or whatever advanced, Just-In-Time compiled, Virtual Machine powered, Garbage Collected, uber-secure engine powers the colorful balls.

What's the big deal, you say? It's just a bunch of colorful balls, they'll be gone in a day or two!

I wish the same could be said about Java in general. Whenever I run any Java-powered program on my computer, even when the program is idle, the OS often needs to power up the fan. To collect a dead object perhaps, who knows. The point is, ever since Java's arrival, we've heard the same mantra over and over: "Oh, it's slow now but don't you worry it'll get faster. Soon. Like, tomorrow. JIT FTW!"

I've lost count on how many years I've been hearing that.

But aren't these colorful dots fun anyway? Not if you realize how wasteful and inefficient the whole thing is. It really is a Googleplex slower than it should be. :)

Gone: CreateRenderTarget

In DirectX 9 there were three types of "surfaces":

• Pure textures, which the GPU can only read,
• Render targets, which the GPU can only write (render) into, and
• Textures that are also render targets, which the GPU can read and write.

With this system, pure textures can be used by the CPU to efficiently write data to video memory for the GPU to read and render targets can be used to efficiently read data that was written by the GPU.

Textures that are also render targets can not be accessed by the CPU at all, but that's fine because if the CPU needs to read the result of a GPU pass, that pass can render into a render target (that is not a texture) which the CPU can read.

In DirectX 10/11 render targets that are not textures are no longer supported, so while the CPU can efficiently write data for the GPU to read, there is no efficient way for the application to read data written by the GPU. Instead, it is required to copy the data from a render target texture into another (non-render-target) texture which can then be mapped by the CPU for reading

D3D9 LockRect vs. D3D10/11 Map

In the good old DirectX 9 days, if the application needed to write data into a texture, it called the LockRect function to get a pointer. The data was written in the memory pointed by the pointer, and then UnlockRect was called.

The nice thing about this API is that it does not specify what kind of memory the returned pointer points. Depending on texture creation flags, the requested access (read/write/write-discard), the current state of the Direct3D device, and the capabilities of the graphics card, the driver might choose to map the texture video memory directly, or it might map a separate temporary video memory buffer, or it might even return a pointer to a system memory buffer which is copied to video memory when UnlockRect is called.

Instead, in DirectX 10 and 11 there seems to be only one choice: video memory is mapped directly if possible; if not, we get an error.

The new semantics are in fact in accord with a major overall architectural shift introduced with DirectX 10. It calls for removing the so-called "API magic": undocumented internal behavior designed to hide inefficiencies and/or lack of capabilities in the hardware. The rationale for avoiding API magic is that it makes application performance inconsistent across different hardware and driver versions.

It is true that depending on the actual behavior of LoctRect, the application performance can vary significantly. That is indeed a downside, but I wonder if the designers of DirectX 10 and 11 are old enough to remember DirectX 3. It also lacked any API magic. The idea was that the application would create execute buffers that would reside on the graphics card, removing all abstraction and maximizing performance. Yet, because the interface was designed with hardware engineers in mind, it was basically unusable. The more abstract DirectX 5 interface was much easier to use yet (surprise!) didn't lead to lower frame rates.

Similarly, the more abstract interface of LockRect in DirectX 9 is more practical than the less sophisticated DirectX 10/11 Map behavior. Sure, in the simplest use cases the difference is negligible, but then again in the simplest cases LockRect wouldn't use API magic either, so the user would not be penalized by it. It is the non-trivial, less frequent yet performance-critical uses that need a more abstract interface.

For example, if the texture is created and locked with the correct flags, DirectX 9 could let the application download new data to a texture even while it is currently used by a shader, which isn't possible in DirectX 10/11. How does that work in DirectX 9? If write-discard locking is requested, the driver could map a separate temporary video memory buffer for access by the application. As soon as the device is done using the texture, the new memory buffer can be associated with the texture at the cost of a pointer swap.

It can be argued that this is done behind the user's back: if that's what the application wanted to do it could do it itself right? The problem is that this type of systems are difficult to program. Besides, even if the user has the skill and resources needed to provide a high-quality implementation, they can't possibly compete with a driver programmer who is not only a specialist but also has the advantage of writing hardware-specific code and is enjoying much lower-level access to the graphics card.

Why do I think that writing this library was a good idea? Because it makes no sense for any of us to have to spell out how a 3x3 matrix is multiplied by another 3x3 matrix; there should be a way to express that algorithm generically and apply it to any and all 3x3 matrix types in the world.

The only tricky part is that operations such as matrix multiplication should use operator overloads (seriously, it's retarded not to) and that presents a challenge: how do you define type-safe operator overloads without using specific matrix types? That's basically what (Boost) LA pulls off, using SFINAE.

The scoop

A user-defined vector type float3 can be introduced to (Boost) LA like this:

After a similar specialization of the matrix_traits template for a user-defined 3x3 matrix type float33, a full range of vector and matrix operations defined in (Boost) LA headers become available automatically:

The full documentation and source code, released under the Boost Software License, is here.

v[X] = 0;  // before v|X = 0;
m2[col<1>][YXZ] = m1 * v; // before: m2|col<1>|YXZ = m1 * v;
m2[col<1>] = m1 * v[YXZ]; // no precedence issues. before: m2|col<1> = m1 * (v|YXZ);

v2 = v1[Z,X,Y]; // instead of: v2 = v1|ZXY;
v2 = v1[Y,-X];  // v1 and v2 are now perpendicular. Not possible with current syntax.

  op[X,Y,-Z]

What caught my eye is the focus of the author on a single reason why the TM model is flawed: complex software systems do not merely operate on memory.

This strikes me as important because I've observed a similar issue with garbage collection systems and languages. Like multi-threading programming, dealing with memory is difficult and it is easy for novice programmers to end up with a unmanageable mess of dangling pointers and memory leaks. And the solution? Simply don't worry about memory -- use as much as you need whenever you need it, the garbage collector will do its magic and it'll just work.

The problem with garbage collection systems is exactly the same: complex software systems do not merely operate on memory. Indeed, garbage collectors themselves do not manage memory. They manage objects lifetimes.

In the twisted mind of a Java developer we shouldn't worry about when the object will be collected: it can lurk around until an opportune moment arrives when the system has nothing better to do, and then it'll take care of it; and because the only type of resource most objects acquire is memory, most of the time we don't care when the object will be collected.

Yet, in the real world we must deal with all kinds of resources: files, sockets, locks, etc. We can't be sloppy with their acquisition and release. Their lifetime is just as hard to manage as memory and it is just as easy for a novice programmer to create a mess.

Solve that problem with finally and you're back to square one.

Java throws an exception.

C# and Visual Basic display a dialog box by default but provide an interface for extending and customizing program behavior when assertions fail.

In C and C++, the default behavior for assertion violations is to abort the program immediately. Not surprisingly, many C and C++ programmers create their own assertion-checking macros that are, well, "smarter".

What is the correct behavior then?

Some library developers would answer that there is no single correct behavior, and they'll point out at all the different behaviors people find useful. Why make a difficult design decision when you can shift that responsibility to the user?

What this train of thought is missing is that when an assertion fires, we can no longer reason about the state of the program; there is no way to know what will happen if the program is not terminated.

"But it might be important to minimize the damage! In some instances, ignoring a particular assertion might be better than terminating the program!"

Certainly, except that when something the programmer considered impossible has just happened, all bets are off. Aborting seems drastic? Indeed it is, but any other alternative would be like making a zombie run a marathon.

Besides, it isn't always realistic to assume that the user knows the correct answer. What would you reply to

Assertion failure: "Your nuclear reactor has overheated. Abort, Debug, Ignore?"

:)

I thought, OK, maybe few people use C any more. So I'd just shrug and try another search.

However, it seems that the problem is deeper than that. Just now I looked up D3D11_PRIMITIVE_TOPOLOGY on MSDN and I got the following result:

• D3D10_PRIMITIVE_TOPOLOGY Enumeration (Windows)
• SimpleBezier11 Sample
• effect files tesselation features - XNA Community Forums
• The Lepidoptera Project
• ...

Obviously this search query is very specific. There is no way D3D10_PRIMITIVE_TOPOLOGY to be a better match than the D3D11_PRIMITIVE_TOPOLOGY page that I know exists on MSDN (click here to see current MSDN search results for this query.)

Is it that there is something wrong with my search? Google doesn't think so: with the same query, the D3D11_PRIMITIVE_TOPOLOGY page is at the top of its search results.

Is this a problem with MSDN itself? Maybe it's using old search technology that Microsoft hasn't been able to update yet? Surely, Bing can do better? Not really, here is what Bing found:

• D3D10_PRIMITIVE_TOPOLOGY Enumeration (Windows)
• SimpleBezier11 Sample
• Anteru’s blog » directx
• Anteru’s blog » 2010 » March » 01
• ...

(Click here for current Bing search results for this query.)

So there you have it: Google seems better at searching the MSDN pages than Microsoft. :)

• floats, which was the default,
• integers, designated by a % after their name, and
• strings, designated by a $ after their name.

So if you wanted to use a string, you just type:

Most programming languages today have similar level of built-in string type support but not C and C++ where string support is provided through the standard library.

However, the result is essentially the same:

The problem is that string support is indeed so basic and so trivial that pretty much any decent C++ programmer can implement a string class of their own.

And so they do.

And then, some poor soul decides to learn C++ after having been programming in other languages.

And they can't believe that someone -- an otherwise rational person most programmers are -- could seriously think that writing yet another string class is a good idea.

It also feels good to support an open standard like that. I love open standards. For example I find it ridiculous that Windows is not POSIX; even though it does serve their corporate interests, Apple demonstrated that the same corporate interests can be served with a POSIX-compliant OS.

And then OpenGL showed its ugly head.

Extensions

How has OpenGL survived for so many years? By extensions.

Every time a graphics chip manufacturer implements a cool new feature in hardware, OpenGL allows them to provide whatever functions they feel like in the form of extensions. For example, if ATI needed to implement a cool new function, they simply document it and compile it in the video driver shared libraries/DLLs, using a function name like glCoolNewFeatureATI.

If two or more graphics chip manufacturers agree on the same API for a cool new feature, then the OpenGL stardard allows them to use the suffix EXT: glCoolNewFeatureEXT. That way, programs can look for and link to that function without having to know what graphics hardware they're running on.

Then there is the OpenGL Architecture Review Board which looks at various extensions that appear and if they like an EXT function, it gets the ARB blessing and vendors are allowed to use the suffix ARB with the name, so we get glCoolNewFeatureARB.

Finally, most (all?) ARB functions are made part of the next revision of the OpenGL standard, at which point all suffixes are dropped and we're left with glCoolNewFeature added to the rest of the OpenGL functions.

That's how committees work: because nobody is in charge, nobody can take the responsibility for making the correct architectural decision. Because nobody can take that responsibility, it is necessary to have a cumbersome system of checks and balances to minimize the possibility of breaking the standard.

But the result is a mess anyway. Users end up with potentially 4 different versions for many OpenGL functions. Which one should they call?

You might think that a reasonable approach is to look up the suffix-less version first, if that fails look up the ARB version, and if that fails look up the EXT version, and finally if that also fails just announce to the user that their OpenGL driver sucks and exit. But that's easier said than done.

For starters, some of these functions take enums as parameters. The names of the enums also feature the corresponding suffix. For example, a possible value for the first parameter of glBindBufferARB is GL_ARRAY_BUFFER_ARB, but if you're calling glBindBufferEXT you should be using GL_ARRAY_BUFFER_EXT instead, and if you're calling simply glBindBuffer then you'd use GL_ARRAY_BUFFER.

This arrangement makes it difficult for the graphics programmer to abstract the logic for selecting the correct function: it isn't sufficient to simply store a function pointer or something similar. The only viable solution is to create a wrapper layer over OpenGL with its own naming conventions and its own enums, which then get translated depending on which of the 3 or 4 variants of the function should be called on the target platform.

Or, you could just pick one variant and use only that or fail if it isn't available. For example, I thought that it is reasonable for my program to require vertex buffer support in the OpenGL driver, so I started writing code which simply calls glBindBuffer without any suffixes. And it turned out that on my system glBindBuffer is available but is broken. glBindBufferARB is also available, and it works fine.

So, I feel stuck. So much so that blogging about the problem seemed more appealing than trying to figure out what's the correct solution. :)

Yes, a telephone was much easier to use in the 70s, but then again it didn't do that much, did it? Could you imagine having to memorize the phone numbers of everyone you need to text or call? Right, that would have sucked. How about having to fast forward in order to get to the next song on a compact cassette? Ouch.

Yet, some things from the past are worth admiring. To me, a steam engine is prettier than the most advanced internal combustion engines of today. Not really practical, yet pretty.

But I'm a programmer, and a lot of the old stuff I admire is software. And while I have (if only once) programmed a computer with punchcards, those were already antiques when I was in school; the computer I grew up programming was the Apple ][.

So here we go: at the risk of wasting my time raving about something most programmers today can't appreciate, I'll try to explain but just a tiny bit of Wozniak's brilliancy:

The Apple ][ floppy disk controller bootstrapping routine

Some background: on physical magnetic media, you can't "just record data". Instead, 1 is encoded as a magnetic polarity transition (also known as flux reversal), and 0 is encoded as, well, lack of transition. Basically, for each bit there is a limited time window in which flux reversal is expected to occur. If it occurs, the bit is 1, otherwise it's 0. The problem is that the time window is so small that there is a limit on the accuracy with which the data window length can be measured. So, while detecting a series of ones is not a problem, it's difficult to know how many zeroes are encoded in a measured period of lack of flux reversal.

Wozniak's original hardware design imposed two constraints on the raw data:

• between any two 1-bits, there can be no more than one 0-bit, and
• each 8-bit byte must start with a 1-bit

However, using simple FM encoding "wastes" 4 bits per raw byte, which would allow only 10 256-byte sectors per track to be recorded. Instead, he devised a more complex encoding scheme that was based on the fact that there are 34 8-bit numbers which have the top bit set and no two 0-bits in a row. That way, 13 sectors per track could be recorded. Later on the hardware design of the floppy disk controller was modified to allow no more than one occurrence of two consecutive 0-bits in a byte, which lead to different encoding called 6&2; it allowed 16 sectors per track.

A conventional floppy disk controller design would put all this bit twiddling in silicone which just DMAs the decoded bytes in memory -- but it would cost more in hardware. So what is a Wozniak to do? Obviously: screw hardware, do everything in software.

That would have been impressive enough on a 6502 CPU, but even more impressive is what is required of the bootstrapping routine. It must:

• generate the 6&2 decoding table in RAM
• seek the disk drive to track zero
• look for the beginning marker of sector zero and read the raw data in RAM
• decode the data and jump into it

...all in no more than 256 bytes of code, which is the addressing limit for the ROM on Apple ][ expansion cards.

By the way, there are no timers on the Apple ][, all timing is based on the CPU clock, e.g. you'd know that an INX instruction takes 2 microseconds to execute. The 6502 has three 8-bit registers: an accumulator A which can add, subtract, shift, rotate, and, or, xor, etc., and two 8-bit index registers X and Y which can do none of those operations. :)

Here are some pictures I found of Bulgarian-made Apple ][ clones: the first two are of Pravetz-82 from the late 70s/early 80s, the third picture is of Pravetz-8C from the late 80s/early 90s. These Bulgarian computers were compatible with Apple ][, but their evolution didn't entirely follow the evolution of Apple ][, e.g. some models didn't have an exact original.

So, what's so special about shared_ptr? Let me begin with parsing the smart pointer concept: what does it mean to be "smart" and what does it mean to be a "pointer"?

1) Smart

The smartness is the ability of smart pointers to keep track of the lifetime of the objects they refer to.

There are multiple ways to implement "smartness". Arguably, the most practical implementation is through refcounting, because other (possibly more optimal) solutions typically lead to non-deterministic termination, and that renders RAII useless and forces programmers to write finally clauses like there's no tomorrow. If finally doesn't bug you, you must be a Java programmer and in this case I'm wondering how did you get this far in my post to begin with. :)

2) Pointer

Pointers are both a primary reason why C and C++ programs are very efficient, and a major obstacle for compiler optimizations. Regardless, they are at the very base of these languages; we C and C++ programmers can't live without pointers.

What's so cool about pointers? First and foremost, pointers give us universal means to refer to any object whatsoever (I'm specifically ignoring type safety here, because it just makes it less likely that we make a silly mistake by forgetting what's the type of the object we point to.)

Using plain old C pointers, a factory function can create an object of some type and return a pointer to the user. The user can hold on to the pointer, make (and destroy) any number of copies of the pointer, organize pointers in containers, pass pointers to other functions, etc. For example:

As this interface example illustrates, copying a pointer doesn't require a complete type. In fact, the type of the pointee is irrelevant as far as copying or destroying the pointer itself is concerned -- even (typeless) void pointers can be freely copied around. The trick is to not destroy (forget about) all pointer copies we've made, or else we get a leak.

Smart, pointer

C++ allows operator-> and operator* overloads specifically so that (in combination with RAII) programmers can implement smart pointers:

Let's leave the refcounting mechanics aside for now and focus on the refcount_ptr destructor. Its implementation appears straight-forward:

Right? Wrong! Remember, a (smart) pointer must be copyable (and destroyable) in contexts where the type of the pointee (T in our refcount_ptr example) is incomplete. But in such contexts, ~refcount_ptr won't compile: delete requires a complete type!

Solve that problem, and you'll discover that refcount_ptr can not only work with incomplete types, but it also supports type erasure -- refcount_ptr<void> would work just fine.

And by that time you'll be well on your way to reinventing shared_ptr -- all the rest of its features follow from it being a pointer, just "smart".

Aliasing support

Here's something else you could do with plain old C pointers:

The above code is so basic it's actually easy to fail to appreciate its importance. It demonstrates that we can use the & operator to make a pointer that points to any object whatsoever, including an int that is a member of some other object foo. The x member of a can now be accessed as a->x or by dereferencing the other pointer, *b.

Imagine now that foobar takes a smart pointer of type foo. Could it then make a smart pointer of type int from it? Yep, shared_ptr can do that too:

Note: the b object shares ownership with a; that is, creating/destroying a or b copies will manipulate the same refcount. And when that refcount reaches zero, the foo destructor will be called, even if the last reference to it was through a shared_ptr<int>.

Pointer arithmetics?

It's even possible to provide operator++/-- for shared_ptr:

This of course would be the prefix version of operator++, a postfix overload can be defined by using a second, unused parameter of type int. With this and a few additional similar overloads, you can use shared_ptr<T> to iterate over arrays of T managed by shared_ptr. This is way cool, if not that practical. :)

Using shared_ptr to manage system resources

Here is how you can hold on to a Direct3D9 object using shared_ptr:

Similar use, holding on to a FILE:

The two examples above take advantage of the fact that the type returned by the API is a pointer, so the shared_ptr template can be directly instantiated with it.

With a bit of trickery, shared_ptr can also be used to manage handles (of non-pointer type), for example OpenGL texture IDs:

(The make_handle function template used above is not part of Boost. Follow the link to see how it's defined.)

In all of these examples, besides keeping track of the shared count and releasing the resource when the last shared_ptr copy expires, we gain the ability to use weak_ptr with those resources.

Using shared_ptr in games

When talking about using shared_ptr in games, many programmers dismiss its benefits because they think in terms of the narrow scope of other smart "pointers", which merely know when to call delete. Due to their very dynamic nature, games must manage memory carefully and this often means avoiding new and delete altogether.

But the ability of shared_ptr to decouple user code from the exact mechanics of allocating and freeing resources is, I would say, critically important in game development. For example, shared_ptr makes it trivial to implement a factory which allocates objects from a pre-allocated pool of static size, without putting any burden on the user to remember how to destroy them. What's more, the factory can dynamically choose between multiple pools when allocating each individual object instance, or even resort to a less optimal allocation when all pools have been exhausted.

And since game programmers are especially prone to the "I'll write my own" syndrome, this is a good place to quote Scott Meyers:

Overhead

Yes, sometimes you can't afford to use shared_ptr. But do yourself a favor and don't assume that an alternative solution would outperform it. Only believe hard evidence; especially avoid basing your decisions on profiling some toy example. Only data from profiling your actual program (or a relevant part of it) is valid evidence.

And even when faced with hard evidence that shared_ptr is slowing you down, ask yourself:

• Have you considered the use of custom allocators with shared_ptr? You can optimize allocations per object instance, not only depending on object type. For example, you can easily use different allocation strategy for "small" vs. "big" object instances of the same type T.
• Have you considered storing the control block (which keeps the refcounts) and the object itself in the same memory block? This trick often outperforms even intrusive refcounting solutions.
• Have you considered the ability to store multiple control blocks (for different objects) in the same memory block? This trick avoids cache misses in use cases that are intensive on refcount changes.

In my experience if I can't afford shared_ptr, I can't afford any smart pointer. Which isn't the end of the world, I love plain old C pointers too. :)