diff options
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | cacount.cpp | 50 | ||||
| -rw-r--r-- | timer.hpp | 35 |
3 files changed, 69 insertions, 21 deletions
@@ -2,7 +2,10 @@ CXX=g++ -std=c++0x -O3 -Wall -Wextra -Werror -lpthread all: cacount -cacount_%: cacount.cpp +cacount :: cacount.cpp packed_array.hpp timer.hpp + $(CXX) -fwhole-program $< -o $@ + +cacount_%: cacount.cpp packed_array.hpp timer.hpp $(CXX) -DBIT_WIDTH=$(shell echo $@ | egrep -o '[^_]*$$') -fwhole-program $< -o $@ clean: 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); diff --git a/timer.hpp b/timer.hpp new file mode 100644 index 0000000..8d413b3 --- /dev/null +++ b/timer.hpp @@ -0,0 +1,35 @@ +#pragma once + +#include <sys/time.h> +#include <string> +#include <iostream> +#include <boost/optional.hpp> + +struct PerfPrinter { + timeval start; + boost::optional<std::string> msg; + + PerfPrinter(boost::optional<std::string> msg) : msg(msg) { + if (msg) + std::cerr << "\r\033[K" + << *msg + << std::flush; + gettimeofday(&start,NULL); + } + + ~PerfPrinter() { + if (msg) + std::cerr << "\r\033[K" + << *msg + << ": " + << diff() + << " s" + << std::endl; + } + + double diff() { + timeval stop; + gettimeofday(&stop,NULL); + return (stop.tv_sec + stop.tv_usec/1000000.0) - (start.tv_sec + start.tv_usec/1000000.0); + } +}; |