Type Erasure in C++ Explained
blog.the-pans.com
blog.the-pans.com
Have a look at std::any : https://en.cppreference.com/w/cpp/utility/any/
you can place a value of any type T in it (well, obviously it needs to be constructible etc.), or a std::nullopt, which is like an "Empty" or "Nothing" indicator that is not in T.
Then you can pass the `any` around without knowing its type. Finally, when you want to restore the typed value, you use any::get<T>(). It will succeed if T is the correct type, and throw an exception otherwise.
This was introduced into C++ in the C++17 version of the standard. Before, it existed as a Boost library facility.
for (auto x : vec) { x.foo(); }
As far as I know (I don't really follow the committee work) the latest attempt to introduce run-time duck-typing in the standard was https://github.com/andyprowl/virtual-concepts, which seems dead.
> run-time polymorphism (type erasure)
I would argue that it's the first rather than the second.
Modern software development in a nutshell.
But we're also moving in the other direction, for example Java is introducing value types ("inline classes") and low-level memory allocation/manipulation APIs. That's a big step for a language that started with the idea of everything is an object (and an object is an indirection).
I work with some of the most brilliant people in the world (in my opinion) and the problems we are working on are how to grab peoples attention and show them relevant ads. And we don’t call them “ads” but recommendations.
Sorry I’m working right now and wondering what I’m doing with my life.
I’m waiting for the day that someone figures out and does a blog post showing that every std data structure can be rewritten with type erasure.
Here’s how it works:
Let’s use vector because it’s simple. This vector impl works with just plain void* memory with no type information.
The vector type wrapper (matching std::vector) is a template but instead of recreating the entire data structure with a different type, it will instead create the void* implementing vector in a unique_ptr and pass boiler plate functions so that the vector know how to: 1. the size of T 2. in place constructor of T at the void* 3. in place destructor of T at the void* 4. A copy constructor of T at void* src, dst.
The wrapper vector<T> that owns the vector impl then does the necessary casts back to T. For example vector::at could be implemented as such:
<template typename T>
class vector { // type wrapper.
T& at(size_t i) {
void* p = vector_impl_->get(i);
T* t = static_cast<T*>(p);
return *t;
}
...
}
This can be extrapolated to complex algorithms like std::map. And as a bonus the polymorphic wrapper can do all the boiler plate generation so that the interface could be made to match the std::map.
Testing the bloat size reduction could be performed on a code base with significant usage of std map across multiple types, and see if the optimizing compiler will reduce the final binary size with the type erased map swapped in.
Uhhhh, gonna have to disagree there.
2. The run time semantics is ugly. Let's see:
"Now if we pass our Bar1 to foo it will first implicitly construct a Bar object with a pointer to BarWrapper<Bar1> when bar.doSomething() is called inside foo, it will trigger vtable lookup and find BarWrapper<Bar1>::doSomething which then calls Bar1::doSomething which is exactly what we want."
Which reads to me like:
"Now if we pass our Bar1 to foo it will first wastefully construct an overhead object, with a pointer to overhead, when bar.doSomething() is called inside foo, it will trigger overhead lookup to find some overhead wrapper which then finally calls the piece of code which is exactly what we want."
By the time you've done all this, a dynamic language function call starts to look good.
Sure, as written, there is lots of overhead, because it will copy `t` (by my count) three times, plus do a heap allocation, every time you call `foo`. The heap allocation part might make sense if you're planning to store the type-erased object somewhere and then use it repeatedly. The copying part makes no sense, though it's understandable, because C++ is terrible and makes copying the default.
But the general pattern of implementing type erasure using a wrapper object is sound, and can be made zero-overhead or near-zero-overhead depending on the use case. Here is a simple version where the wrapper object just stores a pointer (making it suitable for cases where the function doesn't store the object beyond its own execution):
https://gcc.godbolt.org/z/hEWv1hqEo
In this case, the `Bar` object is passed to `foo` as two registers, a function pointer and the pointer to the object itself. `Bar::doSomething` is inlined into `foo`, and `Example::doSomething` is inlined into `Bar::doSomethingWrapper<Example>`, so it winds up with `foo` calling a function pointer that leads directly to the implementation of Example::doSomething.
If `Example::doSomething` couldn't be inlined, `Bar::doSomethingWrapper<Example>` would likely be compiled as a single instruction jumping to it, which is quite minimal overhead.
I'll get back to you when my work projects are allowed to use a C++ version newer than C++11. </rant>
But, more seriously: I'm curious if so few people are actually using C++20 (for work, at least) that it will take a while to answer questions like yours.
In many business, many coders learn just enough to get the job done and never care about moving forward with their knowledge unless obliged to do so.
When doing contracting where one gets to jump into random codebases just for a couple of months, it is quite sadding the quality of code that we routinely find out.
It is like playing Mikado with code.
With C++ you're basically always at a point where you only know a little, even if you've worked on your C++ skills for years... :-P
Bare bones strcpy() and memcpy(), pointer arithmetic all over the place without helper functions to validate application invariants, #ifdef spaghetti code, not using translation units as poor man's modules,...
Ugly as hell, ouch! Really?
GNU C++ had something called signatures years ago, which was removed. It was far more elegant.
You could declare a signature which was a class-like thing: function declarations in curly braces.
Having that signature declared, you could lift a pointer of that type to any object which had those functions (without any relationship to the signature having to be declared by that object).
Found a nice document on it:
https://csc.lsu.edu/~gb/Signatures/index.html
So, here is how the code would look:
class Bar { // nothing to inherit here
public:
void doSomething() { }
};
signature Do {
void doSomething();
};
void foo(Do &doer)
{
doer.doSomething();
}
int main()
{
Bar bar;
foo(bar);
}
Sure, the implementation has to bend over backwards. But signatures are more declarative, so the implementation has a clearer idea of your intent. It can do whatever magic is required.
It seems clear to me that there is a static way to bind the Do signature reference to the Bar type. You probably have to construct some vtable like object which does the right sort of indirection.
The translation unit could emit some hidden __Do__Bar_table item which does exactly that: it's a vtable-like table made in the shape of Do, which is filled with pointers (perhaps fat pointers with offsets and whatever is necessary) to the matching functions in Bar.
If that can be set up at compile time, then maybe the Do &doer argument just has to be some sort of fat reference consisting of the pointer to bar, and to the __Do_Bar_table which translates the Do calls into Bar calls.
It seems cheaper than the convolution presented in this article.
Signatures didn't make it into ISO C++, but since that time, a lot of cruft has which is worse.
Looks like this 1999 commit may be what removed signatures:
https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=6eabb2412f6c4c...
It doesn't point to any information about the removal. We probably have to dig into mailing lists. At least it gives a date, thanks to which we can find this posting. Unfortunately, the one from which it quotes is missing for some reason:
https://gcc.gnu.org/pipermail/gcc/1999-August/035433.html
"This patch removes support for `signature', a g++ extension that is little-used and which Jason and I agreed should go. The reduction in complexity elsewhere in the front-end will be a big win."
OMG, you would absolutely not see this today in C++ development. "Jason and I" decided that some C++ gadget is too little used and we will remove it.
How naive that seems; these people had no idea about the deluge of garbage that was coming down the pipe into standard C++ over the following two decades, that they would have to implement.
They removed a good thing on a whim.
They're both missing the Indiana `concept_map` which were runtime-free functors -- like -- proper functors.
What is the added value? What is the cost? Virtual methods are not free. Indirections are not free (when you read the code)
What it achieves is exactly erasing the type (conforming to an affordance). The cost is definitely there. You pay vtable lookup when using std::function.
If you do have that problem, the alternative is to write an adapter or wrapper by hand. You may regard this as an improvement, or not, depending on your specific circumstances.
After all, Inheritance Is The Base Class of Evil (https://www.youtube.com/watch?v=2bLkxj6EVoM).
Inheritance is just fine, used well. You've got a counterargument? Give it. Not a video; give me the actual argument.
The summary is in https://www.youtube.com/watch?v=2bLkxj6EVoM&t=1275s
Sure, inheritance is fine, I use it all the time. If it were that bad we would already have Virtual Concepts in the standard. But duck-typing is better, if only because the argument you already gave: "lets you treat things that aren't from the same class hierarchy as if they are from the same hierarchy". It's a lie that I want something that inherits from my class, I simply want something I can draw() with, but we keep telling that lie all the time... which sure, is not the end of the world.
Why am I not going to watch it? Well, how long is the video? 5 minutes? 30 minutes? An hour? Two hours? But it took me 30 seconds to read your post here. (I'm hoping that the last paragraph was a summary of the video's argument.) Even if it took you five minutes to write, your five minutes plus my 30 seconds is still a big win compared to a half-hour video.
But we're on a public forum. If 10 people, or 100, have to go watch the video to figure out what your point is, that gets really inefficient. Which is why I yell at people - not just you - about making the readers do the work to figure out what the poster is talking about.
> But duck-typing is better, if only because the argument you already gave: "lets you treat things that aren't from the same class hierarchy as if they are from the same hierarchy".
Right; duck typing is better when you have that problem. But in 25 years of using C++, I have never had that problem. So I'm pushing back on you stating "duck typing is better" like it's a universal. It's not.
> It's a lie that I want something that inherits from my class, I simply want something I can draw() with, but we keep telling that lie all the time...
Sometimes I want more than that. I want something I can draw() that also satisfies the constraints of my class, at which point I do want something that inherits from my class, which makes it not a lie.
Look, this approach has its place. That place is not everywhere, but a more limited set of places. I don't have a problem with people using this approach. I don't have a problem with people teaching others how to use this approach. I have a problem with people talking like this is the one right way. It's not.
You never used types such as std:: function?