add parallel execution

2 files changed, 23 insertions, 12 deletions

diff --git a/Makefile b/Makefile
index 010c76d..221f015 100644
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,4 @@
-CXX=g++ -std=c++0x -O3 -Wall -Wextra -Werror
+CXX=g++ -std=c++0x -O3 -Wall -Wextra -Werror -lpthread
 
 all: cacount
 
diff --git a/cacount.cpp b/cacount.cpp
index bd8f1a6..1ef159b 100644
--- a/cacount.cpp
+++ b/cacount.cpp
@@ -6,8 +6,10 @@
 #include <bitset>
 #include <functional>
 #include <iostream>
+#include <list>
 #include <map>
 #include <set>
+#include <thread>
 
 #include <sys/mman.h>
 
@@ -31,36 +33,45 @@ State update(State s) {
 
 typedef array<State, maxState> Trans;
 
-void iterState(function<void(int)> f) {
-  for (State s=0; s<maxState; s++)
-    f(s);
+void iterState(function<void(int)> f, int numThreads=1) {
+  list<thread*> tasks;
+  for (int t=0; t<numThreads; t++) {
+    tasks.push_front(new thread([=]{
+	  for (State s = maxState / numThreads * t; 
+	       s < ((t == numThreads - 1) ? maxState : (maxState / numThreads * (t+1)));
+	       s++)
+	    f(s);
+	}));
+  }
+  for (; !tasks.empty(); tasks.front()->join(), delete tasks.front(), tasks.pop_front());    
 }
 
-void iterTrans(int times, function<void(int)> f, bool verbose=false) {
-  if (verbose) cerr << times << " left\r";
+void iterTrans(int times, function<void(int)> f, char *msg = nullptr) {
+  if (msg) cerr << msg << times << " left\r";
   while (times--) {
     iterState(f);
-    if (verbose) cerr << times << " left\r";
+    if (msg) cerr << msg << times << " left\r";
   }
-  if (verbose) cerr << "           \r";
+  if (msg) cerr << "                                  \r";
 }
 
 void init(Trans &t) {
-  iterState([&](int s) { 
-      t[s] = update(s); });
+  iterState([&](int s) {
+      t[s] = update(s); },
+    thread::hardware_concurrency());
 }
 
 void findCycle(Trans &t, Trans &c) {
   // forward to t=maxState; now every state is in a cycle
   iterTrans(logState, [&](int s) {
-      t[s] = t[t[s]]; }, true);
+      t[s] = t[t[s]]; }, (char*) "fwd time: ");
   // compute loop id (lowest occuring state no): go through the loop again and
   // record the lowest occuring state number
   iterState([&](int s) { 
       c[s] = t[s]; });
   iterTrans(logState, [&](int s) {
       c[s] = min(c[s], c[t[s]]);
-      t[s] = t[t[s]]; }, true);
+      t[s] = t[t[s]]; }, (char*) "cycles: ");
 }
 
 void cycleStat(Trans &c) {