4 ms·

An extra indirection (indirect call versus direct call) is practically nothing on modern hardware. Branch predictors are insanely good, and this isn't something

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 2y 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 2y 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 2y 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 2y 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.
- simonask 2y ago
  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.
- dblohm7 2y ago
  Firefox has done a lot of work on devirtualization over the years. There is a cost.
ot1138 2y ago
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.
- mgaunard 2y ago
  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.
pixelpoet 2y ago
Vfuncs are only fast when they can be predicted: https://forwardscattering.org/post/28 https://forwardscattering.org/post/28
- mgaunard 2y ago
  Same as any other branch. They're fast if predicted correctly and slow if not. If they cannot be predicted, write your code accordingly.

rurban 2y 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 2y 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 2y 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 2y 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.

simonask 2y ago
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.
dblohm7 2y ago
Firefox has done a lot of work on devirtualization over the years. There is a cost.

ot1138 2y ago

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.

mgaunard 2y ago
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.

pixelpoet 2y ago

Vfuncs are only fast when they can be predicted: https://forwardscattering.org/post/28 https://forwardscattering.org/post/28

mgaunard 2y ago
Same as any other branch. They're fast if predicted correctly and slow if not. If they cannot be predicted, write your code accordingly.