Parallel build

7 files changed, 202 insertions, 38 deletions

diff --git a/builder.cpp b/Builder.cpp
index ee9c16b..1f6fbb2 100644
--- a/builder.cpp
+++ b/Builder.cpp
@@ -1,6 +1,7 @@
-#include "builder.h"
+#include "Builder.h"
 
 #include <algorithm>
+#include <chrono>
 #include <cstdlib>
 #include <filesystem>
 #include <iostream>
@@ -9,13 +10,13 @@
 #include <stack>
 #include <stdexcept>
 #include <string>
+#include <thread>
 #include <unordered_map>
 #include <unordered_set>
 #include <vector>
 
 #include <boost/property_tree/ptree.hpp>
 #include <boost/property_tree/xml_parser.hpp>
-#include <boost/process.hpp>
 
 #include <fmt/format.h>
 
@@ -23,8 +24,8 @@
 #include <libreichwein/stringhelper.h>
 
 namespace fs = std::filesystem;
-namespace bp = boost::process;
 namespace pt = boost::property_tree;
+using namespace std::chrono_literals;
 using namespace std::string_literals;
 
 namespace {
@@ -165,7 +166,7 @@ bool Builder::is_outdated(const fs::path& p) {
 }
 
 // build 1 file
-void Builder::build(const fs::path& p) {
+void Builder::build_file(const fs::path& p) {
  std::string command;
 
  if (p.extension() == ".o") {
@@ -185,51 +186,75 @@ void Builder::build(const fs::path& p) {
  }
 
  std::cout << command << std::endl;
- int result{system(command.c_str())};
- if (result != 0) {
-  throw std::runtime_error(fmt::format("Error {}", result));
+ _runner.spawn(p.string(), command.c_str());
+}
+
+void Builder::cleanup() {
+ std::string path;
+ int exit_code{_runner.wait_one(path)};
+ _activelist.erase(fs::path{path});
+
+ _donelist.insert(fs::path{path});
+ if (exit_code != 0) {
+  throw std::runtime_error(fmt::format("Exit code {}", exit_code));
  }
 }
 
 // build list of files
-// eats up input
-void Builder::build(std::unordered_set<fs::path>& buildlist) {
- std::unordered_set<fs::path> activelist; // currently building
- std::unordered_set<fs::path> donelist; // build done
+// eats up _buildlist
+void Builder::build_list() {
 
- if (buildlist.empty()) {
+ if (_buildlist.empty()) {
   std::cout << "Everything up to date." << std::endl;
  } else {
   std::cout << "Running commands: " << std::endl;
  }
 
- while (!buildlist.empty()) {
+ while (!_buildlist.empty()) {
   // find file which can be built directly since its build dependencies are up to date
-  // this holds for either any member of the set (e.g. at begin()), or any of its direct or indirect dependencies
-  fs::path current {*buildlist.begin()};
 
-  bool found_outdated{}; // outdated dependencies
+  fs::path current;
 
-  do {
-   found_outdated = false;
-   std::vector<fs::path> deps{dependencies_of(current)};
-   for (auto& i: deps) {
-    if (activelist.find(i) == activelist.end() && is_outdated(i)) {
-     found_outdated = true;
+  while (current.empty()) {
+   for (auto &i: _buildlist) {
+    std::vector<fs::path> deps{dependencies_of(i)};
+    bool deps_up_to_date{true};
+    for (auto& dep: deps) {
+     if (_activelist.find(dep) != _activelist.end() || is_outdated(dep)) {
+      deps_up_to_date = false;
+     }
+    }
+    if (deps_up_to_date) {
      current = i;
      break;
     }
    }
-  } while (found_outdated);
 
-  buildlist.erase(current);
+   if (current.empty()) {
+    std::this_thread::sleep_for(10ms); // short wait before retry
+    if (_runner.finished() > 0) {
+     cleanup();
+    }
+   }
+  }
 
-  activelist.insert(current);
-  // TODO: build in background
-  build(current);
-  activelist.erase(current);
+  _buildlist.erase(current);
+  _activelist.insert(current);
+
+  while (_runner.full() || _runner.finished() > 0) {
+   cleanup();
+  }
+
+  build_file(current); // calls spawn() on _runner
+ }
+
+ // final cleanup
+ while (_runner.finished() != 0 || _runner.running() != 0) {
+  cleanup();
+ }
 
-  donelist.insert(current);
+ if (!_activelist.empty()) {
+  throw std::runtime_error("Files left actively building");
  }
 }
 
@@ -244,7 +269,6 @@ void Builder::build() {
 
  // create build list by depth-first search
  std::cout << "Calculating build list..." << std::endl;
- std::unordered_set<fs::path> buildlist;
  std::stack<fs::path> container; // temporary container for search algorithm
  container.push(_target);
  while (!container.empty()) {
@@ -257,16 +281,16 @@ void Builder::build() {
   }
 
   if (is_outdated(current) && is_buildable_by_extension(current)) {
-   buildlist.insert(current);
+   _buildlist.insert(current);
   }
  }
 
  std::cout << "Build list:" << std::endl;
- for (auto &i: buildlist) {
+ for (auto &i: _buildlist) {
   std::cout << "  " << i << std::endl;
  }
 
- build(buildlist);
+ build_list();
 }
 
 void Builder::clean() {
diff --git a/builder.h b/Builder.h
index c139d2a..12338f0 100644
--- a/builder.h
+++ b/Builder.h
@@ -7,6 +7,8 @@
 
 #include <boost/property_tree/ptree.hpp>
 
+#include "ProcessRunner.h"
+
 class Builder
 {
 public:
@@ -19,11 +21,20 @@ private:
  std::vector<std::filesystem::path> dependencies_of(const std::filesystem::path& p);
  bool is_outdated(const std::filesystem::path& p);
 
- void build(const std::filesystem::path& p);
- void build(std::unordered_set<std::filesystem::path>& buildlist);
+ void build_file(const std::filesystem::path& p);
+ void build_list();
+
+ void cleanup();
 
  std::filesystem::path _target;
  std::vector<std::filesystem::path> _objects;
  std::vector<std::filesystem::path> _sources;
  std::unordered_map<std::filesystem::path, std::vector<std::filesystem::path>> _dependencies;
+
+ ProcessRunner _runner;
+
+ std::unordered_set<std::filesystem::path> _buildlist; // build done
+ std::unordered_set<std::filesystem::path> _activelist; // currently building
+ std::unordered_set<std::filesystem::path> _donelist; // build done
 };
+
diff --git a/Makefile b/Makefile
index c24af4d..c0a8132 100644
--- a/Makefile
+++ b/Makefile
@@ -1,6 +1,6 @@
 PROJECTNAME=ymake
 
-SRC=main.cpp ymake.cpp builder.cpp
+SRC=main.cpp ymake.cpp Builder.cpp ProcessRunner.cpp
 
 OBJ=$(SRC:.cpp=.o)
 
diff --git a/ProcessRunner.cpp b/ProcessRunner.cpp
new file mode 100644
index 0000000..bdde054
--- /dev/null
+++ b/ProcessRunner.cpp
@@ -0,0 +1,92 @@
+#include "ProcessRunner.h"
+
+#include <stdexcept>
+#include <thread>
+
+#include <boost/process.hpp>
+
+#include <sys/wait.h>
+
+namespace bp = boost::process;
+
+ProcessRunner::ProcessRunner():
+ _max_number_of_processes{static_cast<int>(std::thread::hardware_concurrency())}
+{}
+
+void ProcessRunner::spawn(const std::string& key, const std::string& command)
+{
+ _processes.emplace_back(process{key, command});
+}
+
+bool ProcessRunner::empty()
+{
+ return running() == 0;
+}
+
+bool ProcessRunner::full()
+{
+ return running() == _max_number_of_processes;
+}
+
+int ProcessRunner::wait_one(std::string& key)
+{
+ if (running() > 0 && finished() == 0) {
+  waitpid(-1, NULL, 0);
+ }
+
+ // Actually, several childs may have finished. Therefore, end and
+ // remove all finished childs.
+ if (finished() > 0) {
+  for (auto it = _processes.begin(); it != _processes.end(); ++it) {
+   bp::child &child{it->child};
+   if (!child.running()) {
+    child.wait();
+    int result{child.exit_code()};
+
+    key = it->key;
+
+    _processes.erase(it, it+1);
+    return result;
+   }
+  }
+ };
+
+ if (_processes.empty()) {
+  throw std::runtime_error("No process to wait for");
+ }
+
+ throw std::runtime_error("No process finished");
+}
+
+int ProcessRunner::wait_all()
+{
+ int ret{};
+ for (auto &i: _processes) {
+  i.child.wait();
+  int result{i.child.exit_code()};
+  if (result != 0 && ret == 0) {
+   ret = result;
+  }
+ }
+
+ _processes.clear();
+
+ return ret;
+}
+
+size_t ProcessRunner::running()
+{
+ size_t result{};
+ for (auto &i: _processes) {
+  if (i.child.running()) {
+   ++result;
+  }
+ }
+ return result;
+}
+
+size_t ProcessRunner::finished()
+{
+ return _processes.size() - running();
+}
+
diff --git a/ProcessRunner.h b/ProcessRunner.h
new file mode 100644
index 0000000..1c0789d
--- /dev/null
+++ b/ProcessRunner.h
@@ -0,0 +1,36 @@
+#pragma once
+
+#include <deque>
+#include <string>
+
+#include <boost/process.hpp>
+
+struct process
+{
+ process(const std::string& k, const std::string& command): key{k}, child{command} {}
+ std::string key;
+ boost::process::child child;
+};
+
+// runs a number of processes in parallel, with an upper limit
+class ProcessRunner
+{
+public:
+ ProcessRunner();
+
+ void spawn(const std::string& key, const std::string& command);
+
+ bool empty(); // number of running processes is zero
+ bool full(); // number of running processes equals maximum
+
+ int wait_one(std::string& key); // returns exit code, and key via reference
+ int wait_all();
+
+ size_t running(); // number of running processes in queue
+ size_t finished(); // number of finished processes in queue
+
+private:
+ int _max_number_of_processes;
+ std::deque<process> _processes;
+};
+
diff --git a/YMakefile b/YMakefile
index 152ccc6..2881c10 100644
--- a/YMakefile
+++ b/YMakefile
@@ -1,8 +1,9 @@
 <ymake>
  <build>
   <name>ymake</name>
-  <source>builder.cpp</source>
+  <source>Builder.cpp</source>
   <source>main.cpp</source>
+  <source>ProcessRunner.cpp</source>
   <source>ymake.cpp</source>
  </build>
 </ymake>
diff --git a/ymake.cpp b/ymake.cpp
index 93a813e..ad46d3c 100644
--- a/ymake.cpp
+++ b/ymake.cpp
@@ -1,6 +1,6 @@
 #include "ymake.h"
 
-#include "builder.h"
+#include "Builder.h"
 
 #include <algorithm>
 #include <cstdlib>