Index: source/simulation2/Simulation2.h =================================================================== --- source/simulation2/Simulation2.h +++ source/simulation2/Simulation2.h @@ -21,12 +21,11 @@ #include "simulation2/system/CmpPtr.h" #include "simulation2/system/Components.h" #include "simulation2/helpers/SimulationCommand.h" +#include "simulation2/helpers/SparseFlatMap.h" #include "scriptinterface/ScriptVal.h" #include "lib/file/vfs/vfs_path.h" -#include - #include class CSimulation2Impl; @@ -207,7 +206,7 @@ void BroadcastMessage(const CMessage& msg) const; typedef std::vector > InterfaceList; - typedef boost::unordered_map InterfaceListUnordered; + typedef SparseFlatMap InterfaceListUnordered; /** * Returns a list of components implementing the given interface, and their Index: source/simulation2/components/CCmpRangeManager.cpp =================================================================== --- source/simulation2/components/CCmpRangeManager.cpp +++ source/simulation2/components/CCmpRangeManager.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2018 Wildfire Games. +/* Copyright (C) 2019 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -21,7 +21,6 @@ #include "ICmpRangeManager.h" #include "ICmpTerrain.h" -#include "simulation2/system/EntityMap.h" #include "simulation2/MessageTypes.h" #include "simulation2/components/ICmpFogging.h" #include "simulation2/components/ICmpMirage.h" @@ -33,6 +32,7 @@ #include "simulation2/components/ICmpVision.h" #include "simulation2/components/ICmpWaterManager.h" #include "simulation2/helpers/Render.h" +#include "simulation2/helpers/SparseFlatMap.h" #include "simulation2/helpers/Spatial.h" #include "graphics/Overlay.h" @@ -234,6 +234,8 @@ cassert(sizeof(EntityData) == 24); +using EntityMap = SparseFlatMap; + /** * Serialization helper template for Query */ @@ -299,7 +301,7 @@ */ struct EntityDistanceOrdering { - EntityDistanceOrdering(const EntityMap& entities, const CFixedVector2D& source) : + EntityDistanceOrdering(const EntityMap& entities, const CFixedVector2D& source) : m_EntityData(entities), m_Source(source) { } @@ -313,7 +315,7 @@ return (vecA.CompareLength(vecB) < 0); } - const EntityMap& m_EntityData; + const EntityMap& m_EntityData; CFixedVector2D m_Source; private: @@ -365,7 +367,7 @@ // Range query state: tag_t m_QueryNext; // next allocated id std::map m_Queries; - EntityMap m_EntityData; + EntityMap m_EntityData; FastSpatialSubdivision m_Subdivision; // spatial index of m_EntityData std::vector m_SubdivisionResults; @@ -458,7 +460,7 @@ serialize.NumberU32_Unbounded("query next", m_QueryNext); SerializeMap()(serialize, "queries", m_Queries, GetSimContext()); - SerializeEntityMap()(serialize, "entity data", m_EntityData); + SerializeSparseFlatMap()(serialize, "entity data", m_EntityData); SerializeVector()(serialize, "los reveal all", m_LosRevealAll); serialize.Bool("los circular", m_LosCircular); @@ -539,7 +541,7 @@ entdata.size = cmpObstruction->GetSize().ToInt_RoundToInfinity(); // Remember this entity - m_EntityData.insert(ent, entdata); + m_EntityData.insert_or_assign(ent, entdata); break; } case MT_PositionChanged: @@ -547,7 +549,7 @@ const CMessagePositionChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) @@ -614,7 +616,7 @@ const CMessageOwnershipChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) @@ -648,7 +650,7 @@ const CMessageDestroy& msgData = static_cast (msg); entity_id_t ent = msgData.entity; - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) @@ -673,7 +675,7 @@ const CMessageVisionRangeChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) @@ -713,7 +715,7 @@ const CMessageVisionSharingChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) @@ -862,7 +864,7 @@ m_LosTiles.clear(); m_LosTiles.resize(m_LosTilesPerSide*m_LosTilesPerSide); - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) + for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) if (it->second.HasFlag()) { if (it->second.HasFlag()) @@ -893,7 +895,7 @@ { m_Subdivision.Reset(x1, z1); - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) + for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) if (it->second.HasFlag()) m_Subdivision.Add(it->first, CFixedVector2D(it->second.x, it->second.z), it->second.size); } @@ -1062,7 +1064,7 @@ { std::vector entities; - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) + for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) { // Check owner and add to list if it matches if (CalcOwnerMask(it->second.owner) & ownerMask) @@ -1175,7 +1177,7 @@ // Special case: range -1.0 means check all entities ignoring distance if (q.maxRange == entity_pos_t::FromInt(-1)) { - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) + for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) { if (!TestEntityQuery(q, it->first, it->second)) continue; @@ -1196,7 +1198,7 @@ for (size_t i = 0; i < m_SubdivisionResults.size(); ++i) { - EntityMap::const_iterator it = m_EntityData.find(m_SubdivisionResults[i]); + EntityMap::const_iterator it = m_EntityData.find(m_SubdivisionResults[i]); ENSURE(it != m_EntityData.end()); if (!TestEntityQuery(q, it->first, it->second)) @@ -1234,7 +1236,7 @@ for (size_t i = 0; i < m_SubdivisionResults.size(); ++i) { - EntityMap::const_iterator it = m_EntityData.find(m_SubdivisionResults[i]); + EntityMap::const_iterator it = m_EntityData.find(m_SubdivisionResults[i]); ENSURE(it != m_EntityData.end()); if (!TestEntityQuery(q, it->first, it->second)) @@ -1550,7 +1552,7 @@ virtual void SetEntityFlag(entity_id_t ent, const std::string& identifier, bool value) { - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // We don't have this entity if (it == m_EntityData.end()) @@ -1578,7 +1580,7 @@ virtual void ActivateScriptedVisibility(entity_id_t ent, bool status) { - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); if (it != m_EntityData.end()) it->second.SetFlag(status); } @@ -1616,7 +1618,7 @@ CmpPtr cmpVisibility(ent); // Possibly ask the scripted Visibility component - EntityMap::const_iterator it = m_EntityData.find(ent.GetId()); + EntityMap::const_iterator it = m_EntityData.find(ent.GetId()); if (it != m_EntityData.end()) { if (it->second.HasFlag() && cmpVisibility) @@ -1712,7 +1714,7 @@ if (std::find(m_ModifiedEntities.begin(), m_ModifiedEntities.end(), entId) != m_ModifiedEntities.end()) return ComputeLosVisibility(ent, player); - EntityMap::const_iterator it = m_EntityData.find(entId); + EntityMap::const_iterator it = m_EntityData.find(entId); if (it == m_EntityData.end()) return ComputeLosVisibility(ent, player); @@ -1790,7 +1792,7 @@ void UpdateVisibility(entity_id_t ent, player_id_t player) { - EntityMap::iterator itEnts = m_EntityData.find(ent); + EntityMap::iterator itEnts = m_EntityData.find(ent); if (itEnts == m_EntityData.end()) return; @@ -1956,7 +1958,7 @@ // So we just remember what entities to mirage and do that later. std::vector miragableEntities; - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) + for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) { CmpPtr cmpPosition(GetSimContext(), it->first); if (!cmpPosition || !cmpPosition->IsInWorld()) Index: source/simulation2/helpers/SparseFlatMap.h =================================================================== --- /dev/null +++ source/simulation2/helpers/SparseFlatMap.h @@ -0,0 +1,521 @@ +/* Copyright (C) 2019 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_SparseFlatMap +#define INCLUDED_SparseFlatMap + +#include "simulation2/serialization/ISerializer.h" +#include "simulation2/serialization/IDeserializer.h" + +#include +#include +#include +#include + +/** + * SparseFlatMap is a faster replacement for std::map. + * Requirements of T: 0 is an "invalid" state, and T can be compared with numbers. + * Requirements of V: default-constructible (state may be invalid though) + * + * It has: + * - guaranteed ordering + * - fast insertion (similar to a vector with SBO, add the data container's insert without) + * - fast iteration (particularly when the data is compact, i.e. it doesn't have to jump over many invalid entities). + * - very fast lookup (O(1) - with SBO about as fast as a vector) + * - fast/very fast deletion - essentially a NOP at the moment, see TODO below. We merely reset the Key to "invalid". + * This erasing behaviour is why this is a sparse map - but sparsity is an enemy here to memory usage and performance. + * + * Note that we pay a cleanup cost when the SparseFlatMap is destroyed, as memory is then reclaimed. + * + * This class can handle storing entities with IDs starting at n and m (such as 1 and LOCAL_ENTITY). + * However if one inputs MAX for INTERLEAVED_ID, this behaviour is removed at compile-time at essentially no cost. + * + * This class separates "keys" and data. The reason is that iterating over a vector with a smaller data type is faster, + * so if V becomes large enough it's far too slow to iterate over. This means we pay the cost of another dereference + * when accessing the stored value however. To avoid paying the cost of the data container's access, store a pointer. + * (NB: we need the data container to guarantee it won't move items - std::unordered_map, std::deque if you're careful...). + * + * This class uses a variant of "small buffer optimization": + * if the mapped_type has a size <= to a pointer, it will not even use the data containers + * making it extremely fast. Non-SBO variant remains faster than an std::map at the cost of RAM overhead when compact + * and can become slower when the vector becomes sparse. + * + * TODO: figure out the best number for SBO optimisation for 0 A.D.'s use case. + * TODO: figure out the best data container. unordered_map seems good, but maybe std::deque is better for 0 A.D.'s use case + * TODO: it might be worth erasing in the data container if it gets large, or implementing a way to compact data. + * TODO: The mapped type could be used to store how far ahead we must jump to get to the next valid ID + * (at the cost of slower erasing). This might be faster when iterating over sparse data. + * + * There is a disabled performance test in our tests. Take care if you compare it with say, a straight std::map + * as tests tend to result in contiguous memory allocations that may not happen in-game. + */ + +template +class SparseFlatMap +{ + static_assert(FIRST_VALID_ID > 0, "0 must be an invalid key"); +private: + friend class TestSparseFlatMap; + +public: + + typedef T key_type; + typedef V mapped_type; + typedef std::pair value_type; + // Our value type is a reference but the element itself is a temporary. + typedef value_type reference; + + static const T NO_SECONDARY_IDS = std::numeric_limits::max(); +private: + static const bool USE_SECONDARY_IDS = INTERLEAVED_ID < NO_SECONDARY_IDS; + + static const bool USE_SBO = sizeof(mapped_type) <= sizeof(mapped_type*); + using keys_mapped_type = typename std::conditional::type; + + using keys_container = std::vector>; + keys_container m_Keys1; + keys_container m_Keys2; + + using data_container = std::unordered_map; + data_container m_Data1; + data_container m_Data2; + + // number of 'valid' entity id's + size_t m_Count; + + // SFINAE-out the complexity of handling two ID ranges +#define IF_SECONDARY(x) template inline typename std::enable_if::type +#define NO_SECONDARY(x) template inline typename std::enable_if::type + + IF_SECONDARY(key_type) Idx(const key_type& key) const + { + return key - (key >= INTERLEAVED_ID ? INTERLEAVED_ID : FIRST_VALID_ID); + } + + NO_SECONDARY(key_type) Idx(const key_type& key) const + { + return key - FIRST_VALID_ID; + } + + IF_SECONDARY(keys_container&) Keys(const key_type& key) { return key >= INTERLEAVED_ID ? m_Keys2 : m_Keys1; } + IF_SECONDARY(const keys_container&) Keys(const key_type& key) const { return key >= INTERLEAVED_ID ? m_Keys2 : m_Keys1; } + NO_SECONDARY(keys_container&) Keys(const key_type&) { return m_Keys1; } + NO_SECONDARY(const keys_container&) Keys(const key_type&) const { return m_Keys1; } + + IF_SECONDARY(data_container&) Data(const key_type& key) { return key >= INTERLEAVED_ID ? m_Data2 : m_Data1; } + IF_SECONDARY(const data_container&) Data(const key_type& key) const { return key >= INTERLEAVED_ID ? m_Data2 : m_Data1; } + NO_SECONDARY(data_container&) Data(const key_type&) { return m_Data1; } + NO_SECONDARY(const data_container&) Data(const key_type&) const { return m_Data1; } + +#undef IF_SECONDARY +#undef NO_SECONDARY + + // Keep a valid entity ID at the end() so _iter<>::operator++ knows when to stop the loop. + // Use FIRST_VALID_ID since we are sure that that is indeed a valid ID. +#define ITERATOR_FENCE { FIRST_VALID_ID, keys_mapped_type{} } +public: + + SparseFlatMap() + { + clear(); + } + + SparseFlatMap(const SparseFlatMap& o) + { + m_Count = o.m_Count; + std::copy(o.m_Keys1.begin(), o.m_Keys1.end(), std::back_inserter(m_Keys1)); + std::copy(o.m_Keys2.begin(), o.m_Keys2.end(), std::back_inserter(m_Keys2)); + std::copy(o.m_Data1.begin(), o.m_Data1.end(), std::inserter(m_Data1, m_Data1.begin())); + std::copy(o.m_Data2.begin(), o.m_Data2.end(), std::inserter(m_Data2, m_Data2.begin())); + } + + SparseFlatMap& operator=(const SparseFlatMap& o) + { + SparseFlatMap tmp(o); + m_Count = tmp.m_Count; + m_Keys1.swap(tmp.m_Keys1); + m_Keys2.swap(tmp.m_Keys2); + m_Data1.swap(tmp.m_Data1); + m_Data2.swap(tmp.m_Data2); + return *this; + } + + template struct _iter + : public std::iterator + { +#define NOP(x) typename std::remove_pointer::type +#define NOCONST(x) typename std::remove_const::type +#define NOCONSTP(x) NOCONST(NOP(x))* + + key_t m_CurrentKey; + key_vector_t m_Keys; + value_vector_t m_Data; + const std::pair* m_ResetAt; + key_vector_t m_KeysSwitchAt; + value_vector_t m_DataSwitchAt; + + _iter(T key, key_vector_t keys, value_vector_t data, + const std::pair* reset = nullptr, key_vector_t ks = nullptr, value_vector_t ds = nullptr) + : m_CurrentKey(key), m_Keys(keys), m_Data(data), m_ResetAt(reset), m_KeysSwitchAt(ks), m_DataSwitchAt(ds) + {} + + _iter(const _iter& o) + : m_CurrentKey(o.m_CurrentKey), m_Keys(o.m_Keys), m_Data(o.m_Data), + m_ResetAt(o.m_ResetAt), m_KeysSwitchAt(o.m_KeysSwitchAt), m_DataSwitchAt(o.m_DataSwitchAt) + {} + + template ::value>::type> + _iter(const _iter& o) + : m_CurrentKey(o.m_CurrentKey), m_Keys(o.m_Keys), m_Data(o.m_Data), + m_ResetAt(o.m_ResetAt), m_KeysSwitchAt(o.m_KeysSwitchAt), m_DataSwitchAt(o.m_DataSwitchAt) + {} +#undef NOCONST +#undef NOCONSTP +#undef NOP + + // If we use SBO, return a pair of references to the value_type of Keys. + // This leverages the SBO to avoid fetching memory from an unrelated data structure. + template > + typename std::enable_if::type operator*() + { + return std::pair((*m_Keys)[m_CurrentKey].first, (*m_Keys)[m_CurrentKey].second); + } + + // Otherwise return a pair of references on Keys and Data.- + template > + typename std::enable_if::type operator*() + { + return std::pair((*m_Keys)[m_CurrentKey].first, *(*m_Keys)[m_CurrentKey].second); + } + + template > + typename std::enable_if::type operator*() const + { + return std::pair((*m_Keys)[m_CurrentKey].first, (*m_Keys)[m_CurrentKey].second); + } + + template > + typename std::enable_if::type operator*() const + { + return std::pair((*m_Keys)[m_CurrentKey].first, *(*m_Keys)[m_CurrentKey].second); + } + + + // Hack to provide operator-> + template + class temporary { + A a; + public: + temporary(const A& a) : a(a) {} + A* operator ->() { return &a; } + }; + + template > + typename std::enable_if>::type operator->() + { + return temporary(ret((*m_Keys)[m_CurrentKey].first, (*m_Keys)[m_CurrentKey].second)); + } + + template > + typename std::enable_if>::type operator->() const + { + return temporary(ret((*m_Keys)[m_CurrentKey].first, (*m_Keys)[m_CurrentKey].second)); + } + + template > + typename std::enable_if>::type operator->() + { + return temporary(ret((*m_Keys)[m_CurrentKey].first, *(*m_Keys)[m_CurrentKey].second)); + } + + template > + typename std::enable_if>::type operator->() const + { + return temporary(ret((*m_Keys)[m_CurrentKey].first, *(*m_Keys)[m_CurrentKey].second)); + } + + template + typename std::enable_if::type operator++() // ++it + { + do + ++m_CurrentKey; + while ((*m_Keys)[m_CurrentKey].first == INVALID_ENTITY); + if (&(*m_Keys)[m_CurrentKey] == m_ResetAt) + { + m_Keys = m_KeysSwitchAt; + m_Data = m_DataSwitchAt; + m_CurrentKey = 0; + if ((*m_Keys)[m_CurrentKey].first == INVALID_ENTITY) + ++(*this); + } + return *this; + } + template + typename std::enable_if::type operator++() // ++it + { + do + ++m_CurrentKey; + while ((*m_Keys)[m_CurrentKey].first == INVALID_ENTITY); + return *this; + } + _iter operator++(int) // it++ + { + _iter orig = *this; + ++(*this); + return orig; + } + + template typename std::enable_if::type + operator==(_iter o) { return m_Keys == o.m_Keys && m_CurrentKey == o.m_CurrentKey; } + + template typename std::enable_if::type + operator==(_iter o) { return m_CurrentKey == o.m_CurrentKey; } + + template typename std::enable_if::type + operator!=(_iter o) { return m_Keys != o.m_Keys || m_CurrentKey != o.m_CurrentKey; } + + template typename std::enable_if::type + operator!=(_iter o) { return m_CurrentKey != o.m_CurrentKey; } + }; + + typedef _iter iterator; + typedef _iter const_iterator; + + iterator it(const key_type& key) + { + return iterator(Idx(key), &Keys(key), &Data(key), &m_Keys1.back(), &m_Keys2, &m_Data2); + } + + const_iterator it(const key_type& key) const + { + return const_iterator(Idx(key), &Keys(key), &Data(key), &m_Keys1.back(), &m_Keys2, &m_Data2); + } + + iterator begin() + { + iterator i = it(FIRST_VALID_ID); + if ((*i).first != INVALID_ENTITY && m_Keys1.size() > 1) + return i; + else if (m_Keys1.size() == 1 && m_Keys2.size() == 1) + return end(); + else if (m_Keys1.size() == 1 && m_Keys2.size() > 1) + return ++it(INTERLEAVED_ID); + return ++i; // skip invalid entities + } + + const_iterator begin() const + { + const_iterator i = it(FIRST_VALID_ID); + if ((*i).first != INVALID_ENTITY && m_Keys1.size() > 1) + return i; + else if (m_Keys1.size() == 1 && m_Keys2.size() == 1) + return end(); + else if (m_Keys1.size() == 1 && m_Keys2.size() > 1) + return ++it(INTERLEAVED_ID); + return ++i; // skip invalid entities + } + + // return the ITERATOR_FENCE of the keys vector, which is where the iterator will stop. + template typename std::enable_if::type + end() { return it(INTERLEAVED_ID + m_Keys2.size() - 1); } + template typename std::enable_if::type + end() const { return it(INTERLEAVED_ID + m_Keys2.size() - 1); } + + template typename std::enable_if::type + end() { return it(FIRST_VALID_ID + m_Keys1.size() - 1); } + template typename std::enable_if::type + end() const { return it(FIRST_VALID_ID + m_Keys1.size() - 1); } + + bool empty() const { return m_Count == 0; } + size_t size() const { return m_Count; } + +private: + // Internal assign, implemented differently if we use SBO. + template + typename std::enable_if::type + assign(keys_container& keys, data_container& UNUSED(data), const key_type& idx, const key_type& key, const mapped_type& value) + { + keys[idx] = { key, value }; + } + + template + typename std::enable_if::type + assign(keys_container& keys, data_container& data, const key_type& idx, const key_type& key, const mapped_type& value) + { + data[idx] = value; + keys[idx] = { key, &data[idx] }; + } + +public: + std::pair insert_or_assign(const key_type& key, const mapped_type& value) + { + ENSURE(key >= FIRST_VALID_ID); + + key_type idx = Idx(key); + auto& keys = Keys(key); + auto& data = Data(key); + if (static_cast(idx) >= keys.size() - 1) + { + // reset current iterator gate + keys.back() = { INVALID_ENTITY, keys_mapped_type{} }; + + // Fill [end(),…,key[ invalid entities, our new key, and then add a new iterator gate at the end; + // resize, make sure to keep a valid entity ID at the end by adding a new ITERATOR_FENCE + keys.resize(idx+2, { INVALID_ENTITY, keys_mapped_type{} }); + + keys.back() = ITERATOR_FENCE; + } + bool inserted = false; + if (keys[idx].first == INVALID_ENTITY) + { + inserted = true; + ++m_Count; + } + assign(keys, data, idx, key, value); + return {it(key), inserted}; + } + + size_t erase(iterator it) + { + if ((*it).first != INVALID_ENTITY && it != end()) + { + // We don't want to let external users change our IDs since that'd break everything + // thus iterators->first are const key_type&, but we _do_ want to reset it when erasing, + // so const_cast the const away. + const_cast((*it).first) = INVALID_ENTITY; + (*it).second.~V(); // call dtor + --m_Count; + return 1; + } + return 0; + } + + size_t erase(const key_type& key) + { + ENSURE(key >= FIRST_VALID_ID); + key_type idx = Idx(key); + if (static_cast(idx) < Keys(key).size() - 1) + return erase(it(key)); + return 0; + } + + static void setup(std::vector& data) + { + data.push_back(V{}); + } + + template + static void setup(A& data) + { + data.insert(std::make_pair(0, V{})); + } + + void clear() + { + m_Keys1.clear(); + m_Keys2.clear(); + m_Keys1.reserve(4096); + m_Keys2.reserve(4096); + m_Keys1.push_back(ITERATOR_FENCE); + m_Keys2.push_back(ITERATOR_FENCE); + + m_Data1.clear(); + m_Data2.clear(); + m_Data1.reserve(4096); + m_Data2.reserve(4096); + setup(m_Data1); + setup(m_Data2); + + m_Count = 0; + } + + mapped_type& operator[] (const key_type& k) + { + if (find(k) != end()) + return (*find(k)).second; + + // Insert a default item in a valid spot so the user may modify it. + // This has the same flaw as std::map that you may inadvertantly create an item when iterating. + return (*insert_or_assign(k, V{}).first).second; + } + + const mapped_type& at(const key_type& k) const + { + ENSURE(find(k) != end()); + return (*find(k)).second; + } + + iterator find(const key_type& key) + { + if (key < FIRST_VALID_ID) + return end(); + key_type idx = Idx(key); + if (static_cast(idx) < Keys(key).size() - 1 && Keys(key)[idx].first != INVALID_ENTITY) + return it(key); + return end(); + } + + const_iterator find(const key_type& key) const + { + if (key < FIRST_VALID_ID) + return end(); + key_type idx = Idx(key); + if (static_cast(idx) < Keys(key).size() - 1 && Keys(key)[idx].first != INVALID_ENTITY) + return it(key); + return end(); + } +#undef ITERATOR_FENCE +}; + +template +struct SerializeSparseFlatMap +{ + template + void operator()(ISerializer& serialize, const char* UNUSED(name), SparseFlatMap& value) + { + size_t len = value.size(); + serialize.NumberU32_Unbounded("length", (u32)len); + size_t count = 0; + for (typename SparseFlatMap::reference data : value) + { + serialize.NumberU32_Unbounded("key", data.first); + VSerializer()(serialize, "value", data.second); + count++; + } + // test to see if the sparse flat map count wasn't wrong + // (which causes a crashing deserialisation) + ENSURE(count == len); + } + + template + void operator()(IDeserializer& deserialize, const char* UNUSED(name), SparseFlatMap& 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_or_assign(k, v); + } + } +}; + +#endif Index: source/simulation2/system/ComponentManager.h =================================================================== --- source/simulation2/system/ComponentManager.h +++ source/simulation2/system/ComponentManager.h @@ -30,6 +30,7 @@ #include #include #include +#include "simulation2/helpers/SparseFlatMap.h" class IComponent; class CParamNode; @@ -267,7 +268,7 @@ typedef std::pair InterfacePair; typedef std::vector InterfaceList; - typedef boost::unordered_map InterfaceListUnordered; + typedef SparseFlatMap InterfaceListUnordered; InterfaceList GetEntitiesWithInterface(InterfaceId iid) const; const InterfaceListUnordered& GetEntitiesWithInterfaceUnordered(InterfaceId iid) const; @@ -345,22 +346,25 @@ ComponentTypeId m_CurrentComponent; // used when loading component types bool m_CurrentlyHotloading; - // TODO: some of these should be vectors + // Use SparseFlatMap for indexing since ComponentTypeId, MessageTypeId, InterfaceId all have 0 as invalid + // and this is much more efficient than using std::map or std::unordered_map + using EntityComponentMap = SparseFlatMap; + std::map m_ComponentTypesById; - std::vector m_ScriptedSystemComponents; - std::vector > m_ComponentsByInterface; // indexed by InterfaceId - std::map > m_ComponentsByTypeId; - std::map > m_LocalMessageSubscriptions; - std::map > m_GlobalMessageSubscriptions; + std::vector m_ScriptedSystemComponents; + SparseFlatMap m_ComponentsByInterface; + SparseFlatMap m_ComponentsByTypeId; + SparseFlatMap > m_LocalMessageSubscriptions; + SparseFlatMap > m_GlobalMessageSubscriptions; std::map m_ComponentTypeIdsByName; std::map m_MessageTypeIdsByName; - std::map m_MessageTypeNamesById; + SparseFlatMap m_MessageTypeNamesById; std::map m_InterfaceIdsByName; std::map m_DynamicMessageSubscriptionsNonsync; std::map > m_DynamicMessageSubscriptionsNonsyncByComponent; - std::unordered_map m_ComponentCaches; + SparseFlatMap m_ComponentCaches; // TODO: maintaining both ComponentsBy* is nasty; can we get rid of one, // while keeping QueryInterface and PostMessage sufficiently efficient? Index: source/simulation2/system/ComponentManager.cpp =================================================================== --- source/simulation2/system/ComponentManager.cpp +++ source/simulation2/system/ComponentManager.cpp @@ -104,7 +104,7 @@ m_ScriptInterface.SetGlobal("INVALID_PLAYER", (int)INVALID_PLAYER); m_ScriptInterface.SetGlobal("SYSTEM_ENTITY", (int)SYSTEM_ENTITY); - m_ComponentsByInterface.resize(IID__LastNative); + m_ComponentsByInterface[IID__LastNative]; // resize ResetState(); } @@ -214,17 +214,16 @@ } // Remove the old component type's message subscriptions - std::map >::iterator it; - for (it = componentManager->m_LocalMessageSubscriptions.begin(); it != componentManager->m_LocalMessageSubscriptions.end(); ++it) + for (auto it = componentManager->m_LocalMessageSubscriptions.begin(); it != componentManager->m_LocalMessageSubscriptions.end(); ++it) { - std::vector& types = it->second; + std::vector& types = (*it).second; std::vector::iterator ctit = find(types.begin(), types.end(), cid); if (ctit != types.end()) types.erase(ctit); } - for (it = componentManager->m_GlobalMessageSubscriptions.begin(); it != componentManager->m_GlobalMessageSubscriptions.end(); ++it) + for (auto it = componentManager->m_GlobalMessageSubscriptions.begin(); it != componentManager->m_GlobalMessageSubscriptions.end(); ++it) { - std::vector& types = it->second; + std::vector& types = (*it).second; std::vector::iterator ctit = find(types.begin(), types.end(), cid); if (ctit != types.end()) types.erase(ctit); @@ -305,11 +304,11 @@ { // For every script component with this cid, we need to switch its // prototype from the old constructor's prototype property to the new one's - const std::map& comps = componentManager->m_ComponentsByTypeId[cid]; - std::map::const_iterator eit = comps.begin(); + const EntityComponentMap& comps = componentManager->m_ComponentsByTypeId[cid]; + EntityComponentMap::const_iterator eit = comps.begin(); for (; eit != comps.end(); ++eit) { - JS::RootedValue instance(cx, eit->second->GetJSInstance()); + JS::RootedValue instance(cx, (*eit).second->GetJSInstance()); if (!instance.isNull()) { componentManager->m_ScriptInterface.SetPrototype(instance, protoVal); @@ -357,7 +356,7 @@ // IIDs start at 1, so size+1 is the next unused one size_t id = componentManager->m_InterfaceIdsByName.size() + 1; componentManager->m_InterfaceIdsByName[name] = (InterfaceId)id; - componentManager->m_ComponentsByInterface.resize(id+1); // add one so we can index by InterfaceId + componentManager->m_ComponentsByInterface[id + 1]; // resize componentManager->m_ScriptInterface.SetGlobal(("IID_" + name).c_str(), (int)id); } @@ -509,27 +508,23 @@ m_DynamicMessageSubscriptionsNonsyncByComponent.clear(); // Delete all IComponents - std::map >::iterator iit = m_ComponentsByTypeId.begin(); - for (; iit != m_ComponentsByTypeId.end(); ++iit) + for (std::pair componentsByType : m_ComponentsByTypeId) { - std::map::iterator eit = iit->second.begin(); - for (; eit != iit->second.end(); ++eit) + for (std::pair component : componentsByType.second) { - eit->second->Deinit(); - m_ComponentTypesById[iit->first].dealloc(eit->second); + component.second->Deinit(); + m_ComponentTypesById[componentsByType.first].dealloc(component.second); } } - - std::vector >::iterator ifcit = m_ComponentsByInterface.begin(); - for (; ifcit != m_ComponentsByInterface.end(); ++ifcit) - ifcit->clear(); + for (std::pair components : m_ComponentsByInterface) + components.second.clear(); m_ComponentsByTypeId.clear(); // Delete all SEntityComponentCaches - std::unordered_map::iterator ccit = m_ComponentCaches.begin(); - for (; ccit != m_ComponentCaches.end(); ++ccit) - free(ccit->second); + for (std::pair cache : m_ComponentCaches) + free(cache.second); + m_ComponentCaches.clear(); m_SystemEntity = CEntityHandle(); @@ -753,17 +748,15 @@ const ComponentType& ct = it->second; - ENSURE((size_t)ct.iid < m_ComponentsByInterface.size()); +// ENSURE((size_t)ct.iid < m_ComponentsByInterface.size()); - boost::unordered_map& emap1 = m_ComponentsByInterface[ct.iid]; + EntityComponentMap& emap1 = m_ComponentsByInterface[ct.iid]; if (emap1.find(ent.GetId()) != emap1.end()) { LOGERROR("Multiple components for interface %d", ct.iid); return NULL; } - std::map& emap2 = m_ComponentsByTypeId[cid]; - // If this is a scripted component, construct the appropriate JS object first JS::RootedValue obj(cx); if (ct.type == CT_Script) @@ -783,9 +776,11 @@ component->SetEntityHandle(ent); component->SetSimContext(m_SimContext); + EntityComponentMap& emap2 = m_ComponentsByTypeId[cid]; + // Store a reference to the new component - emap1.insert(std::make_pair(ent.GetId(), component)); - emap2.insert(std::make_pair(ent.GetId(), component)); + emap1.insert_or_assign(ent.GetId(), component); + emap2.insert_or_assign(ent.GetId(), component); // TODO: We need to more careful about this - if an entity is constructed by a component // while we're iterating over all components, this will invalidate the iterators and everything // will break. @@ -804,10 +799,10 @@ // Just add it into the by-interface map, not the by-component-type map, // so it won't be considered for messages or deletion etc - boost::unordered_map& emap1 = m_ComponentsByInterface.at(iid); + EntityComponentMap& emap1 = m_ComponentsByInterface[iid]; if (emap1.find(ent.GetId()) != emap1.end()) debug_warn(L"Multiple components for interface"); - emap1.insert(std::make_pair(ent.GetId(), &component)); + emap1.insert_or_assign(ent.GetId(), &component); SEntityComponentCache* cache = ent.GetComponentCache(); ENSURE(cache != NULL && iid < (int)cache->numInterfaces && cache->interfaces[iid] == NULL); @@ -831,8 +826,7 @@ CEntityHandle CComponentManager::LookupEntityHandle(entity_id_t ent, bool allowCreate) { - std::unordered_map::iterator it; - it = m_ComponentCaches.find(ent); + SparseFlatMap::iterator it = m_ComponentCaches.find(ent); if (it == m_ComponentCaches.end()) { if (allowCreate) @@ -925,17 +919,16 @@ FlattenDynamicSubscriptions(); // Destroy the components, and remove from m_ComponentsByTypeId: - std::map >::iterator iit = m_ComponentsByTypeId.begin(); - for (; iit != m_ComponentsByTypeId.end(); ++iit) + for (std::pair entityComponents : m_ComponentsByTypeId) { - std::map::iterator eit = iit->second.find(ent); - if (eit != iit->second.end()) + EntityComponentMap::iterator eit = entityComponents.second.find(ent); + if (eit != entityComponents.second.end()) { - eit->second->Deinit(); - RemoveComponentDynamicSubscriptions(eit->second); - m_ComponentTypesById[iit->first].dealloc(eit->second); - iit->second.erase(ent); - handle.GetComponentCache()->interfaces[m_ComponentTypesById[iit->first].iid] = NULL; + (*eit).second->Deinit(); + RemoveComponentDynamicSubscriptions((*eit).second); + m_ComponentTypesById[entityComponents.first].dealloc((*eit).second); + entityComponents.second.erase(ent); + handle.GetComponentCache()->interfaces[m_ComponentTypesById[entityComponents.first].iid] = NULL; } } @@ -943,47 +936,38 @@ m_ComponentCaches.erase(ent); // Remove from m_ComponentsByInterface - std::vector >::iterator ifcit = m_ComponentsByInterface.begin(); - for (; ifcit != m_ComponentsByInterface.end(); ++ifcit) - { - ifcit->erase(ent); - } + for (std::pair components : m_ComponentsByInterface) + components.second.erase(ent); } } } IComponent* CComponentManager::QueryInterface(entity_id_t ent, InterfaceId iid) const { - if ((size_t)iid >= m_ComponentsByInterface.size()) - { - // Invalid iid - return NULL; - } - - boost::unordered_map::const_iterator eit = m_ComponentsByInterface[iid].find(ent); - if (eit == m_ComponentsByInterface[iid].end()) + if (m_ComponentsByInterface.find(iid) == m_ComponentsByInterface.end() || + m_ComponentsByInterface.at(iid).find(ent) == m_ComponentsByInterface.at(iid).end()) { // This entity doesn't implement this interface return NULL; } - return eit->second; + return (*m_ComponentsByInterface.at(iid).find(ent)).second; } CComponentManager::InterfaceList CComponentManager::GetEntitiesWithInterface(InterfaceId iid) const { std::vector > ret; - if ((size_t)iid >= m_ComponentsByInterface.size()) + if (m_ComponentsByInterface.find(iid) == m_ComponentsByInterface.end()) { - // Invalid iid + // Invalid iid or no entities return ret; } - ret.reserve(m_ComponentsByInterface[iid].size()); + ret.reserve(m_ComponentsByInterface.at(iid).size()); - boost::unordered_map::const_iterator it = m_ComponentsByInterface[iid].begin(); - for (; it != m_ComponentsByInterface[iid].end(); ++it) + EntityComponentMap::const_iterator it = m_ComponentsByInterface.at(iid).begin(); + for (; it != m_ComponentsByInterface.at(iid).end(); ++it) ret.push_back(*it); std::sort(ret.begin(), ret.end()); // lexicographic pair comparison means this'll sort by entity ID @@ -994,13 +978,13 @@ static CComponentManager::InterfaceListUnordered g_EmptyEntityMap; const CComponentManager::InterfaceListUnordered& CComponentManager::GetEntitiesWithInterfaceUnordered(InterfaceId iid) const { - if ((size_t)iid >= m_ComponentsByInterface.size()) + if (m_ComponentsByInterface.find(iid) == m_ComponentsByInterface.end()) { - // Invalid iid + // Invalid iid or no entities return g_EmptyEntityMap; } - return m_ComponentsByInterface[iid]; + return m_ComponentsByInterface.at(iid); } void CComponentManager::PostMessage(entity_id_t ent, const CMessage& msg) @@ -1008,22 +992,20 @@ PROFILE2_IFSPIKE("Post Message", 0.0005); PROFILE2_ATTR("%s", msg.GetScriptHandlerName()); // Send the message to components of ent, that subscribed locally to this message - std::map >::const_iterator it; - it = m_LocalMessageSubscriptions.find(msg.GetType()); + SparseFlatMap >::const_iterator it = m_LocalMessageSubscriptions.find(msg.GetType()); if (it != m_LocalMessageSubscriptions.end()) { - std::vector::const_iterator ctit = it->second.begin(); - for (; ctit != it->second.end(); ++ctit) + for (const ComponentTypeId& componentTypeId : (*it).second) { // Find the component instances of this type (if any) - std::map >::const_iterator emap = m_ComponentsByTypeId.find(*ctit); + SparseFlatMap::const_iterator emap = m_ComponentsByTypeId.find(componentTypeId); if (emap == m_ComponentsByTypeId.end()) continue; // Send the message to all of them - std::map::const_iterator eit = emap->second.find(ent); - if (eit != emap->second.end()) - eit->second->HandleMessage(msg, false); + EntityComponentMap::const_iterator eit = (*emap).second.find(ent); + if (eit != (*emap).second.end()) + (*eit).second->HandleMessage(msg, false); } } @@ -1033,22 +1015,19 @@ void CComponentManager::BroadcastMessage(const CMessage& msg) { // Send the message to components of all entities that subscribed locally to this message - std::map >::const_iterator it; - it = m_LocalMessageSubscriptions.find(msg.GetType()); + SparseFlatMap >::const_iterator it = m_LocalMessageSubscriptions.find(msg.GetType()); if (it != m_LocalMessageSubscriptions.end()) { - std::vector::const_iterator ctit = it->second.begin(); - for (; ctit != it->second.end(); ++ctit) + for (const ComponentTypeId& componentTypeId : (*it).second) { // Find the component instances of this type (if any) - std::map >::const_iterator emap = m_ComponentsByTypeId.find(*ctit); + SparseFlatMap::const_iterator emap = m_ComponentsByTypeId.find(componentTypeId); if (emap == m_ComponentsByTypeId.end()) continue; // Send the message to all of them - std::map::const_iterator eit = emap->second.begin(); - for (; eit != emap->second.end(); ++eit) - eit->second->HandleMessage(msg, false); + for (std::pair component : (*emap).second) + component.second->HandleMessage(msg, false); } } @@ -1062,32 +1041,29 @@ // (Common functionality for PostMessage and BroadcastMessage) // Send the message to components of all entities that subscribed globally to this message - std::map >::const_iterator it; - it = m_GlobalMessageSubscriptions.find(msg.GetType()); + SparseFlatMap>::const_iterator it = m_GlobalMessageSubscriptions.find(msg.GetType()); if (it != m_GlobalMessageSubscriptions.end()) { - std::vector::const_iterator ctit = it->second.begin(); - for (; ctit != it->second.end(); ++ctit) + for (const ComponentTypeId& componentTypeId : (*it).second) { // Special case: Messages for local entities shouldn't be sent to script // components that subscribed globally, so that we don't have to worry about // them accidentally picking up non-network-synchronised data. if (ENTITY_IS_LOCAL(ent)) { - std::map::const_iterator it = m_ComponentTypesById.find(*ctit); + std::map::const_iterator it = m_ComponentTypesById.find(componentTypeId); if (it != m_ComponentTypesById.end() && it->second.type == CT_Script) continue; } // Find the component instances of this type (if any) - std::map >::const_iterator emap = m_ComponentsByTypeId.find(*ctit); + SparseFlatMap::const_iterator emap = m_ComponentsByTypeId.find(componentTypeId); if (emap == m_ComponentsByTypeId.end()) continue; // Send the message to all of them - std::map::const_iterator eit = emap->second.begin(); - for (; eit != emap->second.end(); ++eit) - eit->second->HandleMessage(msg, true); + for (const std::pair component : (*emap).second) + component.second->HandleMessage(msg, true); } } @@ -1132,17 +1108,17 @@ std::vector componentTypes; - for (std::map::const_iterator it = m_ComponentTypesById.begin(); it != m_ComponentTypesById.end(); ++it) + for (const std::pair& componentType : m_ComponentTypesById) { schema += - "" - "" - "" + it->second.schema + "" + "" + "" + "" + componentType.second.schema + "" "" ""; - interfaceComponentTypes[it->second.iid].push_back(it->second.name); - componentTypes.push_back(it->second.name); + interfaceComponentTypes[componentType.second.iid].push_back(componentType.second.name); + componentTypes.push_back(componentType.second.name); } // Declare the implementation of each interface, for documentation Index: source/simulation2/system/ComponentManagerSerialization.cpp =================================================================== --- source/simulation2/system/ComponentManagerSerialization.cpp +++ source/simulation2/system/ComponentManagerSerialization.cpp @@ -58,15 +58,9 @@ std::map > components; //std::map names; - std::map >::const_iterator ctit = m_ComponentsByTypeId.begin(); - for (; ctit != m_ComponentsByTypeId.end(); ++ctit) - { - std::map::const_iterator eit = ctit->second.begin(); - for (; eit != ctit->second.end(); ++eit) - { - components[eit->first][ctit->first] = eit->second; - } - } + for (const std::pair& entityComponents : m_ComponentsByTypeId) + for (const std::pair& component : entityComponents.second) + components[component.first][entityComponents.first] = component.second; std::map >::const_iterator cit = components.begin(); for (; cit != components.end(); ++cit) @@ -109,19 +103,18 @@ serializer.StringASCII("rng", SerializeRNG(m_RNG), 0, 32); serializer.NumberU32_Unbounded("next entity id", m_NextEntityId); - std::map >::const_iterator cit = m_ComponentsByTypeId.begin(); - for (; cit != m_ComponentsByTypeId.end(); ++cit) + for (const std::pair& entityComponents : m_ComponentsByTypeId) { // In quick mode, only check unit positions - if (quick && !(cit->first == CID_Position)) + if (quick && !(entityComponents.first == CID_Position)) continue; // Only emit component types if they have a component that will be serialized bool needsSerialization = false; - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& component : entityComponents.second) { // Don't serialize local entities - if (ENTITY_IS_LOCAL(eit->first)) + if (ENTITY_IS_LOCAL(component.first)) continue; needsSerialization = true; @@ -131,16 +124,16 @@ if (!needsSerialization) continue; - serializer.NumberI32_Unbounded("component type id", cit->first); + serializer.NumberI32_Unbounded("component type id", entityComponents.first); - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& component : entityComponents.second) { // Don't serialize local entities - if (ENTITY_IS_LOCAL(eit->first)) + if (ENTITY_IS_LOCAL(component.first)) continue; - serializer.NumberU32_Unbounded("entity id", eit->first); - eit->second->Serialize(serializer); + serializer.NumberU32_Unbounded("entity id", component.first); + component.second->Serialize(serializer); } } @@ -188,21 +181,19 @@ serializer.StringASCII("rng", SerializeRNG(m_RNG), 0, 32); serializer.NumberU32_Unbounded("next entity id", m_NextEntityId); - std::map >::const_iterator cit; - uint32_t numSystemComponentTypes = 0; uint32_t numComponentTypes = 0; std::set serializedSystemComponentTypes; std::set serializedComponentTypes; - for (cit = m_ComponentsByTypeId.begin(); cit != m_ComponentsByTypeId.end(); ++cit) + for (const std::pair& entityComponents : m_ComponentsByTypeId) { // Only emit component types if they have a component that will be serialized bool needsSerialization = false; - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& component : entityComponents.second) { // Don't serialize local entities, and handle SYSTEM_ENTITY separately - if (ENTITY_IS_LOCAL(eit->first) || eit->first == SYSTEM_ENTITY) + if (ENTITY_IS_LOCAL(component.first) || component.first == SYSTEM_ENTITY) continue; needsSerialization = true; @@ -212,24 +203,24 @@ if (needsSerialization) { numComponentTypes++; - serializedComponentTypes.insert(cit->first); + serializedComponentTypes.insert(entityComponents.first); } - if (cit->second.find(SYSTEM_ENTITY) != cit->second.end()) + if (entityComponents.second.find(SYSTEM_ENTITY) != entityComponents.second.end()) { numSystemComponentTypes++; - serializedSystemComponentTypes.insert(cit->first); + serializedSystemComponentTypes.insert(entityComponents.first); } } serializer.NumberU32_Unbounded("num system component types", numSystemComponentTypes); - for (cit = m_ComponentsByTypeId.begin(); cit != m_ComponentsByTypeId.end(); ++cit) + for (const std::pair& entityComponents : m_ComponentsByTypeId) { - if (serializedSystemComponentTypes.find(cit->first) == serializedSystemComponentTypes.end()) + if (serializedSystemComponentTypes.find(entityComponents.first) == serializedSystemComponentTypes.end()) continue; - std::map::const_iterator ctit = m_ComponentTypesById.find(cit->first); + std::map::const_iterator ctit = m_ComponentTypesById.find(entityComponents.first); if (ctit == m_ComponentTypesById.end()) { debug_warn(L"Invalid ctit"); // this should never happen @@ -238,23 +229,23 @@ serializer.StringASCII("name", ctit->second.name, 0, 255); - std::map::const_iterator eit = cit->second.find(SYSTEM_ENTITY); - if (eit == cit->second.end()) + EntityComponentMap::const_iterator eit = entityComponents.second.find(SYSTEM_ENTITY); + if (eit == entityComponents.second.end()) { debug_warn(L"Invalid eit"); // this should never happen return false; } - eit->second->Serialize(serializer); + (*eit).second->Serialize(serializer); } serializer.NumberU32_Unbounded("num component types", numComponentTypes); - for (cit = m_ComponentsByTypeId.begin(); cit != m_ComponentsByTypeId.end(); ++cit) + for (const std::pair& entityComponents : m_ComponentsByTypeId) { - if (serializedComponentTypes.find(cit->first) == serializedComponentTypes.end()) + if (serializedComponentTypes.find(entityComponents.first) == serializedComponentTypes.end()) continue; - std::map::const_iterator ctit = m_ComponentTypesById.find(cit->first); + std::map::const_iterator ctit = m_ComponentTypesById.find(entityComponents.first); if (ctit == m_ComponentTypesById.end()) { debug_warn(L"Invalid ctit"); // this should never happen @@ -265,10 +256,10 @@ // Count the components before serializing any of them uint32_t numComponents = 0; - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& component : entityComponents.second) { // Don't serialize local entities or SYSTEM_ENTITY - if (ENTITY_IS_LOCAL(eit->first) || eit->first == SYSTEM_ENTITY) + if (ENTITY_IS_LOCAL(component.first) || component.first == SYSTEM_ENTITY) continue; numComponents++; @@ -278,14 +269,14 @@ serializer.NumberU32_Unbounded("num components", numComponents); // Serialize the components now - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& component : entityComponents.second) { // Don't serialize local entities or SYSTEM_ENTITY - if (ENTITY_IS_LOCAL(eit->first) || eit->first == SYSTEM_ENTITY) + if (ENTITY_IS_LOCAL(component.first) || component.first == SYSTEM_ENTITY) continue; - serializer.NumberU32_Unbounded("entity id", eit->first); - eit->second->Serialize(serializer); + serializer.NumberU32_Unbounded("entity id", component.first); + component.second->Serialize(serializer); } } Index: source/simulation2/system/EntityMap.h =================================================================== --- source/simulation2/system/EntityMap.h +++ /dev/null @@ -1,282 +0,0 @@ -/* 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: - 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 =================================================================== --- source/simulation2/tests/test_EntityMap.h +++ /dev/null @@ -1,308 +0,0 @@ -/* Copyright (C) 2019 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; // it++ incorrectly returns a pointer in svn - 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 (EntityMap::value_type& 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; // it++ incorrectly returns a pointer in svn - 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); - test.erase(4);// TS_ASSERT(test.erase(4) == 1); - -// TS_ASSERT(test.m_Data.size() == 5); - TS_ASSERT(test.size() == 0); - - test.erase(5);// 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_DISABLED() - { - EntityMap test; - printf("Testing performance of EntityMap\n"); - - double t = timer_Time(); - for (int i = 1; i <= 200000; ++i) - test.insert(i,i); - double tt = timer_Time() - t; - printf("inserting 200K elements in order: %lfs\n", tt); - - t = timer_Time(); - for (int i = 1; i <= 200000; ++i) - test.erase(i); - tt = timer_Time() - t; - printf("Erasing 200K elements, by key: %lfs\n", tt); - - t = timer_Time(); - for (int i = 200000; i >= 1; --i) - test.insert(i,i); - tt = timer_Time() - t; - printf("inserting 200K elements in reverse order: %lfs\n", tt); - - t = timer_Time(); - for (auto i = test.begin(); i != test.end(); ++i) - test.erase(i); - tt = timer_Time() - t; - printf("Erasing 200K elements, by iterator: %lfs\n", tt); - - t = timer_Time(); - for (int i = 1; i <= 200000; ++i) - test.erase(i); - tt = timer_Time() - t; - printf("Erasing 200K non-existing elements: %lfs\n", tt); - - // 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; - printf("200K random lookups in random order: %lfs\n", tt); - - t = timer_Time(); - for (auto& p : test) - p.second = 3; - tt = timer_Time() - t; - printf("auto iteration on 200K continuous entitymap: %lfs\n", tt); - - test.clear(); - - for (int i = 1; i <= 200000; ++i) - test.insert(i*5,i); - - t = timer_Time(); - for (EntityMap::value_type& p : test) - p.second = 3; - tt = timer_Time() - t; - printf("auto iteration on 200K sparse (holes of 5): %lfs\n", tt); - - test.clear(); - - for (int i = 1; i <= 4000; ++i) - test.insert(i*50,i); - - t = timer_Time(); - for (EntityMap::value_type& p : test) - p.second = 3; - tt = timer_Time() - t; - printf("auto iteration on 4K sparse (holes of 50): %lfs\n", tt); - - test.clear(); - - for (int i = 1; i <= 200000; ++i) - test.insert(i*50,i); - - t = timer_Time(); - for (EntityMap::value_type& p : test) - p.second = 3; - tt = timer_Time() - t; - printf("auto iteration on 200K sparse (holes of 50): %lfs\n", tt); - - test.clear(); - - for (int i = 1; i <= 2000000; ++i) - test.insert(i*50,i); - - t = timer_Time(); - for (EntityMap::iterator i = test.begin(); i != test.end(); ++i) - i->second = 3; - tt = timer_Time() - t; - printf("manual ++iteration on 2000K sparse (holes of 50) (warmup 1): %lfs\n", tt); - - t = timer_Time(); - for (EntityMap::iterator i = test.begin(); i != test.end(); ++i) - i->second = 3; - tt = timer_Time() - t; - printf("manual ++iteration on 2000K sparse (holes of 50) (warmup 2): %lfs\n", tt); - - t = timer_Time(); - for (EntityMap::iterator i = test.begin(); i != test.end(); ++i) - i->second = 3; - tt = timer_Time() - t; - printf("manual ++iteration on 2000K sparse (holes of 50): %lfs\n", tt); - - t = timer_Time(); - for (EntityMap::iterator i = test.begin(); i != test.end(); ++i) - i->second = 3; - tt = timer_Time() - t; - printf("manual iteration++ on 2000K sparse (holes of 50): %lfs\n", tt); - } -}; Index: source/simulation2/tests/test_SparseFlatMap.h =================================================================== --- /dev/null +++ source/simulation2/tests/test_SparseFlatMap.h @@ -0,0 +1,489 @@ +/* Copyright (C) 2017 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" + +// Defines FIRST_LOCAL_ENTITY, should go before SparseFlatMap.h +#include "simulation2/system/Entity.h" + +#include "simulation2/helpers/SparseFlatMap.h" +#include "simulation2/serialization/ISerializer.h" +#include "simulation2/serialization/IDeserializer.h" + +#include "lib/timer.h" + +#include + +struct LargeStruct { + size_t a; + size_t b; + size_t bc; + size_t bd; + size_t be; + LargeStruct() + { + a = 0; + } + LargeStruct(int a) + { + this->a = a; + } + bool operator==(LargeStruct o) const + { + return a == o.a; + }; + bool operator==(int o) const + { + return a == static_cast(o); + }; +}; + + +// Testing with SBO and without. +using TestMap1 = SparseFlatMap; +using TestMap2 = SparseFlatMap; +// No secondary ID range - should be slightly faster (mostly at iterating). +using TestMap3 = SparseFlatMap::NO_SECONDARY_IDS>; + +class TestSparseFlatMap : public CxxTest::TestSuite +{ +public: + template + void insert_or_assign() + { + TestMap test; + + TS_ASSERT(test.empty()); + + test.insert_or_assign(1,1); + TS_ASSERT(test.insert_or_assign(2,2).second); + test.insert_or_assign(3,3); + test.insert_or_assign(4,4); + TS_ASSERT(!test.insert_or_assign(4,5).second); + test.insert_or_assign(4,6); + + TS_ASSERT(test.size() == 4); + TS_ASSERT((*test.find(3)).second == 3); + TS_ASSERT((*test.find(4)).second == 6); + + test.insert_or_assign(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); + + // TODO: switch to if constexpr on C++17 + if (!only_first_range) + { + test.insert_or_assign(FIRST_LOCAL_ENTITY,3); + TS_ASSERT(test.size() == 6); + TS_ASSERT((*test.find(FIRST_LOCAL_ENTITY)).second == 3); + test.insert_or_assign(FIRST_LOCAL_ENTITY+1,4); + test.insert_or_assign(FIRST_LOCAL_ENTITY+2,5); + TS_ASSERT(test.size() == 8); + TS_ASSERT((*test.find(FIRST_LOCAL_ENTITY+1)).second == 4); + TS_ASSERT((*test.find(FIRST_LOCAL_ENTITY+2)).second == 5); + } + + // EntityMap test2; + + // test2.insert_or_assign(8,5); + // TS_ASSERT(test2.find(8)->second == 5); + // TS_ASSERT(test2.m_Data.size() == 5); + // TS_ASSERT(test2.size() == 1); + + } + + template + void iterators() + { + TestMap test; + + size_t iter = 0; + for (typename TestMap::reference v : test) + iter += v.first; // use the variable to silence the warning + + TS_ASSERT(iter == 0); + + test.insert_or_assign(1,1); + + iter = 0; + for (typename TestMap::reference v : test) + iter += v.first; // use the variable to silence the warning + TS_ASSERT(iter == 1); + + test.insert_or_assign(2, 2); + test.insert_or_assign(3, 3); + test.insert_or_assign(4, 4); + // TODO: switch to if constexpr on C++17 + if (!only_first_range) + test.insert_or_assign(FIRST_LOCAL_ENTITY + 3, 6); + + typename TestMap::iterator it = test.begin(); + TS_ASSERT((*it).first == 1); + ++it; + TS_ASSERT(it->first == 2); + ++it; + TS_ASSERT((*it).first == 3); + ++it; + TS_ASSERT(it->first == 4); + it++; + if (!only_first_range) + { + TS_ASSERT((*it).first == FIRST_LOCAL_ENTITY + 3); + it = test.end(); + test.erase(FIRST_LOCAL_ENTITY + 3); + } + + + for (typename TestMap::const_iterator cit1 = test.begin(); cit1 != test.end(); ++cit1) + {} + + typename TestMap::const_iterator cit = test.begin(); + + const TestMap& ref = test; + typename TestMap::const_iterator cit2 = cit; + typename TestMap::const_iterator cit3 = it; + TS_ASSERT(cit2->first == 1); + typename TestMap::const_iterator cit4 = ref.begin(); + // silence unused warnings + cit2 = cit3; + cit4 = cit2; + + TS_ASSERT((*cit).first == 1); + + iter = 0; + for (typename TestMap::reference 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_or_assign(10,1); + test.insert_or_assign(20,2); + test.insert_or_assign(30,3); + test.insert_or_assign(40,4); + + it = test.begin(); + TS_ASSERT((*it).second == 1); + ++it; // it++ incorrectly returns a pointer in svn + TS_ASSERT((*it).second == 2); + ++it; + TS_ASSERT((*it).second == 3); + it = test.end(); + // TS_ASSERT((*it).first == test.m_Data.back().first); + + } + + template + void erase() + { + TestMap test; + test.insert_or_assign(1,1); + test.insert_or_assign(2,2); + test.insert_or_assign(3,3); + test.insert_or_assign(4,4); + + TS_ASSERT(test.erase(2) == 1); + + // 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); + test.erase(4);// TS_ASSERT(test.erase(4) == 1); + + // TS_ASSERT(test.m_Data.size() == 5); + TS_ASSERT(test.size() == 0); + + test.erase(5);// TS_ASSERT(test.erase(5) == 0); + + test.insert_or_assign(1,1); + test.insert_or_assign(2,2); + test.insert_or_assign(3,3); + test.insert_or_assign(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); + } + + template + void clear() + { + TestMap test; + test.insert_or_assign(1,1); + test.insert_or_assign(2,2); + test.insert_or_assign(3,3); + test.insert_or_assign(4,4); + + test.clear(); + + // TS_ASSERT(test.m_Data.size() == 1); + TS_ASSERT(test.size() == 0); + } + + template + void find() + { + TestMap test; + test.insert_or_assign(1,1); + test.insert_or_assign(2,2); + test.insert_or_assign(3,3); + test.insert_or_assign(40,4); + + TS_ASSERT((*test.find(1)).second == 1); + TS_ASSERT(test.find(40)->second == 4); + TS_ASSERT(test.at(3) == 3); + TS_ASSERT(test.at(2) == 2); + TS_ASSERT(test[2] == 2); + TS_ASSERT(test[1] == 1); + TS_ASSERT(test.find(40)->second == 4); + TS_ASSERT(test.find(30) == test.end()); + + TS_ASSERT(test[5] == 0); + test[5] = 3; + TS_ASSERT(test[5] == 3); + test[6] = 6; + TS_ASSERT(test.at(6) == 6); + } + + template + void perf() + { + TestMap test; + printf("Testing performance of EntityMap\n"); + + auto t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.insert_or_assign(i,i); + auto tt = timer_Time() - t; + printf("insert_or_assigning 200K elements in order: %lfs\n",tt); + + if (!only_first_range) + { + for (int i = 1; i <= 200000; ++i) + test.insert_or_assign(FIRST_LOCAL_ENTITY + i,i); + tt = timer_Time() - t; + printf("insert_or_assigning 200K interleaved elements in order: %lfs\n",tt); + } + + t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.erase(i); + tt = timer_Time() - t; + printf("Erasing 200K elements, by key: %lfs\n",tt); + + if (!only_first_range) + { + for (int i = 1; i <= 200000; ++i) + test.erase(FIRST_LOCAL_ENTITY + i); + tt = timer_Time() - t; + printf("Erasing 200K interleaved elements, by key: %lfs\n",tt); + } + + t = timer_Time(); + for (int i = 200000; i >= 1; --i) + test.insert_or_assign(i,i); + tt = timer_Time() - t; + printf("insert_or_assigning 200K elements in reverse order: %lfs\n",tt); + + t = timer_Time(); + for (auto i = test.begin(); i != test.end(); ++i) + test.erase(i); + tt = timer_Time() - t; + printf("Erasing 200K elements, by iterator: %lfs\n",tt); + + t = timer_Time(); + for (int i = 1; i <= 200000; ++i) + test.erase(i); + tt = timer_Time() - t; + printf("Erasing 200K non-existing elements: %lfs\n",tt); + + // 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_or_assign(i,i); + + t = timer_Time(); + for (int i = 0; i < 200000; ++i) + (*test.find(vec[i])).second = 3; + tt = timer_Time() - t; + printf("200K random lookups in random order: %lfs\n",tt); + + t = timer_Time(); + for (typename TestMap::reference p : test) + p.second = 3; + tt = timer_Time() - t; + printf("auto iteration on 200K continuous entitymap: %lfs\n",tt); + + test.clear(); + + for (int i = 1; i <= 200000; ++i) + test.insert_or_assign(i*5,i); + + t = timer_Time(); + for (int i = 0; i < 200000; ++i) + (*test.find(vec[i]*5)).second = 3; + tt = timer_Time() - t; + printf("200K random lookups in random order (holes of 5): %lfs\n",tt); + + t = timer_Time(); + for (typename TestMap::reference p : test) + p.second = 3; + tt = timer_Time() - t; + printf("auto iteration on 200K sparse (holes of 5): %lfs\n",tt); + + test.clear(); + + for (int i = 1; i <= 4000; ++i) + test.insert_or_assign(i*50,i); + + t = timer_Time(); + for (typename TestMap::reference p : test) + p.second = 3; + tt = timer_Time() - t; + printf("auto iteration on 4K sparse (holes of 50): %lfs\n",tt); + + test.clear(); + + for (int i = 1; i <= 200000; ++i) + test.insert_or_assign(i*50,i); + + t = timer_Time(); + for (int i = 0; i < 200000; ++i) + (*test.find(vec[i]*50)).second = 3; + tt = timer_Time() - t; + printf("200K random lookups in random order (holes of 50): %lfs\n",tt); + + t = timer_Time(); + for (typename TestMap::reference p : test) + p.second = 3; + tt = timer_Time() - t; + printf("auto iteration on 200K sparse (holes of 50): %lfs\n",tt); + + test.clear(); + + for (int i = 1; i <= 2000000; ++i) + test.insert_or_assign(i*50,i); + + printf("manual ++iteration on 2000K sparse (holes of 50) (warmup 1): %lfs\n",tt); + + t = timer_Time(); + for (typename TestMap::iterator i = test.begin(); i != test.end(); ++i) + (*i).second = 3; + tt = timer_Time() - t; + printf("manual ++iteration on 2000K sparse (holes of 50) (warmup 2): %lfs\n",tt); + + t = timer_Time(); + for (typename TestMap::iterator i = test.begin(); i != test.end(); ++i) + (*i).second = 3; + tt = timer_Time() - t; + printf("manual ++iteration on 2000K sparse (holes of 50): %lfs\n",tt); + + t = timer_Time(); + for (typename TestMap::iterator i = test.begin(); i != test.end(); ++i) + (*i).second = 3; + tt = timer_Time() - t; + printf("manual iteration++ on 2000K sparse (holes of 50): %lfs\n",tt); + + test.clear(); + + for (int i = 1; i <= 100000; ++i) + test.insert_or_assign(i*500,i); + + t = timer_Time(); + for (int i = 0; i < 200000; ++i) + (*test.find((vec[i] % 100000 + 1)*500)).second = 3; + tt = timer_Time() - t; + printf("200K random lookups in random order (holes of 500): %lfs\n",tt); + + t = timer_Time(); + for (typename TestMap::iterator i = test.begin(); i != test.end(); ++i) + (*i).second = 3; + tt = timer_Time() - t; + printf("manual ++iteration on 100K sparse (holes of 500) (warmup 1): %lfs\n",tt); + + t = timer_Time(); + for (typename TestMap::iterator i = test.begin(); i != test.end(); ++i) + (*i).second = 3; + tt = timer_Time() - t; + printf("manual ++iteration on 100K sparse (holes of 500) (warmup 2): %lfs\n",tt); + + t = timer_Time(); + for (typename TestMap::iterator i = test.begin(); i != test.end(); ++i) + (*i).second = 3; + tt = timer_Time() - t; + printf("manual ++iteration on 100K sparse (holes of 500): %lfs\n",tt); + + t = timer_Time(); + for (typename TestMap::iterator i = test.begin(); i != test.end(); ++i) + (*i).second = 3; + tt = timer_Time() - t; + printf("manual ++iteration on 100K sparse (holes of 500): %lfs\n",tt); + } + + void test_sbo() + { + find(); + insert_or_assign(); + iterators(); + erase(); + clear(); + perf(); + } + + void test_large() + { + find(); + insert_or_assign(); + iterators(); + erase(); + clear(); + perf(); + } + + void test_no_secondary_ids() + { + find(); + insert_or_assign(); + iterators(); + erase(); + clear(); + perf(); + } +}; Index: source/tools/atlas/GameInterface/DeltaArray.h =================================================================== --- source/tools/atlas/GameInterface/DeltaArray.h +++ source/tools/atlas/GameInterface/DeltaArray.h @@ -18,6 +18,8 @@ #ifndef INCLUDED_DELTAARRAY #define INCLUDED_DELTAARRAY +#include + template class DeltaArray2D { public: