News for hackers. Stuff that matters.
Re:The Performance Impact of C++'s `final` Keyword by chipdart on Tuesday April 23, 2024 @01:57AM (#40128945)
> What final enables is devirtualization in certain cases. The main advantage of devirtualization is that it is necessary for inlining.

I think that enabling inlining is just one of the indirect consequences of devirtualization, and perhaps one that is largely irrelevant for performance improvements.

The whole point of devirtualization is eliminating the need to resort to pointer dereferencing when calling virtual members. The main trait of a virtual class is it's use of a vtable that requires dereferencing virtual members to access each and every one of them.

In classes with larger inheritance chains, you can easily have more than one pointer dereferencing taking place before you call a virtual members function.

Once a class is final, none of that is required anymore. When a member is referred, no dereferencing takes place.

Devirtualization helps performance because you are able to benefit from inheritance and not have to pay a performance penalty for that. Without the final keyword, a performance oriented project would need to be architected to not use inheritance at all, or in the very least in code in the hot path, because that sneaks gratuitous pointer dereferences all over the place, which require running extra operations and has a negative impact on caching.

The whole purpose of the final keyword is that compilers can easily eliminate all pointer dereferencing used by virtual members. What stops them from applying this optimization is that they have no information on whether that class will be inherited and one of its members will either override any of its members or invoke any member function implemented by one of its parent classes.

With the introduction of the final keyword, you are now able to tell the compiler "from thereon, this is exactly what you get" and the compiler can trim out anything loose.

Re:The Performance Impact of C++'s `final` Keyword by simonask on Tuesday April 23, 2024 @02:21AM (#40129061)
An extra indirection (indirect call versus direct call) is practically nothing on modern hardware. Branch predictors are insanely good, and this isn't something you generally have to worry about.

Inlining is by far the most impactful optimization here, because it can eliminate the call altogether, and thus specialize the called function to the callsite, lifting constants, hoisting loop variables, etc.

Re:The Performance Impact of C++'s `final` Keyword by silvestrov on Tuesday April 23, 2024 @04:48AM (#40129864)
"is practically nothing on modern hardware" if the data is already present in the L2 cache. Random RAM access that stalls execution is expensive.

My guess is this is why he didn't see any speedup: all the code could fit inside the L2 cache, so he did not have to pay for RAM access for the deference.

The number of different classes is important, not the number of objects as they have the same small number of vtable pointers.

It might be different for large codebases like Chrome and Firefox.

Re:The Performance Impact of C++'s `final` Keyword by dblohm7 on Tuesday April 23, 2024 @01:25PM (#40134545)
Firefox has done a lot of work on devirtualization over the years. There is a cost.
Re:The Performance Impact of C++'s `final` Keyword by simonask on Wednesday April 24, 2024 @03:31AM (#40141665)
Both the number of objects (dcache) and the number of classes (icache) are significant, as well as the size of both, but yeah. It's pretty rare to have extremely wide class hierarchies, though. You really have to go out of your way to run into significant icache misses.
Re:The Performance Impact of C++'s `final` Keyword by ot1138 on Tuesday April 23, 2024 @09:51AM (#40131957)
I had a section of code which incurred ~20 clock cycles to make a function call to a virtual function in a critical loop. That's over and above potential delays resulting from cache misses and the need to place multiple parameters on the stack.

I was going to eliminate polymorphism altogether for this object but later figured out how to refactor so that this particular call could be called once a millisecond. Then if more work was needed, it would dispatch a task to a dedicated CPU.

This was an incredibly performant improvement which made a significant difference to my P&L.

Re:The Performance Impact of C++'s `final` Keyword by mgaunard on Tuesday April 23, 2024 @04:50PM (#40137095)
Could just be inefficient spilling caused by ABI requirements due to the inability to inline.

In general if you're manipulating values that fit into registers and work on a platform with a shitty ABI,you need to be very careful of what your function call boundaries look like.

The most obvious example is SIMD programming on Windows x86 32-bit.

Re:The Performance Impact of C++'s `final` Keyword by pixelpoet on Tuesday April 23, 2024 @12:45PM (#40133999)
Vfuncs are only fast when they can be predicted: https://forwardscattering.org/post/28
Re:The Performance Impact of C++'s `final` Keyword by mgaunard on Tuesday April 23, 2024 @04:52PM (#40137113)
Same as any other branch. They're fast if predicted correctly and slow if not.

If they cannot be predicted, write your code accordingly.

Re:The Performance Impact of C++'s `final` Keyword by rurban on Tuesday April 23, 2024 @11:18PM (#40140126)
C++ vtables need 2 levels of indirection. See the asm or decompile it with ghidra. First the vtable field, and then the method field.

Of course you have to worry about pointer chasing, when you can easily avoid it. Either via a switch to a single indirection (by passing method pointers around) or inlining with final. Or other compile-time specialization.

Re:The Performance Impact of C++'s `final` Keyword by simonask on Wednesday April 24, 2024 @03:20AM (#40141592)
Show me the receipts. :-)

In general it takes a significant amount of nondeterministic pointer chasing to fool modern branch predictors. Decades of research have been put into optimizing the hardware for languages like C++ and Java, both of which exhibit a lot of pointer chasing.

Re:The Performance Impact of C++'s `final` Keyword by phire on Wednesday April 24, 2024 @03:59PM (#40148864)
Though the branch predictor can chew though both layers of indirection. It can actually start fetching code from the function (and even executing it) before it even reads the function pointer from the vtable.

Though, that assumes a correct prediction. But modern branch predictors are really good, they can track and correctly predict hundreds (if not thousands) of indirect calls, taking into account the history of the last few branches (so it can even get an idea of what class is currently being executed, and make branch predictions based on that). Modern branch predictors do a really good job at chewing up indirect branches in hot sequences of code.

Virtual functions are probably the most harmful for warm code. We are talking about code that's executed too often to be considered cold code, but not often enough to stick around in the branch predictors' cache, executed only a few hundred times a second. It's a death by a thousand cuts type thing. And that's where devirtualisation will help the most...

As long as you don't go too far with the inlining and start causeing icache misses with code bloat. In an ideal would the compiler would inline enough to devirtualise the class, but not necessarily inline the actual function (unless they are small, or only called from one place)

Re:The Performance Impact of C++'s `final` Keyword by account42 on Tuesday April 23, 2024 @07:23AM (#40130592)
> Devirtualization helps performance because you are able to benefit from inheritance and not have to pay a performance penalty for that. Without the final keyword, a performance oriented project would need to be architected to not use inheritance at all, or in the very least in code in the hot path, because that sneaks gratuitous pointer dereferences all over the place, which require running extra operations and has a negative impact on caching.

virtual inheritance. Regular old inheritance does not need or benefit from devirtualization. This is why the CRTP exists.

Re:The Performance Impact of C++'s `final` Keyword by chipdart on Tuesday April 23, 2024 @07:50AM (#40130822)
> This is why the CRTP exists.

CRTP does not exist for that. CRTP was one of the many happy accidents in template metaprogramming that happened to be discovered when doing recursive templates.

Also, you've missed the whole point. CRTP is a way to rearchitect your code to avoid dereferencing pointers to virtual members in inheritance. The whole point is that with final you do not need to pull tricks: just tell the compiler that you don't want the class to be inherited, and the compiler picks up from there and does everything for you.

Re:The Performance Impact of C++'s `final` Keyword by account42 on Tuesday April 23, 2024 @08:35AM (#40131221)
If that's your point then it is simply wrong. Final does not allow the compiler to devirtualize calls through a base pointer, it only eliminates the virtualness for calls through pointers to the (final) derived type. The compiler can devirtualize calls through base pointers in others ways (by deducing the possible derived types via whole program optimization or PGO) but final does not help with that.
Re:The Performance Impact of C++'s `final` Keyword by chipdart on Tuesday April 23, 2024 @10:41AM (#40132530)
> If that's your point then it is simply wrong. Final does not allow the compiler to devirtualize calls through a base pointer, it only eliminates the virtualness for calls through pointers to the (final) derived type.

Please read my post. That's not my claim. I think I was very clear.

Re:The Performance Impact of C++'s `final` Keyword by scaredginger on Tuesday April 23, 2024 @03:11PM (#40135944)
Maybe a nitpick, but virtual inheritance is a term used for something else entirely.

What you're talking about is dynamic dispatch

Re:The Performance Impact of C++'s `final` Keyword by oasisaimlessly on Tuesday April 23, 2024 @03:34PM (#40136221)
> In classes with larger inheritance chains, you can easily have more than one pointer dereferencing taking place before you call a virtual members function.

This is not a thing in C++; vtables are flat, not nested. Function pointers are always 1 dereference away.