Настроение:	amused
Entry tags:	computing

How efficient is ECS?

Well, we all know that doing

  struct agent_t {
    int guid;
    int type;
    bool is_ally;
    bool is_herbivore;
    ...
  }

Is a really bad idea, since the bools will waste a lot of memory and to do
analytical operations (i.e. listing all matching objects) you have to go through
every object. So even if the struct is heavily packed into a bit stream, and
your CPU has bit unpacking support, it is still super memory intensive.

Now storing separate columns allows packing bools as actual bits.
Therefore ECS reduces the memory requirement to store the same data.

There is of course the question of mapping from, the agent_t.guid to
the bit, when only part of the agents have these field.
That mapping is probably the hardest part about ECS or columnar DBs generally.
But it is solvable with a page table and allocating guids for specific types
in blocks.  Then the lookup comes down to something like:

  uint64_t index = guid - min;
  return index < size ? data[index] : NIL;

Yet since allocation happens in blocks, we can pack adjanced bits with
1d version of a sparse voxel tree. Voila! We have less than 1 bit per field!
It is also possible to iterate over all these items without going through
a huge bit array. I.e. if you allocated 1024 carnivores in a row, you've just
compressed 1024 bits into 1!

Although implementing such trees efficiently is non-trivial and requires
unrolling the recursion. Yet that is probably the most efficient way to
implement set theoretic structures in your program, and games are all about
set theoretic relationships. So it is a core data structure, you have to
implement in the best way possible. And ECS opens a way to do that.