Index: source/simulation2/system/EntityMap.h =================================================================== --- source/simulation2/system/EntityMap.h +++ source/simulation2/system/EntityMap.h @@ -21,223 +21,155 @@ /** * A fast replacement for map. - * We make the following assumptions: - * - entity id's (keys) are unique - * - modifications (add / delete) are far less frequent then look-ups - * - preformance for iteration is important + * Behaves like a much faster std:map with one key difference: + * -calling insert on an existing key replaces it instead of returning the original + * (not that you should be doing that anyways) */ -template class EntityMap + +template class EntityMap { private: + friend class TestEntityMap; + EntityMap(const EntityMap&); // non-copyable EntityMap& operator=(const EntityMap&); // non-copyable public: typedef entity_id_t key_type; - typedef T mapped_type; - template struct key_val { - typedef K first_type; - typedef V second_type; - K first; - V second; - }; - typedef key_val value_type; + typedef V mapped_type; + typedef std::pair value_type; private: - size_t m_BufferSize; // number of elements in the buffer - size_t m_BufferCapacity; // capacity of the buffer - value_type* m_Buffer; // vector with all the mapped key-value pairs + std::vector > m_Data; size_t m_Count; // number of 'valid' entity id's public: - inline EntityMap() : m_BufferSize(1), m_BufferCapacity(4096), m_Count(0) - { - // for entitymap we allocate the buffer right away - // with first element in buffer being the Invalid Entity - m_Buffer = (value_type*)malloc(sizeof(value_type) * (m_BufferCapacity + 1)); - - // create the first element: - m_Buffer[0].first = INVALID_ENTITY; - m_Buffer[1].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF - } - inline ~EntityMap() + EntityMap() : m_Count(0) { - free(m_Buffer); + ENSURE(FIRST_VALID_ENTITY_ID > INVALID_ENTITY); + m_Data.reserve(4096); + // keep a valid entity ID at the end() so that we know to stop + m_Data.push_back({FIRST_VALID_ENTITY_ID, V()}); } - // Iterators template struct _iter : public std::iterator { U* val; - inline _iter(U* init) : val(init) {} - inline U& operator*() { return *val; } - inline U* operator->() { return val; } - inline _iter& operator++() // ++it + _iter(U* init) : val(init) {} + _iter(typename std::vector::iterator init) : val(&*init) {} + + U& operator*() { return *val; } + U* operator->() { return val; } + _iter& operator++() // ++it { ++val; - while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities + while (val->first == INVALID_ENTITY) + ++val; return *this; } - inline _iter& operator++(int) // it++ + _iter operator++(int) // it++ { U* ptr = val; ++val; - while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities + while (val->first == INVALID_ENTITY) + ++val; return ptr; } - inline bool operator==(_iter other) { return val == other.val; } - inline bool operator!=(_iter other) { return val != other.val; } - inline operator _iter() const { return _iter(val); } + bool operator==(_iter other) { return val == other.val; } + bool operator!=(_iter other) { return val != other.val; } + operator _iter() const { return _iter(val); } }; typedef _iter iterator; typedef _iter const_iterator; - inline iterator begin() + iterator begin() { - value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY - while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities - return ptr; + iterator it = m_Data.begin(); + if (it->first == INVALID_ENTITY) + ++it; + return it; } - inline iterator end() + + iterator end() { - return iterator(m_Buffer + m_BufferSize); + return iterator(&m_Data.back()); } - inline const_iterator begin() const + + const_iterator begin() const { - value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY - while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities - return ptr; + const_iterator it = m_Data.begin(); + if (it->first == INVALID_ENTITY) + ++it; + return it; } - inline const_iterator end() const + + const_iterator end() const { - return const_iterator(m_Buffer + m_BufferSize); + return const_iterator(&m_Data.back()); } - // Size - inline bool empty() const { return m_Count == 0; } - inline size_t size() const { return m_Count; } + bool empty() const { return m_Count == 0; } + size_t size() const { return m_Count; } - // Modification void insert(const key_type key, const mapped_type& value) { - if (key >= m_BufferCapacity) // do we need to resize buffer? + ENSURE (key >= FIRST_VALID_ENTITY_ID); + if (key-FIRST_VALID_ENTITY_ID >= m_Data.size()-1) { - size_t newCapacity = m_BufferCapacity + 4096; - while (key >= newCapacity) newCapacity += 4096; - // always allocate +1 behind the scenes, because end() must have a 0xFFFFFFFF key - value_type* mem = (value_type*)realloc(m_Buffer, sizeof(value_type) * (newCapacity + 1)); - if (!mem) - { - debug_warn("EntityMap::insert() realloc failed! Out of memory."); - throw std::bad_alloc(); // fail to expand and insert - } - m_BufferCapacity = newCapacity; - m_Buffer = mem; - goto fill_gaps; - } - else if (key > m_BufferSize) // weird insert far beyond the end - { -fill_gaps: - // set all entity id's to INVALID_ENTITY inside the new range - for (size_t i = m_BufferSize; i <= key; ++i) - m_Buffer[i].first = INVALID_ENTITY; - m_BufferSize = key; // extend the new size + // resize, make sure to keep a valid entity ID at the end + size_t currentEnd = m_Data.size()-1; + m_Data.resize(key-FIRST_VALID_ENTITY_ID+2, {INVALID_ENTITY, V()}); + m_Data.back() = std::move(m_Data[currentEnd]); + m_Data[currentEnd].first = INVALID_ENTITY; } - value_type& item = m_Buffer[key]; - key_type oldKey = item.first; - item.first = key; - if (key == m_BufferSize) // push_back - { - ++m_BufferSize; // expand - ++m_Count; - new (&item.second) mapped_type(value); // copy ctor to init - m_Buffer[m_BufferSize].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF - } - else if(!item.first) // insert new to middle - { - ++m_Count; - new (&item.second) mapped_type(value); // copy ctor to init - } - else // set existing value - { - if (oldKey == INVALID_ENTITY) - m_Count++; - item.second = value; // overwrite existing - } + if (m_Data[key-FIRST_VALID_ENTITY_ID].first == INVALID_ENTITY) + m_Count++; + + m_Data[key-FIRST_VALID_ENTITY_ID] = {key, value}; } - void erase(iterator it) + size_t erase(iterator it) { - value_type* ptr = it.val; - if (ptr->first != INVALID_ENTITY) + if (it->first != INVALID_ENTITY && it != end()) { - ptr->first = INVALID_ENTITY; - ptr->second.~T(); // call dtor + it->first = INVALID_ENTITY; + it->second.~V(); // call dtor --m_Count; + return 1; } + return 0; } - void erase(const entity_id_t key) - { - if (key < m_BufferSize) - { - value_type* ptr = m_Buffer + key; - if (ptr->first != INVALID_ENTITY) - { - ptr->first = INVALID_ENTITY; - ptr->second.~T(); // call dtor - --m_Count; - } - } - } - inline void clear() + + size_t erase(const key_type key) { - // orphan whole range - value_type* ptr = m_Buffer; - value_type* end = m_Buffer + m_BufferSize; - for (; ptr != end; ++ptr) - { - if (ptr->first != INVALID_ENTITY) - { - ptr->first = INVALID_ENTITY; - ptr->second.~T(); // call dtor - } - } - m_Count = 0; // no more valid entities + if (key-FIRST_VALID_ENTITY_ID < m_Data.size()-1) + return erase(m_Data.begin() + key-FIRST_VALID_ENTITY_ID); + return 0; } - // Operations - inline iterator find(const entity_id_t key) + void clear() { - if (key < m_BufferSize) // is this key in the range of existing entitites? - { - value_type* ptr = m_Buffer + key; - if (ptr->first != INVALID_ENTITY) - return ptr; - } - return m_Buffer + m_BufferSize; // return iterator end() + m_Data.clear(); + m_Count = 0; + m_Data.push_back({FIRST_VALID_ENTITY_ID, V()}); } - inline const_iterator find(const entity_id_t key) const + + iterator find(const key_type key) { - if (key < m_BufferSize) // is this key in the range of existing entitites? - { - const value_type* ptr = m_Buffer + key; - if (ptr->first != INVALID_ENTITY) - return ptr; - } - return m_Buffer + m_BufferSize; // return iterator end() + if (key-FIRST_VALID_ENTITY_ID < m_Data.size()-1 && m_Data[key-FIRST_VALID_ENTITY_ID].first != INVALID_ENTITY) + return m_Data.begin() + key - FIRST_VALID_ENTITY_ID; + return end(); } - inline size_t count(const entity_id_t key) const + + const_iterator find(const key_type key) const { - if (key < m_BufferSize) - { - if (m_Buffer[key].first != INVALID_ENTITY) - return 1; - } - return 0; + if (key-FIRST_VALID_ENTITY_ID < m_Data.size()-1 && m_Data[key-FIRST_VALID_ENTITY_ID].first != INVALID_ENTITY) + return m_Data.begin() + key - FIRST_VALID_ENTITY_ID; + return end(); } }; Index: source/simulation2/system/EntityMap_old.h =================================================================== --- /dev/null +++ source/simulation2/system/EntityMap_old.h @@ -0,0 +1,283 @@ +/* Copyright (C) 2013 Wildfire Games. + * This file is part of 0 A.D. + * + * 0 A.D. is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 2 of the License, or + * (at your option) any later version. + * + * 0 A.D. is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with 0 A.D. If not, see . + */ +#ifndef INCLUDED_ENTITYMAP +#define INCLUDED_ENTITYMAP + +#include "Entity.h" + +/** + * A fast replacement for map. + * We make the following assumptions: + * - entity id's (keys) are unique + * - modifications (add / delete) are far less frequent then look-ups + * - preformance for iteration is important + */ +template class EntityMap +{ +private: + friend class TestEntityMapOld; + EntityMap(const EntityMap&); // non-copyable + EntityMap& operator=(const EntityMap&); // non-copyable + +public: + typedef entity_id_t key_type; + typedef T mapped_type; + template struct key_val { + typedef K first_type; + typedef V second_type; + K first; + V second; + }; + typedef key_val value_type; + +private: + size_t m_BufferSize; // number of elements in the buffer + size_t m_BufferCapacity; // capacity of the buffer + value_type* m_Buffer; // vector with all the mapped key-value pairs + + size_t m_Count; // number of 'valid' entity id's + +public: + + inline EntityMap() : m_BufferSize(1), m_BufferCapacity(4096), m_Count(0) + { + // for entitymap we allocate the buffer right away + // with first element in buffer being the Invalid Entity + m_Buffer = (value_type*)malloc(sizeof(value_type) * (m_BufferCapacity + 1)); + + // create the first element: + m_Buffer[0].first = INVALID_ENTITY; + m_Buffer[1].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF + } + inline ~EntityMap() + { + free(m_Buffer); + } + + // Iterators + template struct _iter : public std::iterator + { + U* val; + inline _iter(U* init) : val(init) {} + inline U& operator*() { return *val; } + inline U* operator->() { return val; } + inline _iter& operator++() // ++it + { + ++val; + while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities + return *this; + } + inline _iter& operator++(int) // it++ + { + U* ptr = val; + ++val; + while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities + return ptr; + } + inline bool operator==(_iter other) { return val == other.val; } + inline bool operator!=(_iter other) { return val != other.val; } + inline operator _iter() const { return _iter(val); } + }; + + typedef _iter iterator; + typedef _iter const_iterator; + + inline iterator begin() + { + value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY + while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities + return ptr; + } + inline iterator end() + { + return iterator(m_Buffer + m_BufferSize); + } + inline const_iterator begin() const + { + value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY + while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities + return ptr; + } + inline const_iterator end() const + { + return const_iterator(m_Buffer + m_BufferSize); + } + + // Size + inline bool empty() const { return m_Count == 0; } + inline size_t size() const { return m_Count; } + + // Modification + void insert(const key_type key, const mapped_type& value) + { + if (key >= m_BufferCapacity) // do we need to resize buffer? + { + size_t newCapacity = m_BufferCapacity + 4096; + while (key >= newCapacity) newCapacity += 4096; + // always allocate +1 behind the scenes, because end() must have a 0xFFFFFFFF key + value_type* mem = (value_type*)realloc(m_Buffer, sizeof(value_type) * (newCapacity + 1)); + if (!mem) + { + debug_warn("EntityMap::insert() realloc failed! Out of memory."); + throw std::bad_alloc(); // fail to expand and insert + } + m_BufferCapacity = newCapacity; + m_Buffer = mem; + goto fill_gaps; + } + else if (key > m_BufferSize) // weird insert far beyond the end + { +fill_gaps: + // set all entity id's to INVALID_ENTITY inside the new range + for (size_t i = m_BufferSize; i <= key; ++i) + m_Buffer[i].first = INVALID_ENTITY; + m_BufferSize = key; // extend the new size + } + + value_type& item = m_Buffer[key]; + key_type oldKey = item.first; + item.first = key; + if (key == m_BufferSize) // push_back + { + ++m_BufferSize; // expand + ++m_Count; + new (&item.second) mapped_type(value); // copy ctor to init + m_Buffer[m_BufferSize].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF + } + else if(!item.first) // insert new to middle + { + ++m_Count; + new (&item.second) mapped_type(value); // copy ctor to init + } + else // set existing value + { + if (oldKey == INVALID_ENTITY) + m_Count++; + item.second = value; // overwrite existing + } + } + + void erase(iterator it) + { + value_type* ptr = it.val; + if (ptr->first != INVALID_ENTITY) + { + ptr->first = INVALID_ENTITY; + ptr->second.~T(); // call dtor + --m_Count; + } + } + void erase(const entity_id_t key) + { + if (key < m_BufferSize) + { + value_type* ptr = m_Buffer + key; + if (ptr->first != INVALID_ENTITY) + { + ptr->first = INVALID_ENTITY; + ptr->second.~T(); // call dtor + --m_Count; + } + } + } + inline void clear() + { + // orphan whole range + value_type* ptr = m_Buffer; + value_type* end = m_Buffer + m_BufferSize; + for (; ptr != end; ++ptr) + { + if (ptr->first != INVALID_ENTITY) + { + ptr->first = INVALID_ENTITY; + ptr->second.~T(); // call dtor + } + } + m_Count = 0; // no more valid entities + } + + // Operations + inline iterator find(const entity_id_t key) + { + if (key < m_BufferSize) // is this key in the range of existing entitites? + { + value_type* ptr = m_Buffer + key; + if (ptr->first != INVALID_ENTITY) + return ptr; + } + return m_Buffer + m_BufferSize; // return iterator end() + } + inline const_iterator find(const entity_id_t key) const + { + if (key < m_BufferSize) // is this key in the range of existing entitites? + { + const value_type* ptr = m_Buffer + key; + if (ptr->first != INVALID_ENTITY) + return ptr; + } + return m_Buffer + m_BufferSize; // return iterator end() + } + inline size_t count(const entity_id_t key) const + { + if (key < m_BufferSize) + { + if (m_Buffer[key].first != INVALID_ENTITY) + return 1; + } + return 0; + } +}; + +template +struct SerializeEntityMap +{ + template + void operator()(ISerializer& serialize, const char* UNUSED(name), EntityMap& value) + { + size_t len = value.size(); + serialize.NumberU32_Unbounded("length", (u32)len); + size_t count = 0; + for (typename EntityMap::iterator it = value.begin(); it != value.end(); ++it) + { + serialize.NumberU32_Unbounded("key", it->first); + VSerializer()(serialize, "value", it->second); + count++; + } + // test to see if the entityMap count wasn't wrong + // (which causes a crashing deserialisation) + ENSURE(count == len); + } + + template + void operator()(IDeserializer& deserialize, const char* UNUSED(name), EntityMap& value) + { + value.clear(); + uint32_t len; + deserialize.NumberU32_Unbounded("length", len); + for (size_t i = 0; i < len; ++i) + { + entity_id_t k; + V v; + deserialize.NumberU32_Unbounded("key", k); + VSerializer()(deserialize, "value", v); + value.insert(k, v); + } + } +}; + + +#endif Index: source/simulation2/tests/test_EntityMap.h =================================================================== --- /dev/null +++ source/simulation2/tests/test_EntityMap.h @@ -0,0 +1,309 @@ +/* Copyright (C) 2010 Wildfire Games. + * This file is part of 0 A.D. + * + * 0 A.D. is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 2 of the License, or + * (at your option) any later version. + * + * 0 A.D. is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with 0 A.D. If not, see . + */ + +#include "lib/self_test.h" +#include "lib/timer.h" + +#include "simulation2/serialization/ISerializer.h" +#include "simulation2/serialization/IDeserializer.h" + +#include "simulation2/system/EntityMap.h" + +class TestEntityMap : public CxxTest::TestSuite +{ +public: + void setUp() + { + } + + void tearDown() + { + } + + void test_insert() + { + EntityMap test; + + TS_ASSERT(test.empty()); + + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(4,4); + test.insert(4,5); + test.insert(4,6); + + TS_ASSERT(test.m_Data.size() == 5); + TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY); + TS_ASSERT(test.size() == 4); + TS_ASSERT(test.find(3)->second == 3); + TS_ASSERT(test.find(4)->second == 6); + + test.insert(10,7); + TS_ASSERT(test.m_Data.size() == 11); + TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY); + TS_ASSERT(test.size() == 5); + TS_ASSERT(test.find(4)->second == 6); + TS_ASSERT(test.find(5) == test.end()); + TS_ASSERT(test.find(6) == test.end()); + TS_ASSERT(test.find(7) == test.end()); + TS_ASSERT(test.find(8) == test.end()); + TS_ASSERT(test.find(9) == test.end()); + TS_ASSERT(test.find(10)->second == 7); + + EntityMap test2; + + test2.insert(8,5); + TS_ASSERT(test2.find(8)->second == 5); + TS_ASSERT(test2.m_Data.size() == 5); + TS_ASSERT(test2.size() == 1); + + } + void test_iterators() + { + EntityMap test; + + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(4,4); + + EntityMap::iterator it = test.begin(); + TS_ASSERT(it->first == 1); + it++; + TS_ASSERT(it->first == 2); + ++it; + TS_ASSERT(it->first == 3); + it = test.end(); + TS_ASSERT(it->first == test.m_Data.back().first); + + EntityMap::const_iterator cit = test.begin(); + TS_ASSERT(cit->first == 1); + cit = test.end(); + TS_ASSERT(cit->first == test.m_Data.back().first); + + size_t iter = 0; + for (auto& v : test) + { + ++iter; + TS_ASSERT(test.find(iter)->second == (int)iter); + TS_ASSERT(test.find(iter)->second == v.second); + } + TS_ASSERT(iter == 4); + + test.clear(); + + test.insert(10,1); + test.insert(20,2); + test.insert(30,3); + test.insert(40,4); + + it = test.begin(); + TS_ASSERT(it->second == 1); + it++; + TS_ASSERT(it->second == 2); + ++it; + TS_ASSERT(it->second == 3); + it = test.end(); + TS_ASSERT(it->first == test.m_Data.back().first); + + } + + void test_erase() + { + EntityMap test; + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(4,4); + + test.erase(2); + + TS_ASSERT(test.m_Data.size() == 5); + TS_ASSERT(test.size() == 3); + TS_ASSERT(test.find(2) == test.end()); + + test.erase(1); + test.erase(3); + TS_ASSERT(test.erase(4) == 1); + + TS_ASSERT(test.m_Data.size() == 5); + TS_ASSERT(test.size() == 0); + + TS_ASSERT(test.erase(5) == 0); + + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(4,4); + + test.erase(test.begin()); + TS_ASSERT(test.m_Data.size() == 5); + TS_ASSERT(test.size() == 3); + TS_ASSERT(test.find(1) == test.end()); + + TS_ASSERT(test.erase(test.end()) == 0); + TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY); + } + + void test_clear() + { + EntityMap test; + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(4,4); + + test.clear(); + + TS_ASSERT(test.m_Data.size() == 1); + TS_ASSERT(test.size() == 0); + } + + void test_find() + { + EntityMap test; + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(40,4); + + TS_ASSERT(test.find(1)->second == 1); + TS_ASSERT(test.find(40)->second == 4); + TS_ASSERT(test.find(30) == test.end()); + } + + void test_perf() + { + EntityMap test; + std::cout << std::endl << "Testing performance of EntityMap" << std::endl; + + double t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.insert(i,i); + double tt = timer_Time() - t; + std::cout << "Inserting 200K elements in order: " << tt << "s" << std::endl; + + t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.erase(i); + tt = timer_Time() - t; + std::cout << "Erasing 200K elements, by key: " << tt << "s" << std::endl; + + t = timer_Time(); + for (int i = 200000; i >= 1; --i) + test.insert(i,i); + tt = timer_Time() - t; + std::cout << "Inserting 200K elements in reverse order: " << tt << "s" << std::endl; + + t = timer_Time(); + for (auto i = test.begin(); i != test.end(); ++i) + test.erase(i); + tt = timer_Time() - t; + std::cout << "Erasing 200K elements, by iterator: " << tt << "s" << std::endl; + + t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.erase(i); + tt = timer_Time() - t; + std::cout << "Erasing 200K non-existing elements: " << tt << "s" << std::endl; + + // prep random vector + std::vector vec; + for (int i = 1; i <= 200000; ++i) + vec.push_back(i); + std::random_shuffle(vec.begin(), vec.end()); + + for (int i = 1; i <= 200000; ++i) + test.insert(i,i); + + t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.find(vec[i])->second = 3; + tt = timer_Time() - t; + std::cout << "200K random lookups in random order: " << tt << "s" << std::endl; + + t = timer_Time(); + for (auto& p : test) + p.second = 3; + tt = timer_Time() - t; + std::cout << "auto iteration on 200K continuous entitymap: " << tt << "s" << std::endl; + + test.clear(); + + for (int i = 1; i <= 200000; ++i) + test.insert(i*5,i); + + t = timer_Time(); + for (auto& p : test) + p.second = 3; + tt = timer_Time() - t; + std::cout << "auto iteration on 200K sparse (holes of 5): " << tt << "s" << std::endl; + + test.clear(); + + for (int i = 1; i <= 4000; ++i) + test.insert(i*50,i); + + t = timer_Time(); + for (auto& p : test) + p.second = 3; + tt = timer_Time() - t; + std::cout << "auto iteration on 4K sparse (holes of 50): " << tt << "s" << std::endl; + + test.clear(); + + for (int i = 1; i <= 200000; ++i) + test.insert(i*50,i); + + t = timer_Time(); + for (auto& p : test) + p.second = 3; + tt = timer_Time() - t; + std::cout << "auto iteration on 200K sparse (holes of 50): " << tt << "s" << std::endl; + + test.clear(); + + for (int i = 1; i <= 2000000; ++i) + test.insert(i*50,i); + + t = timer_Time(); + for (auto i = test.begin(); i != test.end(); ++i) + i->second = 3; + tt = timer_Time() - t; + std::cout << "manual ++iteration on 2000K sparse (holes of 50) (warmup 1): " << tt << "s" << std::endl; + + t = timer_Time(); + for (auto i = test.begin(); i != test.end(); i++) + i->second = 3; + tt = timer_Time() - t; + std::cout << "manual iteration++ on 2000K sparse (holes of 50) (warmup 2): " << tt << "s" << std::endl; + + t = timer_Time(); + for (auto i = test.begin(); i != test.end(); ++i) + i->second = 3; + tt = timer_Time() - t; + std::cout << "manual ++iteration on 2000K sparse (holes of 50): " << tt << "s" << std::endl; + + t = timer_Time(); + for (auto i = test.begin(); i != test.end(); i++) + i->second = 3; + tt = timer_Time() - t; + std::cout << "manual iteration++ on 2000K sparse (holes of 50): " << tt << "s" << std::endl; + + } +}; Index: source/simulation2/tests/test_EntityMap_old.h =================================================================== --- /dev/null +++ source/simulation2/tests/test_EntityMap_old.h @@ -0,0 +1,238 @@ +/* Copyright (C) 2010 Wildfire Games. + * This file is part of 0 A.D. + * + * 0 A.D. is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 2 of the License, or + * (at your option) any later version. + * + * 0 A.D. is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with 0 A.D. If not, see . + */ + +#include "lib/self_test.h" +#include "lib/timer.h" + +#include "simulation2/serialization/ISerializer.h" +#include "simulation2/serialization/IDeserializer.h" + +#include "simulation2/system/EntityMap_old.h" + +class TestEntityMapOld : public CxxTest::TestSuite +{ +public: + void setUp() + { + } + + void tearDown() + { + } + + void test_insert() + { + EntityMap test; + + TS_ASSERT(test.empty()); + + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(4,4); + test.insert(4,5); + test.insert(4,6); + + TS_ASSERT(test.size() == 4); + TS_ASSERT(test.find(3)->second == 3); + TS_ASSERT(test.find(4)->second == 6); + + test.insert(10,7); + TS_ASSERT(test.size() == 5); + TS_ASSERT(test.find(4)->second == 6); + TS_ASSERT(test.find(5) == test.end()); + TS_ASSERT(test.find(6) == test.end()); + TS_ASSERT(test.find(7) == test.end()); + TS_ASSERT(test.find(8) == test.end()); + TS_ASSERT(test.find(9) == test.end()); + TS_ASSERT(test.find(10)->second == 7); + + } + void test_iterators() + { + EntityMap test; + + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(4,4); + + EntityMap::iterator it = test.begin(); + TS_ASSERT(it->first == 1); + + EntityMap::const_iterator cit = test.begin(); + TS_ASSERT(cit->first == 1); + + size_t iter = 0; + for (auto& v : test) + { + ++iter; + TS_ASSERT(test.find(iter)->second == (int)iter); + TS_ASSERT(test.find(iter)->second == v.second); + } + TS_ASSERT(iter == 4); + } + + void test_erase() + { + EntityMap test; + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(4,4); + + test.erase(2); + + TS_ASSERT(test.size() == 3); + TS_ASSERT(test.find(2) == test.end()); + + test.erase(1); + test.erase(3); + test.erase(4); + + TS_ASSERT(test.size() == 0); + + + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(4,4); + + test.erase(test.begin()); + TS_ASSERT(test.size() == 3); + TS_ASSERT(test.find(1) == test.end()); + + } + + void test_clear() + { + EntityMap test; + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(4,4); + + test.clear(); + + TS_ASSERT(test.size() == 0); + } + + void test_find() + { + EntityMap test; + test.insert(1,1); + test.insert(2,2); + test.insert(3,3); + test.insert(40,4); + + TS_ASSERT(test.find(1)->second == 1); + TS_ASSERT(test.find(40)->second == 4); + TS_ASSERT(test.find(30) == test.end()); + } + + void test_perf() + { + EntityMap test; + std::cout << std::endl << "Testing performance of old EntityMap" << std::endl; + + double t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.insert(i,i); + double tt = timer_Time() - t; + std::cout << "Inserting 200K elements in order: " << tt << "s" << std::endl; + + t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.erase(i); + tt = timer_Time() - t; + std::cout << "Erasing 200K elements, by key: " << tt << "s" << std::endl; + + t = timer_Time(); + for (int i = 200000; i >= 1; --i) + test.insert(i,i); + tt = timer_Time() - t; + std::cout << "Inserting 200K elements in reverse order: " << tt << "s" << std::endl; + + t = timer_Time(); + for (auto i = test.begin(); i != test.end(); ++i) + test.erase(i); + tt = timer_Time() - t; + std::cout << "Erasing 200K elements, by iterator: " << tt << "s" << std::endl; + + t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.erase(i); + tt = timer_Time() - t; + std::cout << "Erasing 200K non-existing elements: " << tt << "s" << std::endl; + + // prep random vector + std::vector vec; + for (int i = 1; i <= 200000; ++i) + vec.push_back(i); + std::random_shuffle(vec.begin(), vec.end()); + + for (int i = 1; i <= 200000; ++i) + test.insert(i,i); + + t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.find(vec[i])->second = 3; + tt = timer_Time() - t; + std::cout << "200K random lookups in random order: " << tt << "s" << std::endl; + + t = timer_Time(); + for (auto& p : test) + p.second = 3; + tt = timer_Time() - t; + std::cout << "auto iteration on 200K continuous entitymap: " << tt << "s" << std::endl; + + test.clear(); + + for (int i = 1; i <= 200000; ++i) + test.insert(i*5,i); + + t = timer_Time(); + for (auto& p : test) + p.second = 3; + tt = timer_Time() - t; + std::cout << "auto iteration on 200K sparse (holes of 5): " << tt << "s" << std::endl; + + test.clear(); + + for (int i = 1; i <= 4000; ++i) + test.insert(i*50,i); + + t = timer_Time(); + for (auto& p : test) + p.second = 3; + tt = timer_Time() - t; + std::cout << "auto iteration on 4K sparse (holes of 50): " << tt << "s" << std::endl; + + test.clear(); + + for (int i = 1; i <= 200000; ++i) + test.insert(i*50,i); + + t = timer_Time(); + for (auto& p : test) + p.second = 3; + tt = timer_Time() - t; + std::cout << "auto iteration on 200K sparse (holes of 50): " << tt << "s" << std::endl; + + test.clear(); + } +};