From e2f6b686003f86af8a64e7c6f7e8cf8c2da7ba69 Mon Sep 17 00:00:00 2001 From: drd Date: Thu, 16 Feb 2017 17:28:54 +0100 Subject: Preliminary alternative parallel traversal/benchmarking work --- src/server/CompiledGraph.cpp | 84 +++++++++++++++++++------------------------- 1 file changed, 36 insertions(+), 48 deletions(-) (limited to 'src/server/CompiledGraph.cpp') diff --git a/src/server/CompiledGraph.cpp b/src/server/CompiledGraph.cpp index b808cb90..5553140c 100644 --- a/src/server/CompiledGraph.cpp +++ b/src/server/CompiledGraph.cpp @@ -1,6 +1,6 @@ /* This file is part of Ingen. - Copyright 2015-2016 David Robillard + Copyright 2015-2017 David Robillard Ingen is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free @@ -43,7 +43,7 @@ public: CompiledGraph::CompiledGraph(GraphImpl* graph) : _log(graph->engine().log()) , _path(graph->path()) - , _master(Task::Mode::SEQUENTIAL) + , _master(new Task(Task::Mode::PARALLEL)) { compile_graph(graph); } @@ -76,7 +76,7 @@ CompiledGraph::compile_set(const std::set& blocks, // Each block is the start of a new sequential task Task seq(Task::Mode::SEQUENTIAL); compile_block(block, seq, k); - task.push_back(seq); + task.push_front(std::move(seq)); } } @@ -91,41 +91,29 @@ CompiledGraph::compile_graph(GraphImpl* graph) // Mark all blocks as unvisited initially b.set_mark(BlockImpl::Mark::UNVISITED); - if (b.providers().empty()) { - // Block has no dependencies, add to initial working set + if (b.dependants().empty()) { + // Block has no dependants, add to initial working set blocks.insert(&b); } } - // Compile initial working set into master task - Task start(Task::Mode::PARALLEL); - std::set next; - compile_set(blocks, start, next); - _master.push_back(start); - // Keep compiling working set until all connected nodes are visited - while (!next.empty()) { - blocks.clear(); + while (!blocks.empty()) { + std::set next; + // The working set is a parallel task... Task par(Task::Mode::PARALLEL); - for (BlockImpl* block : next) { - // ... where each block is the start of a new sequential task + for (BlockImpl* block : blocks) { + // ... where each block is the tail of a new sequential task Task seq(Task::Mode::SEQUENTIAL); - compile_block(block, seq, blocks); - par.push_back(seq); - } - _master.push_back(par); - next = blocks; - } - - // Compile any nodes that weren't reached (disconnected cycles) - for (auto& b : graph->blocks()) { - if (b.get_mark() == BlockImpl::Mark::UNVISITED) { - compile_block(&b, _master, next); + compile_block(block, seq, next); + par.push_front(std::move(seq)); } + _master->push_front(std::move(par)); + blocks = next; } - _master.simplify(); + _master = Task::simplify(std::move(_master)); if (graph->engine().world()->conf().option("trace").get()) { dump([this](const std::string& msg) { @@ -160,23 +148,23 @@ check_feedback(const BlockImpl* root, BlockImpl* dependant) } void -CompiledGraph::compile_dependant(const BlockImpl* root, - BlockImpl* block, - Task& task, - std::set& k) +CompiledGraph::compile_provider(const BlockImpl* root, + BlockImpl* block, + Task& task, + std::set& k) { - if (block->providers().size() > 1) { - /* Dependant has other providers, so this is the start of a sequential task. - Add dependant to future working set and stop traversal. */ + if (block->dependants().size() > 1) { + /* Provider has other dependants, so this is the start of a sequential task. + Add provider to future working set and stop traversal. */ check_feedback(root, block); k.insert(block); } else { - // Dependant has only this provider, add here + // Provider has only this dependant, 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, k); - task.push_back(seq); + task.push_front(std::move(seq)); } else { // Append to given sequential task compile_block(block, task, k); @@ -191,21 +179,21 @@ CompiledGraph::compile_block(BlockImpl* n, Task& task, std::set& k) case BlockImpl::Mark::UNVISITED: n->set_mark(BlockImpl::Mark::VISITING); - // Execute this task before the dependants to follow - task.push_back(Task(Task::Mode::SINGLE, n)); + // Execute this task after the providers to follow + task.push_front(Task(Task::Mode::SINGLE, n)); - if (n->dependants().size() < 2) { - // Single dependant, append to this sequential task - for (auto& d : n->dependants()) { - compile_dependant(n, d, task, k); + if (n->providers().size() < 2) { + // Single provider, append to this sequential task + for (auto& d : n->providers()) { + compile_provider(n, d, task, k); } } else { - // Multiple dependants, create a new parallel task + // Multiple providers, create a new parallel task Task par(Task::Mode::PARALLEL); - for (auto& d : n->dependants()) { - compile_dependant(n, d, par, k); + for (auto& d : n->providers()) { + compile_provider(n, d, par, k); } - task.push_back(par); + task.push_front(std::move(par)); } n->set_mark(BlockImpl::Mark::VISITED); break; @@ -221,7 +209,7 @@ CompiledGraph::compile_block(BlockImpl* n, Task& task, std::set& k) void CompiledGraph::run(RunContext& context) { - _master.run(context); + _master->run(context); } void @@ -229,7 +217,7 @@ CompiledGraph::dump(std::function sink) const { sink("(compiled-graph "); sink(_path); - _master.dump(sink, 2, false); + _master->dump(sink, 2, false); sink(")\n"); } -- cgit v1.2.1