Entt: Call for comments: fewer allocations, faster destroy, slower each

[skypjack]

A lighting _call for comments_ about a change I'm working on.
The idea is to get rid of the available vector in the registry and replace it with an identifier that acts as an entry point of an implicit _freelist_ within the entities vector.

Put aside the details of the internal changes that are probably not so appealing, these are the benefits:

• Fewer allocations for obvious reasons.
• The destroy member function gets a x4 in terms of performance (results of a preliminary test), that is an incredibly boost!

The member functions involved by this change are:

• create: apparently it's not affected at all in terms of performance.
• destroy: gets a x4, it's worth it definitely.
• Registry::each: I've not yet tested it, but it could be slightly affected. However this function is already pretty slow by design and its intended use is mainly for serialization, so I wouldn't bother much for that.

As a side note, each member functions of views aren't affected at all.

From my point of view, the change is worth it. Fewer allocations and a faster destroy are something I'd like to have.

Unless someone comes with a good reason not to do it, I'm finalizing the change and merging it during the week.

The API of EnTT won't be affected at all.

[dbacchet]

does it mean that the entities vector is not tightly packed? Not an issue at all, just want to understand.
Is it gonna be something similar to http://bitsquid.blogspot.com/2011/09/managing-decoupling-part-4-id-lookup.html ?
I implemented a similar lookup table for my frameworks and the performance and level of control on the memory was totally worth it.

[skypjack]

@dbacchet

What it's called _packed array_ in the article is mostly similar to how sparse sets work (the internal data structures of EnTT).

The change I'm gonna doing is something slightly different and won't affect sparse sets at all fortunately.
It means that neither views nor iterations will suffer any performance hit. Packed arrays returned by views remain unchanged.

The entities vector is tightly packed today. It contains both entities in use and destroyed ones. Ironically, available is a perfect copy of it if you destroy all the entities and its sole purpose is to avoid iterating entities to find available entities.
After the change, the entities vector will still be a packed one. Entities in use will still occupy the position they occupy today. However, identifiers of destroyed ones will be used to create an implicit freelist and get rid of the other vector around.

Before someone asks it: no, the way identifiers and versions work won't change.
Apart for the lower memory usage and the performance boost on the destroy member function, users should not even notice the change.
From outside, everything will remain exactly the same.

---

Trust me: the change is harder to describe than to code. :-)
I'll push it in a single commit, so that you can look at it to understand how it works.

[skypjack]

Here it is (7baf608). Unless someone gives me a good reason not to merge it with master, I'll do it tomorrow.

Affected functions:

• create (creating 10M entities: 0.0388s -> 0.0423s)
• destroy (destroying 10M entities: 0.0828s -> 0.0221s)

Registry::each has been slightly affected, but I've not benchmarks for it. However, the performance hit is probably minimal and I prefer a faster destroy than a faster Registry::each.
All the other functions around have not been involved by this commit.

@dbacchet
If you get a look at it, let me know what you think. Thank you. :-)

[DomRe]

Looks like a nice bit of extra performance. Thanks :)

[skypjack]

@reworks
I tried to figure out why in EnTT everything was much faster than with other well known ECS while the destroy was so slower.
Moreover I focused on the available vector because it looked to me like I was wasting memory for no benefits and I guessed how to get rid of it.
Fortunately both the answers where in the same place. :-)

[skypjack]

So far, so good. I'm going to merge the PR with master because it seems a widely accepted tradeoff. Time to close the issue.

Thank you all for your feedback.

[skypjack]

Just to mention it (I don't want to create an issue for that).
Another improvement is almost ready to merge. I'm working on it in my free time, so the schedule is hard to set.
It's a speed up on standard multi component views. For those that care about memory usage and do not create persistent views all around the codebase, it will give a boost from 20% up to 50% (how much mostly depends on the number of components of the view).
In some cases, as an example views built with two or three components when only half of the entities have one of the components (see the benchmark table for more details), results are comparable with the ones of other compile-time ECS.
Not that bad, isn't it? :-)