changed containers

7 files changed, 412 insertions, 162 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..1802ec8
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+main
+test
+xtest
diff --git a/EntityXBenchmark.h b/EntityXBenchmark.h
new file mode 100644
index 0000000..defa37c
--- /dev/null
+++ b/EntityXBenchmark.h
@@ -0,0 +1,155 @@
+#ifndef ENTITYXBENCHMARK_H_
+#define ENTITYXBENCHMARK_H_
+
+#include <string>
+#include <vector>
+#include <memory>
+#include <random>
+#include <numeric>
+#include <functional>
+
+#include "entityx/entityx.h"
+
+class EntityXBenchmark {
+    public:
+
+    struct PositionComponent {
+        float x = 0.0f;
+        float y = 0.0f;
+    };
+
+    struct DirectionComponent {
+        float x = 0.0f;
+        float y = 0.0f;
+    };
+
+    struct ComflabulationComponent {
+        float thingy = 0.0;
+        int dingy = 0;
+        bool mingy = false;
+        std::string stringy;
+    };
+
+
+    // Convenience types for our entity system.
+    using Entity = entityx::Entity;
+    using EntityManager = entityx::EventManager;
+    using EventManager = entityx::EventManager;
+
+    template <typename C>
+    using Component = entityx::ComponentHandle<C>;
+
+    using TimeDelta = entityx::TimeDelta;
+
+
+
+    template<class S>
+    using System = entityx::System<S>;
+
+
+    class MovementSystem : public System<MovementSystem> {
+        public:
+        MovementSystem() = default;
+
+        void update(entityx::EntityManager &es, entityx::EventManager &events, entityx::TimeDelta dt) override {
+            Component<PositionComponent> position;
+            Component<DirectionComponent> direction;
+
+            for (auto entity : es.entities_with_components(position, direction)) {
+                position->x += direction->x * dt;
+                position->y += direction->y * dt;
+            }
+        }
+    };
+
+    class ComflabSystem : public System<ComflabSystem> {
+        public:
+        ComflabSystem() = default;
+
+        void update(entityx::EntityManager &es, entityx::EventManager &events, entityx::TimeDelta dt) override {
+            Component<ComflabulationComponent> comflab;
+
+            for (auto entity : es.entities_with_components(comflab)) {
+                comflab->thingy *= 1.000001f;
+                comflab->mingy = !comflab->mingy;
+                comflab->dingy++;
+                //comflab.stringy = std::to_string(comflab.dingy);
+            }
+        }
+    };
+
+    #ifdef USE_MORECOMPLEX_SYSTEM
+    class MoreComplexSystem : public System<MoreComplexSystem> {
+        private:
+        int random(int min, int max){
+            // Seed with a real random value, if available
+            static std::random_device r;
+        
+            // Choose a random mean between min and max
+            static std::default_random_engine e1(r());
+
+            std::uniform_int_distribution<int> uniform_dist(min, max);
+
+            return uniform_dist(e1);
+        }
+
+        public:
+        MoreComplexSystem() = default;
+
+        void update(entityx::EntityManager &es, entityx::EventManager &events, entityx::TimeDelta dt) override {
+            Component<PositionComponent> position;
+            Component<DirectionComponent> direction;
+            Component<ComflabulationComponent> comflab;
+
+            for (auto entity : es.entities_with_components(comflab, direction, comflab)) {
+                if(comflab) {
+                    std::vector<double> vec;
+                    for(size_t i = 0;i < comflab->dingy && i < 100;i++){
+                        vec.push_back(i * comflab->thingy);
+                    }
+
+                    int sum = std::accumulate(std::begin(vec), std::end(vec), 0.0);
+                    int product = std::accumulate(std::begin(vec), std::end(vec), 1, std::multiplies<double>());
+
+                    comflab->stringy = std::to_string(comflab->dingy);
+
+                    if(position && direction && comflab->dingy % 10000 == 0) {
+                        if(position->x > position->y) {
+                            direction->x = random(0, 5);
+                            direction->y = random(0, 10);
+                        } else {
+                            direction->x = random(0, 10);
+                            direction->y = random(0, 5);
+                        }
+                    }
+                }
+            }
+        }
+    };
+    #endif
+
+    class Application : public entityx::EntityX {
+        public:
+        Application() {
+            this->systems.add<MovementSystem>();
+            this->systems.add<ComflabSystem>();
+            #ifdef USE_MORECOMPLEX_SYSTEM
+            this->systems.add<MoreComplexSystem>();
+            #endif
+
+            this->systems.configure();
+        }
+
+        void update(TimeDelta dt) {
+            this->systems.update<MovementSystem>(dt);
+            this->systems.update<ComflabSystem>(dt);
+            #ifdef USE_MORECOMPLEX_SYSTEM
+            this->systems.update<MoreComplexSystem>(dt);
+            #endif
+        }
+    };
+
+    static constexpr double fakeDeltaTime = 1.0 / 60;
+};
+
+#endif // ENTITYXBENCHMARK_H_
diff --git a/Makefile b/Makefile
index 12b3c0c..b1a2703 100644
--- a/Makefile
+++ b/Makefile
@@ -2,5 +2,6 @@ all:
 	g++ -std=c++17 -ggdb -pedantic -Wall -Wextra main.cpp -o main -lentityx
 
 test:
-	g++ -std=c++17 -Wall -Wextra bench.cpp -o test -O1
+	g++ -std=c++17 -Wall -Wextra bench.cpp -o test -O1 
+	g++ -std=c++17 -Wall -Wextra xtest.cpp -o xtest -O1 -lentityx
 	
diff --git a/README.md b/README.md
index 6059fb4..5ee9502 100644
--- a/README.md
+++ b/README.md
@@ -1,2 +1,49 @@
 # entities
 A C++ simple entity component system
+
+## the library
+The file that actually contains the library is entities.hpp.
+
+## compared to EntityX
+entities:
+```
+entityx create destroy entity with components     5000000         254 ns/op
+      [25] entityx       25 entities component systems update     1000000        1572 ns/op
+      [50] entityx       50 entities component systems update      500000        3009 ns/op
+     [100] entityx      100 entities component systems update      200000        5995 ns/op
+     [200] entityx      200 entities component systems update      100000       11848 ns/op
+     [400] entityx      400 entities component systems update       50000       23631 ns/op
+     [800] entityx      800 entities component systems update       20000       51669 ns/op
+    [1600] entityx     1600 entities component systems update       10000      112446 ns/op
+    [3200] entityx     3200 entities component systems update        5000      225504 ns/op
+    [5000] entityx     5000 entities component systems update        5000      368282 ns/op
+   [10000] entityx    10000 entities component systems update        1000     1240502 ns/op
+   [30000] entityx    30000 entities component systems update         200     5196731 ns/op
+  [100000] entityx   100000 entities component systems update         100    18331731 ns/op
+  [500000] entityx   500000 entities component systems update          20    93182044 ns/op
+ [1000000] entityx  1000000 entities component systems update          10   191315282 ns/op
+ [2000000] entityx  2000000 entities component systems update           5   299790721 ns/op
+./test 43.175s
+```
+
+EntityX:
+```
+entityx create destroy entity with components     5000000         200 ns/op
+      [25] entityx       25 entities component systems update      500000        2903 ns/op
+      [50] entityx       50 entities component systems update      200000        5721 ns/op
+     [100] entityx      100 entities component systems update      100000       11338 ns/op
+     [200] entityx      200 entities component systems update       50000       22622 ns/op
+     [400] entityx      400 entities component systems update       50000       45560 ns/op
+     [800] entityx      800 entities component systems update       20000       92718 ns/op
+    [1600] entityx     1600 entities component systems update       10000      180159 ns/op
+    [3200] entityx     3200 entities component systems update        5000      360127 ns/op
+    [5000] entityx     5000 entities component systems update        2000      563316 ns/op
+   [10000] entityx    10000 entities component systems update        1000     1130659 ns/op
+   [30000] entityx    30000 entities component systems update         500     3431964 ns/op
+  [100000] entityx   100000 entities component systems update         100    11680312 ns/op
+  [500000] entityx   500000 entities component systems update          20    59996331 ns/op
+ [1000000] entityx  1000000 entities component systems update          10   128663563 ns/op
+ [2000000] entityx  2000000 entities component systems update           5   271582063 ns/op
+./xtest 41.912s
+```
+You can find EntityX [here](https://github.com/alecthomas/entityx).
diff --git a/entities.hpp b/entities.hpp
index 3580d65..4291e3f 100644
--- a/entities.hpp
+++ b/entities.hpp
@@ -7,10 +7,10 @@
 
 #include <algorithm> // std::find_if
 #include <type_traits> // std::is_convertible
-//#include "pvector.hpp"
 #include <vector>
+#include <forward_list>
+#include <map>
 
-#define Container std::vector
 
 /**
  * @class Component
@@ -35,7 +35,8 @@ struct EntityData {
 	Id id;
 
 	/** A vector of all components. */
-	Container<Component*> components;
+	std::forward_list<size_t> componentHash;
+	std::forward_list<Component*> components;
 
 	/** Constructs an entity with the given ID. */
 	EntityData(Id _id = -1)
@@ -54,10 +55,10 @@ struct EntityData {
  * EntityManager's EntityData array.
  */
 struct Entity {
-	Container<EntityData>::iterator pos;
+	std::vector<EntityData>::iterator pos;
 
 	/** Constructs an entity object to handle the given entity data. */
-	Entity(Container<EntityData>::iterator p)
+	Entity(std::vector<EntityData>::iterator p)
 		:  pos(p) {}
 	Entity(EntityData& d)
 		: pos(&d) {}
@@ -72,7 +73,8 @@ struct Entity {
 		static_assert(std::is_convertible<T*, Component*>::value,
 			"components must inherit Component base class");
 		auto comp = new T(args...);
-		(*pos).components.push_back(comp);
+		(*pos).components.push_front(comp);
+		(*pos).componentHash.emplace_front(typeid(T).hash_code());
 		return comp;
 	}
 
@@ -83,10 +85,15 @@ struct Entity {
 	void remove(void) {
 		static_assert(std::is_convertible<T*, Component*>::value,
 			"components must inherit Component base class");
-		auto c = std::find_if((*pos).components.begin(), (*pos).components.end(),
-			[](auto c){ return dynamic_cast<T*>(c); });
-		if (c != (*pos).components.end())
-			(*pos).components.erase(c);
+		auto it = (*pos).componentHash.begin();
+		auto ic = (*pos).components.before_begin();
+		for (; it != (*pos).componentHash.end(); ic++, it++) {
+			if (*it == typeid(T).hash_code()) {
+				(*pos).components.erase_after(ic);
+				break;
+			}
+		}
+		(*pos).componentHash.remove(typeid(T).hash_code());
 	}
 
 	/**
@@ -97,9 +104,7 @@ struct Entity {
 	bool hasComponent(void) const {
 		static_assert(std::is_convertible<T*, Component*>::value,
 			"components must inherit Component base class");
-		auto c = std::find_if((*pos).components.begin(), (*pos).components.end(),
-			[](auto c){ return dynamic_cast<T*>(c); });
-		return c != (*pos).components.end();
+		return std::binary_search((*pos).componentHash.begin(), (*pos).componentHash.end(), typeid(T).hash_code());
 	}
 
 	/**
@@ -110,9 +115,13 @@ struct Entity {
 	T* component(void) {
 		static_assert(std::is_convertible<T*, Component*>::value,
 			"components must inherit Component base class");
-		auto c = std::find_if((*pos).components.begin(), (*pos).components.end(),
-			[](auto c){ return dynamic_cast<T*>(c); });
-		return (c != (*pos).components.end()) ? dynamic_cast<T*>(*c) : nullptr;
+		auto it = (*pos).componentHash.begin();
+		auto ic = (*pos).components.begin();
+		for (; it != (*pos).componentHash.end(); ic++, it++) {
+			if (*it == typeid(T).hash_code())
+				return dynamic_cast<T*>(*ic);
+		}
+		return nullptr;
 	}
 };
 
@@ -123,7 +132,7 @@ struct Entity {
 class EntityManager {
 private:
 	/** The array of all entities. */
-	Container<EntityData> entities;
+	std::vector<EntityData> entities;
 
 public:
 	// max is not enforced
@@ -170,46 +179,25 @@ public:
 			f(Entity(i));
 	}
 
-	template<class T1>
-	void trySort(void) {
-		static unsigned int oldSize = 0;
-		if (entities.size() < 100000 && entities.size() != oldSize) {
-			oldSize = entities.size();
-
-			std::sort(entities.begin(), entities.end(),
-			[](auto&& e1, auto&& e2){
-					return Entity(e1).hasComponent<T1>() && !Entity(e2).hasComponent<T1>();
-			});
-		}
-	}
-
 	/**
 	 * Runs a function through all entities with the given components.
 	 * @param f the function to run through
 	 */
 	template<class T1>
 	void each(std::function<void(Entity e)> f) {
-		trySort<T1>();
-		bool good = false;
 		for (auto i = entities.begin(); i < entities.end(); ++i) {
 			Entity en (i);
-			if (en.hasComponent<T1>()) {
+			if (en.hasComponent<T1>())
 				f(en);
-				good = true;
-			} else if (good) break;
 		}
 	}
 
 	template<class T1, class T2>
 	void each(std::function<void(Entity e)> f) {
-		trySort<T1>();
-		bool good = false;
 		for (auto i = entities.begin(); i < entities.end(); ++i) {
 			Entity en (i);
-			if (en.hasComponent<T1>() && en.hasComponent<T2>()) {
+			if (en.hasComponent<T1>() && en.hasComponent<T2>())
 				f(en);
-				good = true;
-			} else if (good) break;
 		}
 	}
 };
@@ -225,7 +213,7 @@ public:
 
 class SystemManager {
 private:
-	Container<System*> systems;
+	std::map<size_t, System*> systems;
 	EntityManager& entities;
 
 public:
@@ -236,19 +224,14 @@ public:
 	void add(Args... args) {
 		static_assert(std::is_convertible<T*, System*>::value,
 			"systems must inherit System base class");
-		systems.push_back(new T(args...));
+		systems.try_emplace(typeid(T).hash_code(), new T(args...));
 	}
 
 	template<class T>
 	void update(DeltaTime dt) {
 		static_assert(std::is_convertible<T*, System*>::value,
 			"systems must inherit System base class");
-		for (auto s : systems) {
-			if (dynamic_cast<T*>(s)) {
-				s->update(entities, dt);
-				return;
-			}
-		}
+		systems.at(typeid(T).hash_code())->update(entities, dt);
 	}
 };
 
diff --git a/pvector.hpp b/pvector.hpp
deleted file mode 100644
index 8fb2f1b..0000000
--- a/pvector.hpp
+++ /dev/null
@@ -1,113 +0,0 @@
-#ifndef PVECTOR_HPP_
-#define PVECTOR_HPP_
-
-constexpr unsigned int pvectorSizeChange = 32;
-
-template<class T>
-class pvector {
-private:
-	T* items;
-	unsigned int _size;
-	unsigned int capacity;
-
-public:
-	class iterator {
-	private:
-		T* pos;
-	public:
-		iterator(T* p)
-			: pos(p) {}
-
-		T operator*(void) const {
-			return *pos;
-		}
-
-		template<typename N>
-		iterator operator+(N inc) const {
-			return pos + inc;	
-		}
-
-		iterator& operator++(void) {
-			++pos;
-			return *this;
-		}
-
-		template<typename N>
-		iterator operator-(N inc) const {
-			return pos - inc;
-		}
-
-		bool operator>(const iterator& i) const {
-			return pos > i.pos;
-		}
-
-		bool operator<(const iterator& i) const {
-			return pos < i.pos;
-		}
-
-		bool operator!=(const iterator& i) const {
-			return pos != i.pos;
-		}
-	};
-
-	pvector(void)
-		: items(new T[pvectorSizeChange]), _size(0),
-		capacity(pvectorSizeChange) {}
-
-	~pvector(void) {
-		delete items;
-	}
-
-	inline iterator begin(void) {
-		return iterator(items);
-	}
-
-	inline iterator end(void) {
-		return iterator(items + _size);
-	}
-
-	inline unsigned int size(void) const {
-		return _size;
-	}
-
-	T& push_back(T& t) {
-		if (_size >= capacity) {
-			auto nItems = new T[capacity + pvectorSizeChange];
-			for (unsigned int i = 0; i < capacity; i++)
-				nItems[i] = items[i];
-			delete items;
-			items = nItems;
-		}
-
-		auto& r = items[_size++] = t;
-		return r;
-	}
-
-	template<typename... Args>
-	T& emplace_back(Args... args) {
-		if (_size >= capacity) {
-			auto nItems = new T[capacity + pvectorSizeChange];
-			for (unsigned int i = 0; i < capacity; i++)
-				nItems[i] = items[i];
-			delete items;
-			items = nItems;
-		}
-		auto& r = items[_size++] = T(args...);
-		return r;
-	}
-
-	void erase(iterator it) {
-		for (unsigned int i = it - begin(); i < capacity; i++)
-			items[i] = items[i + 1];
-		_size--;
-	}
-
-	void clear(void) {
-		delete items;
-		items = new T[pvectorSizeChange];
-		_size = 0;
-		capacity = pvectorSizeChange;
-	}
-};
-
-#endif // PVECTOR_HPP_
diff --git a/xtest.cpp b/xtest.cpp
new file mode 100644
index 0000000..2f814c5
--- /dev/null
+++ b/xtest.cpp
@@ -0,0 +1,174 @@
+#include <string>
+#include <vector>
+#include <thread>
+#include <memory>
+
+#define BENCHPRESS_CONFIG_MAIN
+#include "benchpress.hpp"
+
+#include <entityx/entityx.h>
+
+#include "EntityXBenchmark.h"
+
+inline void init_entities(entityx::EntityManager& entities, size_t nentities){
+    for (size_t i = 0; i < nentities; i++) {
+		auto entity = entities.create();
+
+		entity.assign<EntityXBenchmark::PositionComponent>();
+		entity.assign<EntityXBenchmark::DirectionComponent>();
+
+		if (i % 2) {
+			entity.assign<EntityXBenchmark::ComflabulationComponent>();
+		}
+	}
+}
+
+inline void runEntitiesSystemsEntityXBenchmark(benchpress::context* ctx, size_t nentities) {
+    EntityXBenchmark::Application app;
+    auto& entities = app.entities;
+
+    init_entities(entities, nentities);
+
+    ctx->reset_timer();
+    for (size_t i = 0; i < ctx->num_iterations(); ++i) {
+        app.update(EntityXBenchmark::fakeDeltaTime);
+    }
+}
+
+
+
+
+BENCHMARK("entityx create destroy entity with components", [](benchpress::context* ctx) {
+    entityx::EntityX app;
+    auto& entities = app.entities;
+
+    ctx->reset_timer();
+    for (size_t i = 0; i < ctx->num_iterations(); ++i) {
+        auto entity = entities.create();
+
+        entity.assign<EntityXBenchmark::PositionComponent>();
+		entity.assign<EntityXBenchmark::DirectionComponent>();
+		entity.assign<EntityXBenchmark::ComflabulationComponent>();
+
+        entity.destroy();
+    }
+})
+
+
+
+
+
+class BenchmarksEntityX {
+    public:
+    static const std::vector<int> ENTITIES;
+
+    static inline void makeBenchmarks(std::string name) {
+        makeBenchmarks(name, ENTITIES);
+    }
+    
+    static void makeBenchmarks(std::string name, const std::vector<int>& entities) {
+        for(int nentities : entities) {
+            std::string tag = "[" + std::to_string(nentities) + "]";
+
+            std::stringstream ss;
+            ss << std::right << std::setw(10) << tag << ' ';
+            ss << name << ' ';
+            ss << std::right << std::setw(8) << nentities;
+            ss << " entities component systems update";
+
+            std::string benchmark_name = ss.str();
+            BENCHMARK(benchmark_name, [nentities](benchpress::context* ctx) {
+                runEntitiesSystemsEntityXBenchmark(ctx, nentities);
+            })
+        }
+    }
+
+    BenchmarksEntityX(std::string name){
+        makeBenchmarks(name);
+    }
+};
+const std::vector<int> BenchmarksEntityX::ENTITIES = {
+    25, 50, 
+    100, 200, 400, 800, 
+    1600, 3200, 5000, 
+    10'000, 30'000, 
+    100'000, 500'000, 
+    1'000'000, 2'000'000
+};
+
+BenchmarksEntityX entityxbenchmarks ("entityx");
+
+
+
+
+
+/*
+BENCHMARK("[25]     entityx      25 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 25);
+})
+
+BENCHMARK("[50]     entityx      50 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 50);
+})
+
+BENCHMARK("[100]    entityx     100 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 100);
+})
+
+BENCHMARK("[200]    entityx     200 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 200);
+})
+
+
+BENCHMARK("[400]    entityx     400 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 400);
+})
+
+
+BENCHMARK("[800]    entityx     800 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 800);
+})
+
+
+BENCHMARK("[1600]    entityx   1600 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 1600);
+})
+
+
+
+BENCHMARK("[3200]    entityx   3200 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 3200);
+})
+
+
+BENCHMARK("[5000]    entityx   5000 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 5000);
+})
+
+
+BENCHMARK("[10000]   entityx  10000 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 10'000);
+})
+
+BENCHMARK("[30000]   entityx  30000 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 30'000);
+})
+
+
+BENCHMARK("[100000]  entityx 100000 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 100'000L);
+})
+
+
+BENCHMARK("[500000]  entityx 500000 entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 500'000L);
+})
+
+BENCHMARK("[1000000] entityx     1M entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 1'000'000L);
+})
+
+BENCHMARK("[2000000] entityx     2M entities component systems update", [](benchpress::context* ctx) {
+    runEntitiesSystemsEntityXBenchmark(ctx, 2'000'000L);
+})
+*/