5 ms·

See this is why I find this odd. Is there a theory as to how devirtualisation could hurt performance?

samus 2y ago
Devirtualization maybe not necessarily, but inlining might make code fail to fit into instruction caches.
hansvm 2y ago
There's a cost to loading more instructions, especially if you have more types of instructions. The main advantages to inlining are (1) avoiding a jump and other function call overhead, (2) the ability to push down optimizations. If you execute the "same" code (same instructions, different location) in many places that can cause cache evictions and other slowdowns. It's worse if some minor optimizations were applied by the inlining, so you have more types of instructions to unpack. The question, roughly, is whether the gains exceed the costs. This can be a bit hard to determine because it can depend on the size of the whole program and other non-local parameters, leading to performance cliffs at various stages of complexity. Microbenchmarks will tend to suggest inlining is better in more cases that it actually is. Over time you get a feel for which functions should be inlined. E.g., very often you'll have guard clauses or whatnot around a trivial amount of work when the caller is expected to be able to prove the guarded information at compile-time. A function call takes space in the generated assembly too, and if you're only guarding a few instructions it's usually worth forcing an inline (even in places where the compiler's heuristics would choose not to because the guard clauses take up too much space), regardless of the potential cache costs.
masklinn 2y ago
Code bloat causing icache evictions?
cogman10 2y ago
Through inlining. If you have something like a `while` loop and that while loop's instructions fit neatly on the cache line, then executing that loop can be quiet fast even if you have to jump to different code locations to do the internals. However, if you pump in more instructions in that loop you can exceed the length of the cache line which causes you to need more memory loads to do the same work. It can also create more code. A method that took a `foo(NotFinal& bar)` could be duplicated by the compiler for the specialized cases which would be bad if there's a lot of implementations of `NotFinal` that end up being marshalled into foo. You could end up loading multiple implementations of the same function which may be slower than just keeping the virtual dispatch tables warm.
phire 2y ago
Jumps/calls are actually be pretty cheap with modern branch predictors. Even indirect calls through vtables, which is the opposite of most programmers intuition. And if the devirtualisation leads to inlining, that results in code bloat which can lower performance though more instruction cache misses, which are not cheap. Inlining is actually pretty evil. It almost always speeds things up for microbenchmarks, as such benchmarks easily fit in icache. So programmers and modern compilers often go out of their way to do more inlining. But when you apply too much inlining to a whole program, things start to slow down. But it's not like inlining is universally bad in larger program, inlining can enable further optimisations, mostly because it allows constant propagation to travel across function boundaries. Basically, compilers need better heuristics about when they should be inlining. If it's just saving the overhead of a lightweight call, then they shouldn't be inlining.
- qsdf38100 2y ago
  "Inlining is actually pretty evil". No it's not. Except if you __force_inline__ everything, of course. Inlining reduces the number of instructions in a lot of cases. Especially when things are abstracted and factored with lot of indirections into small functions that calls other small functions and so on. Consider a 'isEmpty' function, which dissolves to 1 cpu instruction once inlined, compared with a call/save reg/compare/return. Highly dynamic code (with most functions being virtual) tend to result in a fest of chained calls, jumping into functions doing very little work. Yes the stack is usually hot and fast, but spending 80% of the instructions doing stack management is still a big waste. Compilers already have good heuristics about when they should be inlining, chances are they are a lot better at it than you. They don't always inline, and that's not possible anyway. My experience is that compiler do marvels with inlining decisions when there are lots of small functions they _can_ inline if they want to. It gives the compiler a lot of freedom. Lambdas are great for that as well. Make sure you make the most possible compile-time information available to the compiler, factor your code, don't have huge functions, and let the compiler do its magic. As a plus, you can have high level abstractions, deep hierarchies, and still get excellent performances.
  - grdbjydcv 2y ago
neonsunset 2y ago
Practically - it never does. It is always cheaper to perform a direct, possibly inlined, call (devirtualization != inlining) than a virtual one. Guarded devirtualization is also cheaper than virtual calls, even when it has to do if (instance is SpecificType st) { st.Call() } else { instance.Call() } or even chain multiple checks at once (with either regular ifs or emitting a jump table) This technique is heavily used in various forms by .NET, JVM and JavaScript JIT implementations (other platforms also do that, but these are the major ones) The first two devirtualize virtual and interface calls (important in Java because all calls default to virtual, important in C# because people like to abuse interfaces and occasionally inheritance, C# delegates are also devirtualized/inlined now). The JS JIT (like V8) performs "inline caching" which is similar where for known object shapes property access is shape type identifier comparison and direct property read instead of keyed lookup which is way more expensive.
- ynik 2y ago
  Caution! If you compare across languages like that, not all virtual calls are implemented equally. A C++ virtual call is just a load from a fixed offset in the vtbl followed by an indirect call. This is fairly cheap, on modern CPUs pretty much the same as a non-virtual non-inlined call. A Java/C# interface call involves a lot more stuff, because there's no single fixed vtbl offset that's valid for all classes implementing the interface.
  - neonsunset 2y ago
    Yes, it is true that there is difference. I'm not sure about JVM implementation details but the reason the comment says "virtual and interface" calls is to outline it. Virtual calls in .NET are sufficiently close[0] to virtual calls in C++. Interface calls, however, are coded differently[1]. Also you are correct - virtual calls are not terribly expensive, but they encroach on ever limited* CPU resources like indirect jump and load predictors and, as noted in parent comments, block inlining, which is highly undesirable. [0] https://github.com/dotnet/runtime/blob/5111fdc0dc464f01647d6b6078342f451bf3a499/src/coreclr/vm/amd64/virtualcallstubcpu.hpp#L471-L505 https://github.com/dotnet/runtime/blob/5111fdc0dc464f01647d6... [1] https://github.com/dotnet/runtime/blob/main/docs/design/coreclr/botr/virtual-stub-dispatch.md https://github.com/dotnet/runtime/blob/main/docs/design/core... (mind you, the text was initially written 18 years ago, wow) * through great effort of our industry to take back whatever performance wins each generation brings with even more abstractions that fail to improve our productivity
variadix 2y ago
It basically never should unless the inliner made a terrible judgement. Devirtualizing in C++ can remove 3 levels of pointer chasing, all of which could be cache misses. Many optimizations in modern compilers require the context of the function to be inlined to make major optimizations, which requires devirtualization. The only downside is I$ pressure, but this is generally not a problem because hot loops are usually tight.
bandrami 2y ago
If it's done badly, the same code that runs N times also gets cached N times because it's in N different locations in memory rather than one location that gets jumped to. Modern compilers and schedulers will eliminate a lot of that (but probably not for anything much smaller than a page), but in general there's always a tradeoff.

Devirtualization maybe not necessarily, but inlining might make code fail to fit into instruction caches.

There's a cost to loading more instructions, especially if you have more types of instructions. The main advantages to inlining are (1) avoiding a jump and other function call overhead, (2) the ability to push down optimizations. If you execute the "same" code (same instructions, different location) in many places that can cause cache evictions and other slowdowns. It's worse if some minor optimizations were applied by the inlining, so you have more types of instructions to unpack. The question, roughly, is whether the gains exceed the costs. This can be a bit hard to determine because it can depend on the size of the whole program and other non-local parameters, leading to performance cliffs at various stages of complexity. Microbenchmarks will tend to suggest inlining is better in more cases that it actually is. Over time you get a feel for which functions should be inlined. E.g., very often you'll have guard clauses or whatnot around a trivial amount of work when the caller is expected to be able to prove the guarded information at compile-time. A function call takes space in the generated assembly too, and if you're only guarding a few instructions it's usually worth forcing an inline (even in places where the compiler's heuristics would choose not to because the guard clauses take up too much space), regardless of the potential cache costs.

masklinn 2y ago

Code bloat causing icache evictions?

cogman10 2y ago

Through inlining. If you have something like a `while` loop and that while loop's instructions fit neatly on the cache line, then executing that loop can be quiet fast even if you have to jump to different code locations to do the internals. However, if you pump in more instructions in that loop you can exceed the length of the cache line which causes you to need more memory loads to do the same work. It can also create more code. A method that took a `foo(NotFinal& bar)` could be duplicated by the compiler for the specialized cases which would be bad if there's a lot of implementations of `NotFinal` that end up being marshalled into foo. You could end up loading multiple implementations of the same function which may be slower than just keeping the virtual dispatch tables warm.

phire 2y ago

Jumps/calls are actually be pretty cheap with modern branch predictors. Even indirect calls through vtables, which is the opposite of most programmers intuition. And if the devirtualisation leads to inlining, that results in code bloat which can lower performance though more instruction cache misses, which are not cheap. Inlining is actually pretty evil. It almost always speeds things up for microbenchmarks, as such benchmarks easily fit in icache. So programmers and modern compilers often go out of their way to do more inlining. But when you apply too much inlining to a whole program, things start to slow down. But it's not like inlining is universally bad in larger program, inlining can enable further optimisations, mostly because it allows constant propagation to travel across function boundaries. Basically, compilers need better heuristics about when they should be inlining. If it's just saving the overhead of a lightweight call, then they shouldn't be inlining.

qsdf38100 2y ago
"Inlining is actually pretty evil". No it's not. Except if you __force_inline__ everything, of course. Inlining reduces the number of instructions in a lot of cases. Especially when things are abstracted and factored with lot of indirections into small functions that calls other small functions and so on. Consider a 'isEmpty' function, which dissolves to 1 cpu instruction once inlined, compared with a call/save reg/compare/return. Highly dynamic code (with most functions being virtual) tend to result in a fest of chained calls, jumping into functions doing very little work. Yes the stack is usually hot and fast, but spending 80% of the instructions doing stack management is still a big waste. Compilers already have good heuristics about when they should be inlining, chances are they are a lot better at it than you. They don't always inline, and that's not possible anyway. My experience is that compiler do marvels with inlining decisions when there are lots of small functions they _can_ inline if they want to. It gives the compiler a lot of freedom. Lambdas are great for that as well. Make sure you make the most possible compile-time information available to the compiler, factor your code, don't have huge functions, and let the compiler do its magic. As a plus, you can have high level abstractions, deep hierarchies, and still get excellent performances.
- grdbjydcv 2y ago

neonsunset 2y ago

Practically - it never does. It is always cheaper to perform a direct, possibly inlined, call (devirtualization != inlining) than a virtual one. Guarded devirtualization is also cheaper than virtual calls, even when it has to do if (instance is SpecificType st) { st.Call() } else { instance.Call() } or even chain multiple checks at once (with either regular ifs or emitting a jump table) This technique is heavily used in various forms by .NET, JVM and JavaScript JIT implementations (other platforms also do that, but these are the major ones) The first two devirtualize virtual and interface calls (important in Java because all calls default to virtual, important in C# because people like to abuse interfaces and occasionally inheritance, C# delegates are also devirtualized/inlined now). The JS JIT (like V8) performs "inline caching" which is similar where for known object shapes property access is shape type identifier comparison and direct property read instead of keyed lookup which is way more expensive.

ynik 2y ago
Caution! If you compare across languages like that, not all virtual calls are implemented equally. A C++ virtual call is just a load from a fixed offset in the vtbl followed by an indirect call. This is fairly cheap, on modern CPUs pretty much the same as a non-virtual non-inlined call. A Java/C# interface call involves a lot more stuff, because there's no single fixed vtbl offset that's valid for all classes implementing the interface.
- neonsunset 2y ago
  Yes, it is true that there is difference. I'm not sure about JVM implementation details but the reason the comment says "virtual and interface" calls is to outline it. Virtual calls in .NET are sufficiently close[0] to virtual calls in C++. Interface calls, however, are coded differently[1]. Also you are correct - virtual calls are not terribly expensive, but they encroach on ever limited* CPU resources like indirect jump and load predictors and, as noted in parent comments, block inlining, which is highly undesirable. [0] https://github.com/dotnet/runtime/blob/5111fdc0dc464f01647d6b6078342f451bf3a499/src/coreclr/vm/amd64/virtualcallstubcpu.hpp#L471-L505 https://github.com/dotnet/runtime/blob/5111fdc0dc464f01647d6... [1] https://github.com/dotnet/runtime/blob/main/docs/design/coreclr/botr/virtual-stub-dispatch.md https://github.com/dotnet/runtime/blob/main/docs/design/core... (mind you, the text was initially written 18 years ago, wow) * through great effort of our industry to take back whatever performance wins each generation brings with even more abstractions that fail to improve our productivity

variadix 2y ago

It basically never should unless the inliner made a terrible judgement. Devirtualizing in C++ can remove 3 levels of pointer chasing, all of which could be cache misses. Many optimizations in modern compilers require the context of the function to be inlined to make major optimizations, which requires devirtualization. The only downside is I$ pressure, but this is generally not a problem because hot loops are usually tight.

bandrami 2y ago

If it's done badly, the same code that runs N times also gets cached N times because it's in N different locations in memory rather than one location that gets jumped to. Modern compilers and schedulers will eliminate a lot of that (but probably not for anything much smaller than a page), but in general there's always a tradeoff.