summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2018-03-14 20:44:01 -0400
committerDavid Robillard <d@drobilla.net>2018-03-14 20:44:01 -0400
commitbffcef562bfc7037470adc07f104524350021260 (patch)
tree3cbae413749ea1c03742fc583759023597d4d7e6
parentd35f222ac3ae5828f028b4158aaeb8017227f7ce (diff)
downloadingen-bffcef562bfc7037470adc07f104524350021260.tar.gz
ingen-bffcef562bfc7037470adc07f104524350021260.tar.bz2
ingen-bffcef562bfc7037470adc07f104524350021260.zip
Simplify depth-first search algorithm
-rw-r--r--src/server/CompiledGraph.cpp61
-rw-r--r--src/server/CompiledGraph.hpp2
2 files changed, 7 insertions, 56 deletions
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;