From 33ef45b6374a0ed26540b4b98f73d8cfecba3656 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Tue, 18 Mar 2025 13:21:10 +0200
Subject: [PATCH] Track individual dependencies in SystemScheduler

Arranging the systems in groups does not provide enough flexibility for
parallelizing the execution.
---
 source/game/stage.cpp           | 27 +-----------
 source/game/stage.h             |  2 -
 source/game/systemscheduler.cpp | 77 +++++++++++++++++++--------------
 source/game/systemscheduler.h   | 17 ++++----
 4 files changed, 54 insertions(+), 69 deletions(-)

diff --git a/source/game/stage.cpp b/source/game/stage.cpp
index 040f7ef..059b9ab 100644
--- a/source/game/stage.cpp
+++ b/source/game/stage.cpp
@@ -1,5 +1,4 @@
 #include "stage.h"
-#include <msp/debug/demangle.h>
 #include <msp/strings/format.h>
 #include "accessguard.h"
 #include "camera.h"
@@ -56,7 +55,6 @@ void Stage::remove_system(System &s)
 {
 	scheduler.remove_system(s);
 	erase_if(systems, [&s](auto &p){ return p.get()==&s; });
-	pending_reschedule = true;
 }
 
 void Stage::set_active_camera(Handle<Camera> c)
@@ -85,33 +83,10 @@ void Stage::synthesize_initial_events(Handle<Entity> entity, EventObserver &targ
 
 void Stage::tick(Time::TimeDelta dt)
 {
-	if(pending_reschedule)
-	{
-		scheduler.schedule();
-		pending_reschedule = false;
-	}
-
 	for(const auto &s: systems)
 		s->early_tick();
 
-	{
-#ifdef DEBUG
-		AccessGuard::BlockForScope _block;
-#endif
-		for(const SystemScheduler::Group &g: scheduler.get_groups())
-			for(System *s: g.systems)
-			{
-				System::Activator act(*s);
-				try
-				{
-					s->tick(dt);
-				}
-				catch(const invalid_access &exc)
-				{
-					throw invalid_access(format("%s by %s", exc.what(), Debug::demangle(typeid(*s).name())));
-				}
-			}
-	}
+	scheduler.run(dt);
 
 	for(const auto &s: systems)
 		s->deferred_tick();
diff --git a/source/game/stage.h b/source/game/stage.h
index b8020c9..8466a36 100644
--- a/source/game/stage.h
+++ b/source/game/stage.h
@@ -46,7 +46,6 @@ private:
 	std::vector<std::unique_ptr<System>> systems;
 	SystemScheduler scheduler;
 	Handle<Camera> active_camera;
-	bool pending_reschedule = false;
 
 public:
 	Stage(const std::string &, ThreadPool &, Reflection::Reflector &, DataFile::Collection &);
@@ -98,7 +97,6 @@ inline T &Stage::add_system(Args &&... args)
 	auto &sys = static_cast<T &>(*systems.emplace_back(std::make_unique<T>(*this, std::forward<Args>(args)...)));
 	reflector.get_or_create_class<T>().template set_polymorphic_base<System>(sys);
 	scheduler.add_system(sys);
-	pending_reschedule = true;
 	return sys;
 }
 
diff --git a/source/game/systemscheduler.cpp b/source/game/systemscheduler.cpp
index 1ad2ea5..7cad3e1 100644
--- a/source/game/systemscheduler.cpp
+++ b/source/game/systemscheduler.cpp
@@ -10,54 +10,32 @@ namespace Msp::Game {
 
 void SystemScheduler::add_system(System &s)
 {
+	if(nodes.size()>=MAX_SYSTEMS)
+		throw invalid_state("SystemScheduler::add_system");
 	nodes.emplace_back(&s, reflector.find_class(typeid(s)));
+	pending_reschedule = true;
 }
 
 void SystemScheduler::remove_system(System &s)
 {
 	erase_if(nodes, [&s](const GraphNode &n){ return n.system==&s; });
-	for(auto i=groups.begin(); i!=groups.end(); )
-	{
-		erase_if(i->systems, [&s](System *gs){ return gs==&s; });
-		if(i->systems.empty())
-			i = groups.erase(i);
-		else
-			++i;
-	}
+	pending_reschedule = true;
 }
 
 void SystemScheduler::schedule()
 {
 	for(GraphNode &n: nodes)
-	{
-		n.scheduled_order = ~0U;
-		n.predecessors.clear();
-	}
+		n.prerequisites = 0;
 
-	for(auto i=nodes.begin(); i!=nodes.end(); ++i)
-		for(auto j=i; ++j!=nodes.end(); )
+	for(size_t i=0; i+1<nodes.size(); ++i)
+		for(size_t j=i+1; j<nodes.size(); ++j)
 		{
-			int order = get_order(*i, *j);
+			int order = get_order(nodes[i], nodes[j]);
 			if(order<0)
-				j->predecessors.push_back(&*i);
+				nodes[j].prerequisites |= 1ULL<<i;
 			else if(order>0)
-				i->predecessors.push_back(&*j);
+				nodes[i].prerequisites |= 1ULL<<j;
 		}
-
-	groups.clear();
-	unsigned unscheduled_count = nodes.size();
-	while(unscheduled_count)
-	{
-		unsigned order = groups.size();
-		Group &group = groups.emplace_back();
-		for(GraphNode &n: nodes)
-			if(!~n.scheduled_order && ranges::all_of(n.predecessors, [order](GraphNode *p){ return p->scheduled_order<order; }))
-			{
-				group.systems.push_back(n.system);
-				n.scheduled_order = order;
-				--unscheduled_count;
-			}
-	}
 }
 
 int SystemScheduler::get_order(const GraphNode &node1, const GraphNode &node2)
@@ -147,4 +125,39 @@ int SystemScheduler::get_data_order(const GraphNode &node1, const GraphNode &nod
 	return data_order;
 }
 
+void SystemScheduler::run(Time::TimeDelta dt)
+{
+	if(nodes.empty())
+		return;
+
+	if(pending_reschedule)
+	{
+		schedule();
+		pending_reschedule = false;
+	}
+
+#ifdef DEBUG
+	AccessGuard::BlockForScope _block;
+#endif
+
+	uint64_t pending = (~0ULL)>>(MAX_SYSTEMS-nodes.size());
+	while(pending)
+	{
+		for(size_t i=0; i<nodes.size(); ++i)
+			if(!(pending&nodes[i].prerequisites))
+			{
+				System::Activator act(*nodes[i].system);
+				try
+				{
+					nodes[i].system->tick(dt);
+				}
+				catch(const invalid_access &exc)
+				{
+					throw invalid_access(format("%s by %s", exc.what(), nodes[i].type->get_name()));
+				}
+				pending &= ~(1ULL<<i);
+			}
+	}
+}
+
 } // namespace Msp::Game
diff --git a/source/game/systemscheduler.h b/source/game/systemscheduler.h
index 4bb11d1..94c2702 100644
--- a/source/game/systemscheduler.h
+++ b/source/game/systemscheduler.h
@@ -2,6 +2,7 @@
 #define MSP_GAME_SYSTEMSCHEDULER_H_
 
 #include <vector>
+#include <msp/time/timedelta.h>
 #include "mspgame_api.h"
 #include "reflection.h"
 
@@ -18,23 +19,20 @@ public:
 class MSPGAME_API SystemScheduler
 {
 public:
-	struct Group
-	{
-		std::vector<System *> systems;
-	};
+	using PrerequisiteMask = std::uint64_t;
+	static constexpr unsigned MAX_SYSTEMS = sizeof(PrerequisiteMask)*8;
 
-private:
 	struct GraphNode
 	{
 		System *system = nullptr;
 		Reflection::ClassBase *type = nullptr;
-		std::vector<GraphNode *> predecessors;
-		unsigned scheduled_order = 0;
+		PrerequisiteMask prerequisites = 0;
 	};
 
+private:
 	Reflection::Reflector &reflector;
 	std::vector<GraphNode> nodes;
-	std::vector<Group> groups;
+	bool pending_reschedule = false;
 
 public:
 	SystemScheduler(Reflection::Reflector &r): reflector(r) { }
@@ -46,8 +44,9 @@ private:
 	static int get_order(const GraphNode &, const GraphNode &);
 	static int get_explicit_order(const GraphNode &, const GraphNode &);
 	static int get_data_order(const GraphNode &, const GraphNode &);
+
 public:
-	const std::vector<Group> &get_groups() const { return groups; }
+	void run(Time::TimeDelta);
 };
 
 } // namespace Msp::Game
-- 
2.45.2