MSVC (Microsoft's C++ compiler) had an pretty advanced inter-procedural (LTO) way of doing devirtualization, but it was so buggy and slow that it eventually got disabled. It was trying to prove that a pointer can only target a certain class all the time (or maybe a couple), but things get really messy with typical C/C++ code and even worse once you have DLLs which may inject new derived classes.
I think this is unfortunately wishful thinking, a lot of code is still written with traditional inheritance. It just makes unit testing with mocks much easier.
Conclusion: devirtualization optimization is so fragile, so that it's better to avoid using virtual calls in performance-critical code to be sure, that no virtual call happens.
The big problem with virtual calls is it hinders inlining, but if you design your API correctly that can usually be optimised away by design (put loops inside the call, don't call inside a loop)
Putting loops inside virtual functions can't work in any cases. Like when a heterogenous collection is iterated and a virtual call is performed for each object.
In such cases I prefer using std::variant instead of inheritance, but this works only if all possible types are known ahead of time.
It's the same problem with autovectorization. Often the only way to tell whether a compiler optimization is successful is to check the produced assembly or benchmark the code.
It seems that for devirtualization GCC has a warning option -Wsuggest-final-types which is supposed to tell when devirtualization fails in link-time optimization. Not sure how reliable that is, or whether it will produce gobs of unhelpful warnings. Maybe it could be combined with some kind of hint that we want this particular call to be devirtualized, and don't care about calls without the hint.
I also wonder what about devirtualization of dyn traits in Rust. Sure, impl traits like foo<T: AsRef>(bar: T) or foo(bar: impl AsRef) is for sure devirtualized, but foo(bar: &dyn AsRef) or most likely foo(bar: Box<dyn AsRef>), far as I remember, isn't always devirtualized. Sometimes it does, sometimes it doesn't. I wonder if it is MIR that did it, or just completely handed off to LLVM for detection.
Dynamic dispatch seems to be way less popular in Rust than C++. Presumably because it has worse ergonomics (you have to add `Box` everywhere) whereas in C++ the opposite is true (you have to deal with templates).
No. You don't have to add Box everywhere. You do need dynamic storage that is not guaranteed to be known in compile time. Box is just one of them, you can also use "thin box" or "stacked box" or a good ol' "&mut dyn T" would also do great. It basically means a construct of this object with this trait and solved on dynamic dispatch. In C++ that is virtual/pure virtual function.
I ran into a fun crash a year or so ago in the interaction of clang’s profile guided speculative devirtualization and identical code folding (ICF) done by BOLT on the binary.
Clang relied on checking the address of a function pointer in the vtable to validate the class was the type it expected, but it wasn’t necessarily the function that is currently being called. But due to ICF two different subclasses with two different functions shared the same address, so the code made incorrect assumptions about the type. Then it promptly segfaulted.
For comparison, Java will devirtualize calls if the call site typically calls only a single type. To the extent that writing a byte to a ByteBuffer, which looks like five or six virtual calls if you follow the java source code, actually ends up being a single assembly store instruction.
Would Pete get made fun of if he couldn't explain the difference between a member function and a method and why this distinction matters in C++ more than using the term understood everywhere else?
Nice post, I had never thought about those tricky ways of proving leafness outside of the obvious "final".
Re "When we know the dynamic type", I made a similar assertion on HN years ago, and of course it turned out that there's a weird wrinkle:
If the code in your snippet is expanded to:
Derived d;
Base *p = &d;
any_external_func(); // Added
p->f();
where any_external_func() is defined in some other translation unit (and, I'm now fairly sure, Derived's ctor is also defined in another translation unit, or it transitively calls something that is), this would seem not to affect anything -- but in fact the compiler must not assume that p's dynamic type is still Derived by the final line. Why? Because the following insane sequence of events might have happened:
1. d's ctor registers its this pointer in some global table.
2. Using this table, any_external_func() calls d's dtor and then overwrites it in place with a fresh instance of Base using placement new, which replaces everything, including its vtable, meaning that p->f() should call Base's version, not Derived's.
(It might be UB to call placement new on static or automatic storage holding an in-lifetime object, I don't know. If so, the above construction is moot -- but the closely analogous situation where we instead dynamically allocate dp = new Derived() still goes through, and is nearly as surprising.)
The compiler is still able to devirtualize and inline the p->f() call, even with an external linkage call preceding it. https://clang.godbolt.org/z/jE3o56ozz
I’ve been programming C++ on and off for over 20 years and have had my moments where I’ve checked on godbolt to make sure classes got devirtualised.
This year, I’ve finally taken the plunge to properly learn Rust (I’ve used it for little things over the years, but never for anything particularly extensive) and one thing that jumped out at me is that you don’t need to think about it, because Rust makes it explicit: everything is statically known unless you explicitly ask for it to be virtual.
[edit: since it wasn’t clear, I mean polymorphism in rust is static by default while in c++ static polymorphism requires relying on the compiler or using templates, otherwise polymorphism is via virtual]
It’s was a little annoying at first because some things don’t just work automatically, but once I got used to it, it was wonderful to never have to think about when the compiler might do something. You also don’t need dynamism most of the time.
I still like tinkering in C++, but I do find you need to know too much about compiler heuristics.
I don’t see how that’s relevant when discussing specific language features or semantics, nor how it’s relevant to what I said about Rusts static polymorphism. Nobody is claiming C and C++ didn’t make great contributions or that they aren’t still heavily used.
In C++, you can’t have an interface without virtual unless you jump through hoops.
In rust, you can have traits without dyn.
That is, static polymorphism is the default in rust, while in c++ you must jump through hoops for it (eg, see the excellent EnTT’s static polymorphism companion library).
I feel like it’s still missing the point. In a discussion about devitalisation, I thought it was interesting that it’s not something that you have to think about in Rust, while in C++ you do.
30 comments:
MSVC (Microsoft's C++ compiler) had an pretty advanced inter-procedural (LTO) way of doing devirtualization, but it was so buggy and slow that it eventually got disabled. It was trying to prove that a pointer can only target a certain class all the time (or maybe a couple), but things get really messy with typical C/C++ code and even worse once you have DLLs which may inject new derived classes.
Maybe just me, but doesn't most C++ code being written today not use inheritance very much, and so make virtual dispatch moot?
Only on conference slides maybe, real production code looks quite different, including game engines like Unreal and Godot.
CUDA frameworks, V8, LLVM and GCC, you name it.
It's still the most convenient way to implement type erasure, so no.
There are codebases out there that don’t use a lot of TMP and prefer Java-like type management.
To each their own, but yeah, your experience matches mine.
90's C++ you mean, a decade before Java came to be, and responsible for famous books like GoF.
The GoF book came out in 94, and Java in 95.
I think this is unfortunately wishful thinking, a lot of code is still written with traditional inheritance. It just makes unit testing with mocks much easier.
Conclusion: devirtualization optimization is so fragile, so that it's better to avoid using virtual calls in performance-critical code to be sure, that no virtual call happens.
The big problem with virtual calls is it hinders inlining, but if you design your API correctly that can usually be optimised away by design (put loops inside the call, don't call inside a loop)
Putting loops inside virtual functions can't work in any cases. Like when a heterogenous collection is iterated and a virtual call is performed for each object.
In such cases I prefer using std::variant instead of inheritance, but this works only if all possible types are known ahead of time.
It's the same problem with autovectorization. Often the only way to tell whether a compiler optimization is successful is to check the produced assembly or benchmark the code.
It seems that for devirtualization GCC has a warning option -Wsuggest-final-types which is supposed to tell when devirtualization fails in link-time optimization. Not sure how reliable that is, or whether it will produce gobs of unhelpful warnings. Maybe it could be combined with some kind of hint that we want this particular call to be devirtualized, and don't care about calls without the hint.
I also wonder what about devirtualization of dyn traits in Rust. Sure, impl traits like foo<T: AsRef>(bar: T) or foo(bar: impl AsRef) is for sure devirtualized, but foo(bar: &dyn AsRef) or most likely foo(bar: Box<dyn AsRef>), far as I remember, isn't always devirtualized. Sometimes it does, sometimes it doesn't. I wonder if it is MIR that did it, or just completely handed off to LLVM for detection.
Dynamic dispatch seems to be way less popular in Rust than C++. Presumably because it has worse ergonomics (you have to add `Box` everywhere) whereas in C++ the opposite is true (you have to deal with templates).
No. You don't have to add Box everywhere. You do need dynamic storage that is not guaranteed to be known in compile time. Box is just one of them, you can also use "thin box" or "stacked box" or a good ol' "&mut dyn T" would also do great. It basically means a construct of this object with this trait and solved on dynamic dispatch. In C++ that is virtual/pure virtual function.
I ran into a fun crash a year or so ago in the interaction of clang’s profile guided speculative devirtualization and identical code folding (ICF) done by BOLT on the binary.
Clang relied on checking the address of a function pointer in the vtable to validate the class was the type it expected, but it wasn’t necessarily the function that is currently being called. But due to ICF two different subclasses with two different functions shared the same address, so the code made incorrect assumptions about the type. Then it promptly segfaulted.
For comparison, Java will devirtualize calls if the call site typically calls only a single type. To the extent that writing a byte to a ByteBuffer, which looks like five or six virtual calls if you follow the java source code, actually ends up being a single assembly store instruction.
> final method
A pedantic Pete would mention C++ has member functions.
Would Pete get made fun of if he couldn't explain the difference between a member function and a method and why this distinction matters in C++ more than using the term understood everywhere else?
Go Pete!
Whats the difference between a member function and a method?
Nice post, I had never thought about those tricky ways of proving leafness outside of the obvious "final".
Re "When we know the dynamic type", I made a similar assertion on HN years ago, and of course it turned out that there's a weird wrinkle:
If the code in your snippet is expanded to:
where any_external_func() is defined in some other translation unit (and, I'm now fairly sure, Derived's ctor is also defined in another translation unit, or it transitively calls something that is), this would seem not to affect anything -- but in fact the compiler must not assume that p's dynamic type is still Derived by the final line. Why? Because the following insane sequence of events might have happened:1. d's ctor registers its this pointer in some global table.
2. Using this table, any_external_func() calls d's dtor and then overwrites it in place with a fresh instance of Base using placement new, which replaces everything, including its vtable, meaning that p->f() should call Base's version, not Derived's.
(It might be UB to call placement new on static or automatic storage holding an in-lifetime object, I don't know. If so, the above construction is moot -- but the closely analogous situation where we instead dynamically allocate dp = new Derived() still goes through, and is nearly as surprising.)
The compiler is still able to devirtualize and inline the p->f() call, even with an external linkage call preceding it. https://clang.godbolt.org/z/jE3o56ozz
I’ve been programming C++ on and off for over 20 years and have had my moments where I’ve checked on godbolt to make sure classes got devirtualised.
This year, I’ve finally taken the plunge to properly learn Rust (I’ve used it for little things over the years, but never for anything particularly extensive) and one thing that jumped out at me is that you don’t need to think about it, because Rust makes it explicit: everything is statically known unless you explicitly ask for it to be virtual.
[edit: since it wasn’t clear, I mean polymorphism in rust is static by default while in c++ static polymorphism requires relying on the compiler or using templates, otherwise polymorphism is via virtual]
It’s was a little annoying at first because some things don’t just work automatically, but once I got used to it, it was wonderful to never have to think about when the compiler might do something. You also don’t need dynamism most of the time.
I still like tinkering in C++, but I do find you need to know too much about compiler heuristics.
While Rust is a good improvement, without C++ there isn't Rust compiler, at least for the forseable future.
I don’t see how that’s relevant when discussing specific language features or semantics, nor how it’s relevant to what I said about Rusts static polymorphism. Nobody is claiming C and C++ didn’t make great contributions or that they aren’t still heavily used.
It is a heads up given how many Rusties downplay the role of C++ in the industry, including their own compiler.
> everything is statically known unless you explicitly ask for it to be virtual.
This is true in C++ also...
In C++, you can’t have an interface without virtual unless you jump through hoops.
In rust, you can have traits without dyn.
That is, static polymorphism is the default in rust, while in c++ you must jump through hoops for it (eg, see the excellent EnTT’s static polymorphism companion library).
Yes you can, you only need to adopt modern C++ with concepts, compile time execution and now compile time reflection.
I feel like it’s still missing the point. In a discussion about devitalisation, I thought it was interesting that it’s not something that you have to think about in Rust, while in C++ you do.