Index: binaries/data/config/default.cfg =================================================================== --- binaries/data/config/default.cfg +++ binaries/data/config/default.cfg @@ -439,6 +439,9 @@ enable = false deadzone = 8192 +[multithreading] +pathfinder = 0 ; How many threads to use for pathfinding. Special values: 0 chooses automatically, 1 de-activates threading entirely. + [chat] timestamp = true ; Show at which time chat messages have been sent Index: binaries/data/mods/public/gui/credits/texts/programming.json =================================================================== --- binaries/data/mods/public/gui/credits/texts/programming.json +++ binaries/data/mods/public/gui/credits/texts/programming.json @@ -141,6 +141,7 @@ { "nick": "kingadami", "name": "Adam Winsor" }, { "nick": "kingbasil", "name": "Giannis Fafalios" }, { "nick": "Krinkle", "name": "Timo Tijhof" }, + { "nick": "Kuba386", "name": "Jakub Kośmicki" }, { "nick": "lafferjm", "name": "Justin Lafferty" }, { "nick": "LeanderH", "name": "Leander Hemelhof" }, { "nick": "leper", "name": "Georg Kilzer" }, Index: binaries/data/mods/public/gui/options/options.json =================================================================== --- binaries/data/mods/public/gui/options/options.json +++ binaries/data/mods/public/gui/options/options.json @@ -84,6 +84,14 @@ "tooltip": "Show only generic names for units." } ] + }, + { + "type": "number", + "label": "Number of pathfinder threads", + "tooltip": "Number of pathfinder worker threads. Use 0 to choose automatically and 1 to disable threading altogether.", + "config": "multithreading.pathfinder", + "min": 0, + "max": 64 } ] }, Index: source/ps/ThreadFrontier.h =================================================================== --- /dev/null +++ source/ps/ThreadFrontier.h @@ -0,0 +1,73 @@ +/* Copyright (C) 2021 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_THREADFRONTIER +#define INCLUDED_THREADFRONTIER + +#include +#include + +/* + * A ThreadFrontier is similar to a Barrier in that it synchronizes n threads. + * A frontier has one thread waiting for n other threads to go through the Frontier. + */ +class ThreadFrontier +{ +public: + ThreadFrontier() : m_Expecting(0), m_Count(0) {}; + + void Setup(int expect) + { + ENSURE(m_Expecting == 0 && m_Count == 0); + std::lock_guard lock(m_Mutex); + m_Expecting = expect; + // The frontier is open, call Reset() to close it. + m_Count = m_Expecting; + } + + void Reset() + { + m_Count = 0; + } + + void Watch() + { + std::unique_lock lock(m_Mutex); + // If all threads have already gone through the frontier, we can stop watching right away. + if (m_Count == m_Expecting) + return; + m_ConditionVariable.wait(lock, [this] { return m_Count == m_Expecting; }); + } + + void GoThrough() + { + // Acquire the lock: we must be sure that the watching thread is either not yet in Watch() + // or is fully in the waiting state. Without this mutex lock, we could notify when the watching thread + // is in wait() but not yet in the waiting state, thus deadlocking. + std::lock_guard lock(m_Mutex); + // Notify the watching thread if we are the last to go through. + if (++m_Count == m_Expecting) + m_ConditionVariable.notify_one(); + } +private: + std::mutex m_Mutex; + std::condition_variable m_ConditionVariable; + int m_Expecting; + int m_Count; +}; + +#endif // INCLUDED_THREADFRONTIER Index: source/ps/ThreadUtil.h =================================================================== --- source/ps/ThreadUtil.h +++ source/ps/ThreadUtil.h @@ -38,6 +38,11 @@ */ void SetMainThread(); +/** + * Returns the number of threads we want for the pathfinder. + */ +u32 GetNumberOfPathfindingThreads(); + } #endif // INCLUDED_THREADUTIL Index: source/ps/Threading.cpp =================================================================== --- source/ps/Threading.cpp +++ source/ps/Threading.cpp @@ -19,6 +19,8 @@ #include "Threading.h" +#include "ps/ConfigDB.h" + #include static bool g_MainThreadSet; @@ -39,3 +41,19 @@ g_MainThread = std::this_thread::get_id(); g_MainThreadSet = true; } + + +u32 Threading::GetNumberOfPathfindingThreads() +{ + u32 wantedThreads = 0U; + + if (CConfigDB::IsInitialised()) + CFG_GET_VAL("multithreading.pathfinder", wantedThreads); + + // By default use (# of cores - 1) cores + if (wantedThreads == 0U) + return std::thread::hardware_concurrency() - 1U; + + // Keep in sync with options.json. + return std::min(wantedThreads, 64U); +} Index: source/simulation2/Simulation2.cpp =================================================================== --- source/simulation2/Simulation2.cpp +++ source/simulation2/Simulation2.cpp @@ -26,6 +26,7 @@ #include "simulation2/system/ComponentManager.h" #include "simulation2/system/ParamNode.h" #include "simulation2/system/SimContext.h" +#include "simulation2/system/SimSynchronization.h" #include "simulation2/components/ICmpAIManager.h" #include "simulation2/components/ICmpCommandQueue.h" #include "simulation2/components/ICmpTemplateManager.h" @@ -53,9 +54,9 @@ CSimulation2Impl(CUnitManager* unitManager, shared_ptr cx, CTerrain* terrain) : m_SimContext(), m_ComponentManager(m_SimContext, cx), m_EnableOOSLog(false), m_EnableSerializationTest(false), m_RejoinTestTurn(-1), m_TestingRejoin(false), - m_SecondaryTerrain(nullptr), m_SecondaryContext(nullptr), m_SecondaryComponentManager(nullptr), m_SecondaryLoadedScripts(nullptr), m_MapSettings(cx->GetGeneralJSContext()), m_InitAttributes(cx->GetGeneralJSContext()) { + m_SimContext.m_SynchronizationData = &m_SynchronizationData; m_SimContext.m_UnitManager = unitManager; m_SimContext.m_Terrain = terrain; m_ComponentManager.LoadComponentTypes(); @@ -81,11 +82,6 @@ ~CSimulation2Impl() { - delete m_SecondaryTerrain; - delete m_SecondaryContext; - delete m_SecondaryComponentManager; - delete m_SecondaryLoadedScripts; - UnregisterFileReloadFunc(ReloadChangedFileCB, this); } @@ -123,6 +119,7 @@ CSimContext m_SimContext; CComponentManager m_ComponentManager; + SSimSynchronization m_SynchronizationData; double m_DeltaTime; float m_LastFrameOffset; @@ -143,11 +140,12 @@ int m_RejoinTestTurn; bool m_TestingRejoin; - // Secondary simulation - CTerrain* m_SecondaryTerrain; - CSimContext* m_SecondaryContext; - CComponentManager* m_SecondaryComponentManager; - std::set* m_SecondaryLoadedScripts; + // Secondary simulation (NB: order matters for destruction). + std::unique_ptr m_SecondarySynchronizationData; + std::unique_ptr m_SecondaryComponentManager; + std::unique_ptr m_SecondaryTerrain; + std::unique_ptr m_SecondaryContext; + std::unique_ptr> m_SecondaryLoadedScripts; struct SerializationTestState { @@ -404,20 +402,18 @@ if (startRejoinTest) debug_printf("Initializing the secondary simulation\n"); - delete m_SecondaryTerrain; - m_SecondaryTerrain = new CTerrain(); + m_SecondaryTerrain = std::make_unique(); + m_SecondarySynchronizationData = std::make_unique(); - delete m_SecondaryContext; - m_SecondaryContext = new CSimContext(); - m_SecondaryContext->m_Terrain = m_SecondaryTerrain; + m_SecondaryContext = std::make_unique(); + m_SecondaryContext->m_Terrain = m_SecondaryTerrain.get(); + m_SecondaryContext->m_SynchronizationData = m_SecondarySynchronizationData.get(); - delete m_SecondaryComponentManager; - m_SecondaryComponentManager = new CComponentManager(*m_SecondaryContext, scriptInterface.GetContext()); + m_SecondaryComponentManager = std::make_unique(*m_SecondaryContext, scriptInterface.GetContext()); m_SecondaryComponentManager->LoadComponentTypes(); - delete m_SecondaryLoadedScripts; - m_SecondaryLoadedScripts = new std::set(); - ENSURE(LoadDefaultScripts(*m_SecondaryComponentManager, m_SecondaryLoadedScripts)); + m_SecondaryLoadedScripts = std::make_unique>(); + ENSURE(LoadDefaultScripts(*m_SecondaryComponentManager, m_SecondaryLoadedScripts.get())); ResetComponentState(*m_SecondaryComponentManager, false, false); // Load the trigger scripts after we have loaded the simulation. @@ -425,7 +421,7 @@ ScriptRequest rq2(m_SecondaryComponentManager->GetScriptInterface()); JS::RootedValue mapSettingsCloned(rq2.cx, m_SecondaryComponentManager->GetScriptInterface().CloneValueFromOtherCompartment(scriptInterface, m_MapSettings)); - ENSURE(LoadTriggerScripts(*m_SecondaryComponentManager, mapSettingsCloned, m_SecondaryLoadedScripts)); + ENSURE(LoadTriggerScripts(*m_SecondaryComponentManager, mapSettingsCloned, m_SecondaryLoadedScripts.get())); } // Load the map into the secondary simulation @@ -447,8 +443,8 @@ VfsPath mapfilename = VfsPath(mapFile).ChangeExtension(L".pmp"); mapReader->LoadMap(mapfilename, *scriptInterface.GetContext(), JS::UndefinedHandleValue, - m_SecondaryTerrain, NULL, NULL, NULL, NULL, NULL, NULL, - NULL, NULL, m_SecondaryContext, INVALID_PLAYER, true); // throws exception on failure + m_SecondaryTerrain.get(), NULL, NULL, NULL, NULL, NULL, NULL, + NULL, NULL, m_SecondaryContext.get(), INVALID_PLAYER, true); // throws exception on failure } LDR_EndRegistering(); @@ -896,6 +892,7 @@ bool CSimulation2::DeserializeState(std::istream& stream) { + m->m_SynchronizationData.Reset(); // TODO: need to make sure the required SYSTEM_ENTITY components get constructed return m->m_ComponentManager.DeserializeState(stream); } Index: source/simulation2/TypeList.h =================================================================== --- source/simulation2/TypeList.h +++ source/simulation2/TypeList.h @@ -124,6 +124,7 @@ INTERFACE(Obstruction) COMPONENT(Obstruction) +// Must come before Pathfinder. INTERFACE(ObstructionManager) COMPONENT(ObstructionManager) @@ -136,6 +137,7 @@ INTERFACE(ParticleManager) COMPONENT(ParticleManager) +// Must come after ObstructionManager. INTERFACE(Pathfinder) COMPONENT(Pathfinder) Index: source/simulation2/components/CCmpObstructionManager.cpp =================================================================== --- source/simulation2/components/CCmpObstructionManager.cpp +++ source/simulation2/components/CCmpObstructionManager.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2020 Wildfire Games. +/* Copyright (C) 2021 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -30,13 +30,14 @@ #include "simulation2/helpers/Render.h" #include "simulation2/helpers/Spatial.h" #include "simulation2/serialization/SerializedTypes.h" +#include "simulation2/system/SimSynchronization.h" #include "graphics/Overlay.h" #include "graphics/Terrain.h" #include "maths/MathUtil.h" #include "ps/Profile.h" -#include "renderer/Scene.h" #include "ps/CLogger.h" +#include "renderer/Scene.h" // Externally, tags are opaque non-zero positive integers. // Internally, they are tagged (by shape) indexes into shape lists. @@ -235,6 +236,8 @@ // So anything that happens here should be safely serialized. virtual void SetBounds(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1) { + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); + m_WorldX0 = x0; m_WorldZ0 = z0; m_WorldX1 = x1; @@ -259,6 +262,8 @@ void ResetSubdivisions(entity_pos_t x1, entity_pos_t z1) { + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); + // Use 8x8 tile subdivisions // (TODO: find the optimal number instead of blindly guessing) m_UnitSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE)); @@ -281,6 +286,8 @@ virtual tag_t AddUnitShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_pos_t clearance, flags_t flags, entity_id_t group) { + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); + UnitShape shape = { ent, x, z, clearance, flags, group }; u32 id = m_UnitShapeNext++; m_UnitShapes[id] = shape; @@ -294,6 +301,8 @@ virtual tag_t AddStaticShape(entity_id_t ent, entity_pos_t x, entity_pos_t z, entity_angle_t a, entity_pos_t w, entity_pos_t h, flags_t flags, entity_id_t group, entity_id_t group2 /* = INVALID_ENTITY */) { + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); + fixed s, c; sincos_approx(a, s, c); CFixedVector2D u(c, -s); @@ -333,6 +342,7 @@ virtual void MoveShape(tag_t tag, entity_pos_t x, entity_pos_t z, entity_angle_t a) { + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); ENSURE(TAG_IS_VALID(tag)); if (TAG_IS_UNIT(tag)) @@ -382,6 +392,7 @@ virtual void SetUnitMovingFlag(tag_t tag, bool moving) { + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag)); if (TAG_IS_UNIT(tag)) @@ -398,6 +409,7 @@ virtual void SetUnitControlGroup(tag_t tag, entity_id_t group) { + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); ENSURE(TAG_IS_VALID(tag) && TAG_IS_UNIT(tag)); if (TAG_IS_UNIT(tag)) @@ -409,6 +421,7 @@ virtual void SetStaticControlGroup(tag_t tag, entity_id_t group, entity_id_t group2) { + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); ENSURE(TAG_IS_VALID(tag) && TAG_IS_STATIC(tag)); if (TAG_IS_STATIC(tag)) @@ -421,6 +434,7 @@ virtual void RemoveShape(tag_t tag) { + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); ENSURE(TAG_IS_VALID(tag)); if (TAG_IS_UNIT(tag)) @@ -493,6 +507,8 @@ virtual void SetPassabilityCircular(bool enabled) { + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); + m_PassabilityCircular = enabled; MakeDirtyAll(); Index: source/simulation2/components/CCmpPathfinder.cpp =================================================================== --- source/simulation2/components/CCmpPathfinder.cpp +++ source/simulation2/components/CCmpPathfinder.cpp @@ -36,10 +36,12 @@ #include "simulation2/helpers/VertexPathfinder.h" #include "simulation2/serialization/SerializedPathfinder.h" #include "simulation2/serialization/SerializedTypes.h" +#include "simulation2/system/SimSynchronization.h" #include "ps/CLogger.h" #include "ps/CStr.h" #include "ps/Profile.h" +#include "ps/ThreadUtil.h" #include "ps/XML/Xeromyces.h" #include "renderer/Scene.h" @@ -70,21 +72,6 @@ CParamNode externalParamNode; CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder"); - // Previously all move commands during a turn were - // queued up and processed asynchronously at the start - // of the next turn. Now we are processing queued up - // events several times duing the turn. This improves - // responsiveness and units move more smoothly especially. - // when in formation. There is still a call at the - // beginning of a turn to process all outstanding moves - - // this will handle any moves above the MaxSameTurnMoves - // threshold. - // - // TODO - The moves processed at the beginning of the - // turn do not count against the maximum moves per turn - // currently. The thinking is that this will eventually - // happen in another thread. Either way this probably - // will require some adjustment and rethinking. const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder"); m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt(); @@ -99,13 +86,36 @@ m_PassClassMasks[name] = mask; } - m_Workers.emplace_back(PathfinderWorker{}); -} + u32 wantedThreads = Threading::GetNumberOfPathfindingThreads(); + + // The worker thread will only call std::thread if we actually have > 1 threads, otherwise we're running in the main thread. + if (wantedThreads <= 1) // <= 1 as the above computations returns 0 for one core. + { + m_UseThreading = false; + m_Workers.emplace_back(); + m_Workers.back().Start(*this, 0); + } + else + { + m_PathfinderFrontier.Setup(wantedThreads); + m_UseThreading = true; + // We cannot move workers or threads will run on deleted instances. + m_Workers.resize(wantedThreads); + for (size_t i = 0; i < wantedThreads; ++i) + m_Workers[i].Start(*this, i); + } +}; CCmpPathfinder::~CCmpPathfinder() {}; void CCmpPathfinder::Deinit() { + for (PathfinderWorker& worker : m_Workers) + worker.PrepareToKill(); + + GetSimContext().GetSynchronizationData().m_ComputingPaths = false; + + m_PathfinderConditionVariable.notify_all(); m_Workers.clear(); SetDebugOverlay(false); // cleans up memory @@ -217,6 +227,9 @@ void CCmpPathfinder::SetDebugOverlay(bool enabled) { + if (enabled && m_UseThreading) + LOGWARNING("Warning: the vertex pathfinder only shows immediate requests when using threading. " + "Configure pathfinder threads to 0 to see vertex pathfinder requests"); m_VertexPathfinder->SetDebugOverlay(enabled); m_LongPathfinder->SetDebugOverlay(enabled); } @@ -482,6 +495,8 @@ { PROFILE3("UpdateGrid"); + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); + CmpPtr cmpTerrain(GetSimContext(), SYSTEM_ENTITY); if (!cmpTerrain) return; // error @@ -736,7 +751,31 @@ // Async pathfinder workers -CCmpPathfinder::PathfinderWorker::PathfinderWorker() {} +CCmpPathfinder::PathfinderWorker::PathfinderWorker() : m_Computing(false), m_Kill(false) +{ +} + +CCmpPathfinder::PathfinderWorker::~PathfinderWorker() +{ + if (m_Thread.joinable()) + m_Thread.join(); +} + +void CCmpPathfinder::PathfinderWorker::Start(const CCmpPathfinder& pathfinder, size_t index) +{ + m_VertexPathfinder = std::make_unique(pathfinder.m_MapSize, pathfinder.m_TerrainOnlyGrid); + + if (pathfinder.m_UseThreading) + m_Thread = std::thread(&CCmpPathfinder::PathfinderWorker::InitThread, this, std::ref(pathfinder), index); +} + +void CCmpPathfinder::PathfinderWorker::InitThread(const CCmpPathfinder& pathfinder, size_t index) +{ + g_Profiler2.RegisterCurrentThread("Pathfinder thread " + std::to_string(index)); + debug_SetThreadName(("Pathfinder thread " + std::to_string(index)).c_str()); + + WaitForWork(pathfinder); +} template void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector&, ssize_t) @@ -754,9 +793,35 @@ m_ShortRequests.insert(m_ShortRequests.end(), std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end())); } +void CCmpPathfinder::PathfinderWorker::PrepareToKill() +{ + m_Kill = true; +} + +void CCmpPathfinder::PathfinderWorker::WaitForWork(const CCmpPathfinder& pathfinder) +{ + while (true) + { + { + std::unique_lock lock(pathfinder.m_PathfinderMutex); + pathfinder.m_PathfinderConditionVariable.wait(lock, [this] { return m_Computing || m_Kill; }); + } + + if (m_Kill) + return; + Work(pathfinder); + + // We must be the ones setting our m_Computing to false. + ENSURE(m_Computing); + m_Computing = false; + + pathfinder.m_PathfinderFrontier.GoThrough(); + } +} + void CCmpPathfinder::PathfinderWorker::Work(const CCmpPathfinder& pathfinder) { - while (!m_LongRequests.empty()) + while (!m_LongRequests.empty() && !m_Kill) { const LongPathRequest& req = m_LongRequests.back(); WaypointPath path; @@ -766,10 +831,10 @@ m_LongRequests.pop_back(); } - while (!m_ShortRequests.empty()) + while (!m_ShortRequests.empty() && !m_Kill) { const ShortPathRequest& req = m_ShortRequests.back(); - WaypointPath path = pathfinder.m_VertexPathfinder->ComputeShortPath(req, CmpPtr(pathfinder.GetSystemEntity())); + WaypointPath path = m_VertexPathfinder->ComputeShortPath(req, CmpPtr(pathfinder.GetSystemEntity())); m_Results.emplace_back(req.ticket, req.notify, path); m_ShortRequests.pop_back(); @@ -806,6 +871,12 @@ { PROFILE2("FetchAsyncResults"); + // TODO maybe: a possible improvement here would be to push results from workers whenever they are done, and not when all are done. + + // Wait until all threads have finished computing. + m_PathfinderFrontier.Watch(); + GetSimContext().GetSynchronizationData().m_ComputingPaths = false; + // We may now clear existing requests. m_ShortPathRequests.clear(); m_LongPathRequests.clear(); @@ -837,8 +908,24 @@ PushRequestsToWorkers(longRequests); PushRequestsToWorkers(shortRequests); + m_PathfinderFrontier.Reset(); + + ENSURE(!GetSimContext().GetSynchronizationData().m_ComputingPaths); + GetSimContext().GetSynchronizationData().m_ComputingPaths = true; + + if (!m_UseThreading) + { + m_Workers.back().Work(*this); + return; + } + for (PathfinderWorker& worker : m_Workers) - worker.Work(*this); + { + // Mark as computing to unblock. + ENSURE(!worker.m_Computing); + worker.m_Computing = true; + } + m_PathfinderConditionVariable.notify_all(); } template @@ -871,6 +958,10 @@ // In this instance, work is distributed in a strict LIFO order, effectively reversing tickets. for (PathfinderWorker& worker : m_Workers) { + // Prevent pushing requests when the worker is computing. + // Call FetchAsyncResultsAndSendMessages() before pushing new requests. + ENSURE(!worker.m_Computing); + amount = std::min(amount, from.size()); // Since we are rounding up before, ensure we aren't pushing beyond the end. worker.PushRequests(from, amount); from.erase(from.end() - amount, from.end()); Index: source/simulation2/components/CCmpPathfinder_Common.h =================================================================== --- source/simulation2/components/CCmpPathfinder_Common.h +++ source/simulation2/components/CCmpPathfinder_Common.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2020 Wildfire Games. +/* Copyright (C) 2021 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -35,10 +35,12 @@ #include "graphics/Terrain.h" #include "maths/MathUtil.h" #include "ps/CLogger.h" +#include "ps/ThreadFrontier.h" #include "renderer/TerrainOverlay.h" #include "simulation2/components/ICmpObstructionManager.h" #include "simulation2/helpers/Grid.h" +#include class HierarchicalPathfinder; class LongPathfinder; @@ -65,21 +67,63 @@ friend CCmpPathfinder; public: PathfinderWorker(); + /** + * Implement a noexcept move constructor for std::vector that actually does nothing. + */ + PathfinderWorker(PathfinderWorker&&) noexcept + { + ENSURE(!m_Thread.joinable()); + } - // Process path requests, checking if we should stop before each new one. + ~PathfinderWorker(); + + /** + * Create the std::thread and call InitThread + */ + void Start(const CCmpPathfinder& pathfinder, size_t index); + + void PrepareToKill(); + + /** + * Will loop until a condition_variable notifies us, and call Work(). + */ + void WaitForWork(const CCmpPathfinder& pathfinder); + + /** + * Process path requests, checking if we should stop before each new one. + * Should be callable both synchronously and asynchronously. + */ void Work(const CCmpPathfinder& pathfinder); private: - // Insert requests in m_[Long/Short]Requests depending on from. - // This could be removed when we may use if-constexpr in CCmpPathfinder::PushRequestsToWorkers + /** + * Takes care of what needs to be called to initialise the thread before calling WaitForWork(). + */ + void InitThread(const CCmpPathfinder& pathfinder, size_t index); + + /** + * Insert requests in m_[Long/Short]Requests depending on from. + * This could be removed when we may use if-constexpr in CCmpPathfinder::PushRequestsToWorkers + */ template void PushRequests(std::vector& from, ssize_t amount); // Stores our results, the main thread will fetch this. std::vector m_Results; + std::thread m_Thread; + + std::atomic m_Kill; + std::atomic m_Computing; + std::vector m_LongRequests; std::vector m_ShortRequests; + + // The vertex pathfinder has local caches that cannot be shared across threads + // Since it otherwise has no particular state, we can freely have one for each pathfinder worker. + // (this data could be thread_local, but the performance of that is terrible) + std::unique_ptr m_VertexPathfinder; + // The same is not true of the long-range pathfinder, which uses the grid, but has no particular thread-local state. }; // Allow the workers to access our private variables @@ -124,12 +168,17 @@ GridUpdateInformation m_AIPathfinderDirtinessInformation; bool m_TerrainDirty; + // If threading is used, this will only be used for synchronous calls. std::unique_ptr m_VertexPathfinder; std::unique_ptr m_PathfinderHier; std::unique_ptr m_LongPathfinder; // Workers process pathing requests. std::vector m_Workers; + bool m_UseThreading = false; + mutable std::mutex m_PathfinderMutex; + mutable std::condition_variable m_PathfinderConditionVariable; + mutable ThreadFrontier m_PathfinderFrontier; AtlasOverlay* m_AtlasOverlay; Index: source/simulation2/helpers/LongPathfinder.h =================================================================== --- source/simulation2/helpers/LongPathfinder.h +++ source/simulation2/helpers/LongPathfinder.h @@ -27,6 +27,7 @@ #include "simulation2/helpers/PriorityQueue.h" #include +#include /** * Represents the 2D coordinates of a tile. @@ -225,15 +226,14 @@ u16 m_GridSize; // Debugging - output from last pathfind operation. - // mutable as making these const would require a lot of boilerplate code - // and they do not change the behavioural const-ness of the pathfinder. - mutable LongOverlay* m_DebugOverlay; - mutable PathfindTileGrid* m_DebugGrid; - mutable u32 m_DebugSteps; - mutable double m_DebugTime; - mutable PathGoal m_DebugGoal; - mutable WaypointPath* m_DebugPath; - mutable pass_class_t m_DebugPassClass; + // Static and thread-local - we don't support threading debug code. + static thread_local LongOverlay* m_DebugOverlay; + static thread_local PathfindTileGrid* m_DebugGrid; + static thread_local u32 m_DebugSteps; + static thread_local double m_DebugTime; + static thread_local PathGoal m_DebugGoal; + static thread_local WaypointPath* m_DebugPath; + static thread_local pass_class_t m_DebugPassClass; private: PathCost CalculateHeuristic(int i, int j, int iGoal, int jGoal) const; @@ -273,11 +273,8 @@ void GenerateSpecialMap(pass_class_t passClass, std::vector excludedRegions); bool m_UseJPSCache; - // Mutable may be used here as caching does not change the external const-ness of the Long Range pathfinder. - // This is thread-safe as it is order independent (no change in the output of the function for a given set of params). - // Obviously, this means that the cache should actually be a cache and not return different results - // from what would happen if things hadn't been cached. - mutable std::map > m_JumpPointCache; + + static thread_local std::map > m_JumpPointCache; }; /** Index: source/simulation2/helpers/LongPathfinder.cpp =================================================================== --- source/simulation2/helpers/LongPathfinder.cpp +++ source/simulation2/helpers/LongPathfinder.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2019 Wildfire Games. +/* Copyright (C) 2021 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -25,6 +25,15 @@ #include "Geometry.h" #include "HierarchicalPathfinder.h" +thread_local LongOverlay* LongPathfinder::m_DebugOverlay; +thread_local PathfindTileGrid* LongPathfinder::m_DebugGrid; +thread_local u32 LongPathfinder::m_DebugSteps; +thread_local double LongPathfinder::m_DebugTime; +thread_local PathGoal LongPathfinder::m_DebugGoal; +thread_local WaypointPath* LongPathfinder::m_DebugPath; +thread_local pass_class_t LongPathfinder::m_DebugPassClass; +thread_local std::map > LongPathfinder::m_JumpPointCache; + /** * Jump point cache. * @@ -371,11 +380,11 @@ ////////////////////////////////////////////////////////// -LongPathfinder::LongPathfinder() : - m_UseJPSCache(false), - m_Grid(NULL), m_GridSize(0), - m_DebugOverlay(NULL), m_DebugGrid(NULL), m_DebugPath(NULL) +LongPathfinder::LongPathfinder() : m_UseJPSCache(false), m_Grid(nullptr), m_GridSize(0) { + m_DebugOverlay = nullptr; + m_DebugGrid = nullptr; + m_DebugPath = nullptr; } LongPathfinder::~LongPathfinder() Index: source/simulation2/system/ComponentManager.cpp =================================================================== --- source/simulation2/system/ComponentManager.cpp +++ source/simulation2/system/ComponentManager.cpp @@ -459,9 +459,9 @@ m_DynamicMessageSubscriptionsNonsync.clear(); m_DynamicMessageSubscriptionsNonsyncByComponent.clear(); - // Delete all IComponents - std::map >::iterator iit = m_ComponentsByTypeId.begin(); - for (; iit != m_ComponentsByTypeId.end(); ++iit) + // Delete all IComponents in reverse order of creation. + std::map >::reverse_iterator iit = m_ComponentsByTypeId.rbegin(); + for (; iit != m_ComponentsByTypeId.rend(); ++iit) { std::map::iterator eit = iit->second.begin(); for (; eit != iit->second.end(); ++eit) Index: source/simulation2/system/ComponentTest.h =================================================================== --- source/simulation2/system/ComponentTest.h +++ source/simulation2/system/ComponentTest.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2019 Wildfire Games. +/* Copyright (C) 2021 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -29,6 +29,7 @@ #include "simulation2/serialization/HashSerializer.h" #include "simulation2/serialization/StdSerializer.h" #include "simulation2/serialization/StdDeserializer.h" +#include "simulation2/system/SimSynchronization.h" #include @@ -50,6 +51,7 @@ CSimContext m_Context; CComponentManager m_ComponentManager; CParamNode m_Param; + SSimSynchronization m_SynchronizationData; IComponent* m_Cmp; EComponentTypeId m_Cid; bool m_isSystemEntityInit = false; @@ -58,6 +60,7 @@ ComponentTestHelper(shared_ptr scriptContext) : m_Context(), m_ComponentManager(m_Context, scriptContext), m_Cmp(NULL) { + m_Context.m_SynchronizationData = &m_SynchronizationData; m_ComponentManager.LoadComponentTypes(); } Index: source/simulation2/system/ReplayTurnManager.cpp =================================================================== --- source/simulation2/system/ReplayTurnManager.cpp +++ source/simulation2/system/ReplayTurnManager.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2020 Wildfire Games. +/* Copyright (C) 2021 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -121,5 +121,8 @@ } if (turn == m_FinalTurn) + { g_GUI->SendEventToAll(EventNameReplayFinished); + g_Profiler2.SaveToFile(); + } } Index: source/simulation2/system/SimContext.h =================================================================== --- source/simulation2/system/SimContext.h +++ source/simulation2/system/SimContext.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2016 Wildfire Games. +/* Copyright (C) 2021 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -21,9 +21,11 @@ #include "Entity.h" class CComponentManager; +class ComponentTestHelper; class CUnitManager; class CTerrain; class ScriptInterface; +struct SSimSynchronization; /** * Contains pointers to various 'global' objects that are needed by the simulation code, @@ -45,6 +47,8 @@ ScriptInterface& GetScriptInterface() const; + SSimSynchronization& GetSynchronizationData() const; + void SetSystemEntity(CEntityHandle ent) { m_SystemEntity = ent; } CEntityHandle GetSystemEntity() const { ASSERT(m_SystemEntity.GetId() == SYSTEM_ENTITY); return m_SystemEntity; } @@ -55,13 +59,15 @@ int GetCurrentDisplayedPlayer() const; private: - CComponentManager* m_ComponentManager; - CUnitManager* m_UnitManager; - CTerrain* m_Terrain; + CComponentManager* m_ComponentManager = nullptr; + CUnitManager* m_UnitManager = nullptr; + CTerrain* m_Terrain = nullptr; + SSimSynchronization* m_SynchronizationData = nullptr; CEntityHandle m_SystemEntity; friend class CSimulation2Impl; + friend class ComponentTestHelper; }; #endif // INCLUDED_SIMCONTEXT Index: source/simulation2/system/SimContext.cpp =================================================================== --- source/simulation2/system/SimContext.cpp +++ source/simulation2/system/SimContext.cpp @@ -1,4 +1,4 @@ -/* Copyright (C) 2016 Wildfire Games. +/* Copyright (C) 2021 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -23,8 +23,7 @@ #include "ps/Game.h" -CSimContext::CSimContext() : - m_ComponentManager(NULL), m_UnitManager(NULL), m_Terrain(NULL) +CSimContext::CSimContext() { } @@ -65,6 +64,11 @@ return GetComponentManager().GetScriptInterface(); } +SSimSynchronization& CSimContext::GetSynchronizationData() const +{ + return *m_SynchronizationData; +} + int CSimContext::GetCurrentDisplayedPlayer() const { return g_Game ? g_Game->GetViewedPlayerID() : -1; Index: source/simulation2/system/SimSynchronization.h =================================================================== --- /dev/null +++ source/simulation2/system/SimSynchronization.h @@ -0,0 +1,49 @@ +/* Copyright (C) 2021 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_SIM_SYNCHRONIZATION +#define INCLUDED_SIM_SYNCHRONIZATION + +/** + * Some simulation operations are threaded. + * To avoid logical errors, this holds the status of all relevant operations, + * so that components can ENSURE() they're only doing operations in the correct state(s). + * This is intended to reveal programming errors, not to actually be a synchronization mechanism. + * + * Though data in this class is really intended to be written to from the main thread, + * variables are atomic to ensure that operations are not reordered in a confusing way. + */ +struct SSimSynchronization +{ + NONCOPYABLE(SSimSynchronization); + + SSimSynchronization() : m_ComputingPaths(false) {}; + + void Reset() { + m_ComputingPaths = false; + } + + /** + * When this is true, the pathfinders are computing paths. In practice: + * - Nothing can change the pathfinder grid. + * - Nothing can change obstruction state (neither the obstructions nor the manager's). + * This means no entities can be moved, killed, created, etc. + */ + std::atomic m_ComputingPaths; +}; + +#endif // INCLUDED_SIM_SYNCHRONIZATION