Tharsis presentations

I’m well overdue with my next Tharsis update, which I’ve been planning to write since 3 months ago or so. For now, here are two presentations I gave on Tharsis recently. The first presentation explains the rationale for component-based entities, while the second concentrates on Tharsis itself and its potential performance limitations.

Meanwhile, work on Tharsis is moving (slowly... but still moving). Currently I’m working on an example Process and Component that would handle entity spawning while allowing to modify the entity being spawned (e.g. by overriding its components). Processes and Components such as these will be packaged with Tharsis as an optional library to cover most common use-cases for beginners while advanced users will be able to write their own.

Designing an entity system with threading in mind

At the core of Tharsis, like many other entity systems, are Components and Processes (called Systems in many other frameworks). A Component a simple data struct with no methods. A Process is a class with a process() method called by Tharsis for every entity containing components matching its signature.

Note

Components can’t have a copy constructor or a destructor. Tharsis generates code to load components, and moves them around by direct copying. Components can’t own any memory, but they can refer to Resources such as 3D models or sounds. I will likely write about resources in a future post.

The naive threaded approach is to run processes in separate threads, locking entities as they’re processed. Deadlocks are not an issue as long as entities are processed in the same order, but with large numbers of entities, locking overhead may negate the gains made by parallelization.

In the best case, threads never fight over an entity and we can expect overhead in 10s of nanoseconds per lock. With 30 processes and 5000 entities that adds up to 150000 locks per game update, or more than 1.5 milliseconds; roughly 10% of an update at 60FPS. In reality, threads will fight over data, making this overhead much greater, and worst of all, unpredictable.

Tharsis avoids this by using immutable data; if we keep a copy of state from the previous update and never change it, we can read it without locking.

Past and future

Tharsis has a concept of past state; processes read components from the previous game update and generate future state, which will be the past in the next game update. We have two copies of all game state, similar to double buffering in graphics; past and future buffers are switched between updates, reusing memory. This may seem wasteful, but most memory in a game is usually used by resources such as textures and sounds, not by the game state itself.

We still need to prevent processes to fight over future state they write. Tharsis requires no more than one process to write future state of any component type. This rule may seem limiting, but I found it straightforward to design processes with it in mind; in fact, it forces the code to be separated into a greater number of simpler, atomic processes. Greater process count also improves scalability as we can utilize more cores.

Separating past and future also removes a common problem of component-based entity systems; order the processes run influencing the game behavior.

For example, in a ‘traditional’ component-based entity system, process A multiplies matrices, process B changes health, and process C then starts with a different state than on the beginning of the game update. In Tharsis, a process cannot change the state read by the other processes during an update, since all processes read the immutable past.

Diagram comparing the run order dependencies in traditional component-based entity systems with Tharsis

With a conventional component-based entity system, the game may behave differently based on the order the processes (systems) run in. In this diagram, health affects the speed of an entity, resulting in different position at the end of the frame based on which process runs first. This can accumulate over time, and with many processes may even break the game. Tharsis avoids this by only allowing processes to read the state from the previous frame.

Memory

The past-future distinction has an interesting side effect; components can be removed by not copying them into future state. This enables us to tightly pack components in arrays with no gaps, avoiding cache misses.

For every process, code generated by Tharsis reads these arrays and passes components to the process. If a process writes future components, references to a future component array are also passed. A process can also decide not to write a future component for an individual entity; this can be used to remove components. After processing all entities, we have an array of future components with no wasted space. Note that the future components are written into the past buffer from previous update, avoiding reallocations.

Diagram of memory layout in Tharsis

MultiComponents are component types that allow multiple components of that type per entity. They are passed to processes using D array slices. A MultiComponent type must specify maximum number of components per entity for Tharsis to preallocate enough space. MultiComponents would not be viable without separate past and future; we would need to either insert new components in the middle of a buffer or give up on array storage. Since future components are created as a process sequentially processes entities, they are always added to the end of the buffer.

Conclusion

In current games it’s common to use a small, fixed number of threads for game logic and background worker threads for easily threadable tasks. This works with a small, fixed number of cores (such as on a console), but doesn’t scale well to many-core machines we’re likely to see in future.

I hope that Tharsis will provide a way to program threaded games scalable to tens of CPU cores without manually managing threads. That said, there will always be some need for direct control over threads; especially with dependencies such as OpenGL and SDL. I plan to allow the user to force a process to run in a specific thread if needed.

Tharsis

In the previous post I described my issues with a component-based entity system I used when working on ICE. The most important of these was probably the inability to split the entity system into multiple threads.

Tharsis is my attempt to design an entity component framework without these limitations. Tharsis is a stand-alone project, not tied to any single game. Its main goals are:

  • Simulation results should be independent of how the processes (Tharsis’ equivalent for systems in entity frameworks such as Artemis) are ordered.
  • Processes shoule be automatically assigned to separate threads (mostly) without explicit thread management by the programmer.
  • Performance should scale with increasing amount of cores (as long there is a large enough number of processes).
  • Efficient memory organization, keeping CPU cache in mind.
  • Open source with liberal (Boost) licencing.

The design of Tharsis also has other advantages, such as type safety (utilizing compile-time features of the D language), MultiComponents and serialization of entities.

I hope to write a series of posts describing Tharsis and its development as I add new features. Meanwhile, if you need a D component entity system right now, check out ArtemisD.

Component-based entities in ICE

During the development of ICE, I made a component-based entity system similar to the design described on Adam Martin’s blog. This was a massive improvement over my previous projects which used OOP-style entities. The complex inheritance-based hierarchies disappeared, and all entities were defined in data (YAML files), which made ICE very moddable.

That said, this entity system had its own issues, mostly because it was written in hurry without thinking through its high-level design.

The main problems were:

  • Serialization

    Every component type had to implement code to load a component from YAML. This resulted in various little inconsisitencies (especially in combination with non-trivial data members such as arrays), which made it impossible to add a general serialization system on top of the entity system without a massive rewrite.

  • System run order dependencies

    Every system would modify components that would then be processed by another system. The game behaved differently depending on the order systems were run, leading to some unavoidable and some unexpected dependencies between systems. This escalated to the point where changing the order of systems would break the game.

  • Threading (or lack thereof)

    The initial design of ICE did not include multithreading; it was ‘to be added later’. Once multiple threads were needed, it was impossible without locking every entity by every system, which would lead to massive overhead. Run order dependencies described above made it even worse, as did the ability to get direct pointers to entities and their components. There were too many cases where a system could modify data processed in a different thread.

  • Garbage

    Entities/components in ICE were in arrays for cache locality, and could be accessed by pointers. This made it impossible to move them. There was no efficient way to reuse memory after removing an entity; erasing an element from the middle of an array would be too slow. The only easy way to reuse dead entities was to reuse space when an entity with exactly the same components was added. Even so, over the course of a single game, the amount of wasted memory continued to increase.

  • Components with ‘subcomponents’

    Similarly to other RDBMS-style entity systems, ICE allowed either zero or one component of any single type in an entity. Furthermore, adding or removing components from an entity was not allowed. This allowed very efficient storage of components, but I ended up using components consisting of multiple ‘subcomponents’. For example, a unit might have multiple weapons, or multiple spawn conditions. I used RAII containers here, eventually requiring hidden static allocators. It would be more natural to allow multiple components.

After the first (and probably last) release of ICE I started an overhaul of the entity system. Around that time, Elvis Zhou made a post

at the D forums about a D port of Artemis, an entity system framework. That made me notice existing entity systems similar to the one I used in ICE, and many of the same flaws. For example, Artemis has the same problem with dependencies of systems on the order they run, and its design does not help threading. Also, unlike ICE, its components are quite heavyweight and cache unfriendly.

None of the component based entity frameworks I’ve seen seems to fit my requirements (especially with regard to threading and efficiency). That’s why I decided to start Tharsis, an entity framework that should hopefully address these issues.