5 ms·

> What final enables is devirtualization in certain cases. The main advantage of devirtualization is that it is necessary for inlining. I think that enabling i

> 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.

simonask 3y ago
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.
- rurban 3y ago
  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.
  - simonask 3y ago
    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.
  - phire 3y ago
    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)
- silvestrov 3y ago
  "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.
account42 3y ago
> 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.
- chipdart 3y ago
  > 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.
  - account42 3y ago
    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.
    - chipdart 3y ago
      > 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.
- 3y ago
oasisaimlessly 3y ago
> 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.

simonask 3y ago

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.

rurban 3y ago
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.
- simonask 3y ago
  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.
- phire 3y ago
  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)
silvestrov 3y ago
"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.

account42 3y ago

> 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.

chipdart 3y ago
> 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.
- account42 3y ago
  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.
  - chipdart 3y ago
    > 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.
3y ago

oasisaimlessly 3y ago

> 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.