Type checking in C and C++ is unarguably a useful tool provided by the compiler. But as with most tools there is a cost to using it. In this post I want to put forward the idea that we should carefully evaluate where we need types and where we can get away with erasing them and treating data as more-or-less opaque blobs. Specifically, I find types most useful on API boundaries of systems, but as soon as the boundary is crossed and we're dealing with data within a system, types may become more trouble than they're worth.
A lot of these solutions take inspiration in C because that language has the advantage of not having a lot of fancy syntax, yet being capable of solving all the problems we have (it's Turing complete after all). Many modern languages - C++ especially - get lost in the weeds and people using all the modern features tend to forget how to solve actual problems. Then you sometimes hear things like:
If only we had C++2x with templated lambdas, concepts, ..., then we could solve this or that problem
Anything you need to do is possible in C, it is good to go back there, solve the actual problem and then apply the amount of additional features giving you the maximum benefit for minimum cost. If most of your programming time consists of thinking about language features and standards I'd argue you've already lost, most of your time should be spent on solving actual problems, not making new artificial ones (or "solving" previously introduced artificial ones by adding to them).
Using types everywhere, all the way down in systems may seem like the most natural thing if we find typechecking useful and we're in a typed language. But that is attacking the beast from the completely wrong angle. Types are a made-up concept, they do not correspond to anything the CPU and computer do. We can see this immediately when we interact with a device directly, be it reading a file from disk or uploading data to the GPU. It's all just bytes (or pages/PCI-E packets). And that is where we should start, to keep ourselves honest. Types are useful only for a programmer and only as long as the benefit outweighs their cost of their usage.
To use types throughout a generic system in C++ means a strong usage of templates and possibly a strong usage of the STL (or re-implementing similar concepts like tuple and such). Metaprogramming in C++ is executed so poorly with many additional band-aids throughout the years. When you go through the pain of learning all the new cool tricks and implementing your system you'll end up with a magical piece of code which is unfortunately very rigid (contrary to popular belief), hard to modify, hard to debug, and hard to use in large part because of usually unclear API and terrible compiler error messages - the main reason we do this in the first place by the way is to get more help from the compiler. We would like to avoid all of this while retaining some useful type-checking if possible.
Let's first see what not to do - or what someone with too little experience (me in the past) may see as a great idea. ShaderProgram class I've written about eight years ago for a DX11 renderer. My brilliant idea was that on the C++ side, we would like to create a shader and bind buffers to it in a fully type-safe manner. The shader class would be fully typed and anytime we want to update a buffer we just say which type and magic happens which binds everything together. As soon as you have the temptation for magic to happen in your programs, maybe just don't, your co-workers and future self will thank you.
Anyway this is the class, it's of course a variadic template on the types of buffers. Funnily enough, you can see that the DirectX 11 API is already bringing me back to reality, it does not care about my types and forces me to use ID3D11Buffer*. If it had been up to me, this would have been typed for sure. The next interesting thing is updateConstantBuffer which is the "type safe" buffer update. To do it we need to find the matching buffer type. In C++ template land this means a recursive search through the tuple of types. Maybe you can do this better nowadays but that was the way I knew possible at the time. We have a bunch of structs with functions doing the magic I mentioned. I won't go into details, if you like you can decipher this, it's not too complex.
template<typename ... TCBuffers>
class ShaderProgram : public ResourceHolder {
typedef std::tuple<TCBuffers ...> types;
typedef std::array<ID3D11Buffer*, sizeof...(TCBuffers)> buffer_array_t;
buffer_array_t cbuffers_{};
template<int N, typename T>
struct BuffOfType : std::is_same<T, typename std::tuple_element<N, types>::type>
{ };
template<int N, typename TBuff, bool IsMatch>
struct MatchingBuff {
static ID3D11Buffer* get(buffer_array_t& arr) {
return MatchingBuff<N + 1, TBuff, BuffOfType<N + 1, TBuff>::value>::get(arr);
}
};
template<int N, typename TBuff>
struct MatchingBuff<N, TBuff, true> {
static ID3D11Buffer* get(buffer_array_t& arr) {
return arr[N];
}
};
template<typename TBuff>
struct GetBuffer {
static ID3D11Buffer* get(buffer_array_t& arr) {
return MatchingBuff<0, TBuff, BuffOfType<0, TBuff>::value>::get(arr);
}
};
// ... more internals here ...
public:
template<typename TConstBuffer>
void updateConstantBuffer(ID3D11DeviceContext* context, const TConstBuffer& newBuffer) {
auto buffer = GetBuffer<TConstBuffer>::get(cbuffers_);
context->UpdateSubresource(buffer, 0, nullptr, &newBuffer, 0, 0);
}
// ... more API here ...
};
The point here is that this is already quite involved and you can imagine the compile errors when you get something wrong. Same goes for changing the class or adding anything to it, the barrier is quite high, especially for people who don't regularly use these techniques. What did we get in return? We can update constant buffers of our shaders by type like so:
struct MyConstants
{
int x;
};
ShaderProgram<MyConstants> myShader;
void foo(ID3D11DeviceContext* ctx)
{
MyConstants constants{};
myShader.updateConstantBuffer(ctx, constants);
}
What have we lost? Aside from our sanity (although this code is quite tame, believe me), we've lost the ability to have multiple constant buffers of the same type and we added a lot of maintenance burden. We also did not get the type safety we are actually after, that would be to disallow mismatching types in shaders and in constant buffers we bind/upload. We missed the forest for the trees. The better solution here is to either "just bind things" which immensely simplifies the code, or for example to do a shader reflection and codegen to have shared types and explicit functions for the CPU based on the shaders. In any case, the solution is not templates.
Type erasure is a common technique where at some point we have a typed object in our code and instead of using the type we erase it by storing the object in an opaque blob of memory pointed to by void* for example. We sometimes also want to store the size and alignment of the object for operations like copying. For example:
void* foo(MyStruct* x)
{
// data is type-erased, we can still copy it and pass it around but we no longer know what type it was
// the point is, however, the caller may know and can safely downcast to the appropriate type
void* data = malloc(sizeof(MyStruct));
memcpy(data, x, sizeof(MyStruct)); // memcpy is an example of an API which is "type erased" since it works with memory
return data;
}
The bar set by C++ is so low that almost any other sane metaprogramming model would be better than what we have now but I'm not sure if there is any which would completely eliminate the utility of type erasure as I describe it here.
There are many examples to illustrate my point on, such as resource caches, task systems, pool allocators, ECS systems, render graphs, blackboards and many more. A common theme among them is that they are all quite generic systems working with various types of data but the systems themselves don't really care about what the data is. The system mostly stores and moves around the data when needed, it usually does not operate on the values. Any information about the data can be stored in associated metadata which could be for example flags for a task in a task system.
I took three examples and implemented them in the type-erased fashion. I should have implemented a fully typed counterpart for each of the examples but that feels absolutely masochistic towards me and sadistic towards anyone reading this. Also, I'm not even qualified to do so at this point as I don't write such code anymore (I just have to read it sometimes) and I'm not in the loop of all the new tricks.
⚠️ I'm not proposing these systems as good or bad. But they are common things you may encounter in the wild and want to improve or you may be asked to implement them. In which case some of this may come in handy. If you're already writing simple procedural C-like code this will probably be much less useful. Also, I cannot be bothered implementing this for RAII types, all the examples assume POD types and tend to skip unimportant details of the systems and implementations, they're there just to get the idea across but should be close enough to compile. I'm also not proposing you should start using void* across your code when you can of course. The point is to try to identify where it is useful to use types and where they come in the way.
Imagine a task system which takes arbitrary functors to execute later on multiple threads. Usage of the system should be as straightforward as possible.
void foo()
{
int x = 123;
HTask task = MakeTask(taskSystem,
// Note that we can freely capture here
[value = x](TaskContext* ctx) {
printf("in task! %d, Thread: %d\n", value, ctx->threadId);
return 0;
});
ScheduleTask(taskSystem, task);
WaitOnTask(taskSystem, task);
}
To make a task we pass in a lambda and get a handle to the task. The handle may be used in other operations such as adding dependencies, scheduling, or waiting on it. How do we implement this?
Probably the most drastic solution would be to store the actual types of the various lambdas you get into the system. But I think in this case even the modern C++ crowd would avoid explicit templates and use std::function to capture the functor for example. There is a better way though, one which takes inspiration from how we would solve this in C - with a type erased void* user context pointer.
struct TaskContext
{
int threadId;
};
using HTask = int;
using TaskFunction = int (*)(void*, TaskContext*);
struct TaskSystem
{
TaskFunction* tasks; // Our known type used to invoke the tasks
void** tasksMemory; // Type erase data we get from the user
int tasksCount;
};
template<class FunT>
HTask MakeTask(TaskSystem* taskSystem, FunT&& fun)
{
auto taskWrapper = [](void* taskMemory, TaskContext* ctx)
{
// This restores the type of the type-erased data
return (*(FunT*)taskMemory)(ctx);
};
// Type erasure happens here, all we need to know is size and alignment of the data
// this means the system does not know about any types, all the complexity is contained
// in this API function.
void* taskMemory = AllocTask(taskSystem, sizeof(FunT), alignof(FunT));
memcpy(taskMemory, fun, sizeof(FunT));
taskSystem->tasksMemory[taskSystem->tasksCount] = taskMemory;
taskSystem->tasks[taskSystem->tasksCount] = taskWrapper;
return taskSystem->tasksCount++;
}
The trick we're using here is maybe widely known, maybe not, but at least I know we independently discovered it with one of my colleagues (me for a task system and him for an event system I think). He coined the term in his blog post and since I don't have a better name we'll call it "Kihlander's reverse". Make sure to read the origin of that and the advantages over std::function at Fredrik Kihlander's blog1.
In short, we're erasing the type of our functor and storing this information implicitly in the internal lambda. Note that you can still use the fully C-API to this by not using any lambdas or templates, just make an overload of MakeTask which takes the actual function pointer and void* user context and there you go. This will be a common thread in this post. All the C++ on top of our solutions is completely optional. This also means our solutions tend to be fully data driven, this is not very useful in case of tasks but comes in handy when talking about allocators for example.
Pool allocators are simple enough with or without types, just take whatever "array type" you have and slap a free list on top of it. Done. What I want to show here is nothing more than that, just with the twist of having both a type-safe API and a fully data driven type-erased API.
struct PoolAlloc
{
// Info about the items we store
int itemSize;
int itemAlignment;
void* items; // Type erased items
int itemsCount;
// Simple free list
int* freeSlots;
int freeSlotsCount;
};
// Item handle
using HItem = int;
//------------------------------------------------------------------------------
// C-API
PoolAlloc* PoolAllocCreate(int itemSize, int itemAlignment);
HItem PoolAllocAdd(PoolAlloc* poolAlloc, void* data);
void* PoolAllocGet(PoolAlloc* poolAlloc, HItem item);
void PoolAllocFree(HItem item);
// ...
//------------------------------------------------------------------------------
// C++ API
template<class T>
class PoolAllocTyped
{
public:
void Create()
{
poolAlloc = PoolAllocCreate(sizeof(T), alignof(T));
}
HItem Add(T* item)
{
PoolAllocAdd(poolAlloc, item);
}
T* Get(HItem item)
{
return (T*)PoolAllocGet(poolAlloc, item);
}
// ...
PoolAlloc* poolAlloc;
};
// Usage
void foo(PoolAllocTyped<int>* alloc)
{
int x = 123;
HItem item = alloc->Add(&x);
int* xReturned = alloc->Get(item);
}
The class here is optional and could be replaced by a set of templated free functions but it ensures that the type we work with remains the same - we cannot accidentally Add one type and Get another. The free functions could do similar checking but at runtime (either on size and alignment of the elements or by automatically adding a custom typeid for example).
The advantage of this approach as opposed to having just a fully typed template is that if the items we get come from data, we just need to know their size and alignment. Maybe the items are material data in a material system used for rendering, which we would like to upload to the GPU as opaque blobs. The editor produces this data, saves it to disk, the runtime just loads it, does not care what it contains and uploads it to the GPU, the shader again knows what the data contains and interprets it correctly.
A blackboard is a concept I know from rendering (used for render graphs) and from AI agent systems where it's used by the agents to communicate. In essence it's a hashmap shared by all entities in the system to pass data. The key is usually a string (or not as you'll see) and the value is anything anyone would fancy. In C, this is trivial to implement, in C++ with a bit more type-safe interface it's not that much harder. Again, the system itself does not (and should not) need to know anything about the data it's storing, the only type-safety measures should be taken on the API boundaries.
ℹ️ This example could have been a resource cache as well, which is very similar in its concept. Both are serving as a big hashmap in essence. Specifically, in my first attempt at a game engine I've tried to write a resource manager which would be fully templated and would give you the resource from a cache based on the its type (needless to say I've spent a lot of time with this and I don't think I've fully succeeded anyway).
❌ A fully typed C++ API usage could look like this:
struct LightDir
{
Vec3 dir;
};
void foo()
{
blackboard->Set<LightDir>(LightDir{ Vec3{ 1, 2, 3 } });
Vec3 lightDir = blackboard->Get<LightDir>().dir;
}
I will not even attempt to show the implementation but the idea is that you push the types through the system all the way down using templates and the types are also the keys. However, since you're relying on types so much, you lose the ability to store two values of the same type and need to add many more types just for the sake of it. Also, the idea that the blackboard allows you to decouple systems - a system may look if a value is present and does not care who stored it as long as it's there and if it isn't, it may take a different path. If we use types, all systems which want to access the value need to share the type - we just added a shared dependency which was not there otherwise.
✔️ A type-erased version of this follows. Note that it removes the "type as an ID" requirement and instead uses string hashes as keys, if we wanted to we could still use types of course.
template <typename T>
constexpr u64 CustomTypeId() {
// return unique ID per type, just look around the web for implementations to avoid C++ RAII
}
struct BlackboardKeyValue
{
u64 key; // Hash of the string used as a key
void* value; // Type erased value
u64 typeId; // This is used to verify we store and load the correct type
};
struct Blackboard
{
struct Arena* arena; // Blackboard will be reset every frame just by resetting the arena
BlackboardKeyValue* hashMap;
// ...
};
//------------------------------------------------------------------------------
// C-API
// Add entry to the hashmap - key, value, typeId
void BlackboardSet(Blackboard* blackboard, StringHash name, void* value, int valueSize, int valueAlignment, u64 typeId);
// Retrieve entry from the hashmap based on the key, check typeid to make sure types match
void* BlackboardGet(Blackboard* blackboard, StringHash name, u64 typeId);
//------------------------------------------------------------------------------
// C++ API
template<class T>
void BlackboardSet(Blackboard* blackboard, StringHash name, T* value)
{
BlackboardSet(blackboard, name, value, sizeof(T), alignof(T), CustomTypeId<T>());
}
template<class T>
T* BlackboardGet(Blackboard* blackboard, StringHash name)
{
return (T*)BlackboardGet(blackboard, name, CustomTypeId<T>());
}
// Usage
void foo(Blackboard* blackboard)
{
StringHash lightDirName = HashString("lightDirection"); // This hash can be computed at compile time
// One pass
{
Vec3 lightDir{ 1, 2, 3};
BlackboardSet(blackboard, lightDirName, &lightDir);
}
// Another pass
{
Vec3* lightDir = BlackboardGet<Vec3>(blackboard, lightDirName);
}
}
The C-API in this example is a bit more type safe just to show a different approach. The main point as with all the other examples is that the underlying system is dead simple, easy to read, understand, and trivial to debug. The complexity is contained in the API functions and only if we want it. We can again make a fully C version without any typeid (or just pass 0 as typeid always).
ℹ️ If you're wondering what is the Arena in the Blackboard I encourage you to read an article from Ryan Fleury2 explaining the concept. He has also uploaded a talk on the topic3 if you prefer that format.
I hope the examples and reasoning illustrated how type-erasure can add flexibility and simplicity to systems by containing complexity where it's needed - on the API boundary. The examples are purposefully kept brief and unfortunately don't contain the templated couterparts but I think you'll know them when you see them in the wild, very often you will think magic when looking at the code. However, I would argue a lot of the time the crazy template usage magic is not even fully intentional, I think people just may not know there are simpler ways - it may be some fear of C, of void*, or just a lack of experience writing simple systems - I know I've walked that path as I've shown.
But in any case, the moral of the story here is to go back to basics (C in this case) and first principles, and try to solve the actual problem in a plain procedural manner before reaching for whatever new craziness and band-aids the C++ committee invented. You may be surprised how simple, understandable, and debuggable the code can become when analyzed and approached in this manner. If nothing else it's an interesting challenge to try I'd say. Anyway, programming is a never-ending learning process and it's important to always look for better solutions, I can only hope that in another eight years I will be able to look back and simplify this even further.
API design talk by Casey Muratori - https://caseymuratori.com/blog_0024
Fredrik Kihlander's post - https://kihlander.net/post/looking-at-c-for-better-closures-in-cpp↩
Arena allocator post - https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator↩
Arena allocator talk - https://www.rfleury.com/p/enter-the-arena-talk↩