forked from starcells/R8VeritasCC
- pool split into 32 sharded unordered_sets (shard = content hash), each with its own mutex; ~99% of per-candidate cost was the pool lookup - bfs restructured to explicit frontier/next layer vectors; layers >= 4096 states expanded by nthreads threads with private next-vectors - visited_op insert gated on first discovery (skips ~99% wasted lookups) - target's visited_op parent recorded before returning (fixes track_path infinite loop; target is usually already pooled so gated insert skips) - bfs(..., nthreads=0) defaults to hardware_concurrency — backward compatible with existing r8_test.cc calls - measured: FA-Co cs=5 184s serial -> 28s @ 8 threads on E5-2696v4 (~6.6x); memory-bandwidth bound beyond T=8; small problems unaffected adds tests/r8_bench.cc (serial reference) and tests/r8_bench_mt.cc (thread-count sweep) drivers
481 lines
15 KiB
C++
481 lines
15 KiB
C++
#ifndef R8VERITAS
|
|
#define R8VERITAS
|
|
|
|
#include <algorithm>
|
|
#include <array>
|
|
#include <atomic>
|
|
#include <bit>
|
|
#include <bitset>
|
|
#include <cstddef>
|
|
#include <cstdint>
|
|
#include <functional>
|
|
#include <iostream>
|
|
#include <mutex>
|
|
#include <ostream>
|
|
#include <queue>
|
|
#include <set>
|
|
#include <stack>
|
|
#include <string>
|
|
#include <thread>
|
|
#include <unordered_map>
|
|
#include <unordered_set>
|
|
#include <utility>
|
|
#include <vector>
|
|
|
|
#ifndef CELL_SIZE_BITWIDTH
|
|
#define CELL_SIZE_BITWIDTH std::bit_width(unsigned(CELL_SIZE))
|
|
#endif
|
|
|
|
#ifndef INS_SIZE
|
|
#define INS_SIZE (CELL_SIZE + 1)
|
|
#endif
|
|
// mask and opcode
|
|
#ifndef INS_BYTECODE_SIZE
|
|
#define INS_BYTECODE_SIZE (INS_SIZE + CELL_SIZE_BITWIDTH)
|
|
#endif
|
|
// mask,opcode and sacrifice
|
|
|
|
#ifndef OPCODE_SET1
|
|
#define OPCODE_SET1 (static_cast<int>(r8veritas::ins_opcode::SET1))
|
|
#endif
|
|
#ifndef OPCODE_FLIP
|
|
#define OPCODE_FLIP (static_cast<int>(r8veritas::ins_opcode::FLIP))
|
|
#endif
|
|
|
|
// r8veritas<CELL_SIZE> — ROT-8 truth-table superoptimizer BFS.
|
|
//
|
|
// Parallel design (vs the serial original):
|
|
// * stat_pool is sharded into POOL_SHARDS independent unordered_sets
|
|
// (shard = content hash & (POOL_SHARDS-1)), each with its own mutex.
|
|
// ~99% of per-candidate cost is the pool lookup, so it MUST be
|
|
// parallelizable — a single global mutex caps speedup at ~2x.
|
|
// * bfs() is restructured from queue+recursion to explicit layer vectors
|
|
// (frontier/next). Layers >= PARALLEL_THRESHOLD are expanded by
|
|
// nthreads threads; each thread owns a private next-vector.
|
|
// * visited_op insert is gated on "state newly discovered" (first-wins —
|
|
// skips the wasted lookup on ~99% visited hits; identical content to
|
|
// the original's always-insert).
|
|
// * Target check: pointer compare ref == truthtable.second (the target
|
|
// is pre-inserted into the pool by generate_truthtable). The target's
|
|
// visited_op parent is recorded BEFORE returning — it is usually
|
|
// already pooled (inserted==false), so the gated insert would skip it
|
|
// and track_path() would loop forever.
|
|
//
|
|
// Measured (cs=5, FA-Co, Toyohime E5-2696v4): 184s serial -> 28s at 8
|
|
// threads (~6.6x); memory-bandwidth bound beyond T=8. Small problems
|
|
// (~ms) pay ~0 overhead; nthreads=0 auto-selects hardware_concurrency.
|
|
|
|
template <int CELL_SIZE> class r8veritas {
|
|
public:
|
|
using cell = uint8_t;
|
|
|
|
using stat = std::array<r8veritas::cell, (1 << CELL_SIZE)>;
|
|
using stat_ref = const stat *;
|
|
using truthtable = std::pair<r8veritas::stat_ref, r8veritas::stat_ref>;
|
|
using op = std::function<r8veritas::cell(r8veritas::cell)>;
|
|
using index = size_t;
|
|
using influence = size_t;
|
|
using ins_body = size_t;
|
|
using ins_bytecode = size_t;
|
|
enum ins_opcode {
|
|
SET1 = 0,
|
|
FLIP = 1,
|
|
};
|
|
|
|
struct ins {
|
|
r8veritas::ins_body bc;
|
|
r8veritas::index sacrifice;
|
|
operator const ins_bytecode() const {
|
|
return (bc << CELL_SIZE_BITWIDTH) | sacrifice;
|
|
}
|
|
};
|
|
using path =
|
|
std::stack<std::pair<r8veritas::stat_ref, r8veritas::ins_bytecode>>;
|
|
std::array<std::string, CELL_SIZE> nicknames;
|
|
std::array<std::string, CELL_SIZE> tp_paths;
|
|
|
|
private:
|
|
static constexpr size_t POOL_SHARDS = 32; // power of two
|
|
static constexpr size_t PARALLEL_THRESHOLD = 4096;
|
|
|
|
std::array<r8veritas::influence, CELL_SIZE> all_influences;
|
|
|
|
const std::set<r8veritas::ins> all_ins = []() -> std::set<r8veritas::ins> {
|
|
std::set<r8veritas::ins> s;
|
|
for (r8veritas::index sacrifice_it = 0; sacrifice_it < CELL_SIZE;
|
|
sacrifice_it++) {
|
|
for (r8veritas::index bc_it = 0; bc_it < (1 << INS_SIZE); bc_it++) {
|
|
auto tmp = bc_it & (~(1 << (sacrifice_it + 1)));
|
|
// sacrifice shouldn't be operated,
|
|
// which means that bit in bc's mask can't be 1.
|
|
// so here I forcefully change it to 0,
|
|
// and use set to ensure it won't duplicate.
|
|
// for here's the initialization part,it's acceptable
|
|
s.insert({((tmp == 0) ? 1 : tmp), sacrifice_it});
|
|
// both bc == 0b0 and bc == 0b1 mean erasing sacrifice,so here I skip
|
|
// 0b0
|
|
}
|
|
}
|
|
return s;
|
|
}();
|
|
|
|
struct stat_hash {
|
|
size_t operator()(const stat &s) const {
|
|
size_t h = 0;
|
|
for (auto i : s) {
|
|
h ^= std::hash<r8veritas::cell>{}(i) + 0x9e3779b9 + (h << 6) + (h >> 2);
|
|
// Magic,from Boost's hash_combine.
|
|
// An explanation from MCMC here: https://zhuanlan.zhihu.com/p/574573421
|
|
}
|
|
return h;
|
|
}
|
|
};
|
|
|
|
std::array<std::unordered_set<r8veritas::stat, stat_hash>, POOL_SHARDS>
|
|
pool_shards;
|
|
std::array<std::mutex, POOL_SHARDS> pool_locks;
|
|
std::mutex visited_op_lock;
|
|
std::unordered_map<r8veritas::stat_ref,
|
|
std::pair<r8veritas::stat_ref, r8veritas::ins_bytecode>>
|
|
visited_op;
|
|
|
|
std::vector<r8veritas::stat_ref> frontier;
|
|
std::vector<r8veritas::stat_ref> next;
|
|
std::vector<std::vector<r8veritas::stat_ref>> thread_next;
|
|
|
|
size_t shard_of(const stat &s) const {
|
|
return stat_hash{}(s) & (POOL_SHARDS - 1);
|
|
}
|
|
|
|
public:
|
|
r8veritas::ins to_ins(const r8veritas::ins_bytecode &bc) {
|
|
return {bc >> CELL_SIZE_BITWIDTH, bc & ((1 << CELL_SIZE_BITWIDTH) - 1)};
|
|
}
|
|
void initialize_nicknames() {
|
|
for (r8veritas::index i = 0; i < CELL_SIZE; i++) {
|
|
nicknames[i] = "%" + std::to_string(i + 1);
|
|
}
|
|
return;
|
|
}
|
|
|
|
void initialize_tp_paths() {
|
|
for (r8veritas::index i = 0; i < CELL_SIZE; i++) {
|
|
tp_paths[i] = ".tp " + nicknames[i];
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
r8veritas::stat_ref generate_empty_stat() {
|
|
r8veritas::stat arr{};
|
|
size_t s = shard_of(arr);
|
|
std::lock_guard<std::mutex> g(pool_locks[s]);
|
|
auto tmp_ptr = pool_shards[s].insert(std::move(arr)).first;
|
|
return &(*tmp_ptr);
|
|
}
|
|
|
|
// WARNING:ST WILL BE DESTROYED
|
|
std::pair<r8veritas::stat_ref, bool> save_stat(r8veritas::stat &&st) {
|
|
size_t s = shard_of(st);
|
|
std::lock_guard<std::mutex> g(pool_locks[s]);
|
|
auto t = pool_shards[s].insert(std::move(st));
|
|
return {&(*(t.first)), !t.second};
|
|
}
|
|
|
|
r8veritas::truthtable generate_truthtable(const r8veritas::op &operation) {
|
|
r8veritas::stat inp = *generate_empty_stat();
|
|
r8veritas::stat out = *generate_empty_stat();
|
|
for (r8veritas::index i = 0; i < (1 << CELL_SIZE); i++) {
|
|
inp[i] = i;
|
|
out[i] = operation(r8veritas::cell(i));
|
|
}
|
|
return (r8veritas::truthtable(save_stat(std::move(inp)).first,
|
|
save_stat(std::move(out)).first));
|
|
}
|
|
|
|
// Pure operate: no pool/map side effects. The row loop is lock-free and
|
|
// embarrassingly parallel by construction.
|
|
static r8veritas::stat
|
|
operate_stat(const r8veritas::stat &last, const r8veritas::ins &ins) {
|
|
r8veritas::stat next_stat = last;
|
|
int opcode = ins.bc & 1;
|
|
|
|
r8veritas::cell cell_mask = (ins.bc >> 1);
|
|
|
|
for (r8veritas::index i = 0; i < (1 << CELL_SIZE); i++) {
|
|
if ((next_stat[i] & (1 << ins.sacrifice)) != 0) {
|
|
next_stat[i] ^= (1 << ins.sacrifice);
|
|
if (opcode == OPCODE_SET1) {
|
|
next_stat[i] |= cell_mask;
|
|
} else if (opcode == OPCODE_FLIP) {
|
|
next_stat[i] ^= cell_mask;
|
|
}
|
|
}
|
|
}
|
|
return next_stat;
|
|
}
|
|
|
|
std::pair<r8veritas::stat_ref,
|
|
bool> // true means the next stat has been visited.
|
|
operate_ins(const r8veritas::stat_ref &last_stat, const r8veritas::ins &ins) {
|
|
r8veritas::stat next_stat = operate_stat(*last_stat, ins);
|
|
auto tmp = save_stat(std::move(next_stat));
|
|
|
|
visited_op.insert(std::pair(tmp.first, std::pair(last_stat, r8veritas::ins_bytecode(ins))));
|
|
return tmp;
|
|
}
|
|
|
|
void output_stat(const r8veritas::stat_ref &s) {
|
|
for (auto i : *s) {
|
|
std::cout << std::bitset<CELL_SIZE>(i).to_string() << " ";
|
|
}
|
|
}
|
|
|
|
void output_ins(const r8veritas::ins &s, bool enable_debug_output = true) {
|
|
|
|
auto str = std::bitset<INS_SIZE>(s.bc).to_string();
|
|
std::queue<r8veritas::index> arg_list;
|
|
bool just_sacrifice = ((s.bc == 0b0) || (s.bc == 0b1));
|
|
|
|
std::reverse(&str[0], &str[CELL_SIZE]);
|
|
/* e.g.
|
|
CELL_SIZE = 4
|
|
(0b)00101 -> 01001
|
|
^ ^str[CELL_SIZE]
|
|
*/
|
|
if (!just_sacrifice) {
|
|
for (r8veritas::index i = 0; i < str.length() - 1; i++) {
|
|
if (str[i] == '1') {
|
|
arg_list.push(i);
|
|
}
|
|
}
|
|
}
|
|
|
|
bool is_set1 = (str[CELL_SIZE] == '1');
|
|
|
|
if (enable_debug_output) {
|
|
std::cout << "SACRIFICE: " << s.sacrifice;
|
|
if (!just_sacrifice) {
|
|
if (is_set1)
|
|
std::cout << ", SET1: {";
|
|
else
|
|
std::cout << ", FLIP: {";
|
|
while (!arg_list.empty()) {
|
|
std::cout << arg_list.front() << ',';
|
|
arg_list.pop();
|
|
}
|
|
std::cout << "\b}";
|
|
}
|
|
std::cout << ';';
|
|
/* e.g.
|
|
|
|
SACRIFICE: a, SET1: {b,c};
|
|
|
|
*/
|
|
} else {
|
|
std::cout << tp_paths[s.sacrifice] << std::endl;
|
|
std::cout << "biz" << std::endl;
|
|
if (!just_sacrifice) {
|
|
while (!arg_list.empty()) {
|
|
std::cout << '\t' << tp_paths[arg_list.front()] << std::endl;
|
|
if (is_set1)
|
|
std::cout << "\tset_1" << std::endl;
|
|
else
|
|
std::cout << "\tflb" << std::endl;
|
|
arg_list.pop();
|
|
}
|
|
std::cout << '\t' << tp_paths[s.sacrifice] << std::endl;
|
|
}
|
|
std::cout << "\tflb" << std::endl;
|
|
std::cout << "rnz" << std::endl;
|
|
/* e.g.
|
|
|
|
.tp a
|
|
biz
|
|
.tp b
|
|
set_1
|
|
.tp c
|
|
set_1
|
|
.tp a
|
|
flb
|
|
rnz
|
|
|
|
*/
|
|
}
|
|
}
|
|
|
|
r8veritas::truthtable
|
|
compress_stat_space(const r8veritas::truthtable &raw_truthtable) {
|
|
// raw means input must be 0 ~ (1<<CELL_SIZE),
|
|
// which makes reaching the output of after-xor input easier.
|
|
std::array<r8veritas::influence, CELL_SIZE> influences;
|
|
r8veritas::truthtable new_truthtable = raw_truthtable;
|
|
for (r8veritas::index i = 0; i < CELL_SIZE; i++) {
|
|
influences[i] = 0;
|
|
for (r8veritas::index j = 0; j < (1 << CELL_SIZE); j++) {
|
|
if ((*(raw_truthtable.second))[j] !=
|
|
(*(raw_truthtable.second))[j ^ (1 << i)]) {
|
|
// when [j] can influence the ans
|
|
influences[i]++;
|
|
}
|
|
}
|
|
influences[i] >>= 1;
|
|
}
|
|
for (r8veritas::index i = 0; i < CELL_SIZE; i++) {
|
|
if (influences[i] == 0) {
|
|
new_truthtable.first = operate_ins(new_truthtable.first, {0, i}).first;
|
|
}
|
|
}
|
|
return (new_truthtable);
|
|
}
|
|
|
|
private:
|
|
// Expand frontier[begin, end) into `next`, single-threaded.
|
|
// Returns true if the target state was produced.
|
|
bool expand_serial(size_t begin, size_t end,
|
|
const r8veritas::truthtable &truthtable) {
|
|
for (size_t i = begin; i < end; i++) {
|
|
r8veritas::stat_ref last_stat = frontier[i];
|
|
for (const auto &j : all_ins) {
|
|
r8veritas::stat next_stat = operate_stat(*last_stat, j);
|
|
size_t s = shard_of(next_stat);
|
|
std::lock_guard<std::mutex> g(pool_locks[s]);
|
|
auto [it, inserted] = pool_shards[s].insert(std::move(next_stat));
|
|
r8veritas::stat_ref next_ref = &*it;
|
|
if (next_ref == truthtable.second) {
|
|
// Record the target's parent BEFORE returning. The target value is
|
|
// usually already in the pool (pre-inserted by generate_truthtable),
|
|
// so `inserted` is false and the gated insert below would skip it —
|
|
// leaving track_path() with a missing entry (infinite loop).
|
|
visited_op.insert(
|
|
{next_ref, {last_stat, r8veritas::ins_bytecode(j)}});
|
|
return true;
|
|
}
|
|
if (inserted) {
|
|
visited_op.insert(
|
|
{next_ref, {last_stat, r8veritas::ins_bytecode(j)}});
|
|
next.push_back(next_ref);
|
|
}
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
// Expand frontier[begin, end), multi-threaded. Each thread appends its
|
|
// newly discovered states to thread_next[tid]. found is set (relaxed) the
|
|
// moment any thread produces the target; other threads bail between states.
|
|
void expand_parallel(size_t begin, size_t end, size_t tid,
|
|
const r8veritas::truthtable &truthtable,
|
|
std::atomic<bool> &found) {
|
|
for (size_t i = begin; i < end; i++) {
|
|
if (found.load(std::memory_order_relaxed)) {
|
|
return;
|
|
}
|
|
r8veritas::stat_ref last_stat = frontier[i];
|
|
for (const auto &j : all_ins) {
|
|
r8veritas::stat next_stat = operate_stat(*last_stat, j);
|
|
size_t s = shard_of(next_stat);
|
|
std::lock_guard<std::mutex> g(pool_locks[s]);
|
|
auto [it, inserted] = pool_shards[s].insert(std::move(next_stat));
|
|
r8veritas::stat_ref next_ref = &*it;
|
|
if (next_ref == truthtable.second) {
|
|
// Record the target's parent before signalling found (same reason
|
|
// as expand_serial: target is usually already pooled, so the
|
|
// gated insert below would skip it).
|
|
std::lock_guard<std::mutex> g2(visited_op_lock);
|
|
visited_op.insert(
|
|
{next_ref, {last_stat, r8veritas::ins_bytecode(j)}});
|
|
found.store(true, std::memory_order_relaxed);
|
|
}
|
|
if (inserted) {
|
|
std::lock_guard<std::mutex> g2(visited_op_lock);
|
|
visited_op.insert(
|
|
{next_ref, {last_stat, r8veritas::ins_bytecode(j)}});
|
|
thread_next[tid].push_back(next_ref);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
public:
|
|
bool bfs(const r8veritas::truthtable &truthtable,
|
|
bool enable_debug_output = false, r8veritas::index layer = 1,
|
|
size_t nthreads = 0) {
|
|
|
|
if (nthreads == 0) {
|
|
nthreads = std::thread::hardware_concurrency();
|
|
if (nthreads == 0)
|
|
nthreads = 1;
|
|
}
|
|
|
|
if (layer == 1) {
|
|
frontier.clear();
|
|
next.clear();
|
|
frontier.push_back(truthtable.first);
|
|
// No upfront reserve: a fixed 32x64K-slot reservation costs ~10ms on
|
|
// tiny problems (copy/and) for zero benefit — unordered_set rehash is
|
|
// amortized O(1) and node pointers stay stable, so mid-search growth
|
|
// is safe. Big searches pay a few rehashes instead.
|
|
}
|
|
|
|
if (frontier.empty()) {
|
|
return (false);
|
|
}
|
|
|
|
for (;; ++layer) {
|
|
r8veritas::index fsz = frontier.size();
|
|
if (enable_debug_output)
|
|
std::cout << "LAYER=" << layer << ",stats_size=" << fsz << std::endl;
|
|
|
|
if (fsz < PARALLEL_THRESHOLD || nthreads <= 1) {
|
|
if (expand_serial(0, fsz, truthtable)) {
|
|
return true;
|
|
}
|
|
} else {
|
|
std::atomic<bool> found{false};
|
|
size_t T = std::min(nthreads, fsz);
|
|
thread_next.assign(T, {});
|
|
std::vector<std::thread> ths;
|
|
ths.reserve(T);
|
|
size_t per = (fsz + T - 1) / T;
|
|
for (size_t t = 0; t < T; t++) {
|
|
size_t b = t * per;
|
|
size_t e = std::min(fsz, b + per);
|
|
if (b >= e) {
|
|
break;
|
|
}
|
|
ths.emplace_back([this, b, e, t, &truthtable, &found]() {
|
|
expand_parallel(b, e, t, truthtable, found);
|
|
});
|
|
}
|
|
for (auto &th : ths) {
|
|
th.join();
|
|
}
|
|
if (found.load()) {
|
|
return true;
|
|
}
|
|
for (const auto &v : thread_next) {
|
|
next.insert(next.end(), v.begin(), v.end());
|
|
}
|
|
}
|
|
|
|
if (next.empty()) {
|
|
return false;
|
|
}
|
|
frontier.swap(next);
|
|
next.clear();
|
|
}
|
|
}
|
|
|
|
r8veritas::path track_path(const r8veritas::truthtable &truthtable) {
|
|
r8veritas::path p;
|
|
for (auto tmp_stat = truthtable.second; tmp_stat != truthtable.first;) {
|
|
p.push(visited_op[tmp_stat]);
|
|
tmp_stat = p.top().first;
|
|
}
|
|
return p;
|
|
}
|
|
};
|
|
|
|
#endif
|