%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.
296 lines
8.9 KiB
C++
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
|