Sigma
Sigma copied to clipboard
adam4813
Replace VectorMap by MapArray container for components.
VectorMap suffers from recurrent pointers invalidation due to the dynamic behaviour of vectors. Moreover, iterators give elements in the order of insertion and not the natural order of entity IDs.
These issues lead to the necessity of a constant synchronization of pointers in entity instances, and the bad usage of CPU cache when iterating in natural order, such as when using a BitArray iterator.
This PR propose a new data structure that doesn't have these issues. Pointers are constant during the life of the application and iterators are in natural order.
The data structure is now an ordered map of arrays. Each array is a chunk of 16 components for consecutive entity IDs. The complexity is O(log(n/16)). Since pointers are now constant, the result can be cached by the caller. The address of each chunk can also be cached to avoid to access the map, thus accessing the data of the chunk by index. This data structure consumes more memory since an empty component is created in the empty slots of the chunk. A proper id management is needed to try to use all slots.
This PR shows the effect of this data structure on the orientation component initialized in BulletMover. There is no more need for a "Orientation" object wrapping a pointer to be passed to the entity. Instead the raw pointer is stored since it is always valid.
This simplification allows a big simplification of EntitySystem, since we don't need to centralize the storage of data, but only a bit of information to tell whether an entity has a component or not before trying to access the data (which may be undefined even if the pointer is valid).
The biggest simplification is that we get rid of the need to synchronize the pointers, which is a pain.
Feel free to comment this. This is an unfinished work, I will commit the adaptation of remaining components later.
What about a map of sets? That would allow only 1 instance of a component and it also doesn't suffer the issue of vector resizing plus it takes advantage of the tried and true stl that doesn'trequire us to debug it.
Once we have the bigger design in place micro optimizing by using our own container with the same interface will be a piece of cake. On Jan 26, 2014 4:46 PM, "catageek" [email protected] wrote:
Feel free to comment this. This is an unfinished work, I will commit the adaptation of remaining components later.
— Reply to this email directly or view it on GitHubhttps://github.com/adam4813/Sigma/pull/156#issuecomment-33333249 .
I see what you mean and I agree on the fact that we will have a working code faster with a map of set.
I keep the map of arrays as a TODO to store data in chunks so that we fill a full CPU cache when iterating.
I will commit the change later.
Sounds good. It makes sense to use a buckets like approach at some point to improve memory use and performance. On Jan 27, 2014 12:09 AM, "catageek" [email protected] wrote:
I see what you mean and I agree on the fact that we will have a working code faster with a map of set.
I keep the map of arrays as a TODO to store data in chunks so that we fill a full CPU cache when iterating.
I will commit the change later.
— Reply to this email directly or view it on GitHubhttps://github.com/adam4813/Sigma/pull/156#issuecomment-33344047 .
Trying to replace the array of T by a set of T, I saw that the set interface does not have operator[]. The change would necessitate to use find() and extract the value from the iterator, resulting in more code. The use of C-array is not prone to bugs, it is only the validity of the data that must be provided externally.
I prefer write exhaustive unit tests to check the functionality of the class. Talking about unit tests, are there plans to fix #148 ? I am the only one to be bothered with this ?
Updated with latest evolution, including CompositeSystem and Benchmark engine.
Note that a new test.sc file is included in this PR to be full ECS compliant regarding Physic system.