Optimizing an HTML5 game engine using composition over inheritance

Hey, everybody!

Due to some vacations and other distractions we’re not quite ready to give you our bi-weekly CrossUpdate.
However, as promised, we now finally post our technical article about performance.

Here we go!

Incoming performance problems

We started with HTML5 game development around the end of 2011. We bought an impact.js license and started working on CrossCode. And since CrossCode demanded 3D collision, we modified the engine – and continued doing so until almost every nook and cranny was changed in one way or the other. So it’s safe to say that we did not only develop a game but a whole game engine with it.

And of course, whether you create a game or a game engine, performance is always an issue. To be frank, initially we did not pay too much attention to performance. We saw that our game was running with 60 fps on modern machines. 60 fps for an HTML5 game – what more do you want, right?

However, about half a year after we released the TechDemo++, things changed as we had a terrible realization:

Our game has become slower.

Yes, it was slower. Not because there was more content or complexity. When running the same maps with about the same number of entities, we experience an decrease in performance when comparing the latest development version with the TechDemo++.

Fortunately, we managed to fix these performance issues. And with this technical post, we want to share our experiences.

The core of the problem

Some time ago, Google released a very interesting video about optimizing JavaScript games for V8. Around 33:30 they describe how two properties of the code will decrease JavaScript performance, as they make it hard for V8 to apply its optimizations:

  1. Polymorphism: calling the same functions with lot of different input objects.
  2. Object size: a large number of properties per object.

Our game, as any game based on impact.js, uses composition over inheritance to implement entities.

It turns out that composition over inheritance in JavaScript will inherently lead to polymorphism and huge object sizes and therefore to performance issues. And the worst thing about this: these issues will not show right away but over time as you get a larger variety of complex entities.

Bummer, right? Well, let’s first explain the issue with composition over inheritance in more detail. Afterwards we will show you how you can still fix all this without implementing the whole entity system from scratch.

Composition over inheritance under the looking glass

What does composition over inheritance mean in our context? The idea is that the game engine provides a generic entity base class from which all other game entities should be derived. Derived entities classes can add more properties and implement new functionality. In a game engine such as impact.js it is encouraged that each new entity is created as a new class. So what we get is something like this:

entity-hierarchy

The first problem becomes apparent once our entities grow in complexity: since all functionality is stuffed into entity classes, we accumulate a huge amount of object properties. Here is an example how this applied to our ActorEntity class:

entity-properties

So in short: we easily passed the object property limit until which object access is optimized in V8.

The next problem lies in to the use of our entities within the game engine – the collision engine and rendering. Because collision and rendering is one process that is the same for all kind of entities, we inevitably arrive at this situation:

entity-process

And this, dear readers, is polymorphism to the max. To be precise, it wouldn’t be polymorphism for other object oriented languages such as C++. Those languages have an explicit object system, where the base class can be passed through these kinds of algorithms, guaranteeing fast property access. However, we’re talking about JavaScript here – a prototype-based language in which we merely simulate object oriented programming. As a result, we get flat object structures – one object containing the properties of all ancestor classes and the top class itself. So basically we have an individual object signature per entity class and therefore: polymorphism.

The consequence: the drawing and collision procedures are very hard to optimize for most of today’s JavaScript engines. And these procedures are the very bottlenecks of every game engine. So in short: bad news.

But fear not, as there are ways to fix this. And we don’t even need to throw away the whole composition over inheritance pattern.

Fixing the performance issues

Now that we understand the reason for the performance issues, it’s time to fix them. Since all these issues rise from the composition over inheritance pattern, an obvious “fix” would be to simply not use this pattern and move to something else, e.g. an entity component system. At this point we can basically overhaul the whole game engine itself – and that is not always an option. However, there is also the option to go for a mixture of both patterns, where you introduce components only for performance-critical aspects of entities and use composition over inheritance for everything else.

In our case, we decided to split the drawing and collision aspects of entities into separate components:

  • The drawing aspect is enclosed into Sprite components
  • The collision aspect is enclosed into CollEntry (Collision Entry) components

Both the Sprite and CollEntry components are free from any class hierarchy – there is only one class for each component, which is used for all entities. This is essential to make this fix work.

Entity properties are distributed among the entity class and the two new components. Since the drawing and collision aspects take a major share of these properties, the size of the entities class is greatly reduced.

entity-sprite-collentry

To retain control over all properties, the entity will simply keep a reference to both the Sprite and CollEntry components

Finally, performance-critical algorithms of the game engine are modified to work on the new components only: the collision detection operates on CollEntries and the rendering on Sprites.

And that is all. In practice, these modifications demand a huge amount of code refactoring. However, most of these changes are of syntactical nature, e.g. “this.pos.x” needs to be changed to “this.coll.pos.x”, whereas “coll” is the reference to the CollEntry from within the entity. We managed to refactor our (fairly blown up) game code in about 2 days.

Performance results

Optimizing JavaScript is tricky, since JavaScript engines do a lot of optimizations by themselves. This makes it more important than ever to avoid premature optimizations. You never exactly know what impact your changes will have on the overall performance. In our case, we detected the bottlenecks by comparing profiling results of the TechDemo++ and the current WIP version of CrossCode. Finally, to be certain that our optimizations did in fact help, we compared the overall performance before and after the changes.

First, we compared the collision performance before and after we introduced CollEntries. For this we used a collision stress-test, where plenty of NPCs were simply running against each other:

collision-test

We got the following results:

Browser ms per frame Improvement
before after
Chrome 32 10.7 – 11.6 ms 5.9 – 6.4 ms 45%
Firefox 27 7.8 – 8.4 ms 7.0 – 7.6 ms 10%
IE 10 5.4 – 6.0 ms 5.4 – 5.5 ms 4%

As you can see, we got a general improvement for all browsers. Especially the performance in Chrome increased a lot.

Second, we applied a similar optimization in our GUI system, where we extracted the most common parameters from the GUI base class into a separate Gui Hook class.
Again we used a stress-test, displaying the part of our menu with the most visible content:

menu-test

Again, we got a general improvement:

Browser ms per frame Improvement
before after
Chrome 32 6.0 – 6.2 ms 5.6 – 5.9 ms 6%
Firefox 27 5.0 – 5.8 ms 3.7 – 4.0 ms 29%
IE 10 4.0 – 4.4 ms 3.5 – 4.0 ms 11%

Interesting: even though we basically applied the same optimization, we get more speedup in the other browsers this time, especially in Firefox. We have no idea why that is, really. Again, JavaScript performance is kinda like black magic – it’s hard to tell why exactly things become faster.

Moral of the story

So what did we learn from all of this? How about: Drop composition over inheritance because it is slow! Right?

Frankly, we wouldn’t make this kind of statement. It is clear now that approaches such as the entity component system are a better choice with respect to performance. However, composition over inheritance still has other advantages. For instance, we think that our inheritance based entity classes are much easier to read and understand. In the end inheritance will only lead to performance problems if your game reaches a high degree of complexity. So if your game only includes a small number of entities with a low number of properties (something close to the regular impact.js engine), you’ll be fine. And even if you arrive at complex territory, you can still isolate bottlenecks and apply improvements as described in this article.

So in the end: there is no need to drop composition over inheritance all together.

And this concludes our technical report about performance!
I hope you learned something new about the wild and frustrating world of high performance JavaScript.

Until next time!

9 Comments

  • Awesome article! {:

    • James Pierce on March 11, 2014 at 12:02 am said:

      This was really well explained, thank you for sharing your valuable insights together with a solution. HTML5 Games are so not well documented in my opinion, info like this really stands out.

  • Interesting, starting I’m starting to get to the point where my entities are fairly complex. Haven’t run into these issues yet, but the areas I’m using ImpactJS for are fairly small. Also the maximum number of entities on the screen is usually about 40 for me at all time (other than menu systems opening).

  • Hey Lachsen,

    thanks for this excellent technical post. I think you pointed out a very essential trade-off faced by many programmers: Performance VS structure.

    Personally, I think that the highest priority should be an easy to understand architecture, that follows the principles of OOP such as modularity and extendability.

    Actually, JavaScript is a poor language. It shouldn’t be the concern of the programmer to change the architecture due to low-level performance issues beyond the language’s core API. But this might be a problem of dynamically-typed languages and their implementations (compilers) in general.

    I think you chose a good fix for the problem. Sacrificing just enough of a clear structure to overcome the performance issue. And after all, you stick to a known pattern (components).

    Always looking forward to new technical posts! :)

    Cheers!

    • Hi NicM!

      I generally agree, that a good architecture and structure are more important than best optimized code. It’s especially important to know that you only need to optimize the bottlenecks, which are usually only about 20-30% of the whole game code.

      However, I wouldn’t say, that it’s the fault of the language if you need to adapt your architecture for performance reasons. The correct data structures, which are governed by the architecture, are very often essential for good performance. So there is an dependency that is hard to avoid. That’s not only true for dynamic languages.

      And as far as I know, there are many OOP concept, especially those involving polymorphism (e.g. virtual functions in C++), that are problematic for highly optimized games.
      That’s at least one reason why people came up with the Entity Component Model in contrast to the traditional class inheritance, I think.

      Anyway, the problem with JavaScript really is, that it is often hard to understand, what exactly makes your application slow. That’s why I hope that this article is useful for people.

  • Hi Lachsen,

    thanks for responding!

    I agree that choosing the right data structures is key. But I regard this choice to be on almost the same level as the choices made for the architecture. It is an essential part of your design, independent of any language features (save some memory management issues maybe).

    What I was specifically referring to when talking about poor language, I meant the not-constant object property lookup. For me, this is not an issue the programmer should be concerned with. This is especially true since different implementations of JavaScript engines yield different performance results. And in any statically typed languages, property lookups are constant (Yes, I admit that I like them far more than messy dynamically-typed languages, at least for large-scale projects. ;)).

    I just wonder: Have you ever heard of a language called Eiffel? :)

    Cheers!

  • unique_ptr on May 24, 2014 at 7:29 am said:

    As a result, we get flat object structures – one object containing the properties of all ancestor classes and the top class itself.
    Ich weiß nicht was da nun der Unterschied zu Java oder C++ sein soll. Dort erbt man ebenfalls alle Attribute und Methoden einer Basisklasse.
    Nur weil man Prototypen anstatt Methoden ‘überschreibt’ hat man doch keine flache Objektstruktur, oder verstehe ich da etwas falsch? Ich sehe
    es eher so: Wenn man eine Vererbungshierachie wie ‘ActorEntity > AnimatedEntity > Entity’ mittels Prototypes ‘simuliert’, indem man z.B. die update() Funktion
    mehrfach überschreibt, wodurch dann Aufrufe wie update() … this.parent(); … this.parent(); … Zustande kommen, realisiert man ‘Subtyping-Polymorhpism’.
    Ich kenn mich nicht sonderlich gut mit JavaScript aus, aber ich glaube der Overhead entsteht dabei eher durch die Tiefen-Vererbungstrukturen und den Function-call Overhead.
    Das sichern des Stacks, übergeben der Parameter, cachen von lokalen Variablen, Heap-Allokationen usw.

    Ich finde es jedenfalls Verwirrend ‘Composition over Inheritance’ dafür verantwortlich zu machen, da eher die unnötig aufgeblähte Vererbungshierachie Schuld daran ist.
    Die Gründe dafür sind das man z.B.
    ‘Enemy > Collision > AnimatedSprite > Entity’
    gegeben hat, und zu ‘Collision’ gezwungen wird, obwohl es im Spiel auch Gegner ohne Kollision geben kann. Wie z.B.
    ‘Enemy > AnimatedSprite > Entity’
    oder gar
    ‘Enemy > Sprite > Entity’
    Da soetwas nich ohne Diamant-Vererbung möglich ist und man so auf vielfältige Kombinationen verzichten muss ist die Folge das auslagern in Komponenten.
    Entity
    {
    Animation;
    Sprite;
    Collision;
    KI;
    EventListener;
    }

    Es sind also überlicherweise ‘Entity-Component Systems’ wie auch bei eurer Neuerung, die mittels ‘Composition over Inheritance’ implementiert werden.
    Im Idealfall ist Entity nur ein Handle zu den Komponenten, die jeweils als Daten im SubSystem vorliegen. Durch das Auslagern in SubSysteme wie
    ‘SpriteRenderer’ oder ‘CollisionSolver’ kann auf simple klassiche update(), draw() Aufrufe verzichtent werden. Entity benötigt in diesem Sinne auch
    keine Vererbung mehr, da Funktionalität durch hinzufügen von Komponenten realisiert werden kann. Stichwort: Data-Driven-Design

    Eine ähnliche implementierung bietet z.B. das Artemis Entity System Framework
    http://gamadu.com/artemis/tutorial.html

    Das wegfallen der update()-Aufrufe ist dabei nicht unerheblich! Man stelle sich nur 100 Aufrufe im renderLoop weniger vor. Bei gleicher Funktionalität.
    Es ergeben sich weitere beliebte Vorteile:
    – Physik und Grafik ist völlig unabhängig, kann also theoretisch in verschiedene Threads ausgelagert werden (was in JavaScript wohl zur Quall wird)
    das könnte aber ein bedeutender Geschwindigkeitsvorteil sein, wenn man es richtig macht und geschickt mit Interpolationen arbeitet, lässt sich
    der Kollisionscode auch im 20ms oder 30ms loop Aufrufen, ohne deutlich sichtbare Macken. Das Kollisionssystems wird dadurch deterministisch und
    läuft auch bei verschiedenen Framerates immer zuverlässig, zusätzlich zu weniger CPU Verbrauch und der Möglichkeit von Replays/Rewinds. Wie z.B in Braid.

    http://gafferongames.com/game-physics/fix-your-timestep/

    – anstatt Enemy KI durch Vererbung zu implementieren kann Verhalten in KI StateMachines ausgelagert werden (die nur einmal programmiert werden müssen)

    lästige Dinge wie
    SlightlyChangedMobA > StandardMob > Enemy
    SlightlyChangedMobB > StandardMob > Enemy
    fallen dadurch weg und können zB durch

    enemyA.getComponent(“state-idle”).changePattern(new FollowHero());
    enemyB.getComponent(“state-attack”).changePattern(new SurroundHero());

    realisiert werden.

    – Systeme sind für ihre Daten veranwortlich, nicht die Entities
    , nehmen wir beispielhaft ein PhysicSystem, im Grunde gehört ‘velocity += accerleration * dt;’ nicht in eine Entity, sondern in das Kollisions System.
    Das kann man ebenfalls strikt in ‘CollisionDetection’ und ‘CollisionSolver’ trennen. Vorteilhaft ist da die Datenhaltung, was in JavaScript zu
    deutlichen Performance Steigerung führen kann. Ein physic.solve() kann alle Komponenten Daten in einem Array Speichern und die Verarbeitung kann durch
    Pooling von Berechnungen optimiert werden. Anstatt in Entities haufenweise new Vector2D() zu nutzen kann man systeminterne-lokale Variablen wiederverwenden
    und entlastet somit GarbageCollector und andere Speicherzugriffe.

    Na ja, vielleicht sejt ihr einige Punkte als Inspiration für weitere Optimierungen nutzen.
    Freut mich jedenfalls, dass ihr trotz der Missverständnisse einiges an Leistung pushen konntet.
    Irgendwo muss man wohl auch die Grenze ziehen. Es bleibt numal JavaScript ;D

    • Hi there.

      I hope it’s okay if I answer in English (more people can understand it easier that way).

      I have to admit, that the section about the flat object hierarchy could have been written more clearly. Anyway, fact is, we tested this: it’s not just the repeated function calls that are expensive, it is especially the property access. You can imagine it like this: a property access in JavaScript is basically like a virtual function call in C++, if the property access is not optimized. If you have the same function that receives objects with many different combinations of properties (which is the case if you just use the ‘flat entity objects’), it won’t be optimized, so property access will be very slow.

      This is different to C++. Here, property access is more efficient in the same context, because it can be statically evaluated. While it is true that all properties of a C++ class hierarchy are stored in a ‘flat object’, the properties are clearly sorted. The compiler basically get’s a pointer to the start of the memory block of a certain class object and can efficiently access all its properties and those of the parent classes via static offsets to the pointer. In JavaScript, we don’t really have this optimization, because of it’s prototype-based inheritance pattern: all non-constant properties of the whole class hierarchy are stored in one, generic object. The only structural information about the class hierarchy that remains is the connection of prototypes connected to that generic objects. And those prototypes only store the constant property e.g. constants and functions.

      So basically we’re just highlighting a dramatic issue about the composition-over-inheritance pattern in the context of JavaScript. This is not the original reason why people came up with the entity-composition system. Those you describe pretty well in your post. And we are aware of these issues as well. We usually design our entity classes such that they can be configured for all different use cases. Our enemies do have a kind of state-machine for their AI. We would never get the idea to create a different subclass for each enemy behavior.

      So yeah, collision and rendering are pretty clearly separated in our engine at this point, even operating on their own data structures. Of course, multi-threading optimizations are not very feasible at this point in JavaScript (though we might try something with Web Workers). We already reduced the object creation via new Vector2D() in our physics and rendering (there are many ways to do that), but you have a good point that it is possible to further optimize these component when relying heavily on array data structures. What you describe here is pretty much the approach of asm.js. Something that we might do in the future, is simply writing our rendering and physics cores in C/C++, compile it to JavaScript/asm.js with emscripten as libraries and connect it with the rest of the engine. I’m in fact pretty excited about this idea, but since our focus is currently not to create the most optimized engine, we’ll have a look at this later on.

      Anyway, thanks for pointing out all those technical details! You are clearly familiar with those concepts. :D

  • What you’ve described as composition over inheritance in Impact is actually just inheritance.

    The composition over inheritance achieved by using an entity component system instead. :)

One Trackback

  • By Happy New Year 2016 | A Programming Devblog on January 3, 2016 at 6:47 am

    […] classes – Too many properties; While this may not be significant, it can still be an issue for performance (CrossCode developers’ article on their experience with composite vs inherited classes) in […]

Post a Comment

Your email is kept private. Required fields are marked *