8 ms·

Type Erasure in C++ Explained

43 points by aptxkid 5y ago

AlexanderDhoore 5y ago
"Well, let's just add another level of indirection." Modern software development in a nutshell.
- slver 5y ago
  Indirection is the price of scale. As a system grows, you need breaking points, boundaries. These often result in adding one more level of indirection. 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).
  - rwoerz 5y ago
    I would call indirection the price for abstraction.
- winstonchecksin 5y ago
  Modern software development is a convoluted mess of poor abstractions, new frameworks and flavors of the week, and essentially a million different ways of solving the same problem. 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.
- ChrisSD 5y ago
  Nothing modern about it. This is basically the C philosophy in a nutshell. Assuming "indirection" means "pointer indirection".
stephc_int13 5y ago
I am not sure this is an improvement. What is the added value? What is the cost? Virtual methods are not free. Indirections are not free (when you read the code)
- aptxkid 5y ago
  Well if this is an improvement or not depends on the use case. E.g. std::function does exactly this. 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.
  - nly 5y ago
    You're not wrong in any way, but interestingly, last I looked, common implementations of std::function didn't use virtual under the covers. Instead they re-implement something like the vtable to avoid unwanted extras, like RTTI, bloating your app size
- AnimalMuppet 5y ago
  It lets you treat things that aren't from the same class hierarchy as if they are from the same hierarchy. You probably wouldn't do this unless you had that problem. (And, in my entire career, I have never had this problem.) 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.
  - LaLaLand122 5y ago
    It's a strictly better solution. You don't do it because the standard library doesn't give you tools to do it easily, but if it were the same effort everybody would do it. After all, Inheritance Is The Base Class of Evil (https://www.youtube.com/watch?v=2bLkxj6EVoM https://www.youtube.com/watch?v=2bLkxj6EVoM).
    - AnimalMuppet 5y ago
einpoklum 5y ago
That's not how you do type erasure in C++. Have a look at std::any : https://en.cppreference.com/w/cpp/utility/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.
- aptxkid 5y ago
  However the Type Erasure described here doesn't need to know T even when you use it. E.g. it enables things like for (auto x : vec) { x.foo(); }
  - jhgb 5y ago
    Is this the thing that's called "Voldemort types" in D?
  - LaLaLand122 5y ago
    And if it were in the standard there wouldn't be at least five well known libraries implementing it (including from Adobe and from Facebook): https://github.com/boost-ext/te#similar-libraries https://github.com/boost-ext/te#similar-libraries 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 https://github.com/andyprowl/virtual-concepts, which seems dead.
    - einpoklum 5y ago
      At the link, the library description says: > run-time polymorphism (type erasure) I would argue that it's the first rather than the second.
  - einpoklum 5y ago
ok123456 5y ago
Wouldn't this particular example be better served through C++2a concepts? That is we can specify constraints about template type parameters.
- pjmlp 5y ago
  C++20, the standard has already been ratified.
- dataflow 5y ago
  Do people end up finding concepts useful? They seem nice in theory but I have yet to find a practical case where I want to reach for them. The errors aren't (at least currently) noticeably better than normal template errors, and they can end up being redundant in practice.
  - CoastalCoder 5y ago
    > Do people end up finding concepts useful? 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.
    - pjmlp 5y ago
      It is the same problem as with C, Java and Python. 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.
      - einpoklum 5y ago
        This is not really a problem in C, since there's little beyond the "just enough". But agreed about other languages. 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
zackees 5y ago
This article is not a good explainer of type erasure because it uses inheritance to do it. 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; } ... } In this example, vector<T> wrapper would still be inlined everywhere, however VectorImpl could be defined exactly once in a cpp file. The template bloat problem is reduced from the entire data structure to just the wrapper casting back and forth from void* <—> 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.
- adamrezich 5y ago
  wouldn't all of this templating lead to immensely increased compile times?
  - haneefmubarak 5y ago
    Template heavy C++ (which is a lot of nontrivial C++) DOES have immensely increased compile times hahaha. It's not too bad if you have a decent number of hardware threads and incrementally (re)build in parallel though.
  - edflsafoiewq 5y ago
cobaltoxide 5y ago
> But the result is beautiful. Uhhhh, gonna have to disagree there.
- aptxkid 5y ago
  LOL sure. I think it's arguably terrible behind the curtain. But the interface provided is pretty elegant IMO.
  - kazinator 5y ago
    1. Any piece of code that the program has to provide, rather than the implementation, is by definition in front of the curtain. 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.
    - comex 5y ago
      > "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." 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 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.
kazinator 5y ago
> But the result is beautiful. 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 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); } When foo is called with bar, a Do & signature reference is taken to bar. This is allowed because the type Bar has all the functions declared in the signature type Do, making it compatible. 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=6eabb2412f6c4c8306fb2f8fd05abf608e29caa9 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 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.
nyanpasu64 5y ago
I'm not sure whether Bar having a duck-typed constructor looking for the presence of a method is a good or bad idea, and I rather dislike how `Bar *` and `Bar &` requires a double-indirection to call its contents. It feels inefficient, but I don't know if it's actually slower in practice, and I haven't setup a benchmark to test. https://www.reddit.com/r/cpp/comments/cs9ue4/performance_benchmarks_of_type_erasure_methods/ https://www.reddit.com/r/cpp/comments/cs9ue4/performance_ben... looks interesting but there's a lot of data and I didn't look at the source code of the various benchmark cases.
rambojazz 5y ago
Wasn't this called "injection"?

43 points by aptxkid 5y ago

AlexanderDhoore 5y ago

"Well, let's just add another level of indirection." Modern software development in a nutshell.

slver 5y ago
Indirection is the price of scale. As a system grows, you need breaking points, boundaries. These often result in adding one more level of indirection. 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).
- rwoerz 5y ago
  I would call indirection the price for abstraction.
winstonchecksin 5y ago
Modern software development is a convoluted mess of poor abstractions, new frameworks and flavors of the week, and essentially a million different ways of solving the same problem. 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.
ChrisSD 5y ago
Nothing modern about it. This is basically the C philosophy in a nutshell. Assuming "indirection" means "pointer indirection".

stephc_int13 5y ago

I am not sure this is an improvement. What is the added value? What is the cost? Virtual methods are not free. Indirections are not free (when you read the code)

aptxkid 5y ago
Well if this is an improvement or not depends on the use case. E.g. std::function does exactly this. 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.
- nly 5y ago
  You're not wrong in any way, but interestingly, last I looked, common implementations of std::function didn't use virtual under the covers. Instead they re-implement something like the vtable to avoid unwanted extras, like RTTI, bloating your app size
AnimalMuppet 5y ago
It lets you treat things that aren't from the same class hierarchy as if they are from the same hierarchy. You probably wouldn't do this unless you had that problem. (And, in my entire career, I have never had this problem.) 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.
- LaLaLand122 5y ago
  It's a strictly better solution. You don't do it because the standard library doesn't give you tools to do it easily, but if it were the same effort everybody would do it. After all, Inheritance Is The Base Class of Evil (https://www.youtube.com/watch?v=2bLkxj6EVoM https://www.youtube.com/watch?v=2bLkxj6EVoM).
  - AnimalMuppet 5y ago

einpoklum 5y ago

That's not how you do type erasure in C++. Have a look at std::any : https://en.cppreference.com/w/cpp/utility/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.

aptxkid 5y ago
However the Type Erasure described here doesn't need to know T even when you use it. E.g. it enables things like for (auto x : vec) { x.foo(); }
- jhgb 5y ago
  Is this the thing that's called "Voldemort types" in D?
- LaLaLand122 5y ago
  And if it were in the standard there wouldn't be at least five well known libraries implementing it (including from Adobe and from Facebook): https://github.com/boost-ext/te#similar-libraries https://github.com/boost-ext/te#similar-libraries 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 https://github.com/andyprowl/virtual-concepts, which seems dead.
  - einpoklum 5y ago
    At the link, the library description says: > run-time polymorphism (type erasure) I would argue that it's the first rather than the second.
- einpoklum 5y ago

ok123456 5y ago

Wouldn't this particular example be better served through C++2a concepts? That is we can specify constraints about template type parameters.

pjmlp 5y ago
C++20, the standard has already been ratified.
dataflow 5y ago
Do people end up finding concepts useful? They seem nice in theory but I have yet to find a practical case where I want to reach for them. The errors aren't (at least currently) noticeably better than normal template errors, and they can end up being redundant in practice.
- CoastalCoder 5y ago
  > Do people end up finding concepts useful? 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.
  - pjmlp 5y ago
    It is the same problem as with C, Java and Python. 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.
    - einpoklum 5y ago
      This is not really a problem in C, since there's little beyond the "just enough". But agreed about other languages. 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

zackees 5y ago

This article is not a good explainer of type erasure because it uses inheritance to do it. 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; } ... } In this example, vector<T> wrapper would still be inlined everywhere, however VectorImpl could be defined exactly once in a cpp file. The template bloat problem is reduced from the entire data structure to just the wrapper casting back and forth from void* <—> 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.

adamrezich 5y ago
wouldn't all of this templating lead to immensely increased compile times?
- haneefmubarak 5y ago
  Template heavy C++ (which is a lot of nontrivial C++) DOES have immensely increased compile times hahaha. It's not too bad if you have a decent number of hardware threads and incrementally (re)build in parallel though.
- edflsafoiewq 5y ago

cobaltoxide 5y ago

> But the result is beautiful. Uhhhh, gonna have to disagree there.

aptxkid 5y ago
LOL sure. I think it's arguably terrible behind the curtain. But the interface provided is pretty elegant IMO.
- kazinator 5y ago
  1. Any piece of code that the program has to provide, rather than the implementation, is by definition in front of the curtain. 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.
  - comex 5y ago
    > "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." 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 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.

kazinator 5y ago

> But the result is beautiful. 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 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); } When foo is called with bar, a Do & signature reference is taken to bar. This is allowed because the type Bar has all the functions declared in the signature type Do, making it compatible. 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=6eabb2412f6c4c8306fb2f8fd05abf608e29caa9 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 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.

nyanpasu64 5y ago

I'm not sure whether Bar having a duck-typed constructor looking for the presence of a method is a good or bad idea, and I rather dislike how `Bar *` and `Bar &` requires a double-indirection to call its contents. It feels inefficient, but I don't know if it's actually slower in practice, and I haven't setup a benchmark to test. https://www.reddit.com/r/cpp/comments/cs9ue4/performance_benchmarks_of_type_erasure_methods/ https://www.reddit.com/r/cpp/comments/cs9ue4/performance_ben... looks interesting but there's a lot of data and I didn't look at the source code of the various benchmark cases.

rambojazz 5y ago

Wasn't this called "injection"?