From bffcef562bfc7037470adc07f104524350021260 Mon Sep 17 00:00:00 2001
From: David Robillard <d@drobilla.net>
Date: Wed, 14 Mar 2018 20:44:01 -0400
Subject: Simplify depth-first search algorithm

---
 src/server/CompiledGraph.cpp | 61 +++++---------------------------------------
 src/server/CompiledGraph.hpp |  2 --
 2 files changed, 7 insertions(+), 56 deletions(-)

(limited to 'src/server')

diff --git a/src/server/CompiledGraph.cpp b/src/server/CompiledGraph.cpp
index c2160c75..8b996c10 100644
--- a/src/server/CompiledGraph.cpp
+++ b/src/server/CompiledGraph.cpp
@@ -41,18 +41,6 @@ public:
 	const BlockImpl* root;
 };
 
-static bool
-has_provider_with_many_dependants(BlockImpl* n)
-{
-	for (BlockImpl* p : n->providers()) {
-		if (p->dependants().size() > 1) {
-			return true;
-		}
-	}
-
-	return false;
-}
-
 CompiledGraph::CompiledGraph(GraphImpl* graph)
 	: _master(std::unique_ptr<Task>(new Task(Task::Mode::SEQUENTIAL)))
 {
@@ -89,21 +77,6 @@ num_unvisited_dependants(BlockImpl* block)
 	return count;
 }
 
-static size_t
-parallel_depth(BlockImpl* block)
-{
-	if (has_provider_with_many_dependants(block)) {
-		return 2;
-	}
-
-	size_t min_provider_depth = std::numeric_limits<size_t>::max();
-	for (auto p : block->providers()) {
-		min_provider_depth = std::min(min_provider_depth, parallel_depth(p));
-	}
-
-	return 2 + min_provider_depth;
-}
-
 void
 CompiledGraph::compile_graph(GraphImpl* graph)
 {
@@ -125,17 +98,11 @@ CompiledGraph::compile_graph(GraphImpl* graph)
 	while (!blocks.empty()) {
 		std::set<BlockImpl*> predecessors;
 
-		// Calculate maximum sequential depth to consume this phase
-		size_t depth = std::numeric_limits<size_t>::max();
-		for (auto i : blocks) {
-			depth = std::min(depth, parallel_depth(i));
-		}
-
 		Task par(Task::Mode::PARALLEL);
 		for (auto b : blocks) {
 			assert(num_unvisited_dependants(b) == 0);
 			Task seq(Task::Mode::SEQUENTIAL);
-			compile_block(b, seq, depth, predecessors);
+			compile_block(b, seq, predecessors);
 			par.push_front(std::move(seq));
 		}
 		_master->push_front(std::move(par));
@@ -178,7 +145,6 @@ void
 CompiledGraph::compile_provider(const BlockImpl*      root,
                                 BlockImpl*            block,
                                 Task&                 task,
-                                size_t                max_depth,
                                 std::set<BlockImpl*>& k)
 {
 	if (block->dependants().size() > 1) {
@@ -188,20 +154,16 @@ CompiledGraph::compile_provider(const BlockImpl*      root,
 		if (num_unvisited_dependants(block) == 0) {
 			k.insert(block);
 		}
-	} else if (max_depth > 0) {
+	} else {
 		// Calling dependant has only this provider, add here
 		if (task.mode() == Task::Mode::PARALLEL) {
 			// Inside a parallel task, compile into a new sequential child
 			Task seq(Task::Mode::SEQUENTIAL);
-			compile_block(block, seq, max_depth, k);
+			compile_block(block, seq, k);
 			task.push_front(std::move(seq));
 		} else {
 			// Prepend to given sequential task
-			compile_block(block, task, max_depth, k);
-		}
-	} else {
-		if (num_unvisited_dependants(block) == 0) {
-			k.insert(block);
+			compile_block(block, task, k);
 		}
 	}
 }
@@ -209,7 +171,6 @@ CompiledGraph::compile_provider(const BlockImpl*      root,
 void
 CompiledGraph::compile_block(BlockImpl*            n,
                              Task&                 task,
-                             size_t                max_depth,
                              std::set<BlockImpl*>& k)
 {
 	switch (n->get_mark()) {
@@ -219,26 +180,18 @@ CompiledGraph::compile_block(BlockImpl*            n,
 		// Execute this task after the providers to follow
 		task.push_front(Task(Task::Mode::SINGLE, n));
 
-		if (n->providers().size() < 2) {
+		if (n->providers().size() <= 1) {
 			// Single provider, prepend it to this sequential task
 			for (auto p : n->providers()) {
-				compile_provider(n, p, task, max_depth - 1, k);
+				compile_provider(n, p, task, k);
 			}
-		} else if (has_provider_with_many_dependants(n)) {
+		} else {
 			// Stop recursion and enqueue providers for the next round
 			for (auto p : n->providers()) {
 				if (num_unvisited_dependants(p) == 0) {
 					k.insert(p);
 				}
 			}
-		} else {
-			// Multiple providers with only this node as dependant,
-			// make a new parallel task to execute them
-			Task par(Task::Mode::PARALLEL);
-			for (auto p : n->providers()) {
-				compile_provider(n, p, par, max_depth - 1, k);
-			}
-			task.push_front(std::move(par));
 		}
 		n->set_mark(BlockImpl::Mark::VISITED);
 		break;
diff --git a/src/server/CompiledGraph.hpp b/src/server/CompiledGraph.hpp
index 6b802611..9f4de68c 100644
--- a/src/server/CompiledGraph.hpp
+++ b/src/server/CompiledGraph.hpp
@@ -61,13 +61,11 @@ private:
 
 	void compile_block(BlockImpl* n,
 	                   Task&      task,
-	                   size_t     max_depth,
 	                   BlockSet&  k);
 
 	void compile_provider(const BlockImpl* root,
 	                      BlockImpl*       block,
 	                      Task&            task,
-	                      size_t           max_depth,
 	                      BlockSet&        k);
 
 	std::unique_ptr<Task> _master;
-- 
cgit v1.2.1