add verbose timer function, replace bitset w/ packed_array

Replacing bitset with packed_array is neccessary to allow parallel
access to proximate array cells.

1 files changed, 30 insertions, 20 deletions

diff --git a/cacount.cpp b/cacount.cpp
index 8590eb0..012f33b 100644
--- a/cacount.cpp
+++ b/cacount.cpp
@@ -14,11 +14,13 @@
 #include <sys/mman.h>
 
 #include "packed_array.hpp"
+#include "timer.hpp"
 
 using namespace std;
+using boost::optional;
 
 #ifndef BIT_WIDTH
-#define BIT_WIDTH 31
+#define BIT_WIDTH 16
 #endif
 
 typedef uint64_t State;
@@ -43,8 +45,10 @@ State update(State s) {
 }
 
 typedef packed_array<State, maxState, BIT_WIDTH> Trans;
+typedef packed_array<bool, maxState, 1> pbitset;
 
-void iterState(function<void(int)> f, bool parallel = false) {
+void iterState(function<void(int)> f, optional<string> msg = optional<string>(), bool parallel = false) {
+  PerfPrinter perfPrinter(msg);
   int numThreads=1;
   if (parallel) {
     numThreads = min((State) thread::hardware_concurrency(),
@@ -62,38 +66,42 @@ void iterState(function<void(int)> f, bool parallel = false) {
   for (; !tasks.empty(); tasks.front()->join(), delete tasks.front(), tasks.pop_front());    
 }
 
-void iterTrans(int times, function<void(int)> f, char *msg = nullptr, bool parallel = false) {
-  if (msg) cerr << msg << times << " left   \r";
+void iterTrans(int times, function<void(int)> f, optional<string> msg = optional<string>(), bool parallel = false) {
+  PerfPrinter perfPrinter(msg);
+  auto msg2 = [=,&msg] (int i) {
+    return msg ? (*msg + string(" ") + to_string(times-i) + string("/") + to_string(times)) : msg; };
   while (times--) {
-    iterState(f, parallel);
-    if (msg) cerr << msg << times << " left   \r";
+    iterState(f, msg2(times), parallel);
   }
-  if (msg) cerr << "                                  \r";
 }
 
 void init(Trans &t) {
   iterState([&](int s) {
-      t[s] = update(s); }, true);
+      t[s] = update(s);
+    }, (string) "single step transition table", true);
 }
 
-void findCycle(Trans &t, Trans &c, bitset<maxState> &reachable) {
+void findCycle(Trans &t, Trans &c, pbitset &reachable) {
   // compute reachability
   iterState([&](int s) {
       reachable[t[s]] = 1;
-    }, true);
+    }, (string) "reachability", true);
   // forward to t=maxState; now every state is in a cycle
   iterTrans(logState, [&](int s) {
-      t[s] = t[t[s]]; }, (char*) "fwd time: ");
+      t[s] = t[t[s]];
+    }, (string) "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]; }, true);
+      c[s] = t[s];
+    }, (string) "init cycles", true);
   iterTrans(logState, [&](int s) {
       c[s] = min<State>(c[s], c[t[s]]);
-      t[s] = t[t[s]]; }, (char*) "cycles: ");
+      t[s] = t[t[s]];
+    }, (string) "cycles");
 }
 
-void cycleStat(Trans &c, bitset<maxState> &reachable) {
+void cycleStat(Trans &c, pbitset &reachable) {
   struct Stat {
     State basin, len, eden, minState;
     Stat() : basin(0), len(0), eden(0), minState(maxState) {}
@@ -106,9 +114,10 @@ void cycleStat(Trans &c, bitset<maxState> &reachable) {
       cyc[c[s]].basin++;
       if (!reachable[s])
 	cyc[c[s]].eden++;
-    });
+    }, (string) "basin & eden");
 
   // how long is the cycle, what is the actual minimal state
+  { PerfPrinter perfPrinter((string) "cycle length");
   for (auto i : cyc) {
     Stat &s = cyc[i.first];
     State cur, start;
@@ -118,19 +127,20 @@ void cycleStat(Trans &c, bitset<maxState> &reachable) {
       s.minState = min(s.minState, cur);
       cur=update(cur);
     } while (cur != start);
-  }
+  }}
 
   // find duplicates cycles (only bitshifted)
+  map<State, set<State>> ccyc;
+  { PerfPrinter perfPrinter((string) "find duplicate cycles");
   auto canonize = [](State s) {
     State cs = s;
     for (State i=0; i<logState; i++)
       cs = min(cs, (((s<<i) | (s>>(logState-i))) & (maxState - 1)));
     return cs;
   };
-  map<State, set<State>> ccyc;
   for (auto i : cyc) {
     ccyc[canonize(i.second.minState)].insert(i.first);
-  }
+  }}
 
   // print it
   for (auto i : ccyc) {
@@ -175,8 +185,8 @@ int main(int argc, char **argv) {
   }
   if (!strcmp(argv[2], "cycle")) {
     Trans *t = mmalloc<Trans>(),
-      *c = mmalloc<Trans>();
-    bitset<maxState> *r = new bitset<maxState>(0);
+          *c = mmalloc<Trans>();
+    packed_array<bool, maxState, 1> *r = mmalloc<packed_array<bool, maxState, 1>>();
     init(*t);
     findCycle(*t, *c, *r);
     cycleStat(*c, *r);