Files

504 lines
19 KiB
C++

#include "evo/core/random.hpp"
#include <entt/entt.hpp>
#include <algorithm>
#include <array>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <exception>
#include <expected>
#include <iostream>
#include <memory_resource>
#include <span>
#include <stdexcept>
#include <string_view>
#include <vector>
namespace {
constexpr std::uint64_t max_id = 200'000;
constexpr std::size_t max_count = 100'000;
constexpr std::uint64_t seed = 123456;
void require(bool condition, const char* message) {
if (!condition) {
throw std::runtime_error(message);
}
}
struct Record {
std::uint64_t id{}, counter{}, motion{}, capture{};
std::uint8_t mask{};
bool operator==(const Record&) const = default;
};
struct State {
std::uint64_t high_water{};
std::vector<Record> rows;
bool operator==(const State&) const = default;
};
bool valid(const Record& row) {
return row.id > 0 && row.id <= max_id && row.mask <= 3 &&
((row.mask & 1U) != 0 || row.motion == 0) && ((row.mask & 2U) != 0 || row.capture == 0);
}
Record initial(std::uint64_t id, std::uint64_t world_seed, std::uint32_t density) {
evo::Random rng{world_seed ^ id};
const bool motion = rng.next() % 100 < density;
const bool capture = rng.next() % 100 < density;
return {id, id * 7, motion ? 2U : 0U, capture ? 5U : 0U,
static_cast<std::uint8_t>((motion ? 1U : 0U) | (capture ? 2U : 0U))};
}
// Records requested container bytes, not allocator bookkeeping or process RSS.
class CountingResource final : public std::pmr::memory_resource {
public:
std::size_t live{}, peak{}, calls{};
private:
void* do_allocate(std::size_t bytes, std::size_t alignment) override {
auto* result = std::pmr::new_delete_resource()->allocate(bytes, alignment);
live += bytes;
peak = std::max(peak, live);
++calls;
return result;
}
void do_deallocate(void* pointer, std::size_t bytes, std::size_t alignment) override {
if (bytes > live) {
std::terminate();
}
live -= bytes;
std::pmr::new_delete_resource()->deallocate(pointer, bytes, alignment);
}
bool do_is_equal(const std::pmr::memory_resource& other) const noexcept override {
return this == &other;
}
};
class Rows {
public:
explicit Rows(std::pmr::memory_resource& resource) : rows_{&resource} {}
void create(Record row) {
require(valid(row) && row.id > high_water_ && rows_.size() < max_count,
"Invalid row creation");
rows_.push_back(row);
high_water_ = row.id;
}
bool remove(std::uint64_t id) {
const auto it = std::ranges::lower_bound(rows_, id, {}, &Record::id);
if (it == rows_.end() || it->id != id) {
return false;
}
rows_.erase(it);
return true;
}
void tick() {
for (auto& row : rows_) {
row.counter += 3;
}
for (auto& row : rows_) {
if ((row.mask & 1U) != 0) {
row.counter += row.motion++;
}
}
for (auto& row : rows_) {
if ((row.mask & 2U) != 0) {
row.counter += row.capture;
row.capture += 2;
}
}
}
State state() const {
return {high_water_, {rows_.begin(), rows_.end()}};
}
void restore_high_water(std::uint64_t value) {
require(value >= high_water_ && value <= max_id, "Invalid row high-water mark");
high_water_ = value;
}
private:
std::pmr::vector<Record> rows_;
std::uint64_t high_water_{};
};
struct Identity {
std::uint64_t value;
};
struct Counter {
std::uint64_t value;
};
struct Motion {
std::uint64_t rate;
};
struct Capture {
std::uint64_t rate;
};
// EnTT passes storage allocators explicitly. A standard allocator-traits bridge
// avoids polymorphic_allocator injecting a second allocator during construction.
template <typename T> struct ResourceAllocator {
using value_type = T;
std::pmr::memory_resource* resource = std::pmr::get_default_resource();
ResourceAllocator() = default;
explicit ResourceAllocator(std::pmr::memory_resource& value) : resource{&value} {}
template <typename U>
ResourceAllocator(const ResourceAllocator<U>& other) noexcept : resource{other.resource} {}
T* allocate(std::size_t count) {
return std::pmr::polymorphic_allocator<T>{resource}.allocate(count);
}
void deallocate(T* pointer, std::size_t count) noexcept {
std::pmr::polymorphic_allocator<T>{resource}.deallocate(pointer, count);
}
template <typename U> bool operator==(const ResourceAllocator<U>& other) const noexcept {
return resource->is_equal(*other.resource);
}
};
class EnttStore {
public:
explicit EnttStore(std::pmr::memory_resource& resource)
: registry_{ResourceAllocator<entt::entity>{resource}}, handles_{&resource} {}
void create(Record row) {
require(valid(row) && row.id > high_water_ && count_ < max_count, "Invalid EnTT creation");
const auto entity = registry_.create();
registry_.emplace<Identity>(entity, row.id);
registry_.emplace<Counter>(entity, row.counter);
if ((row.mask & 1U) != 0) {
registry_.emplace<Motion>(entity, row.motion);
}
if ((row.mask & 2U) != 0) {
registry_.emplace<Capture>(entity, row.capture);
}
handles_.resize(static_cast<std::size_t>(row.id + 1), entt::null);
handles_[static_cast<std::size_t>(row.id)] = entity;
high_water_ = row.id;
++count_;
}
bool remove(std::uint64_t id) {
if (id >= handles_.size()) {
return false;
}
auto& entity = handles_[static_cast<std::size_t>(id)];
if (entity == entt::null) {
return false;
}
registry_.destroy(entity);
entity = entt::null;
--count_;
return true;
}
void tick() {
for (auto&& [entity, counter] : registry_.view<Counter>().each()) {
static_cast<void>(entity);
counter.value += 3;
}
for (auto&& [entity, counter, motion] : registry_.view<Counter, Motion>().each()) {
static_cast<void>(entity);
counter.value += motion.rate++;
}
for (auto&& [entity, counter, capture] : registry_.view<Counter, Capture>().each()) {
static_cast<void>(entity);
counter.value += capture.rate;
capture.rate += 2;
}
}
State state() const {
State result{high_water_, {}};
result.rows.reserve(count_);
for (auto&& [entity, identity, counter] : registry_.view<Identity, Counter>().each()) {
const auto* motion = registry_.try_get<Motion>(entity);
const auto* capture = registry_.try_get<Capture>(entity);
result.rows.push_back(
{identity.value, counter.value, motion ? motion->rate : 0,
capture ? capture->rate : 0,
static_cast<std::uint8_t>((motion ? 1U : 0U) | (capture ? 2U : 0U))});
}
std::ranges::sort(result.rows, {}, &Record::id);
return result;
}
void restore_high_water(std::uint64_t value) {
require(value >= high_water_ && value <= max_id, "Invalid EnTT high-water mark");
high_water_ = value;
}
private:
entt::basic_registry<entt::entity, ResourceAllocator<entt::entity>> registry_;
std::pmr::vector<entt::entity> handles_;
std::uint64_t high_water_{};
std::size_t count_{};
};
using Bytes = std::vector<std::uint8_t>;
constexpr std::array<std::uint8_t, 8> magic{'E', 'C', 'S', 'P', 'R', 'F', '0', '1'};
void put(Bytes& bytes, std::uint64_t value) {
for (unsigned index = 0; index < 8; ++index) {
bytes.push_back(static_cast<std::uint8_t>(value & 255U));
value >>= 8U;
}
}
Bytes encode(const State& state) {
Bytes bytes{magic.begin(), magic.end()};
bytes.reserve(24 + state.rows.size() * 33);
put(bytes, state.high_water);
put(bytes, state.rows.size());
for (const auto& row : state.rows) {
put(bytes, row.id);
put(bytes, row.counter);
put(bytes, row.motion);
put(bytes, row.capture);
bytes.push_back(row.mask);
}
return bytes;
}
enum class DecodeError : std::uint8_t { invalid };
std::expected<State, DecodeError> decode(std::span<const std::uint8_t> bytes) {
if (bytes.size() < 24 || bytes.size() > 24 + 33 * max_count ||
!std::ranges::equal(bytes.first(8), magic)) {
return std::unexpected(DecodeError::invalid);
}
std::size_t offset = 8;
const auto get = [&]() {
std::uint64_t value = 0;
for (unsigned shift = 0; shift < 64; shift += 8) {
value |= static_cast<std::uint64_t>(bytes[offset++]) << shift;
}
return value;
};
const auto high_water = get();
const auto count = get();
if (high_water > max_id || count > max_count || bytes.size() != 24 + count * 33) {
return std::unexpected(DecodeError::invalid);
}
State result{high_water, {}};
result.rows.reserve(static_cast<std::size_t>(count));
std::uint64_t previous = 0;
for (std::uint64_t index = 0; index < count; ++index) {
Record row{get(), get(), get(), get(), bytes[offset++]};
if (!valid(row) || row.id <= previous || row.id > high_water) {
return std::unexpected(DecodeError::invalid);
}
previous = row.id;
result.rows.push_back(row);
}
return result;
}
template <typename Store> void restore(Store& store, const Bytes& bytes) {
const auto state = decode(bytes);
require(state.has_value(), "Rejected experimental snapshot");
for (const auto row : state->rows) {
store.create(row);
}
store.restore_high_water(state->high_water);
}
template <typename Store>
void fill(Store& store, std::uint64_t count, std::uint64_t world_seed, std::uint32_t density) {
for (std::uint64_t id = 1; id <= count; ++id) {
store.create(initial(id, world_seed, density));
}
}
template <typename Store> void advance(Store& store, std::uint64_t ticks) {
for (std::uint64_t tick = 0; tick < ticks; ++tick) {
store.tick();
}
}
template <typename Store>
void churn(Store& store, std::uint64_t count, std::uint64_t world_seed, std::uint32_t density) {
for (std::uint64_t id = 10; id <= count; id += 10) {
require(store.remove(id), "Churn removal failed");
}
for (std::uint64_t id = count + 1; id <= count + count / 10; ++id) {
store.create(initial(id, world_seed, density));
}
}
Record closed_form(Record row, std::uint64_t ticks) {
row.counter += 3 * ticks;
if ((row.mask & 1U) != 0) {
row.counter += ticks * row.motion + ticks * (ticks - 1) / 2;
row.motion += ticks;
}
if ((row.mask & 2U) != 0) {
row.counter += ticks * row.capture + ticks * (ticks - 1);
row.capture += 2 * ticks;
}
return row;
}
template <typename Store> void verify_store() {
CountingResource memory;
{
Store store{memory};
store.create({1, 10, 2, 5, 3});
advance(store, 3);
require(store.state().rows == std::vector<Record>{{1, 49, 5, 11, 3}},
"Hand-computed fixture mismatch");
bool duplicate_rejected = false;
try {
store.create({1, 0, 0, 0, 0});
} catch (const std::runtime_error&) {
duplicate_rejected = true;
}
require(duplicate_rejected, "Duplicate ID accepted");
require(store.remove(1) && !store.remove(1), "Stale identity accepted");
const auto bytes = encode(store.state());
Store restored{memory};
restore(restored, bytes);
require(restored.state().high_water == 1, "Deleted high-water mark lost");
bool reused = true;
try {
restored.create({1, 0, 0, 0, 0});
} catch (const std::runtime_error&) {
reused = false;
}
require(!reused, "Restore allowed ID reuse");
restored.create({2, 0, 0, 0, 0});
}
require(memory.live == 0, "Store allocations leaked");
}
void verify() {
verify_store<Rows>();
verify_store<EnttStore>();
for (const auto count : {0U, 1U, 103U}) {
for (const auto density : {0U, 10U, 100U}) {
for (std::uint64_t test_seed = 0; test_seed < 8; ++test_seed) {
CountingResource rows_memory, entt_memory;
{
Rows rows{rows_memory};
EnttStore entt{entt_memory};
fill(rows, count, test_seed, density);
fill(entt, count, test_seed, density);
advance(rows, 17);
advance(entt, 17);
require(rows.state() == entt.state(), "Store state differs after updates");
for (const auto row : rows.state().rows) {
require(row == closed_form(initial(row.id, test_seed, density), 17),
"Closed-form result differs");
}
churn(rows, count, test_seed, density);
churn(entt, count, test_seed, density);
const auto bytes = encode(rows.state());
require(bytes == encode(entt.state()), "Canonical bytes differ after churn");
Rows resumed_rows{rows_memory};
EnttStore resumed_entt{entt_memory};
restore(resumed_rows, bytes);
restore(resumed_entt, bytes);
advance(rows, 5);
advance(entt, 5);
advance(resumed_rows, 5);
advance(resumed_entt, 5);
require(rows.state() == entt.state() && rows.state() == resumed_rows.state() &&
rows.state() == resumed_entt.state(),
"Restored continuation differs");
}
require(rows_memory.live == 0 && entt_memory.live == 0, "Unbalanced allocations");
}
}
}
auto bytes = encode(State{1, {{1, 0, 0, 0, 0}}});
require(decode(bytes).has_value(), "Valid codec fixture rejected");
bytes.back() = 4;
require(!decode(bytes), "Invalid mask accepted");
bytes.pop_back();
require(!decode(bytes), "Truncated input accepted");
require(!decode(encode(State{2, {{1, 0, 0, 0, 0}, {1, 0, 0, 0, 0}}})),
"Duplicate snapshot IDs accepted");
require(!decode(encode(State{0, {{1, 0, 0, 0, 0}}})), "Invalid watermark accepted");
require(!decode(encode(State{1, {{1, 0, 1, 0, 0}}})), "Absent capability payload accepted");
bytes = encode(State{});
bytes[0] = 0;
require(!decode(bytes), "Unknown format accepted");
bytes = encode(State{});
bytes[16] = 255;
require(!decode(bytes), "Invalid count/length accepted");
}
template <typename Function> double timed(Function&& function) {
const auto start = std::chrono::steady_clock::now();
function();
return std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
}
std::uint64_t fingerprint(const Bytes& bytes) {
std::uint64_t result = 14695981039346656037ULL;
for (const auto value : bytes) {
result = (result ^ value) * 1099511628211ULL;
}
return result;
}
template <typename Store>
Bytes measure(std::string_view name, std::uint64_t count, std::uint32_t density, int sample) {
CountingResource memory, restore_memory;
Bytes bytes;
{
Store store{memory};
const auto create_seconds = timed([&] { fill(store, count, seed, density); });
const auto tick_seconds = timed([&] { advance(store, 100); });
const auto churn_seconds = timed([&] { churn(store, count, seed, density); });
const auto export_seconds = timed([&] { bytes = encode(store.state()); });
Store restored{restore_memory};
const auto restore_seconds = timed([&] { restore(restored, bytes); });
require(encode(restored.state()) == bytes, "Measured restore differs");
if (sample >= 0) {
std::cout << "{\"store\":\"" << name << "\",\"entities\":" << count
<< ",\"density_percent\":" << density << ",\"seed\":" << seed
<< ",\"ticks\":100,\"sample\":" << sample
<< ",\"create_s\":" << create_seconds << ",\"tick_s\":" << tick_seconds
<< ",\"churn_s\":" << churn_seconds << ",\"export_s\":" << export_seconds
<< ",\"restore_s\":" << restore_seconds << ",\"live_bytes\":" << memory.live
<< ",\"peak_bytes\":" << memory.peak << ",\"allocations\":" << memory.calls
<< ",\"hash\":\"" << std::hex << fingerprint(bytes) << std::dec << "\"}\n";
}
}
require(memory.live == 0 && restore_memory.live == 0, "Measured store allocations leaked");
return bytes;
}
} // namespace
int main(int argc, char** argv) try {
if (argc != 2 ||
(std::string_view{argv[1]} != "--verify" && std::string_view{argv[1]} != "--measure")) {
std::cerr << "Usage: evo-ecs-experiment --verify|--measure\n";
return 2;
}
verify();
if (std::string_view{argv[1]} == "--verify") {
std::cout << "ECS experiment contracts passed\n";
return 0;
}
std::cout << "{\"experiment\":\"ecs-storage-v1\",\"entt\":\"4.0.0\",\"compiler\":\""
#if defined(__clang__)
<< "Clang " << __clang_version__
#elif defined(_MSC_VER)
<< "MSVC " << _MSC_VER
#elif defined(__GNUC__)
<< "GCC " << __VERSION__
#endif
<< "\",\"build\":\""
#if defined(NDEBUG)
<< "release"
#else
<< "debug"
#endif
<< "\"}\n";
for (const auto count : {1'000U, 10'000U}) {
for (const auto density : {10U, 100U}) {
for (int sample = -1; sample < 7; ++sample) {
Bytes rows, entt;
if (sample % 2 == 0) {
rows = measure<Rows>("rows", count, density, sample);
entt = measure<EnttStore>("entt4", count, density, sample);
} else {
entt = measure<EnttStore>("entt4", count, density, sample);
rows = measure<Rows>("rows", count, density, sample);
}
require(rows == entt, "Measured adapters produced different canonical bytes");
}
}
}
return 0;
} catch (const std::exception& error) {
try {
std::cerr << error.what() << '\n';
} catch (...) {
// Reporting failure must not let an exception escape the process boundary.
return 1;
}
return 1;
} catch (...) {
return 1;
}