Fast Virtual Functions: Hacking the VTable for Fun and Profit
medium.com
medium.com
If virtual vs non-virtual function calls are causing you performance problems, you're calling way too many functions per frame. Batch the objects by concrete type and process them all in a loop.
https://gcc.gnu.org/onlinedocs/gcc/Bound-member-functions.ht...
Both Unreal and Unity make heavy use of per-instance per-frame virtual functions. It's a paradigm that has clear value. Why not make it cheaper at no cost to the dev? The option to take a systems approach to bottlenecks is the same afterwards.
It's a paradigm that had (debatable) value in the late 1990's and early 2000's when Unreal Engine and Unity had been designed and OOP was all the rage ;)
In the meantime we realized that not everything should in fact be an (OOP) object and runtime polymorphism is usually not needed to build games, even if the whole "animal => mammal => dog" classification thing at first sounds like it would be a good match to model game objects.
With runtime polymorphism it's like with memory management. If memory management shows up in profiling at all, it's better to drastically reduce the frequency of allocations instead of looking for a faster general purpose allocator (and if it doesn't show up in profiling as it should be, integrating a faster allocator doesn't make much sense either because it won't make a difference).
Of course stuff like this is not easy to do late into a project because it would involve a complete redesign of the architecture and rewriting all code from scratch - and that's why dropping in a faster allocator sometimes makes sense as a compromise, but it's not a fix for the underlying problem, just a crutch).
Also, the more important problem with indirect function calls than the call overhead is usually that they present a hard optimization barrier for the compiler.
For inheritance, I 100% agree. Composition all the way. I think it has value as an interface though - at least for quick bring up and fast iteration. It can of course bring scaling challenges - I recently worked on a project that had hundreds of devs and more than 50k game components. That brought all of the architectural and performance challenges you'd expect from this approach.
> Also, the more important problem with indirect function calls than the call overhead is usually that they present a hard optimization barrier for the compiler.
In the years I've had to think about this, I'd take a slightly different approach that should be more amenable to compiler optimization. I'd maintain separate lists for each concrete type and have a type aware process function (via templates) which requires all overrides to be marked final. That should allow the compiler to do inlining, avoid indirections, etc. The major downside here is handing over a footgun to the dev - forget that final keyword or pass the object in not as concrete type and performance will suffer. I'd probably still walk the vtable to see if a function has been overridden - it's unfortunate that there doesn't seem to be a way to do this without resorting to such tricks.
Firstly, I think the graph in your article shows no advantage except with a cold cache. I agree with this, and think we probably disagree on how likely a "cold cache" is, or how to model that when thinking about a program. I argue you should never bother.
In a game (or other realtime scenario that runs continuously) you understand that every "n" frames you are going to spill cache "m" times, and that because the game runs continuously "m/n" averages out on some value.
I have worked code that aims for m=0, and it's a little bit like superconductivity in some respects: strange things happen with your code when it looks like that, but remember that L1 is only 64kb so if your program gets any bigger than that or ever does a system call and jumps into the kernel (which is definitely bigger than that) then m= at least 1.
Microbenchmarks tend to be m=0 which makes working with them tricky. Real programs are usually at least m=1 and usually much much bigger: m=1 is still something like 100GB (gigabytes) per second.
Now through all that, it is tempting to try and think of m as the sum of latencies, but it's important to remember that the size of the code matters too: Those instructions have to be fetched from memory just like data does, so if your program gets too big (like can happen if you naively unroll every lookup table with its own function) m is going to get bigger faster than anything else. Look at objdump. Look at how big your program gets doing this. How many multiples of 64KB have you eaten with this trick? Each one of those is another m.
That is why this trick is almost certainly never worth it, and if you ever find a big codebase that benefits from a few strategic hoists of this technique I bet putting a prefetch intrinsic in the right place would help better.
It doesn't feel like there's "no cost to the dev" here because developers will still sooner or later need to understand the relevant code.
But the real penalty for using Virtual Calls is the potential loss of inlining. It depends on how smart your compiler is.
E.g. if you're making a graphics display driver, don't have objref->putpixel(x, y) as your only virtual function, which has to be called thousands of times to draw a line or millions to fill an area.
Why does C++ hate it's users so much?
Since you (in C++) can't cast between "sibling" types and expect it to work, that's enough - each new subclass has a vtable that shares the base with all classes inheriting from the same parent, but adds different sets of new virtual member functions.
In languages with interfaces, or that are more dynamic, you typically have tree common choices:
* Add a dispatch method and call that (really expensive, but extremely flexible)
* Add an indirection and put a pointer to a vtables for each interface in the main vtable (first place I encountered that was in a paper that named it "Protocol Extension" by Michael Franz, who implemented it for Oberon)
* Make the vtable include the superset of all possible methods. My (experimental, incomplete) Ruby compiler does that. It makes the vtables larger, and at some point you'll want to assign some methods to a slower but more compact path, but it works surprisingly well.
But none of those are needed for C++.
No. In fact in a few short months post C++11 will have overtaken pre-C++11 as the majority of the 26 year history of standardized C++ (and similar to prior standards, compilers for the fortunate implemented much of the behavior prior to the official publication).
that's because they switched to a different 'release cycle' for C++ standards, also now they have minor releases like C++14.
Final in C++ indicates that the function/class can no longer be overridden in further child classes. This enables devirtualization as the compiler can then know the function pointer will not change, if it can infer the type at compile time.
Writing Rust for a toy project: "I MUST avoid allocation, and the dyn keyword, at all cost!!"
Writing the same toy project in Python: "lol just copy the string who cares"
For me, there were two. First, I'm having to learn to code in the "Pythonic" style so my code will fit into existing projects. An example in a class I took was moving from while loops to for i in range(len(list)). While you won't forget to increment the counter, it felt like being so clever would reduce optimizations. Another project needed whole, string copies for conciseness vs a char-by-char algorithm that was highly-efficient. While it may be my inexperience, it seems like Pythonic style inherently favors conciseness and readibility standards over performance.
Second, the extensions seem tightly coupled with the CPython interpreter. I've read enough articles to know that's causing problems for people wanting to add capabilities. It may not matter, though, since most of us use Python for its ecosystem benefits. We can just switch tools when needed.
[Edit: You may have meant “when simple integer addition [in a scripting language] can take more time than allocation in a compiled language”, in which case sure, I agree. I had originally interpreted your statement as saying compiled languages can do allocation faster than they can do addition…]
Allocation in most environments I’ve seen involves keeping track of a “free list”, which does some amount of pointer chasing to find a contiguous section of memory that can fulfill the request. Deallocation drops the item from the list, etc. This can result in some fragmentation, and the segments of memory managed by the free list are less likely to be in cache because they’re somewhat dispersed compared to stack memory. Some environments have multiple free lists depending on the expected size of the allocated objects, to avoid fragmentation.
How could all this be faster than a single integer addition?
Also, even when both integers are small, Python usually has to do an allocation anyway to store the result.
The part that baffles me about this entire post is that it's trivial to obtain pointers to member functions legally, without the fragility associated with guessing VTable offsets.
struct Base { virtual void foo(); }
struct Derived: Base ( virtual void foo(); }
auto p = &Base::foo;
Derived d;
(d.*p)();
Consequently, an indirect call via pointer-to-member has to do the virtual/non-virtual check first, and then look up vtable by index if virtual, before performing the actual call. Which is in fact more work than doing the virtual call directly (since the first step is unnecessary in that case), and thus pointers-to-members cannot be used to optimize away the overhead.
Sure it can, you just need to have emitted separate functions for "concrete call" (the traditional one stored in the vtable) and "virtual call" (a bit of code that calls through the vtable).
If this is not done it's probably due to the fact that actually emitting the virtual calls involves more code than just storing the vtable index. But if anyone is implementing a new language I strongly suggest paying the cost anyway, for sanity.
If you emit a stub for each virtual member function that performs the vtable dispatch, at which point do you emit it? If you do it if and when the address is actually taken, then pointers to members in different compilation units will have different stubs (COMDAT folding can take care of this for static linking, but not for dynamic) - which means that &Foo::bar taken in one unit will not compare equal to the same taken in another, which is counter to the C++ specification.
Alternatively, you could emit such a stub proactively for each vtable entry on the basis that its address might be taken in another compilation units - but that means a lot of unused stubs.
The other problem is multiple inheritance combined with upcasting. Consider:
struct Base1 { ... }
struct Base2 { virtual void foo(); }
struct Derived: Base1, Base2 { ... }
void (Derived::*pf)() = &Base2::foo;
Derived d;
(d.*pf)();
If anyone is designing a new language, I strongly suggest not doing anything like C++ unbound member function pointers in the first place; the practical need for such a thing is very rare, since in most cases you want the pointer to be bound to a particular object (and then vtable resolution can be done at the point where the pointer is produced, rather than at the point where it's used). And, on the other hand, in those rare cases where such a thing is needed, it can be trivially done with closures if the language has those (and it should, given their much broader utility). If C++ had lambdas from the get go, I very much doubt that it would also have pointers to member functions.
To be clear to others: the problem appears due to the fact that `R (Base::*)(A...)` can be cast to `R (Derived::*)(A...)` (note the contravariance), not just at construction time but arbitrarily later. This is unfortunately special to the `this` argument; a sane language should allow contravariance of any function pointer argument. (this implies that, if you're emitting C code, all arguments should unfortunately be `Object ` to avoid illegal casts.
I actually disagree that closures fix this though - you can easily end up with deeply nested closures which are opaque so you can't optimize them out. Rather, just make unbound functions identical to free functions.
And yes, I agree that single-inheritance + traits (~ late interfaces, ~ external vtables, which turn out to be easier to think about inlining. You can't use instanceof though) is much saner than multiple-inheritance + ADL. Honestly, I'd say that ADL is C++'s worst mistake, since it intrudes upon every* function call you make, unlike most of the crazy stuff we're doing here.
Doing without single-inheritance is in fact viable but annoying, especially when porting code or programmers. Emulating single-inheritance in terms of traits can be done by splitting each class into a concrete struct + a trait (and aggregating the structs but inheriting the traits), but this requires manually forwarding all the unchanged virtual functions, and also trait pointers are fat which is often undesirable (except note that for small types you often don't want to pay for an embedded vtable pointer). Moving that back to a class inheritance system, however ... I've often thought it is quite useful to support both "pointer to class, virtually" and "pointer to class, final".
It would be trivial to optimize - as that would be a lambda of the form `[](Foo& foo, ...) { foo.bar(...); }` it can just be emitted as a free function with no closure, no matter how deeply nested it is. In fact, looking at it in Godbolt, it seems that compilers do this even when optimizations aren't enabled at all, probably because it's just the most obvious way to codegen.
Effectively, it just becomes a way to define a regular function in-place at the point where its address gets taken. In C++, such a lambda is even implicitly convertible to the corresponding plain function pointer type, so it's already unified with regular free functions on type system level.
Of course, you could then say that &Foo::bar is simply syntactic sugar for such a lambda. I think we agree that the important part here is to avoid having the special notion of pointers-to-member-functions in the type system; the rest is just a question of how to dress it up when you have a use case where you need one.
When downshifting to C, use opaque structs to hide private data and use regular function pointers. There are numerous examples of C VTables but these tend to be slow. When possible, don't use OOP or VTables because it's slow and more difficult to debug. Using plain functional and procedural architectures is much more robust, deterministic, testable, and easier to reason about.
I have mixed opinions about it.
Meanwhile, the Windows XP codebase had 45M LOC in 2011.
Truly big codebases need to be written in sane languages, mostly OOP ones. That excludes C, Zig and Rust.