7 hours ago, Thomas Izzo said:

Your API seems clean and simple which I like. However, I'm curious how you efficiently handle modifying the index when new entities are added/removed.

More specifically, how do you efficiently update the returned index whenever a new entity/component is added? It seems like it would be inefficient to have to iterate over every entity to generate the new EntityIndex array whenever a single entity is added or removed.

I realize this is an implementation detail that I could optimize in the future.

Actually, for my purposes that turned out rather easy but it is definitely a behind the scenes type of thing.  First, everything in that API is actually deferred and does not run immediately.  This is a painful thing to implement and still keep the nice API, but it is doable.  Now that everything is deferred it means that because my engine is fully threaded, I do a lot of lazy cleanup.  So, with entities and components being added/removed in bulk, performing a little sort on the data and then updating the indexes is quite efficient.  I'm not sure if there is a proper name for my method of insert/delete, but it is generally a couple memcpy's.  I start at the highest thing to be inserted and binary search for the location it should be in the index.  I memcpy everything at that location to the end up in memory by the total number of items to be inserted.  Copy the new index and pop it, repeat till done but only moving the portion of memory to the point right before the insertion.  Eventually the gap you made fills in and you've only moved any given element once.

Overall it is a reasonable approach, I think I have some ideas to make it work faster but haven't bothered since in the ridiculous stress test I run the insert/delete hasn't shown up in the top 100 hot spots yet.  The test adds/removes on average five thousand components and three thousand entities every second, so it is being beaten on significantly.

On 7/18/2018 at 6:00 PM, gaxio said:

In an engine I did in C, I actually used #1 but taken to the Nth degree: all entities have memory for all components and a flag to determine which component the entity really has.  It wastes memory, but for a small game, who cares?  It'll make more cache misses since the stride of your iterations is going to be large, but again, for small games who cares?  I even had a fixed limit on

This is actually close to how I started my implementation, though the blocks of memory were per component type.  Basically I had arrays for each component which were not sparse, this had the advantage that for common components such as transform, things were nice and linear in memory during iteration.  The down side is as you mention, the rare components like cameras wasting a bunch of space and being scattered about in those huge arrays.  When I moved to sparse arrays I left the option for fixed arrays for certain components such as transform that exists on basically everything.  Overall, with high create/destroy rates, the fixed arrays were about 5% faster, so not an insignificant win. On the other hand, after implementing the lazy sorting of components (a VERY good reason to never have non POD data in components) sparse arrays were pretty much equivalent once the ordering stabilized in contiguous memory space.  Basically if you are adding/removing components a rapidly the linear blocks are better, if you are not constantly fiddling with components the sparse arrays have an initial inefficiency but quickly converge, so usually it only takes a few frames before they are equivalent again.

The whole point though is that I highly suggest implementing the pattern correctly initially, no matter how slow, so you understand how things are supposed to work.  Then understand what bits and pieces you really need before getting into the performance side.  Maybe the simple starting implementation is good enough, for many games it probably will be in fact.  My implementation evolved for the purpose of experimenting with how best to multithread an entire game engine, so probably 50% of the code is complete overkill for most folks.  But is sure is fun to use it and bring 16+ core ThreadRipper's/Epyc or i9's/Xenon to their knee's without wasting most of the CPU on overhead.

On 7/19/2018 at 5:08 PM, All8Up said:

Actually, for my purposes that turned out rather easy but it is definitely a behind the scenes type of thing.  First, everything in that API is actually deferred and does not run immediately.  This is a painful thing to implement and still keep the nice API, but it is doable.  Now that everything is deferred it means that because my engine is fully threaded, I do a lot of lazy cleanup.  So, with entities and components being added/removed in bulk, performing a little sort on the data and then updating the indexes is quite efficient.  I'm not sure if there is a proper name for my method of insert/delete, but it is generally a couple memcpy's.  I start at the highest thing to be inserted and binary search for the location it should be in the index.  I memcpy everything at that location to the end up in memory by the total number of items to be inserted.  Copy the new index and pop it, repeat till done but only moving the portion of memory to the point right before the insertion.  Eventually the gap you made fills in and you've only moved any given element once.

Overall it is a reasonable approach, I think I have some ideas to make it work faster but haven't bothered since in the ridiculous stress test I run the insert/delete hasn't shown up in the top 100 hot spots yet.  The test adds/removes on average five thousand components and three thousand entities every second, so it is being beaten on significantly.

I've been reading over your original post a few more times. I'm curious, how do you structure your entities hold references to their components?

As of currently, I'm picturing an entity as a class that contains an entity_id, component_mask, and then an array of component id references.

However, because each entity could hold a different amount of components, I don't know the best method for having my entity hold references to its components?

Let's say I have 64 component types, I could have my entity class contain an array (size 64) that holds references to its component ids. However, this seems like a great way to waste space since not every entity will require a component instance. Thus my array of 64 integers would be somewhat bulky for simple entities that only require few components.

So in your "GetComponent" method, how do you actually link an entity and component? Does the entity hold a reference to its component? Or does the component hold a reference to its entity? 

15 minutes ago, Thomas Izzo said:

I've been reading over your original post a few more times. I'm curious, how do you structure your entities hold references to their components?

As of currently, I'm picturing an entity as a class that contains an entity_id, component_mask, and then an array of component id references.

However, because each entity could hold a different amount of components, I don't know the best method for having my entity hold references to its components?

Let's say I have 64 component types, I could have my entity class contain an array (size 64) that holds references to its component ids. However, this seems like a great way to waste space since not every entity will require a component instance. Thus my array of 64 integers would be somewhat bulky for simple entities that only require few components.

So in your "GetComponent" method, how do you actually link an entity and component? Does the entity hold a reference to its component? Or does the component hold a reference to its entity?

This does indeed get quite and complicated at that point as it is fairly indirection heavy.  First off, I would seriously suggest starting with a very simple array of arrays implementation to get started, it may be good enough for your purposes.  But, if that is not the goal, it goes along the following lines:

EntityHandle (uint32_t index) -> EntityData (uint64_t mask)
                                               -> ComponentContainer(s) -> ComponentData

What that is trying to describe is that the entity handle is actually a fixed index which can index into an array of "EntityData" structures and also the index into each of the ComponentContainer arrays which in turn index into the actual ComponentData.

So, effectively this means there is a bit of double indirection going on.  First from the handle to an index, the handle can not change after creation so it is mapped into an array which overtime ends up with some holes.  The holes are part of a free list and as such eventually get reused.  Anyway, the API for this ends up as follows:

enum class EntityHandle : uint64_t {eInvalid = uint64_t(-1)};

EntityHandle Alloc();
Free(EntityHandle);
uint32_t Get(EntityHandle);
void Set(EntityHandle, uint32_t);
// NOTE: For my purposes I assert if any of this is used incorrectly.
// It is internal and means there is a bug in the ECS itself if it fails.

That's basically the entity handle API minus some utilities for the deferred support.  (NOTE: The API is internal and not exposed to the user.)  A handle is a unique uint64_t which allows you to store a uint32_t value.  Using that value, you can now index into the remaining arrays which are all packed such that no holes exist.  I.e. assume I free an entity, it's EntityData is no longer needed so the last entry in the EntityData array is copied into it's place and the index stored in the EntityHandle array is updated to the new position.  Components are updated in much the same manner but with one additional indirection for sparse components.

Things start getting more complicated at the component array level because those can be sparse and not all handles indirect to a valid component.  But, generally speaking it is just a variation of the EntityHandle style solution where you indirect into the actual data array yet again.  There are a couple tricky bits involved, especially when removing components, but overall it's not too bad if you get your head around the packed and free list styles of arrays involved.

Hope this is useful.