Making SoA Tollerable

Chandler Caruth (I think - I can't for the life of me find the reference) said something in a cppcon talk years ago that blew my mind. More or less, 95% of code performance comes from the memory layout and memory access patters of data structures, and 5% comes from clever instruction selection and instruction stream optimization.

That is...terrible news! Instruction selection is now pretty much entirely automated. LLVM goes into my code and goes "ha ha ha foolish human with your integer divide by a constant, clearly you can multiply by this random bit sequence that was proven to be equivalent by a mathematician in the 80s" and my code gets faster. There's not much I have to worry about on this front.

The data structures story is so much worse. I say "I'd like to put these bytes here" and the compiler says "very good sir" in sort of a deferential English butler kind of way. I can sense that maybe there's some judgment and I've made bad life choices, but the compiler is just going to do what I told it. "Lobster Thermidor encrusted in Cool Ranch Doritos, very good sir" and Alfred walks off to leave me in a hell of L2 cache misses of my own design that turn my i-5 into a 486.

I view this as a fundamental design limitation of C++, one that might someday be fixed with generative meta-programming (that is, when we can program C++ to write our C++, we can program it to take our crappy OOPy-goopy data structures and reorganize them into something the cache likes) but that is the Glorious Future™. For now, the rest of this post is about what we can do about it with today's C++.

There Is Only Vector

To go faster, we have to keep the CPU busy, which means not waiting for memory. The first step is to use vector and stop using everything else - see the second half of Chandler's talk. Basically any data structure where the next thing we need isn't directly after the thing we just used is bad because the memory might not be in cache.

We experienced this first hand in X-Plane during the port to Vulkan. Once we moved from OpenGL to Vulkan, our CPU time in driver code went way down - 10x less driver time - and all of the remaining CPU time was in our own code. The clear culprit was the culling code, which walks a hierarchical bounding volume tree to decide what to draw.

I felt very clever when I wrote that bounding volume tree in 2005. It has great O(N) properties and lets us discard a lot of data very efficiently. So much winning!

But also, it's a tree. The nodes are almost never consecutive, and a VTune profile is just a sea of cache misses each time we jump nodes. It's slow because it runs at the speed of main memory.

We replaced it with a structure that would probably cause you to fail CS 102, algorithms and data structures:

1. A bunch of data is kept in an array for a a sub-section of the scenery region.

2. The sub-sections are in an array.

And that's it. It's a tree of fixed design of depth two and a virtually infinite node count.

And it screams. It's absurdly faster than the tree it replaces, because pretty much every time we have to iterate to our next thing, it's right there, in cache. The CPU is good at understanding arrays and is going to get the next cache line while we work. Glorious!

There are problems so big that you still need O(N) analysis, non-linear run-times, etc. If you're like me and have been doing this for a long time, the mental adjustment is how big N has to be to make that switch. If N is 100, that's not a big number anymore - put it in an array and blast through it.

We Have To Go Deeper

So far all we've done is replaced every STL container with vector. This is something that's easy to do for new code, so I would say it should be a style decision - default to vector and don't pick up sets/maps/lists/whatever unless you have a really, really, really good reason.

But it turns out vector's not that great either. It lines up our objects in a row, but it works on whole objects. If we have an object with a lot of data, some of which we touch all of the time and some of which we use once on leap years, we waste cache space on the rarely used data. Putting whole objects into an array makes our caches smaller, by filling them up with stuff we aren't going to use because it happens to be nearby.

Game developers are very familiar with what to do about it - perhaps less so in the C++ community: vector gives us an array of structures - each object is consecutive and then we get to the next object; what we really want is a structure of arrays - each member of the object is consecutive and then we hit the next object.

Imagine we have a shape object with a location, a color, a type, and a label. In the structure of arrays world, we store 4 shapes by storing: [(location1, location2, location3, location4), (color 1, color 2, color3, color4), (type 1, type2, type3, type 4), (label 1, label2, label3, label4)].

First, let's note how much better this is for the cache. When we go looking to see if a shape is on screen, all locations are packed together; every time we skip a shape, the next shape's location is next in memory. We have wasted no cache or memory bandwidth on thing we won't draw. If label drawing is turned off, we can ignore that entire block of memory. So much winning!

Second, let's note how absolutely miserable this is to maintain in C++. Approximately 100% of our tools for dealing with objects and encapsulations go out the window because we have taken our carefully encapsulated objects, cut out their gooey interiors and spread them all over the place. If you showed this code to an OOP guru they'd tell you you've lost your marbles. (Of coarse, SoA isn't object oriented design, it's data oriented design. The objects have been minced on purpose!)

Can We Make This Manageable?

So the problem I have been thinking about for a while now is: how do we minimize the maintenance pain of structures of arrays when we have to use them? X-Plane's user interface isn't so performance critical that I need to take my polymorphic hierarchy of UI widgets and cut it to bits, but the rendering engine has a bunch of places where moving to SoA is the optimization to improve performance.

The least bad C++ I have come up with so far looks something like this:

struct scenery_thingie {

    int            count;

    float *        cull_x;

    float *        cull_y;

    float *        cull_z;

    float *        cull_radius;

    gfx_mesh *     mesh_handle;

    void alloc(UTL_block_alloc * alloc, int count);

    scenery_thingie& operator++();

    scenery_thingie& operator+=(int offset);

};

You can almost squint at this and say "this is an object with five fields", and you can almost squint and this and say "this is an array" - it's both! The trick is that each member field is a base pointer into the first object (of count's) member field, with the next fields coming consecutively. While all cull_y fields don't have to follow cull_x in memory, it's nice if they do - we'd rather not have them on different VM pages, for example.

Our SoA struct can both be an array (in that it owns the memory and has the base pointers) but it can also be an iterator - the increment operator increments each of the base pointers. In fact, we can easily build a sub-array by increasing the base pointers and cutting the count, and iteration is just slicing off smaller sub-arrays in place - it's very cheap.

This turns out to be pretty manageable! We end up writing *iter.cull_x instead of iter->cull_x, but we more or less get to work with our data as expected.

Where Did the Memory Come From?

We have one problem left: where did the memory come from to allocate our SoA? We need a helper - something that will "organize" our dynamic memory request and set up our base pointers to the right locations. This code is doing what operator new[] would have done.

class UTL_block_alloc {

public:

    UTL_block_alloc();

    template<typename T>

    inline void alloc(T ** dest_ptr, size_t num_elements);

    void *    detach();

};

Our allocation block helper takes a bunch of requests for arrays of T's (e.g. arbitrary types) and allocates one big block that allocates them consecutively, filling in dest_ptr to point to each one. When we call detach, the single giant malloc() block is returned to be freed by client code.

We can feed any number of SoA arrays via a single alloc block, letting us pack an entire structure of arrays of structures into one consecutive memory region. With this tool, "alloc" of an SoA is pretty easy to write.

void scenery_thingie::alloc(UTL_block_alloc * a, int in_count)

{

    count = in_count;

    a->alloc(&cull_x,c);

    a->alloc(&cull_y,c);

    a->alloc(&cull_z,c);

    a->alloc(&cull_r,c);

    a->alloc(&mesh_handle,c);

}

A few things to note here:

• The allocation helper is taking the sting out of memory layout by doing it dynamically at run-time. This is probably fine - the cost of the pointer math is trivial compared to actually going and getting memory from the OS.
• When we iterate, we are using memory to find our data members. While there exists some math to find a given member at a given index, we are storing one pointer per member in the iterator instead of one pointer total.

One of these structs could be turned into something that looks more like a value type by owning its own memory, etc. but in our applications I have found that several SoAs tend to get grouped together into a bigger 'system', and letting the system own a single block is best. Since we have already opened the Pandora's box of manually managing our memory, we might as well group things complete and cut down allocator calls while getting better locality.

Someday We'll Have This

Someday we'll have meta-programing, and when we do, it would be amazing to make a "soa_vector" that, given a POD data type, generates something like this:

struct scenery_thingie {

    int            count;

    int            stride

    char *         base_ptr;

    float&         cull_x() { return (*(float *) base_ptr); }

    float&         cull_y() { return *((float *) base_ptr + 4 * stride); }

    float&         cull_z() { return *((float *) base_ptr + 8 * stride); }

    /* */

};

I haven't pursued this in our code because of the annoyance of having to write and maintain the offset-fetch macros by hand, as well as the obfuscation of what the intended data layout really is. I am sure this is possible now with TMP, but the cure would be worse than the disease. But generative meta-programming I think does promise this level of optimized implementation from relatively readable source code.

Nitty Gritty - When To Interleave

One last note - in my example, I split the X, Y and Z coordinates of my culling volume into their own arrays. Is this a good idea?  If it was a vec3 struct (with x,y,z members) what should we have done?

The answer is ... it depends? In our real code, X, Y and Z are separate for SIMD friendliness - a nice side effect of separating the coordinates is that we can load four objects into four lanes of a SIMD register and then perform the math for four objects at once. This is the biggest SIMD win we'll get - it is extremely cache efficient, we waste no time massaging the data into SIMD format, and we get 100% lane utilization. If you have a chance to go SIMD, separate the fields.

But this isn't necessarily best. If we had to make a calculation based on XYZ, together, and we always use them together and we're not going to SIMD them, it might make sense to pack them together (e..g so our data went XYZXYZXYZXYZ, etc.). This would mean fetching position would require only one stride in memory and not three. It's not bad to have things together in cache if we want them together in cache.

When Not To Serialize

Over a decade ago, I wrote a blog post about WorldEditor's file format design and, in particular, why I didn't reuse the serialization code from the undo system to write objects out to disk. The TL;DR version is that the undo system is a straight serialization of the in-memory objects, and I didn't want to tie the permanent file format on disk to the in-memory data model.

That was a good design decision. I have no regrets! The only problem is: the whole premise of the post is quite misleading because:

While WorldEditor does not use its in memory format as a direct representation of objects, it absolutely does use its in-memory linkage between objects to persist higher level data structures. And this turns out to be just as bad.

What Not To Do

WorldEditor's data model works more or less like this (simplified):

• A document is made up of ... um ... things.
• Every thing has an optional parent and zero or more ordered children, referred to by ID.
• Higher level structures are made by trees of things.

For example, a polygon is a thing that has its contours as children (the first contour is the outer contour and the subsequent ones are holes). Contours, in turn, are things that have vertices as children, defining their path.

In a WorldEditor document, a taxiway is a cluster of things with various IDs; to rebuild the full geometric information of a taxiway (which is a polygon) you need to use the parent-child relationships and look up the contours and vertices.

For WorldEditor, the in memory representation is exactly this schema, so the cost of building our polygons in our document is zero. We just build our objects and go home happy.

This seems like a win!  Until...

Changing the Data Structures

As it turns out, polygon has contours has vertices is a poor choice for an in-memory model of polygons. The big bug is: where are the edges??? In this model, edges are implicit - every pair of vertices defines one.

Things get ugly when we want to select edges.  WorldEditor's selection model is based on an arbitrary set of selected things. But this means that if it's not a thing, it can't be selected. Ergo: we can't select edges. This in turn makes the UI counter-intuitive. We have to go to bind-bending levels of awkwardness to pretend edges are selected when they are not.

The obvious thing to do would be to just add edges: introduce a new edge object that references its vertices, let the vertices reference adjacent edges, and go home happy.

This change would be relatively straight forward...until we go to load an old document and all of the edges are missing.

The Cost of Serializing Data Structures

The fail here is that we've serialized our data structures. And this means we have to parse legacy files in terms of those data structures to understand an old file at all. Let's look at all of the fail. To load an old file post-refactor we need to either:

• Keep separate code around that can rebuild the old file structures into memory in their old form, so that we can then migrate those old in-memory structures into new ones. That's potentially a lot of old code that we probably hate - we wouldn't have rewritten it into a radically different form if we liked it.*
• Alternatively, we can create a new data model that can exist with both the layout of the old and new data design. E.g. we can say that edges are optional and then "upgrade" the data model by adding them in when missing. But this sucks because it adds a lot of requirements to an in-memory data model that should probably be focused on performance and correctness.

And of coarse, the old file format you're dealing with was never designed - it's just whatever you had in memory dumped out. That's not going to be a ton of fun to parse in the future.

When Not To Serialize

The moral equivalent of this problem (using the container structures that bind together objects as a file format spec) is dumping your data structures directly into a serializer (e.g. boost::serialize or some other non-brain-damaged serialization system) and calling it a "file format".

To be clear: serializing your data structures is totally fine as long as file format stability over time is not a design goal. So for example, for undo state in WorldEditor this isn't a problem at all - undoes exist only per app run and don't have to interoperate between any instance of the app (let alone ones with code changes).

But if you need a file format that you will be able to continue to read after changing your code, serializing your containers is a poor choice, because the only way to read back the old data into the new code will be to create a shadow version of your data model (using those old containers) to get the data back, then migrate in memory.

Pay Now or Pay Later

My view is: writing code to translate your in-memory data structure from its native memory format to a persistent on disk format is a feature, not a bug: that translation code provides the flexibility to allow your in-memory and on disk data layouts change independently - when you need to change one and not the other, you can add logic to the translator. Serialization code (and the more automagic, the more so) binds these things together tightly. This is a problem when the file format and the in-memory format have different design goals, e.g. data longevity vs. performance tuning.

If you don't write that translation layer for the file format version 1, you'll have to write it for the file format version 2, and the thing you'll be translating won't be designed for longevity and sanity when parsing.


* We had to do this when migrating X-Plane 9's old binary file format (which was a memcpy of the actual airplane in memory) into X-Plane 10.  X-Plane 10 kept around a straight copy of all of the C structs, fread() them into place, and then copied the data out field by field. Since we moved to a key-value pair schema in X-Plane 10, things have been much easier.

The OpenGL Impedance Mismatch

As graphics hardware has changed from a fixed function graphics pipeline to a general purpose parallel computing architecture, mid-level graphic APIs like OpenGL don't fit the execution model of the actual hardware as well as they used to.

In my previous post, I said that the execution of GL state change is deferred so that the driver can figure out what you'r really trying to do and efficiently change all state at once.

This has been true for a while. For example, older fixed function and partly programmable GPUs might have one set of register state to control the entire fixed-function raster operations.  Here's the R300 (e.g. the Radeon 9700).

• The blend function and sources share a single register, but
• The alpha and RGB blend function/sources are in different registers (meaning a single glBlendFuncSeparate partly updates both).
• Alpha-blend enable shares a register with the flag to separate the blender functions. (Why the hardware doesn't just always run separate and let the driver update both sides of the blender is a mystery to me.)
• Some GL state actually matches the register (e.g. the clear color is its own register).

So the match-up between imaginary ideal GL pipeline and the hardware isn't perfect. But in the end, the fit is actually pretty good:

• Fixed function tricks like blending and stenciling are enabled by setting registers on the GPU.
• Uniforms for a given shader live on the chip while the shader is executing.
• The vertex fetcher is fixed functionality that is set up by register.

There's a lot written about AMD's Graphics Core Next (GCN) architecture, the GPU inside the Radeon 7900 and friends.  Since GCN GPUs are in both the X-Box One and Playstation 4 and AMD is reasonably loose with chip documentation and disassembling compilers, we know a lot about how the hardware really works.  And the fit...is not so snug.

• Shader constants come from memory (this has been true for a while now) - this is a good fit for a UBOs but a bad fit for "loose uniforms" that are tied to the shader object.  On the GPU, the shader object and uniforms are fully separable.
• Vertex fetch is entirely in the shader - the driver writes a pre-amble for you.  Thus changing the vertex alignment format (but not the base address) is a shader edit!  Ouch.
• For shaders that write to multiple render targets, OpenGL lets us remap them via glDrawBuffers, but this export mapping is part of the fragment shader, so that's a shader edit too.

Those shader edits are particularly scary - this is a case where we (the app) think we're doing something orthogonal to the shading pipeline (e.g. just setting up a new VBO) but in practice, we're getting a full shader change.

In fact, the impedance match makes this even worse: if we're going to have any hope of changing state quickly, the driver has to track past combinations of vertex layout, MRT indirection, and the actual GLSL linked program, and cache the "real" shader that backs this combined state.  Each time we change the front-end vertex fetch format or back-end MRT layout, the driver has to go see if that combination exists in cache.

The back-end MRT layout isn't the worst problem because we are hopefully not going to change rendering targets that frequently.  But the vertex format is a real mess; every call to glVertexAttribPointer potentially invalidates the vertex layout; the driver can either try to heavily check state change, or regenerate the shader front-end; both options stink.

You can see OpenGL trying to track the moving target of the hardware in the extensions: GL_ARB_vertex_array_object was made part of core OpenGL 3.0 and ties up the entire vertex fetch plus base pointer in a single "object" for quick recall.  But we can see that this is now a pretty poor fit; half of the state that the VAO covers (the layout) is really part of the shader, while the other half (the actual address of the VBO plus offset) is separate.*

A newer extension, GL_ARB_vertex_attrib_binding, separates the vertex format (which is part of the shader in hardware) from the actual data location; it was made part of OpenGL 4.3. I don't know how good of a fit this is; the vertex attribute binding leaves the data stride out of the "expensive" format binding.  (My guess is that the intended implementation is to specify the data stride as a constant in a constant buffer somewhere.) In theory with this extension, only glVertexAttribFormat requires an expensive shader patch, and applications can change VBO sources without calling it.

If there's an executive summary here, it's that OpenGL as an API has never been a perfect representation of what the hardware is doing, but as the hardware moves toward general purpose compute devices that work on buffers of memory, the pipeline-and-state model fits less and less.

In my next posts I'll take a look at Metal and Mantle - these new APIs let us take the red pill and see how deep the rabbit hole goes.


* I am of the opinion that VAOs were a mistake from day one.  VAOs are mutable to allow them to be 'layered' on top of existing code the way VBOs were, and even if they weren't, the data location of the VBO is mutable at the driver level (because the VBO may at the time of draw be in VRAM or system memory, and may require a change to the memory map of the CPU that the GPU holds to draw, or it may require a DMA copy to move it to RAM).  The result is that binding a VAO doesn't let you skip the tons of validation and synchronization needed to actually start drawing once the base pointers have been moved.

You May Not Be Able To Update A Texture In A Thread

It took me a while to understand why this was the case - thanks to Chris for helping me wrap my head around it. Here's the deal: you may not be able to update an existing texture from a thread without getting "white flashes". I discovered this the hard way while working on X-Plane's texture pager but only recently understood why the OpenGL specification makes this so.

In a previous post I described the technique to update OpenGl textures on a thread by creating a new texure, flushing, and then using an atomic operation to "swap" the active texture ID for the rendering engine.

But this begs the question: why not just use glTexSubImage2D to update the texture on the fly and save all of that effort?

So first: if you can use glTexSubImage2D and you don't need mip-mapping, you can, maybe. You won't be able to guarantee which texture the main rendering thread uses unless you are willing to block the main thread (which you don't want to do). It's possible that the main thread could grab an old version.

I say maybe because: the gl spec allows you to do this kind of on-the-fly update for operations that change the contents of memory but not the layout of memory. So you are counting on the GL to not reallocate memory when you sub-texture. One would hope this is the case, but I have never tried it on Windows. I don't think the spec is very clear about when texture operations change memory.

The gl spec also requires glFinish (or the newer fence/sync APIs in OpenGL 3.2) to guarantee your changes take effect. In practice you really only need a flush on current drivers, but I don't know if this will continue to be the case - the flush is enough because current drivers are serialized at the command-to-GPU level, but one would almost hope that this bottleneck goes away.

Before we're done with glTexSubImage2D, we must note that your mip-maps can't all be updated at once unless you are using some kind of auto-mipping extension, so if you manually push mipmaps then you might have a case of inconsistent texturing due to old and new mipmaps being mixed.

What if you can't use glTexSubImage2D? (For example, X-Plane won't use glTexSubImage2D in about 16 different cases to work around driver bugs we've hit over the years.) Then you have a real problem.

The problem is that a texture object is not complete until all of its mip-map levels are complete and its texture parameters have been set. Until then, using it will give you white textures.

But you cannot atomically specify the entire texture object without blocking the main thread.

This is exactly what went wrong with my original implementation of on-the-fly texture updating: I would re-texture the largest mip level (using glTexImage2D) which promptly invalidated the texture, and then the main thread (which was not blocked) would flash white until the rest of the mip-map could be rebuilt.

It is for this reason that I suggest the atomic-operation double-buffering technique. It lets you build your mip-map levels in peace and guarantees consistent rendering, e.g. you always use the old or new texture.

As a final note, my implementation will delete the old texture from a thread after the atomic swap. This is a little bit dangerous if I read section D.1.2. of the spec correctly. From what I can tell, the object should still be valid to use if it is bound (e.g. until I unbind everywhere, we're okay) but the texture ID can be recycled quickly, so theoretically it might get updated mid-use, which would be undesirable.

If the goal is to guarantee a non-blocking rendering thread, a better design would be to "send" the dead objects to the main thread via message queue where they can be deleted in between frames; this would let memory bubble up just a little bit more.

C++ Objects Part 8: The Cost of Virtual Methods

In my last post I covered dynamic casts and ambiguous base classes. This will be my last post on C++ object memory layout: the cost of using objects.

In truth I will only look at the cost of method calls - I will operate under the assumption that using a C++ object is like using a struct from a data-access standpoint, which is mostly true; you can see from past posts that virtual base classes represent containment by pointer while non-virtual base classes are contained by, well, containment, so you can imagine the costs involved.

Before getting into this, one overarching note: in my experience working on X-Plane, effective function inlining is much more important to the rapid execution of performance-critical C++ code than any of the overheads here. In particular, all of these examples assume that inlining has not occurred. The loss of inlining is a much larger cost than the additional pointer references, glue calls, etc. that we'll see.

The compiler can only inline a function when it knows exactly what will be called. Any time we have polymorphism, that goes away, because runtime data determines the call type. These examples are done with inlining and optimization off (mostly to keep the assembly code sane), but basically no call that requires a memory access before the function call to fetch an address can be inlined.

Test Cases

I wrote a stub of code to look at free functions and function pointers (to look at the cost of call-via-memory), virtual functions, and virtual base classes. In all cases I wrote a stupid stub program and let CodeWarrior disassemble the results.

Here's the C++:


static void an_func() { }

class foo {
public:
void non_virt() { }
virtual void virt() { }
};

class bar : public virtual foo { };


I have eliminated any arguments and return types, which avoids a lot of stack setup code that would otherwise make the examples harder to read in assembly. (We can't all be Larry Osterman. I agree with him 100%, but I suspect many programmers don't speak x86 as their first language.)

Here's the test environment:

foo f;
bar b;
void (* anfunc_f)() = an_func;
foo * ff = &f;
bar * bb = &b;

The optimizer is off - in real production code the optimizer may be able to share common setup costs for function calls. This exercise should demonstrate the total number of memory accesses required from a "cold start" to perform the function call.

Also please note: http://hacksoflife.blogspot.com/2007/04/wrong-side-of-war.html my x86 assembler sucks, so in some cases my explanation of what's going on may be sorely lacking.

Direct Function Calls:

Let's start with the simple case - a direct function call that hasn't been inlined.

C++:

an_func();

PPC:
0000001C: 48000001 bl .an_func__Fv
x86:
0x0000002c: E800000000 call ?an_func@@YAXXZ (0x31)


This is the simplest case - a direct function call to a known address - the destination is encoded in the program stream. In terms of my analysis I would say that this jump has a cost of "zero" memory accesses. Obviously the destination address comes from memory, but because it's in the program instruction stream, I expect that by the time we know we're going to branch, we hopefully know where too - no separate access to memory is needed.

Function Call Via Function Pointer

Before looking at this case, a brief tangent on the Mac: OS X for PowerPC, when using the CFM ABI (which happens to be the one I decompiled) uses an indirect function-pointer system called a "t-vector". Basically a function call outside of a single shared library (DLL) is called a "t-vector", and it's a pointer to the function pointer. The t-vector structure also contains additional state that is swapped in to registers as we make the call, effectively switching some runtime context per DLL. (This context is used to manage relocatable global variables - I'll comment on this more some other time.)

The reason I mention it is that a function call outside a DLL is more expensive than one inside a DLL for PPC CFM code. Why do I mention that? Because if we don't know what kind of function call we are going to make, the compiler has to use the expensive kind just in case we're jumping "long distance" into another DLL.

So starting with this case, we're going to start seeing a jump to "ptr_glue", which is a little assembly stub function that does the context switching, that is part of the C runtime.

Given the death of CFM and of the PPC on PCs, is any of this relevant? Only in this: if an ABI has both low and high cost function calls based on the amount of known information, calls through function pointers are going to involve the worst case, most conservative call mechanism (unless some kind of compiler intrinsic adds typing info to function pointers). So when we go to function-pointer calls, we may pick up some ABI overhead. In the case of CFM, the ABI overhead for a "cross-library" call is an extra memory indirection.

In this one case I'll list the PPC and Mach-O code:

C++:

anfunc_f();
PPC (CFM):
00000030: 7FACEB78 mr r12,r29
00000034: 48000001 bl .__ptr_glue
00000038: 60000000 nop

PPC (Mach-O):
00000030: 7FCCF378 mr r12,r30
00000034: 7D8903A6 mtctr r12
00000038: 4E800421 bctrl

x86:
0x00000031: FF55F0 call dword ptr [ebp-0x10] near


A few notes on this:

• The x86 code is actually the most intuitive here - a subroutine call with indirect addressing via a memory location somewhere on the stack (or wherever ebp is aimed right now).
• Because the PowerPC has so many registers, for very small snippets (or a very good compilers), local variables almost always happen to be in register near the time they're needed. So while you can't see the memory load in the PowerPC code (r29 and r30 just happen to have our function pointer in them) they certainly didn't get loaded for free. The compiler has basically just made my local "anfunc_f" varible a "register" variable.
• The PPC will, under some conditions which I've forgotten and am too lazy to look up, call the function immediately after a branch. In some cases the compiler must insert a nop into this slot if it can't be used. I will omit the nops from now on, as they don't tell us much.
• ptr_glue is our C runtime code that will make our "long distance" call. But a bl to ptr_glue with the destination address in r12 is approximately like a subroutine-call to the address stored in r12. (x86 hackers, the general purpose registers for PPC are named r0-r31 - they're all the same and all hold 32-bits on the 32-bit PPC chips).

The cost of a call to a function pointer is thus:

• One extra memory access.
• Any cost for a "long distance" function call based on the ABI.

That memory access might be notable because the memory access must be completed before the instruction stream can be continued. I don't know how well modern CPUs can pipeline this of course, but a cache miss could be expensive.

Non-Virtual Method

Non-virtual methods are basically free functions with some compiler renaming and an implicit pointer to the object as their first argument. (That's how they know what "this" is.) So this will look almost the same as our free function call except that we're going to see the stack get set up a little bit. These functions are fully known so they are candidates for inlining.

(Another PPC hint: arguments on the PowerPC are passed by register starting with r3 when possible.)

C++:

ff->non_virt();
PPC:
00000020: 7FC3F378 mr r3,r30
00000024: 48000001 bl .non_virt__3fooFv
x86:
0x00000034: 8B4DF8 mov ecx,dword ptr [ebp-0x8]
0x00000037: E800000000 call ?non_virt@foo@@QAEXXZ (0x3c)



So - the cost of a non-virtual method is comparable to a direct call to a free function.

Virtual Method Call, Fully Known Object Type

Virtual functions are essentially function pointers that live in a side-table. But if we make a virtual function call and the compiler is 100% sure at compile time of the type of the object, it isn't required to call through the vtable. (Calling via the vtable doesn't have any affect on program correctness as long as we end up calling the right function.)

C++:

f.virt();
PPC:
00000028: 80620000 lwz r3,f(RTOC)
0000002C: 48000001 bl .virt__3fooFv
x86:
0x0000003c: B900000000 mov ecx,offset ?f@@3Vfoo@@A
0x00000041: E800000000 call ?virt@foo@@UAEXXZ (0x46)


So the cost of a virtual method may be as low as a non-virtual method. But I wouldn't count on this. For example, CodeWarrior will generate this optimization for a virtual method defined in a base class and called on the base class, but for a reason that I am not sure of (probably I've missed some subtlety of C++) it won't call a virtual method defined in a base class and called on a derived class that does not override it.

Virtual Method Call Via Object Pointer

This is a true virtual method call - when we have a pointer to the object, we don't know what the runtime type will be, and we actually have to use those vtables.

Truly a virtual function call - since we have a ptr the compiler doesn't know the real type. Now we start to pay a little more for virtual functions.

• Transfering r30 to r3 - this is copying the "this" pointer.
• Copying whatever is pointed to by r3 to r12. This is dereferencing the first word of the object to get the address of its vtable. One memory access.
• Copying whatever is pointed to by r12+8 to r12. This is going to the vtable and pulling up the 3rd ptr. (Before our virtual function is the type-id and offset info.) Two memory accesses.
• We see pointer-glue again here. This is just the Mac's idea of a far function call.

So - the cost in total of using a virtual function via a pointer to the object is:

• Two extra memory reads.
• Any cost of far function calls.

So a virtual method is more expensive than a function pointer, by one memory indirection. If you wanted to optimize this out, you'd put function pointers into the object itself, and pay for the decreased memory chaining with larger object size. The vtable is a layer of indirection.

C++:

ff->virt();
PPC:
00000030: 7FC3F378 mr r3,r30
00000034: 81830000 lwz r12,0(r3)
00000038: 818C0008 lwz r12,8(r12)
0000003C: 48000001 bl .__ptr_glue

x86:
0x00000046: 8B55F8 mov edx,dword ptr [ebp-0x8]
0x00000049: 89D1 mov ecx,edx
0x0000004b: 8B31 mov esi,dword ptr [ecx]
0x0000004d: 89D1 mov ecx,edx
0x0000004f: FF16 call dword ptr [esi] near


To be perfectly honest, I'm not really sure why the x86 code looks like it does. Reading these you might think we've got more memory accesses in the x86 code, but that's due to calling conventions - the PPC code can handle the argument entirely in registers.

Either way we've got two memory fetches:

• One to fetch the vtable ptr from the start of the object pointer.
• One to fetch the actual function ptr, eight bytes into the vtable (skipping the type-id and offset fields, each 32-bits wide).

So the cost of a virtual function call is two memory accesses and any long function call overhead. In other words, virtual function calls cost one more memory access than function pointers. (On the other hand, we save memory by not having the function pointer in every single object.)

Virtual Method Call With Virtual Base Class

When we have a virtual base, and our pointer type is of the derived class, we pick up one more memory access. The compiler must convert our derived pointer into the virtual base type, which requires following a pointer - a memory access.

(We will need the "this" pointer to be adjusted to the base type when we make the method call. The effective argument type of the virtual function must be of the most basic class that defines the virtual function, because this is the only type the "this" pointer could have that client code could set up consistently everywhere.)

I mention the need of the "this" pointer because it occurred to me that if the vtable of a derived class contained all of its base class virtual functions, perhaps we could avoid having to cast first, then start the virtual function. (My idea was: if we could do these memory lookups in parallel, instead of fetching from the last pointer we read, we wouldn't be serialized trying to get data out of memory.)

But alas my idea doesn't work. Remember that the layout of the vtable of a class with a virtual base will be controlled by the full class, and we have no idea what full class "bb" is. So if we wanted to start providing duplicate virtual method entries in bb's vtable, we would have to duplicate every virtual function in the virtual base for every single intermediate derived class. Suffice it to say, the vtables would get somewhat unwieldy. (Speculation: this blog article emphasizes the cost of memory indirections, but perhaps the real cost is cache misses. So keeping the code small and tight and having vtables be small is probably a win. Better 3 memory fetches to cache than 2 to RAM!)

C++:

bb->virt();
PPC:
00000044: 807F0000 lwz r3,0(r31)
00000048: 81830000 lwz r12,0(r3)
0000004C: 818C0008 lwz r12,8(r12)
00000050: 48000001 bl .__ptr_glue
x86:
0x00000016: 8B45F8 mov eax,dword ptr [ebp-0x8]
0x00000019: 8B5004 mov edx,dword ptr [eax+0x4]
0x0000001c: 89D1 mov ecx,edx
0x0000001e: 8B31 mov esi,dword ptr [ecx]
0x00000020: 89D1 mov ecx,edx
0x00000022: FF16 call dword ptr [esi] near


So the cost of a virtual method call through a base class is three memory indirections and a long distance function call - one more indirection than if the base is non-virtual.

Final Thoughts: Examining the ABI

There were three techniques I used to find this information:

1. The C++ runtime for CodeWarrior is available in source, so I was able to examine the source code and its comments.
2. I disassembled simple code and also dumped run-time memory for simple code.
3. In CodeWarrior, at least, you can replace run-time functions with your own code (if you know the "secret" names of the helper functions and, with the right compiler settings, get a link warning, not a link error. This allowed me to add a lot of tracing to the runtime pretty easily.

(If CW 8's debugger worked on OS X 10.4 worked, which it does not for me, I could have stepped through the code and runtime and dumped memory from there. But the debugger is really only a convenience tool for the two true debugging methods, printf and /* */.)

C++ Objects Part 6: Ambiguous Base Classes

An ambiguous base class is a base class that is included in a derived class twice. Because you can't just derive from a class twice, this usually happens by having parent classes who both derive from the same class without virtualizing that common base.

The storage implications of ambiguous base classes are relatively simple. Because each parent class's memory layout contains the base, we know where the two bases will be in memory - we simply apply our pattern for inheritance via containment recursively.

class R { };
class B1 : public R { };
class B2 : public R { };
class D : public B1, public B2 { };

gives us

struct R {
vtable * vt;
};

struct B1 {
R base;
};

struct B2 {
R base;
};

struct D {
B1 base;
B2 base;
};

Thus we have two instance of R: obj.base1.base and obj.base2.base reference each copy of R.

Static casts are casts that can be computed knowing only compile-time information - that is, casts that don't require knowing the full class of the casted object.

A static cast from D to R is illegal because it is ambiguous. Do we want R via B1 or B2? We don't know, and because the cast is static the compiler knows we don't know at compile time and generates an error.

If you cast to B1 first and then R it is legal - you have disambiguated. (This should not be surprising - if we simply had an object of type B1, casting to R would work! Remember, memory layout doesn't change with type!)

Static casts give us compile-time checking of all casts for ambiguity - we always know what we are getting. Next I'll cover dynamic casts and ambiguous base classes, which are more complex.

C++ Objects Part 5: Virtual Base Classes

A virtual base class is a class that is included only once in your derived class no matter how many base classes refer to it. How does this happen?

The answer is two-fold:

First, the actual layout of a class with a virtual base depends on the full class. Consider this case:

class R { };
class B1 : public virtual R { };
class B2 : public virtual R { };
class D : public B1, public B2 { };

In this case R is a virtual base that is included twice in D. The location of R will be different for B1, B2 and D. Each time one of these classes is set up, R is placed in the class once. Since R cannot be in D twice, clearly the location of R relative to B1 and B2 can't be the same when B1 or B2 is the final class vs. D. (If both B1 and B2 took R with them, we'd have two copies in D, which is not acceptable!)

To get around this, we hit the second part of our answer: classes contain pointers to their virtual bases. With non-virtual containment, bases are contained, e.g. a fixed chunk of the derived class's memory is used for the base class. With a virtual base, the derived class simply contains a pointer to the base class. This lets us move R around and adjust the pointer to R (in B1 or B2) at runtime in a way that lets us use different memory layouts for R with various classes that contain B1 or B2.

It should be noted that in D while there is only one copy of R, there are multiple pointers to R - one in B1 and one in B2. This is what assures that the memory layout of B1 and B2 don't change when they are used in a derived class. Only the contents of the layout of B1 and B2 change. The compiler generates code to set up these pointers for us.

For CodeWarrior, pointers to virtual bases come before the pointer to the vtable. This means that to find the vtable we have to know how many virtual bases a class has. Fortunately this information is dependent only on class info that is available at compile time - it never changes.

Here's a C version of what we have above:

struct R {
R_vtable * vtbl;
// R data
};

struct B1_partial {
R * vbase;
B1_vtable * vtbl;
// data for B1
};

struct B1_final {
B1_partial self;
R vbase;
};

struct B2_partial {
R * base;
B2_vtable * vtbl;
// data for B2
};

strut B2_final {
B2_partial self;
R vbase;
};

struct D {
R * vbase;
R vbase_data;
B1_partial base1;
B2_partial base2;
};

One of the interesting things to note here is that B1 and B2 as included in D are not as large as B1 and B2 when used by themselves. This is because B1 and B2 must have storage for the virtual base R at their end when used by themselves. But when used in D, that storage is provided by D.

Now we can see why dynamic cast first goes to the most derived base. Given a ptr to R we have no
idea where the rest of the object is -- position of R varies with the actual final type - that is, the relative position of R in the object is not the same relative to B1 if the real object is B1 or D.

Fortunately the vtable of any object tells us where the final object's real start is. So when R is a virtual base, depending on its final type, it will refer to a vtable that takes into account the actual full class's layout, letting us recover the full type and figure out the true relationship between the virtual base and the whole object.

Note that a static down-cast from a virtual base will cause a compiler error. This is the compiler telling us that it can't even speculate what the memory layout of the virtual base in the final class might be without inspecting the real type at runtime. But dynamic down-casts and even cross-casts are legal, since all dynmic casts are a maximum down cast followed by a possible up-cast.

C++ Objects Part 4: typeid and casts

Now that we have described how multiple inheritance in CodeWarrior C++ works, we can look at how casting and type works in C++. We needed to discuss multiple inheritance first; recall from part 2 that for single inheritance, the "front" of an object in memory is its base. With this system, no work is needed at all to cast when we have only one base class.

For the purpose of this discussion, "full class" means the actual class of an object when it is instantiated - in other-words, the "biggest" downcast we can apply - it's real class.

Please also remember from our previous post that an object that inherits from two base classes has at least two vtables with different layouts. Clearly a pointer to a vtable is not a unique identifier of an object's class, if one object can have two different vtable pointers of different values.

So instead CodeWarrior creates a separate static structure for each class that uniquely identifies it: a type_info structure. This shouldn't be surprising - this is the same structure that you can use with the typeid operator. That is if you do this:

D obj;
const std::type_info& t = (typeid(obj));

"t" is a pointer to the internal type_info structure for class D that is used by the runtime for all operations that require typing. (t is a pointer - it looks like a reference in the C++ code, but in truth they are one and the same to the compiler.)

Every vtable starts with a pointer to a type_info structure, identifying the full type of an object. When an object has two vtables (as in our multiple inheritance case), both vtables point to the same type_info structure. No two classes will ever share a vtable (even if a derived class never overrides any member functions) so this is okay. Because both vtables point to the same type_info, we can get our full runtime class for an object no matter which base we have a pointer to.

Static Casts

With this in mind, let's look at static casts. A static cast is a cast between C++ class types whose effects are fully known at compile time. That is, the compiler uses compile-time type information to change the type (and possibly the pointer value) for an object. The compiler looks at the layout in memory of the base class and the derived class and adjusts the pointer as much as is needed. (When we have only one base class, a static cast will not need to adjust the pointer at all, because the base class is always first in memory.)

There are some casts that cannot be performed statically at all, but we will get to this later. Also, we can't check whether the cast is safe at compile time. If we have a pointer to X that we cast to type Y but the object is not actually of type Y, the compiler will not care and we may crash later.

Full Class and Offsets

When we first introduced the layout of a vtable we mentioned that there is an "offset" right after the type_info. But what is this offset?

The offset in a vtable is the number of bytes that a pointer to an object whose type uses this vtable must be adjusted to find the full class of the object.

So in our case where we have two bases, each embedded somewhere in a class, the vtable of each base contains the offset to recover the full object. Note that one vtable will probably have an offset of 0, and this vtable is the one we will use for the "full" class, so that we never adjust the pointer when we already have the full class.

(As far as I can tell, CodeWarrior layers all static vtables for a class consecutively, so when given a pointer to the first one, it can actually generate calls into any vtable, because their relative positioning is fixed.)

Dynamic Casts

A dynamic cast converts the type of an object using run-time information. The cast returns NULL if the object can't be viewed as a given type. Since dynamic casts look at the object at run-time and can see the full class of the object, they can perform casts that we can't do using only compile-time information.

(Consider a DLL that returns an object of some unknown type, but as a pointer to a base type. Without run-time type information, the compiler has no idea what real type that object is, because it doesn't have the source code. In practice even if we did have the code, the compiler can't track that object's pointers through all of the strange things C++ can do to memory.)

A dynamic cast works by examining the type_info structures of an object and using that information to perform the cast. So to understand dynamic casts, we'll need to look a the type_info structure.

The type_info structure contains a pointer to a static string that names the class - all dynamic casts will use class string-name comparisons to find equivalent type. It then contains a pointer to a "null-terminated" variable-length array of info about base classes. Each item in this array contains a pointer to the type_info of a base class (if this pointer is null, that indicates null termination) and an offset indicating how much the pointer to the full object must be adjusted to cast to this type.

It should be noted that this list of base classes contains all bases, not just immediate bases! In other words, if we have a class Z that derives from Y and Y derives from X, the array of base classes for Z contains X and Y! This means that with a single linear search of the list, we can find any possible base. We do not have to search the entire tree.

(As a side note, each type_info's array contains pointers to parents, so you can follow the chain of inheritance from type_info to type_info. As far as I can tell in CodeWarrior there is no recording of which bases are "immediate bases", as you never need this info in C++. Perhaps the order of the bases in the list would tell us but I am not sure.)

Dynamic cast is therefore a two-step process:

1. Given the vtable of a pointer to an object, use the offset to recover a pointer to the full class. (All adjustments will then be made from this pointer.) This is the equivalent of down-casting to the full class.

2. Search the type_info of the full class for the type we want - in other words, go through a list of all bases. If we find one, use the offset to adjust the pointer again. If the search in step 2 fails, return NULL.

(I am leaving out ambiguous base classes - we'll cover that later!)

C++ Objects Part 2: Single Inheritance

In my previous article I described the basic layout of a C++ object in Metrowerks CodeWarrior, with a pointer in the object to a static table of function pointers and a class description structure. Now we can look at how single inheritance is implemented.

Simple inheritance is, well, simple: the derived class simply contains the first class at the beginning and new data later in memory. The same thing is true for the vtable - new entries are tacked on the end.

(Please note that this is not true for virtual base classes - I'll get to that later.)

This meets our rule: a pointer to X must be laid out the same. Since derived class Y contains X at its beginning, the first bytes of Y look like an X.

Here's subclassing from the last post...

class bar : public foo {
virtual void b(float); // ovrrride
virtual void new_method(int);
char * new_member;
};

virtual base class - only one copy of the base no matter how we derive. How?

struct bar_vtable {
foo_vtable parent;
void (* new_method_func)(int);
};

void bar_b(float);
void bar_new_method(int);

static type_id bar_type_id = { ... };
static bar_vtable sbar_vtable = { &bar_type_id, 0, foo_a, bar_b, bar_new_method };

struct bar {
foo parent; /* superclass goes first. */
char * new_member; /* then new members. */
};

Note that a new vtable is made for the derived class, which may contain a mix of functions - here we have the "a" virtual function from the superclass, an overridden "b" function (bar_b, an override, goes into a slot in foo's vtable), and then a new virtual function in the end.

In fact, bar_b in a slot in a foo_vtable is where the "magic" of overrides happen. This is what lets us call a method from a foo * and get a method from a bar object. Because an object points to its classes vtable, we get that class's behavior.

C++ Objects Part 1: Basic Object Memory Layout

I spent a few minutes dissecting the C++ internal runtime structure for objects within Metrowerks CodeWarrior. There's some internal guts that C++ generates when you make objects; the format is not standardized between compilers, but looking at one implementation reveals some of the costs and implications of C++ objects and inheritance.

C++ breaks objects with methods down into data structures and functions, with function pointers used for virtual functions. Polymorphism depends on our ability to apply fixed unchanging code to diverse data structures and get meaningful execution. Therefore we can immediately postulate one rule that applies to all objects, no matter what C++ feature is used (inheritance, multiple inheritance, virtual base classes, etc): the in-memory layout of a pointer to class X must have a fixed layout no matter what real derived type the object has.

I'm only going to describe the case where objects have virtual functions and run-time type information. Based on the actual code and compiler settings, the compiler may sometimes eliminate these features, changing the in-memory structure, but that's a topic for another blog entry.

CodeWarrior (like virtually all C++ compilers, no pun intended) implements virtual methods via virtual function tables (vtables), which are static structures containing one function pointer for each virtual function. An object has a pointer to its class's vtable before any other object data; there is only one copy of the vtable per class - it's immutable and shared. (This makes objects smaller than having pointers to each virtual function in the actual object.)

The virtual function table actually contains two more entries before the function pointers: a pointer to a "type ID" structure, a separate structure that describes the class itself, and a memory offset whose use we'll look at later. So if we have this C++ code:

class foo {
virtual void a(int);
virtual void b(float);
int c;
float d;
};

The equivalent C code would look something like this:

struct foo_vtable {
typeid * type_id_ptr;
int offset;
void (* ptr_to_a)(int);
void (* ptr_to_b)(float);
};

void foo_a(int) { }
void foo_b(float) { }

static type_id foo_type_id = { ... };
static foo_vtable sfoo_vtable = { &foo_type_id, 0, foo_a, foo_b };

struct foo {
foo_vtable * vtable; // gets inited to &sfoo_vtable
int c;
float d;
};

Class type is stored separately - first ptr in the v-table. Motivation for this will be clear later.
Vtable has an offset - also understood later.

Virtual Base Class - Not Needed for Interfaces

I was going to argue that virtual base classes are logical for interfaces, because we really only need each interface once. E.g.:

class IDeletable {
public:
virtual void delete()=0;
};

class IDrawable : public virtual IDeletable {
public:
virtual void Draw()=0;
};

class ISerializable : public virtual IDeletable {
public:
virtual void Serialize()=0;
};

void PersistentDrawing : public virtual IDrawable, public virtual ISerializable {
};

Turns out we don't need to virtualize the base classes. Virtualizing the base class is used when we have multiple copies of the base class inherited from different objects and we don't want actual copies of the base class.

But Don Box points out in "Essential COM" that this isn't necessary. In particular because the interfaces are truly empty - only a virtual function table, there is no harm in having multiple copies of them in an object. The virtual functions will be overriden correctly even if that base is represented multiple times. (The memory layout for this is moderately surprising, but I'll comment on this some other time.)

Why Not Binary Blobs?

I am working on the data model for WorldEditor, the X-Plane graphical scenery editor. At risk of "life blogging" the development, the design decisions for WED illustrate some design ideas.

WED uses C++ objects to represent the user's data in memory (the "internal data model"). I'll comment at another time on why I made this decision. On disk, however, WED uses an SQLite database file. That's another blog post too.

So one must ask the question, why do we need an on-disk data-model at all? Why not just dump out the C++ object contents to a file?

One might say "because you can't write STL classes to disk verbatim due to their internal pointers and private structure." But...WED uses an object-based undo system that requires each object to know how to serialize itself to a buffer...this means that we've already written serialization code for all of those STL structures.

It would make development faster to just reuse the object serialization code, but the result would be a file format that is a side-effect of the implementation code. This isn't good if:

• You want to edit the data from another application without having code interdendencies or
• You want to refactor the code (which would cause object layout to change) or
• You want to read a subset of the data. (The in-memory structure is, well, in-memory, so it assumes you have access to everything.

The problem is that using object serialization code is designing a file format - but without doing any of the usual work you might do in designing a file format.

In the short term you save time on writing file I/O code, but as soon as you change the object format you must write new code to read the old file format, so you pay the "cost" of that code eventually -- but you must write this code against a file format that wasn't really "designed" at all.

In particular with WED, we want the file format to be stable and low-change over a long period of time, because the kind of data that might be in a WED file can be useful over a relatively long lifetime.

Given this, I am writing an explicit file format up-front rather than use the object serialization mechanism.

Fun with casts

Chris and I were discussing casting this morning…in particular consider this:

class B1 {
public:
int b1_var;
};
class B2 {
public:
int b2_var;
};
class D : public B1, public B2 {
public:
int d_var;
};

This is an example of multiple inheritence. Now for a quiz:

D * d_obj = new D;
void * v = d_obj;
B1 * b1 = (B1 *) v;
B2 * b2 = (B2 *) v;

Now the question is: which of these pointers is safe to use? The answer is: on the compiler I tested (CodeWarrior and probably a number of others, b1 is safe, b2 is not. But I wouldn’t trust b1 either - the programming techique isn’t a good idea!

The problem is that the address of an object and its base sub-object can only be the same for one base of a class. You can think of the C++ compiler as doing something like this:

class D {
int b1_var;
int b2_var;
int d_var;
};

In other words, it stacks up the memory layout of the derived class with the bases inside it so that they are equivalent. But clearly B1 and B2 can’t both have that handy first memory slot in D. The compiler handles this for you by automatically changing the pointer value when you cast. For example:

B1 * b1 = d; // This is safe!
B2 * b2 = d;

This is perfectly legal - in CodeWarrior the first statement assigns the address of D to b1. The second statement adds a few bytes to D and assigns it to b2, such that b2 points to the B2 subobject within D.

The reason the cast from a void * fails is that when casting between a class and an untyped pointer, the compiler cannot correctly adjust the pointer for inheritence. The result is that b1 and b2 have the same actual value as d - no cast involving a void * will change the address.

Making things even more confusing, the cast operator in C++ does 3 different casts. C++ provides explicit named versions: const_cast, reinterpret_cast, static_cast (and dynamic_cast, but this behavior is never available via a C-style cast). I recommend using the C++ casts since they make it clear what the code intends to do and makes you the programmer think about which cast you really want. (C casts are static casts when possible, but reinterpret_casts otherwise…very dangerous!)

The moral of the story is: if you are going to cast to void *, be sure to cast back to the exact same type!