Is prototypal inheritance inherently slower?

Question

I see Javascript 6 will add traditional class based inheritance, and one argument I hear is that classes are inherently much faster than prototypes because they can be optimized away by the compiler when doing (JIT) compilation to native code or to bytecode. That sort of makes sense to my mind, but I'm not nearly an advanced enough programmer to really understand this stuff.

The argument I always saw for prototypal inheritance (PI) was that it conserves memory, which is mostly a completely moot point these days. Personally, I like PI and always felt it "makes sense" in a dynamic language; like it is a luxury you can just as well afford if you already settled for the performance limitations of an interpreted dynamic language.

In C++, classes makes sense because of the limitations that comes with the C++ philosophy that everything takes a back seat to maximum possibility for performance.

Of course you can have PI in C++ and there is a well known design pattern for that, but I'm talking about built-in inheritance in a dynamic language.

If one was looking at the fastest possible implementation of prototypal inheritance in a fictional dynamic language, what would necessarily be the drawbacks with regards to performance vis-à-vis traditional classes?

What if you add the feature to the fictional language that you can specify that some objects are "final" and their prototype chain cannot be changed at runtime? (Coexisting with traditional PI) Also add optional static typing or type hinting if that helps the prototypal language.

Since this might be considered a bit of a vague question, I'm adding:

I guess I'm looking for the thoughts on the subject from people who are more clever and more interested in language theory and/or compiler/interpreter writing than me. Hope that is still an ok question.

This is not about Javascript 6 at all, I just brought it up because Javascript is the most successful prototypal language and it is interesting that they are adding native classes even though Javascript seemed to be doing fine without them (both popularity wise and having some jaw-dropping benchmark improvements in the last few years). I'm also not saying that I believe or think that Javascript is slow.

Really, I'm more interested in learning more about programming languages, possibly with the goal of some day constructing my own dynamic language.

Answer 1

There's really two things to understand:

1. prototypal inheritance has nothing to do with performance at all. The performance issues come from runtime changes to the inheritance structure.
2. prototypal inheritance (and flexible object structures) are not so much inherently slower, as they are harder to optimize.

To illustrate the first claim, Ruby would be a flagship example of class based objects being abysmally slow. The problem generally persists throughout Smalltalk-like langauges, e.g. Objective-C, that employ message passing for method calls. The Objective-C runtime uses some nifty method caching to tackle the issue, but it did take them a while to get that far.

What makes method calls cheap is that the compiler (or JIT or runtime even) has some definite knowledge about the structure of an object. Be that explicitly given in terms of language features, or implicitly inferred from static analysis, the knowledge exists and the compiler can use that to optimize.

Now when the structure can change at runtime, this makes things a little tricky, because you need good heuristics to detect which portions of the code are worth being optimized at all (you want a good ratio between the frequency of the code being run to the frequency at which it changes and the cost of optimizing it), to get the best overall runtime characteristics.

---

So what is the point of classes in dynamic languages? Well, there must be one, because there's numerous JavaScript class systems (like that of Ext). Sure, familiarity for programmers used to classes is one reason. But the real benefit comes from helping to ensure explicit definitions of object types. Such a class definition is one (albeit complex) statement. With vanilla JavaScript constructors, you have a whole bunch of statements, that are grouped together, if you're lucky. The class structure is really just a side effect of imperative code, if you will. Class declarations are unsurprisingly meant to facilitate a more declarative style.

It's worth to note that the Self language that really made prototypal inheritance explicit (although it's really straight forward to achieve in a language with message passing), was created for an environment where you programmed a fully interactive system while it was running. You could actually see an object on screen. This allowed for a clean declaration that was still modifiable at runtime, because the declaration and the result were so intimately coupled. Without such a coupling, fiddling with object structure at runtime can quickly become an unintelligible mess that is really hard to fit in your brain, let alone reason about.

---

You can pretty much get prototypal inheritance if you have good support for delegation. You just delegate all unimplemented calls to an object that you consider a prototype and you're done. It's more flexible. However it's equally harder to optimize.

Answer 2

In C++, classes makes sense because of the limitations that comes with the C++ philosophy that everything takes a back seat to maximum possibility for performance.

You have two false premises inherent in this statement. The first is that classes are a C++ thing. They aren't; the concept is as old as OOP itself, dating back to Simula, the first object-oriented language, and nearly every OO language since then has had classes, including dynamic ones such as Python. It's the prototypal model that is the aberration.

The second is that classes are used because of performance. While that's certainly one benefit, it's hardly the reason for using them. The real reasons for using classes are that they're a natural way to model many important types of programming problems, and that they mesh quite well with static typing as a way to help enforce correctness and head off entire classes of problems (no pun intended) at compile time.

And yes, classes are inherently faster at runtime than prototypal inheritance, for one simple reason: any information that can be calculated at compile time does not have to be calculated at runtime. Classes provide the compiler with certain invariants that it can know ahead of time will not be violated, which allows it to create simpler runtime code that does not need to check for those things.

Depending on how the class is implemented, there can be a second major advantage: if the objects are implemented as contiguous records with fields, then member access becomes a dereference of a pointer at a constant offset from the beginning of the object's memory location, which will be dozens or even hundreds of times faster than looking members up in a hash table or other map, which is how you have to do it at runtime if the object's layout is not known to the compiler.

So yes, classes are inherently faster, which is why modern JavaScript JITs try to turn objects into classes whenever possible. But this is just a side benefit; the real advantage comes from them being inherently safer and more useful as a tool to reason and prove things about the behavior of your code.

Answer 3

AFAIK, there's not much difference between the two. Consider that a C++ class is really a block of data with a special, hidden data structure at the beginning called a vtable. This vtable contains all the pointers to the methods contained within the class.

Now you see its not much different from a javascript prototype - which is a bunch of pointers to functions that comprise the js class.

However, in practice the difference is huge. The C++ one restricts you to not being able to dynamically add, remove or replace those function pointers. This means the compiler knows in advance what they are, and so it can optimise them away completely. It also means it knows exactly where the functions are and can even inline the methods if it thinks its worth it (for many property methods, getID() { return id;} for example, this makes perfect sense).

So in a C++ binary, you often get code that is simply linear steps of program instructions. The CPU will load chunks of code into the cache and execute them as fast as it can. This is what makes modern CPUs perform.

Where CPUs stop performing is if when they have to stop and load a chunk of code from somewhere else. So, in the case of a javascript program where the functions are not known at compile time, and could be anywhere, the compiled program code will instead of jump instructions to the method location. If you're unlucky this can mean the CPU has to stop what its doing, load a new block of code containing the method, execute it, and the return where it came from. You can see this is way less efficient than simply reading 'id' in my simple example.

Note that this isn't a C++ thing. Very early C+ compilers were written as translators to C, so a C++ class would be turned into C code that had a struct and a set of function pointers which would then be compiled by a C compiler.

I've glossed over many complications (including some C++ polymorphism) and optimisations and 'workarounds' CPU and compilers can do to make this work better, but you get the fundamental idea behind it, mainly that compile time processing is faster than runtime processing.

If you want to design a fast language, make it so as much information can be calculated in the compile stage so it doesn't have to be done at runtime. You could design a prototype-based class system and if you could parse the entire program and figure out beforehand where each function was, then you could compile it to machine code that performed as well as a C++ program. The problem is that such a parsing might be more complex than running it! (note that some C++ compilers have a run-time optimisation mechanism where runtime info is calculated and used to feed back into subsequent compiles!)