4 ms·

Huh, I was always told that inheritance hurt performance as it requires additional address lookups. Thats why many game engines are moving away from it. I gues

• andyferris 1y ago
  As I understand it, back when Simula and LISP were invented it was generally the case that loads and stores took 1 cycle and there were no CPU caches. These pointer-chasing languages and techniques really weren't technically bad for the computers of the time - it's just that we have a larger relative penalty for randomly accessing our Random Access Memory these days so locallity is important (hence data-oriented design, ECS, etc). I am kind of amused they _removed_ first-class functions though!
  • int_19h 1y ago
    Function arguments weren't actually first-class to begin with. In Algol 60 (of which Simula started as a superset), you could pass functions as arguments to other functions, but that's it - it wasn't a proper type so you couldn't return it, shove it into a variable, have an array of functions etc. Basically, it had just enough restrictions that you would never get up in a situation where you could possibly call a function for which the corresponding activation frame (i.e. locals) could be gone. But when Simula added classes and objects, now you could suddenly capture arguments in a way that allows them to outlive the callee.
• bitwize 1y ago
  Simple inheritance makes the class hierarchy complicated through issues like the diamond inheritance problem, which C++ resolves in typical C++ fashion: attempt to satisfy everybody, actually satisfy nobody. The designers of StarCraft ran into the pitfalls of designing a sensible inheritance hierarchy, as described here (C-f "Game engine architecture"): https://www.codeofhonor.com/blog/tough-times-on-the-road-to-starcraft https://www.codeofhonor.com/blog/tough-times-on-the-road-to-...
  • virtue3 1y ago
    really amazing read thank you.
  • kragen 1y ago
    Simple inheritance doesn't have the diamond problem, because that requires multiple inheritance, which isn't simple. Smalltalk doesn't have multiple inheritance; I don't think SIMULA did either.
    • int_19h 1y ago
      Simula is strictly single inheritance (and no interfaces).
      • kragen 1y ago
        Thank you!
  • nine_k 1y ago
    The best implementation inheritance hierarchy is none :) If you must, you can use the implementation inheritance for mix-ins / cross-cutting concerns that are the same for all parties involved, e.g. access control. But even that may be better done with composition, especially when you have an injection framework that wires up certain constructor parameters for you. Where inheritance (extension) properly belongs is the definition of interfaces.
• wbl 1y ago
  Dynamic invocation, not strict inheritance is the issue here. Simply getting functions and fields from a superclass costs nothing if at each callsite the compiler knows enough to say where it is from.
  • nine_k 1y ago
    But this may only happen when no virtual / overridden methods are involved, no VMT to look up in, no polymorphism at play. This is tanamount to composition, which should be preferred over inheritance anyway. In this regard, Go and Rust do classes / objects right, Java provides the classical pitfalls, and C++ is the territory where unspeakable horrors can be freely implemented, as usual.
    • vlovich123 1y ago
      Parent is correct - if the compiler has the information to devirtualize it becomes direct dispatch regardless of the mechanisms involved at the source level. This is also typically true for JITs.
      • nine_k 1y ago
        This is true as long as the compiler actually can de-virtualize the method, that is, that it can prove that the objects it's handling at a particular call site do not override it. Quite often this is not the case, because of the pattern when the programmer is expected to override / implement an abstract method to plug in the desired functionality. The lookup can be fast if there are few classes involved, and their vtables get cached. JITs can do many fascinating optimizations based on profiling the actual code. They must always be on guard though for a case when their profiling-based conclusions fail to hold with some new data, and they have to de-optimize. This being on guard also has its cost.
        • vlovich123 1y ago
          Even if you call a pure virtual function of an abstract base class, the compiler can devirtualize if it can determine the type anyway due to data flow analysis. There are limitations but with LTO you’d be surprised at how effective the compiler is here. Also in Rust you’re never going through the vtable unless it’s a &dyn Trait and the compiler fails to devirtualize.
• Reason077 1y ago
  Nah. Classic C++/Java style inheritance with vtable dispatch is very fast. Generally no slower than a C-style function call, and actually sometimes faster depending on how the C code is linked, characteristics of the CPU, etc.
  • nine_k 1y ago
    This assumes that the vtables stay in at least L2 cache, which may be a correct assumption for the few hot-path classes. In this regard, I remember how Facebook's android app once failed to build when the codebase exceeded the limit of 64k classes.
    • xxs 1y ago
      No, Java does Class hierarchy analysis and has multiple way not to use v-table calls. Single site (no class found overriding a method) are static and can be inlined directly. Dual call sites use a class check (which is a simple equality), can be inlined, no v-table. 3-5 call sites use inline caches (e.g. the compiler records what class have been used) that are similar and some can be inlined, usually plus a guard check. Only high polymorphic calls use v-table and in practice is a very rare occasion, even with Java totally embracing inheritance (or polymorphic interfaces) Note: CHA is dynamic and happens at runtime, depending which classes have been loaded. Loading new classes causes CHA to be performed again and if there are affected sites, the latter are to be deoptimized (and re-JIT again)
      • nine_k 1y ago
        Thanks, TIL!
      • josephg 1y ago
        Thats very cool. Does C++ have any of these optimisations?
        • gpderetta 1y ago
          Some compilers do some of these optimizations, at least those that not require a JIT and code patching at runtime. But these optimizations are vastly less critical in C++ where only are minority of functions are virtual.
• kragen 1y ago
  No, inheritance does not require additional address lookups. Single inheritance as discussed here doesn't even require additional address arithmetic; the address of the subclass instance is the same as the address of the superclass instance. Yes, current GCs are very fast and do not suffer from the problems Simula's GC suffered from. Nevertheless, they do still have an easier time when you embed record A as a field of record B (roughly what inheritance achieves in this case) rather than putting a pointer to record A in record B. Allocation may not be any faster, because in either case the compiler can bump the nursery pointer just once (with a copying collector). Deallocation is maybe slightly faster, because with a copying collector, deallocation cost is sort of proportional to how much space you allocate, and the total size of record B is smaller with record A embedded in it than the total size of record A plus record B with a pointer linking them. (That's one pointer bigger.) But tracing gets much faster when there are no pointers to trace. You will also notice from this example that it's failing to embed the superclass (or whatever) that requires an additional record lookup. And probably a cache miss, too. I think the reason many game engines are moving away from inheritance is that they're moving away from OO in general, and more generally the Lisp model of memory as a directed graph of objects linked by pointers, because although inheritance reduces the number of cache misses in OO code, it doesn't reduce them enough. I've written about this at greater length in http://canonical.org/~kragen/memory-models/ http://canonical.org/~kragen/memory-models/, but I never really finished that essay.
  • josephg 1y ago
    > No, inheritance does not require additional address lookups. Single inheritance as discussed here doesn't even require additional address arithmetic; the address of the subclass instance is the same as the address of the superclass instance. Yes it does! Inheritance itself is fine, but inheritance almost always means virtual functions - which can have a significant performance cost because of vtable lookups. Using virtual functions also prevents inlining - which can have a big performance cost in critical code. > Nevertheless, they do still have an easier time when you embed record A as a field of record B (roughly what inheritance achieves in this case) rather than putting a pointer to record A in record B. Huh? No - if you put A and B in separate allocations, you get worse performance. Both because of pointer chasing (which matters a great deal for performance). And also because you're putting more pressure on the allocator / garbage collector. The best way to combine A and B is via simple composition: struct C { a: A, b: B } In this case, there's a single allocation. (At least in languages with value types - like C, C++, C#, Rust, Swift, Zig, etc). In C++, the bytes in memory are actually identical to the case where B inherits from A. But you don't get any class entanglement, or any of the bugs that come along with that. > I think the reason many game engines are moving away from inheritance is that they're moving away from OO in general Games are moving away from OO because C++ style OO is a fundamentally bad way to structure software. Even if it wasn't, struct-of-arrays usually performs better than arrays-of-structs because of how caching works. And modern ECS (entity component systems) can take good advantage of SoA style memory layouts. The performance gap between CPU cache and memory speed has been steadily growing over the last few decades. This means, relatively speaking, pointers are getting slower and big arrays are getting faster on modern computers.
• jayd16 1y ago
  What game engines are moving away from inheritance? Composition is preferred, tho. It's just easier to refactor things that way.
• i_c_b 1y ago
  I was in the game industry when we originally transitioned from C to C++, and here's my recollection of the conversations at the time, more or less. In C++, inheritance of data is efficient because the memory layout of base class members stays the same in different derived classes, so fields don't cost any more to access. And construction is (relatively fast, compared to alternatives) because setting a single vtable pointer is faster than filling in a bunch of variable fields. And non-virtual functions were fast because, again, static memory layouts and access and inlining. Virtual functions were a bit slower, but ultimately that just raised the larger question of when and where a codebase was using function pointers more broadly - virtual functions were just one way of corralling that issue. And the fact that there were idiomatic ways to use classes in C++ without dynamically allocating memory was crucial to selling game developers on the idea, too. So at least from my time when this was happening, the general sense was that, of all the ways OO could be implemented, C++ style OO seemed to be by far the most performant, for the concerns of game developers in the late 90's / early 2000's. I've been out of the industry for a while, so I haven't followed the subsequent conversations since too closely. But I do think, even when I was there, the actual reality of OO class hierarchies were starting to rear their ugly heads. Giant base classes are indeed drastically bad for caches, for example, because they do tend to produce giant, bloated data structures. And deep class hierarchies turn out to be highly sub-optimal, in a lot of cases, for information hiding and evolving code bases (especially for game code, which was one of my specialties). As a practical matter, as you evolve code, you don't get the benefits of information hiding that were advertised on the tin (hence the current boosting of composition over inheritance). I think you can better, smart discussions about those issues in this thread, so I won't cover them. But that was a snapshot of those early experiences - the specific ways C++ implemented inheritance for performance reasons were definitely, originally, much of the draw to game programmers.