6 ms·

What final enables is devirtualization in certain cases. The main advantage of devirtualization is that it is necessary for inlining. Inlining has other requi

• i80and 3y ago
  If you already have LTO, can't the compiler determine this information for devirtualization purposes on its own?
  • nickwanninger 3y ago
    At the level that LLVM's LTO operates, no information about classes or objects is left, so LLVM itself can't really devirtualize C++ methods in most cases
    • nwallin 3y ago
      You appear to be correct. Clang does not devirtualize in LTO, but GCC does. Personally I consider this very strange. $ cat animal.h cat.cpp main.cpp // animal.h #pragma once class animal { public: virtual ~animal() {} virtual void speak() = 0; }; animal& get_mystery_animal(); // cat.cpp #include "animal.h" #include <cstdio> class cat final : public animal { public: ~cat() override{} void speak() override{ puts("meow"); } }; static cat garfield{}; animal& get_mystery_animal() { return garfield; } // main.cpp #include "animal.h" int main() { animal& a = get_mystery_animal(); a.speak(); } $ make clean && CXX=clang++ make -j && objdump --disassemble=main -C lto_test rm -f *.o lto_test clang++ -c -flto -O3 -g cat.cpp -o cat.o clang++ -c -flto -O3 -g main.cpp -o main.o clang++ -flto -O3 -g cat.o main.o -o lto_test lto_test: file format elf64-x86-64 Disassembly of section .init: Disassembly of section .plt: Disassembly of section .plt.got: Disassembly of section .text: 00000000000011b0 <main>: 11b0: 50 push %rax 11b1: 48 8b 05 58 2e 00 00 mov 0x2e58(%rip),%rax # 4010 <garfield> 11b8: 48 8d 3d 51 2e 00 00 lea 0x2e51(%rip),%rdi # 4010 <garfield> 11bf: ff 50 10 call *0x10(%rax) 11c2: 31 c0 xor %eax,%eax 11c4: 59 pop %rcx 11c5: c3 ret Disassembly of section .fini: $ make clean && CXX=g++ make -j && objdump --disassemble=main -C lto_test|sed -e 's,^, ,' rm -f *.o lto_test g++ -c -flto -O3 -g cat.cpp -o cat.o g++ -c -flto -O3 -g main.cpp -o main.o g++ -flto -O3 -g cat.o main.o -o lto_test lto_test: file format elf64-x86-64 Disassembly of section .init: Disassembly of section .plt: Disassembly of section .plt.got: Disassembly of section .text: 0000000000001090 <main>: 1090: 48 83 ec 08 sub $0x8,%rsp 1094: 48 8d 3d 75 2f 00 00 lea 0x2f75(%rip),%rdi # 4010 <garfield> 109b: e8 50 01 00 00 call 11f0 <cat::speak()> 10a0: 31 c0 xor %eax,%eax 10a2: 48 83 c4 08 add $0x8,%rsp 10a6: c3 ret Disassembly of section .fini:
      • ranger_danger 3y ago
        What if you add -fwhole-program-vtables on clang?
      • JonChesterfield 3y ago
        I think this is a bug. There's dedicated metadata that's supposed to end up on the indirect call to list the possible targets and when that list of possible targets is this short it should be turning into a switch over concrete targets. Don't have time to dig into the IR now but it might be worth posting to the github llvm issues.
  • wiml 3y ago
    If your runtime environment has dynamic linking, then the LTO pass can't always be sure that a subclass won't be introduced later that overrides the method.
    • i80and 3y ago
      Aha! That makes sense. I wasn't thinking of that case. Thanks!
    • gpderetta 3y ago
      You can tell the compiler it is indeed compiling the whole program.
  • adzm 3y ago
    MSVC with LTO and PGO will inline virtual calls in some situations along with a check for the expected vtable, bypassing the inlined code and calling the virtual function normally if it is an unexpected value.
  • bluGill 3y ago
    not if there is a shared libray or other plugin. Then you coannot determine until runtime if there is an override.
  • ot 3y ago
    In general the compiler/linker cannot assume that derived classes won't arrive later through a shared object. You can tell it "I won't do that" though with additional flags, like Clang's -fwhole-program-vtables, and even then it's not that simple. There was an effort in Clang to better support whole program devirtualization, but I haven't been following what kind of progress has been made: https://groups.google.com/g/llvm-dev/c/6LfIiAo9g68?pli=1 https://groups.google.com/g/llvm-dev/c/6LfIiAo9g68?pli=1
    • Slix 3y ago
      This optimization option isn't on by default? That sounds like a lot of missed optimization. Most programs aren't going to be loading from shared libraries. Maybe I can set this option at work. Though it's scary because I'd have to be certain.
      • soooosn 3y ago
        I think you have answered your own question: If turning on the setting is scary for you in a very localized project at your company, imagine how scary it would be to turn on by default for everybody :-P
      • Thiez 3y ago
        The JVM can actually perform this optimization optimistically and can undo it if the assumption is violated at runtime. So Java's 'everything is virtual by default' approach doesn't hurt. Of course relying an a sufficiently smart JIT comes with its own trade-offs.
      • JonChesterfield 3y ago
        Optimization means "make it faster without changing behaviour in ways I don't like". Clang can't generally default that one to on because it doesn't know whether you're going to splice in more code it can't see at runtime. Lots of code gets slower if it might need to be called from something not currently in the compiler's scope. That's essentially what ABI overhead is. If there isn't already, there should be a compiler flag that says "this is the whole program, have at it" which implies the vtables option.
  • samus 3y ago
    This is one of the cases where JIT compiling can shine. You can use a bazillion interfaces to decouple application code, and the JIT will optimize the calls after it found out which implementation is used. This works as long as there is only one or two of them actually active at runtime.
    • account42 3y ago
      You don't need a JIT to do whole program optimization.
      • samus 3y ago
        AOT whole program optimization has two limits: * It is possible with `dlopen()` to load code objects that violate the assumptions made during compilation. * The presence of runtime configuration mechanisms and application input can make it impossible to anticipate things like the choice of implementations of an interface. One can always strive to reduce such situations, but it might simply not be necessary if a JIT is present.
• Negitivefrags 3y ago
  See this is why I find this odd. Is there a theory as to how devirtualisation could hurt performance?
  • samus 3y ago
    Devirtualization maybe not necessarily, but inlining might make code fail to fit into instruction caches.
  • hansvm 3y 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 3y ago
    Code bloat causing icache evictions?
  • cogman10 3y 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.
• chipdart 3y ago
  > 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.
• bdjsiqoocwk 3y ago
  Whats devirtualization in C++? Funny how things work. From working with Julia I've built a good intuition for guessing when functions would be inlined. And yet, I've never heard the word devirtualization until now.
  • saagarjha 3y ago
    In C++ virtual functions are polymorphic and indirected, with the target not known to the compiler. Devirtualization gives the compiler this information (in this case a final method cannot be overridden and branch to something else).