Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Inheritance was invented as a performance hack (2021)

catern.com

Post reply on HN
Print view View original

11–20 of 252 posts

Re: Inheritance was invented as a performance hack (2021)

#11

Post by nine_k »

wbl wrote: post #6
impure wrote: post #2

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 guess it could simplify the GC but modern garbage collectors have come a long way.

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.

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.

Re: Inheritance was invented as a performance hack (2021)

#12

Post by kragen »

impure wrote: post #2

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 guess it could simplify the GC but modern garbage collectors have come a long way.

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/, but I never really finished that essay.

Re: Inheritance was invented as a performance hack (2021)

#13

Post by vlovich123 »

nine_k wrote: post #11
wbl wrote: post #6

Earlier quoted context omitted.

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.

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.

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.

Re: Inheritance was invented as a performance hack (2021)

#14

Post by kragen »

bitwize wrote: post #5
impure wrote: post #2

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 guess it could simplify the GC but modern garbage collectors have come a long way.

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

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.

Re: Inheritance was invented as a performance hack (2021)

#15

Post by dang »

Discussed at the time:

Inheritance was invented as a performance hack - https://news.ycombinator.com/item?id=26988839 - April 2021 (252 comments)

plus this bit:

Inheritance was invented as a performance hack - https://news.ycombinator.com/item?id=35261638 - March 2023 (1 comment)

Re: Inheritance was invented as a performance hack (2021)

#16

Post by nine_k »

Reason077 wrote: post #9
impure wrote: post #2

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 guess it could simplify the GC but modern garbage collectors have come a long way.

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.

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.

Re: Inheritance was invented as a performance hack (2021)

#17

Post by kragen »

roenxi wrote: post #10

I'm not sold the evidence is there to show inheritance is a good idea - it basically says that constructors, data storage and interfaces need to be intertwined. That isn't a very powerful abstraction, because they don't need to be and there isn't an obvious advantage from doing so over picking up the concepts separately as required. And inheritance naturally suggests grouping interfaces into a tree in the way that se…

I'm on the fence about inheritance myself; I often regret having used it, and I never regret having not used it. On the other hand, it's awfully expedient. I designed and implemented a programming language called Bicicleta whose only argument-passing mechanism is inheritance, and I'm not sure that was a bad idea.

The object-oriented part of OCaml, by the way, has inheritance that's entirely orthogonal to interfaces, which in OCaml are static types. Languages like Smalltalk and, for the most part, Python don't have interfaces at all.

Re: Inheritance was invented as a performance hack (2021)

#18

Post by echelon »

kragen wrote: post #17
roenxi wrote: post #10

I'm not sold the evidence is there to show inheritance is a good idea - it basically says that constructors, data storage and interfaces need to be intertwined. That isn't a very powerful abstraction, because they don't need to be and there isn't an obvious advantage from doing so over picking up the concepts separately as required. And inheritance naturally suggests grouping interfaces into a tree in the way that se…

I'm on the fence about inheritance myself; I often regret having used it, and I never regret having not used it. On the other hand, it's awfully expedient. I designed and implemented a programming language called Bicicleta whose only argument-passing mechanism is inheritance, and I'm not sure that was a bad idea. The object-oriented part of OCaml, by the way, has inheritance that's entirely orthogonal to interfaces,…

Rigid, "family tree"-style inheritance as in classical OOP is pretty much garbage. "A cow is a mammal is an animal" is largely useless for the day to day work we do except in extremely well-planned, large and elaborate ontologies -- something you typically only see in highly structured software like windowing systems. It just isn't useful for the majority of our work.

"Trait/Typeclass"-style compositional inheritance as in Rust and Haskell is sublime. It's similar to Java interfaces in terms of flexibility, and it doesn't enforce hierarchical rules [1]. You can bolt behaviors and their types onto structures at will. This is how OO should be.

I put together a visual argument on another thread on HN a few weeks ago:

https://imgur.com/a/class-inheritance-vs-traits-oop-isnt-bad...

[1] Though if you want rules on bounds and associated types, you can have them.

Re: Inheritance was invented as a performance hack (2021)

#19

Post by nine_k »

vlovich123 wrote: post #13
nine_k wrote: post #11

Earlier quoted context omitted.

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.

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.

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.

Re: Inheritance was invented as a performance hack (2021)

#20

Post by nine_k »

bitwize wrote: post #5
impure wrote: post #2

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 guess it could simplify the GC but modern garbage collectors have come a long way.

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

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.

Post reply on HN