title: Designs of an entity component system
body: <p>
  I wonder how to implement the fastest version of an entity component system (ECS from now on) in C++.</p>
  
  <p>First off, regarding terminology:</p>
  
  <ul>
  <li>a <em>Scene</em> is a container for <em>Entities</em> (and <em>Systems</em> in some implementations)</li>
  <li>a <em>Component</em> is a simple data storage (like position, collision box, image to render etc)</li>
  <li>a <em>System</em> performs logic on <em>Components</em> fitting the <em>System's</em> requirements (this could be physics, player input, simple rendering etc.)</li>
  <li>an <em>Entity</em> contains several Components to make up the final behavior</li>
  </ul>
  
  <p>I listed all the designs we came up with below.</p>
  
  <hr>
  
  <h2>1. The "naive" way</h2>
  
  <p>The Scene contains all Entities unordered.<br>
  As the Systems update, every System has to loop through all Entities and check whether each Entity contains all required Components and then perform the update upon those Entities.</p>
  
  <p>Obviously, this way is not too performant when having a lot of Systems and/or a lot of Entities.</p>
  
  <hr>
  
  <h2>2. Using "bitmask enums" and mapping</h2>
  
  <p>Each Component contains a type identifier in the form of a bitmask (e.g. <code>1u &lt;&lt; 5</code> / binary <code>[0...]100000</code>). 
  Each Entity can then compose all Component's type identifiers (assuming all typeIDs are unique inside the Entity), so it looks something like </p>
  
  <pre class="lang-cpp prettyprint-override"><code>1u &lt;&lt; 5 | 1u &lt;&lt; 3 | 1u &lt;&lt; 1
  binary [0...]101010
  </code></pre>
  
  <p>The Scene contains some kind of map
  where Systems can easily look up fitting Entities:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>MovementSystem::update() {
      for (auto&amp; kv : parent_scene_) { // kv is pair&lt;TypeID_t, vector&lt;Entity *&gt;&gt;
          if (kv.first &amp; (POSITION | VELOCITY))
              update_entities(kv.second); // update the whole set of fitting entities
      }
  }
  </code></pre>
  
  <p><strong>Pros</strong>:  </p>
  
  <ul>
  <li>Faster than the naive way</li>
  </ul>
  
  <p><strong>Cons</strong>:</p>
  
  <ul>
  <li>Systems have to look up appropriate Entities <em>every single time</em> they are updated.</li>
  <li>A bitmask (enum) is limited to a number of bits (32 for <code>uint32_t</code>, at least 64 for <code>unsigned long long</code>) and in some cases you might need more Components than the bitmask allows.</li>
  </ul>
  
  <hr>
  
  <h2>3. Using no Systems</h2>
  
  <p>This method is described by <a href="https://stackoverflow.com/users/316448/danvil">Danvil</a> in an <a href="https://stackoverflow.com/a/23722720/1795160">answer below</a>.</p>
  
  <p><strong>Pros</strong>:</p>
  
  <ul>
  <li>Gets rid of the bitmask thing completely.</li>
  <li>Likely to be faster than design #2.</li>
  </ul>
  
  <p><strong>Cons</strong>:</p>
  
  <ul>
  <li>Relies on <code>dynamic_cast</code> for looking up a component whereas design #2 can directly look up a component and then safely <code>static_cast</code> it.</li>
  </ul>
  
  <hr>
  
  <h2>4. Using spare sets</h2>
  
  <p>This method has been described in by <a href="https://stackoverflow.com/users/4987285/skypjack">skypjack</a> in an <a href="https://stackoverflow.com/a/44057737/1795160">answer below</a>. He explained his approach in great detail, so I'd suggest you read his answer.</p>