Files
R8Forge/include/r8forge/r8veritas_phase.hh
dsh da16c111cf Add a layout independent metric so a result can be cached and reused
%synth could optimise the real tape characters, but that price depends on where
the cells sit, so the answer was only good for one layout and the cache could
only be shared between call sites with the same addresses.

  metric chars   tape characters including the .tp walk   layout dependent
  metric flat    characters without the walk             layout independent
  metric blocks  block count                             layout independent

'flat' is the step-free mode: it counts biz/flb/rnz and the ops, ignores how
far apart the cells are, so one search result and one cache entry serve every
layout.  The price is a slightly longer tape when the layout happens to suit a
different program: 90 characters for chars, 95 for flat on the full adder.

Checked: examples/full_add_flat.r8asm hits the cache on the second run, and the
same block with 'layout 0 2 4 6 8 10' added hits the *same* entry and emits a
byte-identical tape (the key drops the layout for the layout-free metrics).
Both pass the eight combination check.
2026-11-06 18:39:49 +08:00

296 lines
8.9 KiB
C++

// Phase-parallel tape search.
//
// The sequential search is memory bound on its hash table, so this version does
// not cut the graph up (splitting by first block duplicated the whole middle:
// three to four times the work, sixteen gigabytes -- see the commit before).
// Instead it splits each Dial bucket across threads:
//
// 1. the table is read only for the whole bucket, so threads probe it with no
// locking at all -- that is ~99.7% of the work, because only about one edge
// in four hundred lands on a state we have not seen yet
// 2. misses and dist improvements are buffered per thread and applied by one
// serial pass once the bucket is finished
//
// Cost order is untouched, so the answer is the one the sequential search gives.
#ifndef R8VERITAS_PHASE
#define R8VERITAS_PHASE
#include <algorithm>
#include <array>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <string>
#include <system_error>
#include <thread>
#include <vector>
namespace r8par {
template <int N, int K> struct engine {
static constexpr int M = 1 << K;
static constexpr int KEYW = (N * M + 63) / 64;
static constexpr uint64_t PMASK =
(M >= 64) ? ~uint64_t(0) : ((uint64_t(1) << (M & 63)) - 1);
using key = std::array<uint64_t, KEYW>;
static uint64_t get(const key &k, int b) {
const int off = b * M;
return (k[off >> 6] >> (off & 63)) & PMASK;
}
static void put(key &k, int b, uint64_t v) {
const int off = b * M;
k[off >> 6] =
(k[off >> 6] & ~(PMASK << (off & 63))) | ((v & PMASK) << (off & 63));
}
static key step(const key &k, int sacrifice, int mask, bool or_mode) {
key n = k;
const uint64_t c = get(k, sacrifice);
put(n, sacrifice, 0);
for (int b = 0; b < N; b++)
if (mask & (1 << b))
put(n, b, or_mode ? (get(k, b) | c) : (get(k, b) ^ c));
return n;
}
static uint64_t hash(const key &k) {
uint64_t h = 0xcbf29ce484222325ULL;
for (int i = 0; i < KEYW; i++) {
h ^= k[i];
h *= 0x100000001b3ULL;
h ^= h >> 29;
h *= 0xbf58476d1ce4e5b9ULL;
h ^= h >> 32;
}
return h;
}
};
// cost of one block on the tape (same model as r8veritas::solve_cost)
// N has to be size_t here: std::array<int, N> deduces N as size_t, and clang
// refuses to convert that to an int non-type parameter (MSVC lets it pass)
template <std::size_t N>
inline int block_cost(const std::array<int, N> &addr, int sacrifice, int mask,
bool or_mode, bool count_travel) {
int lo = addr[size_t(sacrifice)], hi = lo, cnt = 0;
for (int b = 0; b < N; b++)
if (mask & (1 << b)) {
cnt++;
lo = std::min(lo, addr[size_t(b)]);
hi = std::max(hi, addr[size_t(b)]);
}
// count_travel = false drops the .tp walk, which is the only part of the
// price that depends on where the cells sit: the result then works for any
// layout and can be cached once for all call sites
return 3 + (count_travel ? 2 * (hi - lo) : 0) + cnt * (or_mode ? 4 : 1);
}
struct result_t {
bool found = false;
bool proven = false;
int cost = 0;
std::vector<std::array<int, 3>> prog;
size_t states = 0;
double seconds = 0;
std::string message;
};
template <int N, int K>
result_t search(const typename engine<N, K>::key &start,
const typename engine<N, K>::key &goal,
const std::vector<std::array<int, 3>> &ins,
const std::array<int, N> &addr, int limit, unsigned nthreads,
size_t max_states, bool count_travel = true) {
using E = engine<N, K>;
using key = typename E::key;
result_t r;
const auto t0 = std::chrono::steady_clock::now();
auto finish = [&]() {
r.seconds =
std::chrono::duration<double>(std::chrono::steady_clock::now() - t0)
.count();
return r;
};
const size_t ni = ins.size();
std::vector<int> w(ni);
int wmax = 0;
for (size_t i = 0; i < ni; i++) {
w[i] = block_cost(addr, ins[i][0], ins[i][1], ins[i][2] != 0, count_travel);
if (w[i] > wmax)
wmax = w[i];
}
if (nthreads < 1)
nthreads = 1;
// ---- the table; only the serial pass ever writes to it
std::vector<key> keys;
std::vector<uint16_t> dists;
std::vector<uint32_t> pars;
std::vector<uint16_t> hows;
std::vector<int32_t> tab(size_t(1) << 20, -1);
size_t tabmask = tab.size() - 1;
auto find_id = [&](const key &k) -> int32_t {
size_t j = size_t(E::hash(k)) & tabmask;
while (tab[j] >= 0) {
if (keys[size_t(tab[j])] == k)
return tab[j];
j = (j + 1) & tabmask;
}
return -1;
};
auto rehash = [&]() {
tab.assign(tab.size() * 2, -1);
tabmask = tab.size() - 1;
for (size_t id = 0; id < keys.size(); id++) {
size_t j = size_t(E::hash(keys[id])) & tabmask;
while (tab[j] >= 0)
j = (j + 1) & tabmask;
tab[j] = int32_t(id);
}
};
auto add = [&](const key &k, int d, uint32_t parent, uint16_t i) -> uint32_t {
if ((keys.size() + 1) * 10 > (tabmask + 1) * 7)
rehash();
const uint32_t id = uint32_t(keys.size());
keys.push_back(k);
dists.push_back(uint16_t(d));
pars.push_back(parent);
hows.push_back(i);
size_t j = size_t(E::hash(k)) & tabmask;
while (tab[j] >= 0)
j = (j + 1) & tabmask;
tab[j] = int32_t(id);
return id;
};
std::vector<std::vector<uint32_t>> ring(size_t(wmax) + 1);
add(start, 0, 0, 0xFFFE);
ring[0].push_back(0);
struct cand {
key k;
uint32_t parent;
uint16_t ins;
int cost;
};
struct upd {
uint32_t id;
uint32_t parent;
uint16_t ins;
int cost;
};
std::vector<std::vector<cand>> cbuf(nthreads);
std::vector<std::vector<upd>> ubuf(nthreads);
auto backtrack = [&](uint32_t id) {
std::vector<std::array<int, 3>> p;
while (hows[id] != 0xFFFE) {
p.push_back(ins[hows[id]]);
id = pars[id];
}
std::reverse(p.begin(), p.end());
return p;
};
int d = 0;
while (d <= limit) {
auto &bucket = ring[size_t(d) % ring.size()];
if (bucket.empty()) {
d++; // plain Dial: step one unit at a time
continue;
}
// ---- if the goal is in this bucket, that is the cheapest way to it
for (uint32_t id : bucket)
if (dists[id] == d && keys[id] == goal) {
r.prog = backtrack(id);
r.cost = d;
r.found = r.proven = true;
r.states = keys.size();
return finish();
}
// ---- parallel probe phase: the table only gets read
for (auto &b : cbuf)
b.clear();
for (auto &b : ubuf)
b.clear();
{
auto body = [&](unsigned t) {
for (size_t j = t; j < bucket.size(); j += nthreads) {
const uint32_t id = bucket[j];
if (dists[id] != d)
continue; // stale entry
const key cur = keys[id];
for (size_t i = 0; i < ni; i++) {
if (E::get(cur, ins[i][0]) == 0)
continue;
const int nd = d + w[i];
if (nd > limit)
continue;
const key nx = E::step(cur, ins[i][0], ins[i][1], ins[i][2] != 0);
const int32_t f = find_id(nx);
if (f < 0)
cbuf[t].push_back({nx, id, uint16_t(i), nd});
else if (nd < dists[size_t(f)])
ubuf[t].push_back({uint32_t(f), id, uint16_t(i), nd});
}
}
};
// a stalled or unavailable thread runtime must not lose the search: if
// spawning fails, carry on with however many threads actually started
std::vector<std::thread> pool;
try {
for (unsigned t = 1; t < nthreads; t++)
pool.emplace_back(body, t);
} catch (const std::system_error &) {
// fall through: run on the threads we have
}
body(0);
for (auto &th : pool)
th.join();
}
// ---- serial apply phase
for (unsigned t = 0; t < nthreads; t++) {
for (const auto &c : cbuf[t]) {
const int32_t f = find_id(c.k);
if (f < 0) {
const uint32_t id = add(c.k, c.cost, c.parent, c.ins);
ring[size_t(c.cost) % ring.size()].push_back(id);
} else if (c.cost < dists[size_t(f)]) {
dists[size_t(f)] = uint16_t(c.cost);
pars[size_t(f)] = c.parent;
hows[size_t(f)] = c.ins;
ring[size_t(c.cost) % ring.size()].push_back(uint32_t(f));
}
}
for (const auto &u : ubuf[t]) {
if (u.cost < dists[size_t(u.id)]) {
dists[size_t(u.id)] = uint16_t(u.cost);
pars[size_t(u.id)] = u.parent;
hows[size_t(u.id)] = u.ins;
ring[size_t(u.cost) % ring.size()].push_back(u.id);
}
}
}
bucket.clear();
if (keys.size() > max_states) {
r.message = "state budget exhausted before the search was complete";
r.states = keys.size();
return finish();
}
}
r.states = keys.size();
r.proven = true;
r.message = "no program with cost <= " + std::to_string(limit);
return finish();
}
} // namespace r8par
#endif