Changeset 25256

Timestamp:
Apr 14, 2021, 9:23:47 AM (3 years ago)
Author:
wraitii
Message:

Rework the pathfinder path computation setup for threading.

Essentially reverts D1918 / rP22902.
Instead of copying path requests to workers, setup the result vector, then setup an index, and compute 'in-place'.
To send messages, the result vectors are read in order. This makes the order trivially constant no matter how many workers there are, and the architecture overall makes it much easier to efficiently paralellise.

Tested by: Langbart, Stan

Differential Revision: ​https://code.wildfiregames.com/D3849

Location:
ps/trunk/source/simulation2
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • ps/trunk/source/simulation2/Simulation2.cpp

    r25250 r25256  
    521521    CmpPtr<ICmpPathfinder> cmpPathfinder(simContext, SYSTEM_ENTITY);
    522522    if (cmpPathfinder)
    523         cmpPathfinder->FetchAsyncResultsAndSendMessages();
     523        cmpPathfinder->s();
    524524
    525525    {
    … …  
    542542    {
    543543        cmpPathfinder->StartProcessingMoves(true);
    544         cmpPathfinder->FetchAsyncResultsAndSendMessages();
     544        cmpPathfinder->s();
    545545    }
    546546    // Send all the update phases
    … …  
    560560    {
    561561        cmpPathfinder->StartProcessingMoves(true);
    562         cmpPathfinder->FetchAsyncResultsAndSendMessages();
     562        cmpPathfinder->s();
    563563    }
    564564

  • ps/trunk/source/simulation2/components/CCmpPathfinder.cpp

    r24915 r25256  
    4444#include "renderer/Scene.h"
    4545
     46
     47
    4648REGISTER_COMPONENT_TYPE(Pathfinder)
    4749
    … …  
    7173    CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder");
    7274
    73     // Previously all move commands during a turn were
    74     // queued up and processed asynchronously at the start
    75     // of the next turn.  Now we are processing queued up
    76     // events several times duing the turn.  This improves
    77     // responsiveness and units move more smoothly especially.
    78     // when in formation.  There is still a call at the
    79     // beginning of a turn to process all outstanding moves -
    80     // this will handle any moves above the MaxSameTurnMoves
    81     // threshold.
    82     //
    83     // TODO - The moves processed at the beginning of the
    84     // turn do not count against the maximum moves per turn
    85     // currently.  The thinking is that this will eventually
    86     // happen in another thread.  Either way this probably
    87     // will require some adjustment and rethinking.
     75    // Paths are computed:
     76    //  - Before MT_Update
     77    //  - Before MT_MotionUnitFormation
     78    //  - 'in-between' turns (effectively at the start until threading is implemented).
     79    // The latter of these must compute all outstanding requests, but the former two are capped
     80    // to avoid spending too much time there (since the latter are designed to be threaded and thus not block the GUI).
     81    // This loads that maximum number (note that it's per computation call, not per turn for now).
    8882    const CParamNode pathingSettings = externalParamNode.GetChild("Pathfinder");
    8983    m_MaxSameTurnMoves = (u16)pathingSettings.GetChild("MaxSameTurnMoves").ToInt();
    … …  
    9993        m_PassClassMasks[name] = mask;
    10094    }
    101 
    102     m_Workers.emplace_back(PathfinderWorker{});
    10395}
    10496
    … …  
    10799void CCmpPathfinder::Deinit()
    108100{
    109     m_Workers.clear();
    110 
    111101    SetDebugOverlay(false); // cleans up memory
    112102    SAFE_DELETE(m_AtlasOverlay);
    … …  
    153143void CCmpPathfinder::SerializeCommon(S& serialize)
    154144{
    155     Serializer(serialize, "long requests", m_LongPathRequests);
    156     Serializer(serialize, "short requests", m_ShortPathRequests);
     145    Serializer(serialize, "long requests", m_LongPathRequests);
     146    Serializer(serialize, "short requests", m_ShortPathRequests);
    157147    serialize.NumberU32_Unbounded("next ticket", m_NextAsyncTicket);
    158148    serialize.NumberU16_Unbounded("map size", m_MapSize);
    … …  
    196186        UpdateGrid();
    197187        // In case we were serialised with requests pending, we need to process them.
    198         if (!m_ShortPathRequests.empty() || !m_LongPathRequests.empty())
     188        if (!m_ShortPathRequests.Requests.empty())
    199189        {
    200190            ENSURE(CmpPtr<ICmpObstructionManager>(GetSystemEntity()));
    … …  
    735725//////////////////////////////////////////////////////////
    736726
    737 // Async pathfinder workers
    738 
    739 CCmpPathfinder::PathfinderWorker::PathfinderWorker() {}
    740 
    741 template<typename T>
    742 void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector<T>&, ssize_t)
    743 {
    744     static_assert(sizeof(T) == 0, "Only specializations can be used");
    745 }
    746 
    747 template<> void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector<LongPathRequest>& from, ssize_t amount)
    748 {
    749     m_LongRequests.insert(m_LongRequests.end(), std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end()));
    750 }
    751 
    752 template<> void CCmpPathfinder::PathfinderWorker::PushRequests(std::vector<ShortPathRequest>& from, ssize_t amount)
    753 {
    754     m_ShortRequests.insert(m_ShortRequests.end(), std::make_move_iterator(from.end() - amount), std::make_move_iterator(from.end()));
    755 }
    756 
    757 void CCmpPathfinder::PathfinderWorker::Work(const CCmpPathfinder& pathfinder)
    758 {
    759     while (!m_LongRequests.empty())
    760     {
    761         const LongPathRequest& req = m_LongRequests.back();
    762         WaypointPath path;
    763         pathfinder.m_LongPathfinder->ComputePath(*pathfinder.m_PathfinderHier, req.x0, req.z0, req.goal, req.passClass, path);
    764         m_Results.emplace_back(req.ticket, req.notify, path);
    765 
    766         m_LongRequests.pop_back();
    767     }
    768 
    769     while (!m_ShortRequests.empty())
    770     {
    771         const ShortPathRequest& req = m_ShortRequests.back();
    772         WaypointPath path = pathfinder.m_VertexPathfinder->ComputeShortPath(req, CmpPtr<ICmpObstructionManager>(pathfinder.GetSystemEntity()));
    773         m_Results.emplace_back(req.ticket, req.notify, path);
    774 
    775         m_ShortRequests.pop_back();
    776     }
    777 }
    778 
    779727u32 CCmpPathfinder::ComputePathAsync(entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass, entity_id_t notify)
    780728{
    781729    LongPathRequest req = { m_NextAsyncTicket++, x0, z0, goal, passClass, notify };
    782     m_LongPathRequests.push_back(req);
     730    m_LongPathRequests.push_back(req);
    783731    return req.ticket;
    784732}
    … …  
    789737{
    790738    ShortPathRequest req = { m_NextAsyncTicket++, x0, z0, clearance, range, goal, passClass, avoidMovingUnits, group, notify };
    791     m_ShortPathRequests.push_back(req);
     739    m_ShortPathRequests.push_back(req);
    792740    return req.ticket;
    793741}
    … …  
    803751}
    804752
    805 void CCmpPathfinder::FetchAsyncResultsAndSendMessages()
    806 {
    807     PROFILE2("FetchAsyncResults");
    808 
    809     // We may now clear existing requests.
    810     m_ShortPathRequests.clear();
    811     m_LongPathRequests.clear();
    812 
    813     // WARNING: the order in which moves are pulled must be consistent when using 1 or n workers.
    814     // We fetch in the same order we inserted in, but we push moves backwards, so this works.
    815     std::vector<PathResult> results;
    816     for (PathfinderWorker& worker : m_Workers)
    817     {
    818         results.insert(results.end(), std::make_move_iterator(worker.m_Results.begin()), std::make_move_iterator(worker.m_Results.end()));
    819         worker.m_Results.clear();
     753template<typename T>
     754template<typename U>
     755void CCmpPathfinder::PathRequests<T>::Compute(const CCmpPathfinder& cmpPathfinder, const U& pathfinder)
     756{
     757    static_assert((std::is_same_v<T, LongPathRequest> && std::is_same_v<U, LongPathfinder>) ||
     758                  (std::is_same_v<T, ShortPathRequest> && std::is_same_v<U, VertexPathfinder>));
     759    size_t maxN = m_Results.size();
     760    size_t startIndex = m_Requests.size() - m_Results.size();
     761    do
     762    {
     763        size_t workIndex = m_NextPathToCompute++;
     764        if (workIndex >= maxN)
     765            break;
     766        const T& req = m_Requests[startIndex + workIndex];
     767        PathResult& result = m_Results[workIndex];
     768        result.ticket = req.ticket;
     769        result.notify = req.notify;
     770        if constexpr (std::is_same_v<T, LongPathRequest>)
     771            pathfinder.ComputePath(*cmpPathfinder.m_PathfinderHier, req.x0, req.z0, req.goal, req.passClass, result.path);
     772        else
     773            result.path = pathfinder.ComputeShortPath(req, CmpPtr<ICmpObstructionManager>(cmpPathfinder.GetSystemEntity()));
     774        if (workIndex == maxN - 1)
     775            m_ComputeDone = true;
     776    }
     777    while (true);
     778}
     779
     780void CCmpPathfinder::SendRequestedPaths()
     781{
     782    PROFILE2("SendRequestedPaths");
     783
     784    if (!m_LongPathRequests.m_ComputeDone || !m_ShortPathRequests.m_ComputeDone)
     785    {
     786        m_ShortPathRequests.Compute(*this, *m_VertexPathfinder);
     787        m_LongPathRequests.Compute(*this, *m_LongPathfinder);
    820788    }
    821789
    822790    {
    823791        PROFILE2("PostMessages");
    824         for (PathResult& path : results)
     792        for (PathResult& path : esults)
    825793        {
    826794            CMessagePathResult msg(path.ticket, path.path);
    827795            GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
    828796        }
    829     }
     797
     798        for (PathResult& path : m_LongPathRequests.m_Results)
     799        {
     800            CMessagePathResult msg(path.ticket, path.path);
     801            GetSimContext().GetComponentManager().PostMessage(path.notify, msg);
     802        }
     803    }
     804    m_ShortPathRequests.ClearComputed();
     805    m_LongPathRequests.ClearComputed();
    830806}
    831807
    832808void CCmpPathfinder::StartProcessingMoves(bool useMax)
    833809{
    834     std::vector<LongPathRequest> longRequests = GetMovesToProcess(m_LongPathRequests, useMax, m_MaxSameTurnMoves);
    835     std::vector<ShortPathRequest> shortRequests = GetMovesToProcess(m_ShortPathRequests, useMax, m_MaxSameTurnMoves - longRequests.size());
    836 
    837     PushRequestsToWorkers(longRequests);
    838     PushRequestsToWorkers(shortRequests);
    839 
    840     for (PathfinderWorker& worker : m_Workers)
    841         worker.Work(*this);
    842 }
    843 
    844 template <typename T>
    845 std::vector<T> CCmpPathfinder::GetMovesToProcess(std::vector<T>& requests, bool useMax, size_t maxMoves)
    846 {
    847     // Keep the original requests in which we need to serialize.
    848     std::vector<T> copiedRequests;
    849     if (useMax)
    850     {
    851         size_t amount = std::min(requests.size(), maxMoves);
    852         if (amount > 0)
    853             copiedRequests.insert(copiedRequests.begin(), requests.end() - amount, requests.end());
    854     }
    855     else
    856         copiedRequests = requests;
    857 
    858     return copiedRequests;
    859 }
    860 
    861 template <typename T>
    862 void CCmpPathfinder::PushRequestsToWorkers(std::vector<T>& from)
    863 {
    864     if (from.empty())
    865         return;
    866 
    867     // Trivial load-balancing, / rounds towards zero so add 1 to ensure we do push all requests.
    868     size_t amount = from.size() / m_Workers.size() + 1;
    869 
    870     // WARNING: the order in which moves are pushed must be consistent when using 1 or n workers.
    871     // In this instance, work is distributed in a strict LIFO order, effectively reversing tickets.
    872     for (PathfinderWorker& worker : m_Workers)
    873     {
    874         amount = std::min(amount, from.size()); // Since we are rounding up before, ensure we aren't pushing beyond the end.
    875         worker.PushRequests(from, amount);
    876         from.erase(from.end() - amount, from.end());
    877     }
     810    m_ShortPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0);
     811    m_LongPathRequests.PrepareForComputation(useMax ? m_MaxSameTurnMoves : 0);
    878812}
    879813

  • ps/trunk/source/simulation2/components/CCmpPathfinder_Common.h

    r24142 r25256  
    1 /* Copyright (C) 2020 Wildfire Games.
     1/* Copyright (C) 202 Wildfire Games.
    22 * This file is part of 0 A.D.
    33 *
    … …  
    4040#include "simulation2/helpers/Grid.h"
    4141
     42
    4243
    4344class HierarchicalPathfinder;
    … …  
    5960class CCmpPathfinder final : public ICmpPathfinder
    6061{
    61 protected:
    62 
    63     class PathfinderWorker
    64     {
    65         friend CCmpPathfinder;
    66     public:
    67         PathfinderWorker();
    68 
    69         // Process path requests, checking if we should stop before each new one.
    70         void Work(const CCmpPathfinder& pathfinder);
    71 
    72     private:
    73         // Insert requests in m_[Long/Short]Requests depending on from.
    74         // This could be removed when we may use if-constexpr in CCmpPathfinder::PushRequestsToWorkers
    75         template<typename T>
    76         void PushRequests(std::vector<T>& from, ssize_t amount);
    77 
    78         // Stores our results, the main thread will fetch this.
    79         std::vector<PathResult> m_Results;
    80 
    81         std::vector<LongPathRequest> m_LongRequests;
    82         std::vector<ShortPathRequest> m_ShortRequests;
    83     };
    84 
    85     // Allow the workers to access our private variables
    86     friend class PathfinderWorker;
    87 
    8862public:
    8963    static void ClassInit(CComponentManager& componentManager)
    … …  
    10478    std::map<std::string, pass_class_t> m_PassClassMasks;
    10579    std::vector<PathfinderPassability> m_PassClasses;
     80
    10681
    10782    // Dynamic state:
    108 
    109     std::vector<LongPathRequest> m_LongPathRequests;
    110     std::vector<ShortPathRequest> m_ShortPathRequests;
    111     u32 m_NextAsyncTicket; // Unique IDs for asynchronous path requests.
    112     u16 m_MaxSameTurnMoves; // Compute only this many paths when useMax is true in StartProcessingMoves.
    11383
    11484    // Lazily-constructed dynamic state (not serialized):
    … …  
    12999    std::unique_ptr<LongPathfinder> m_LongPathfinder;
    130100
    131     // Workers process pathing requests.
    132     std::vector<PathfinderWorker> m_Workers;
     101    template<typename T>
     102    class PathRequests {
     103    public:
     104        std::vector<T> m_Requests;
     105        std::vector<PathResult> m_Results;
     106        // This is the array index of the next path to compute.
     107        size_t m_NextPathToCompute = 0;
     108        // This is false until all scheduled paths have been computed.
     109        bool m_ComputeDone = true;
     110
     111        void ClearComputed()
     112        {
     113            if (m_Results.size() == m_Requests.size())
     114                m_Requests.clear();
     115            else
     116                m_Requests.erase(m_Requests.end() - m_Results.size(), m_Requests.end());
     117            m_Results.clear();
     118        }
     119
     120        /**
     121         * @param max - if non-zero, how many paths to process.
     122         */
     123        void PrepareForComputation(u16 max)
     124        {
     125            size_t n = m_Requests.size();
     126            if (max && n > max)
     127                n = max;
     128            m_NextPathToCompute = 0;
     129            m_Results.resize(n);
     130            m_ComputeDone = n == 0;
     131        }
     132
     133        template<typename U>
     134        void Compute(const CCmpPathfinder& cmpPathfinder, const U& pathfinder);
     135    };
     136    PathRequests<LongPathRequest> m_LongPathRequests;
     137    PathRequests<ShortPathRequest> m_ShortPathRequests;
     138
     139    u32 m_NextAsyncTicket; // Unique IDs for asynchronous path requests.
    133140
    134141    AtlasOverlay* m_AtlasOverlay;
    … …  
    223230    virtual ICmpObstruction::EFoundationCheck CheckBuildingPlacement(const IObstructionTestFilter& filter, entity_pos_t x, entity_pos_t z, entity_pos_t a, entity_pos_t w, entity_pos_t h, entity_id_t id, pass_class_t passClass, bool onlyCenterPoint) const;
    224231
    225     virtual void FetchAsyncResultsAndSendMessages();
     232    virtual void s();
    226233
    227234    virtual void StartProcessingMoves(bool useMax);

  • ps/trunk/source/simulation2/components/ICmpPathfinder.h

    r25004 r25256  
    186186     * Finish computing asynchronous path requests and send the CMessagePathResult messages.
    187187     */
    188     virtual void FetchAsyncResultsAndSendMessages() = 0;
     188    virtual void s() = 0;
    189189
    190190    /**
Note: See TracChangeset for help on using the changeset viewer.