Lookich/UniversalContainer
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
UniversalContainer/tests/adaptive_sequence_tests.cpp
T
Efim Beshmenev 3770224eaf New adaptation policy
2026-08-13 23:42:26 +03:00

786 lines
28 KiB
C++
Raw Permalink Blame History

#include "universal_container/adaptive_sequence.hpp"
#include "universal_container/ring_block.hpp"
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <optional>
#include <random>
#include <stdexcept>
#include <string>
#include <vector>
namespace {
int failures = 0;
void expect(bool condition, const char* expression, int line) {
if (!condition) {
std::cerr << "FAIL line " << line << ": " << expression << '\n';
++failures;
}
}
#define EXPECT(expression) expect(static_cast<bool>(expression), #expression, __LINE__)
struct DeferredTransitionPolicy {
uc::TieredConfig target{8, 4, 2};
bool ready = false;
std::size_t decisions = 0;
std::size_t transitions = 0;
uc::StorageMode last_from = uc::StorageMode::vector;
uc::StorageMode last_to = uc::StorageMode::vector;
void observe(const uc::OperationSample& sample) noexcept {
if (sample.kind == uc::OperationKind::insert) {
ready = true;
}
}
[[nodiscard]] bool decision_ready() const noexcept { return ready; }
[[nodiscard]] std::optional<uc::AdaptationDecision>
recommended_decision(uc::StorageMode current,
std::size_t,
uc::TieredConfig) noexcept {
if (!ready) {
return std::nullopt;
}
ready = false;
++decisions;
if (current == uc::StorageMode::vector) {
return uc::AdaptationDecision{uc::StorageMode::tiered, target, 1.0};
}
return std::nullopt;
}
void on_transition(uc::StorageMode from,
uc::StorageMode to,
uc::TieredConfig active) noexcept {
++transitions;
last_from = from;
last_to = to;
target = active;
ready = false;
}
void reset() noexcept {
ready = false;
decisions = 0;
transitions = 0;
}
};
struct WraparoundHash {
[[nodiscard]] std::size_t operator()(std::uint32_t) const noexcept {
return std::numeric_limits<std::size_t>::max();
}
};
template <class Sequence, class Reference>
void expect_equal(const Sequence& sequence, const Reference& reference) {
EXPECT(sequence.size() == reference.size());
for (std::size_t i = 0; i < reference.size() && i < sequence.size(); ++i) {
EXPECT(sequence[i] == reference[i]);
}
}
void ring_block_offsets() {
uc::detail::RingBlock<int> block(8);
block.push_back(2);
block.push_back(3);
block.insert(0, 1);
block.insert(0, 0);
block.insert(2, 9);
EXPECT(block.offset() != 0);
const std::vector<int> expected{0, 1, 9, 2, 3};
for (std::size_t i = 0; i < expected.size(); ++i) {
EXPECT(block[i] == expected[i]);
}
EXPECT(block.erase(2) == 9);
EXPECT(block.erase(0) == 0);
EXPECT(block.size() == 3);
EXPECT(block[0] == 1 && block[1] == 2 && block[2] == 3);
}
void randomized_differential() {
uc::TieredConfig config{16, 4, 4};
uc::AdaptiveSequence<std::uint32_t> actual(config);
actual.force_tiered_mode();
std::vector<std::uint32_t> expected;
std::mt19937_64 random(0xC0FFEEULL);
for (std::size_t step = 0; step < 30'000; ++step) {
const auto operation = static_cast<unsigned>(random() % 5);
if (expected.empty() || operation == 0) {
const auto value = static_cast<std::uint32_t>(random());
const auto index = expected.empty() ? 0 : static_cast<std::size_t>(random() % (expected.size() + 1));
expected.insert(expected.begin() + static_cast<std::ptrdiff_t>(index), value);
actual.insert(index, value);
} else if (operation == 1) {
const auto index = static_cast<std::size_t>(random() % expected.size());
expected.erase(expected.begin() + static_cast<std::ptrdiff_t>(index));
actual.erase(index);
} else if (operation == 2) {
const auto value = static_cast<std::uint32_t>(random());
expected.push_back(value);
actual.push_back(value);
} else if (operation == 3) {
const auto index = static_cast<std::size_t>(random() % expected.size());
const auto value = static_cast<std::uint32_t>(random());
expected[index] = value;
actual.set(index, value);
} else {
const auto index = static_cast<std::size_t>(random() % expected.size());
EXPECT(actual[index] == expected[index]);
}
if (step % 251 == 0) {
expect_equal(actual, expected);
actual.force_vector_mode();
expect_equal(actual, expected);
actual.force_tiered_mode();
}
}
expect_equal(actual, expected);
}
void indexed_duplicates_and_ids() {
uc::AdaptiveSequence<std::uint32_t, true> values({8, 4, 3});
values.push_back(5);
values.push_back(8);
values.push_back(5);
values.push_back(3);
values.push_back(5);
const auto middle_id = values.id_at(2);
EXPECT(values.contains(5));
EXPECT(values.find_all(5) == std::vector<std::size_t>({0, 2, 4}));
values.force_tiered_mode();
values.insert(1, 5);
EXPECT(values.find_all(5) == std::vector<std::size_t>({0, 1, 3, 5}));
EXPECT(values.id_alive(middle_id));
values.force_tiered_mode({16, 4, 3});
EXPECT(values.find_all(5) == std::vector<std::size_t>({0, 1, 3, 5}));
EXPECT(values.id_alive(middle_id));
values[3] = 42;
EXPECT(values.find_all(5) == std::vector<std::size_t>({0, 1, 5}));
EXPECT(values.contains(42));
values.erase_by_id(middle_id);
EXPECT(!values.id_alive(middle_id));
EXPECT(!values.contains(42));
EXPECT(values.erase_all(5) == 3);
EXPECT(!values.contains(5));
EXPECT(values.size() == 2);
}
void indexed_ids_reuse_slots_without_reviving_stale_handles() {
uc::AdaptiveSequence<std::uint32_t, true> values;
for (std::uint32_t value = 0; value < 64; ++value) {
values.push_back(value);
}
const auto first_id = values.id_at(0);
const auto fixed_allocation = values.allocated_bytes();
for (std::uint32_t step = 0; step < 2'048; ++step) {
const auto retired = values.id_at(0);
values.erase_by_id(retired);
EXPECT(!values.id_alive(retired));
values.push_back(10'000 + step);
const auto replacement = values.id_at(values.size() - 1);
EXPECT(replacement != retired);
EXPECT(values.id_alive(replacement));
EXPECT(!values.id_alive(retired));
EXPECT(!values.id_alive(first_id));
EXPECT(values.find_one(10'000 + step) == values.size() - 1);
EXPECT(values.find_all_ids(10'000 + step)
== std::vector<decltype(values)::stable_id>({replacement}));
bool stale_rejected = false;
try {
values.erase_by_id(retired);
} catch (const std::out_of_range&) {
stale_rejected = true;
}
EXPECT(stale_rejected);
}
// Churn at a fixed live size must recycle the 64 metadata slots instead
// of growing the ID vector outside a logical-capacity boundary.
EXPECT(values.size() == 64);
EXPECT(values.capacity() == 64);
EXPECT(values.allocated_bytes() == fixed_allocation);
values.set(0, 0xf00d);
values.set(1, 0xf00d);
const auto duplicate_ids = values.find_all_ids(0xf00d);
EXPECT(duplicate_ids.size() == 2);
EXPECT(values.erase_all(0xf00d) == 2);
for (const auto id : duplicate_ids) {
EXPECT(!values.id_alive(id));
}
std::vector<decltype(values)::stable_id> ids_before_clear;
ids_before_clear.reserve(values.size());
for (std::size_t index = 0; index < values.size(); ++index) {
ids_before_clear.push_back(values.id_at(index));
}
values.clear();
for (const auto id : ids_before_clear) {
EXPECT(!values.id_alive(id));
}
EXPECT(!values.id_alive(decltype(values)::invalid_id));
values.push_back(77);
const auto after_clear = values.id_at(0);
EXPECT(values.id_alive(after_clear));
EXPECT(std::find(ids_before_clear.begin(), ids_before_clear.end(), after_clear)
== ids_before_clear.end());
}
void moved_from_sequences_are_reusable_and_assignment_invalidates_proxies() {
using Sequence = uc::AdaptiveSequence<std::uint32_t, true>;
Sequence source({8, 4, 3});
for (std::uint32_t value = 0; value < 64; ++value) {
source.push_back(value);
}
source.force_tiered_mode();
const auto transferred_id = source.id_at(17);
Sequence moved(std::move(source));
EXPECT(moved.size() == 64);
EXPECT(moved.id_alive(transferred_id));
EXPECT(source.empty());
EXPECT(source.capacity() == 0);
EXPECT(source.mode() == uc::StorageMode::vector);
EXPECT(!source.id_alive(transferred_id));
for (std::uint32_t value = 0; value < 40; ++value) {
source.push_back(1'000 + value);
}
EXPECT(source.size() == 40);
EXPECT(source.contains(1'039));
Sequence destination;
destination.push_back(7);
auto stale_after_move_assignment = destination[0];
destination = std::move(moved);
bool move_assignment_invalidated = false;
try {
stale_after_move_assignment = 8;
} catch (const std::logic_error&) {
move_assignment_invalidated = true;
}
EXPECT(move_assignment_invalidated);
EXPECT(destination.id_alive(transferred_id));
EXPECT(moved.empty());
moved.push_back(2'000);
EXPECT(moved.contains(2'000));
Sequence copy_source;
copy_source.push_back(99);
auto stale_after_copy_assignment = destination[0];
destination = copy_source;
bool copy_assignment_invalidated = false;
try {
stale_after_copy_assignment = 9;
} catch (const std::logic_error&) {
copy_assignment_invalidated = true;
}
EXPECT(copy_assignment_invalidated);
EXPECT(destination.size() == 1);
EXPECT(destination.contains(99));
}
void hash_backward_shift_handles_wraparound_and_duplicates() {
using Sequence = uc::AdaptiveSequence<std::uint32_t, true,
uc::ResizePolicy, WraparoundHash>;
Sequence values;
std::vector<Sequence::stable_id> ids;
for (std::uint32_t value = 0; value < 12; ++value) {
values.push_back(value);
ids.push_back(values.id_at(values.size() - 1));
}
values.push_back(5);
const auto duplicate_id = values.id_at(values.size() - 1);
const auto buckets = values.hash_bucket_count();
// Every distinct key starts in the final bucket, so the probe chain wraps
// through bucket zero. Removing a middle key must compact that chain
// without losing later keys or the duplicate list.
values.erase_by_id(ids[3]);
EXPECT(!values.id_alive(ids[3]));
for (std::uint32_t value = 0; value < 12; ++value) {
EXPECT(values.contains(value) == (value != 3));
}
EXPECT(values.find_all(5).size() == 2);
EXPECT(values.id_alive(ids[5]));
EXPECT(values.id_alive(duplicate_id));
values.erase_by_id(ids[5]);
EXPECT(values.contains(5));
EXPECT(values.find_all_ids(5)
== std::vector<Sequence::stable_id>({duplicate_id}));
EXPECT(values.hash_bucket_count() == buckets);
}
void indexed_proxy_detects_structural_invalidation() {
uc::AdaptiveSequence<std::uint32_t, true> values({8, 4, 2});
values.push_back(10);
values.push_back(20);
auto stale = values[1];
values.insert(0, 5);
bool invalidation_detected = false;
try {
stale = 99;
} catch (const std::logic_error&) {
invalidation_detected = true;
}
EXPECT(invalidation_detected);
const auto& read_only = values;
EXPECT(read_only[0] == 5);
EXPECT(read_only[1] == 10);
EXPECT(read_only[2] == 20);
}
void iterator_and_contiguous_contract() {
uc::AdaptiveSequence<int> values({8, 4, 3});
for (int i = 0; i < 100; ++i) {
values.push_back(i);
}
values.force_tiered_mode();
EXPECT(values.data() == nullptr);
std::int64_t sum = 0;
values.for_each([&](int value) { sum += value; });
EXPECT(sum == 4'950);
const auto contiguous = values.make_contiguous();
EXPECT(values.mode() == uc::StorageMode::vector);
EXPECT(contiguous.size() == 100);
EXPECT(contiguous[37] == 37);
auto iterator = values.begin();
EXPECT(*iterator == 0);
values.push_back(100);
bool invalidation_detected = false;
try {
(void)*iterator;
} catch (const std::logic_error&) {
invalidation_detected = true;
}
EXPECT(invalidation_detected);
}
struct NonTrivial {
std::string text;
std::uint64_t marker = 0;
NonTrivial(std::string value, std::uint64_t number)
: text(std::move(value)), marker(number) {}
NonTrivial(const NonTrivial&) = default;
NonTrivial(NonTrivial&&) noexcept = default;
NonTrivial& operator=(const NonTrivial&) = default;
NonTrivial& operator=(NonTrivial&&) noexcept = default;
~NonTrivial() { marker ^= 0; }
friend bool operator==(const NonTrivial&, const NonTrivial&) = default;
};
void non_trivial_values() {
uc::AdaptiveSequence<NonTrivial> values({4, 4, 2});
values.push_back(NonTrivial{"alpha", 1});
values.push_back(NonTrivial{"gamma", 3});
values.force_tiered_mode();
values.insert(1, NonTrivial{"beta", 2});
EXPECT(values[0].text == "alpha");
EXPECT(values[1].text == "beta");
EXPECT(values[2].text == "gamma");
values.erase(0);
EXPECT(values[0].marker == 2);
}
void tiered_shape_rebuild_preserves_order() {
uc::AdaptiveSequence<std::uint32_t> values({8, 4, 2});
std::vector<std::uint32_t> expected;
for (std::uint32_t i = 0; i < 257; ++i) {
values.push_back(i * 3 + 1);
expected.push_back(i * 3 + 1);
}
values.force_tiered_mode();
values.force_tiered_mode({64, 8, 3});
EXPECT(values.mode() == uc::StorageMode::tiered);
EXPECT(values.tiered_config() == (uc::TieredConfig{64, 8, 3}));
expect_equal(values, expected);
values.insert(129, 0xfeedu);
expected.insert(expected.begin() + 129, 0xfeedu);
values.force_tiered_mode({16, 4, 4});
EXPECT(values.tiered_config() == (uc::TieredConfig{16, 4, 4}));
expect_equal(values, expected);
values.force_tiered_mode({16, 4, 1});
values.force_tiered_mode({16, 4, 4});
expect_equal(values, expected);
EXPECT(values.policy().telemetry().tiered_rebuilds == 4);
EXPECT(values.policy().telemetry().tiered_leaf_rebuilds == 2);
EXPECT(values.policy().telemetry().tiered_directory_rebuilds == 2);
}
void capacity_boundaries_control_mode_and_geometry() {
uc::ResizePolicyConfig policy_config;
policy_config.minimum_tiered_size = 8;
uc::ResizePolicy policy(policy_config, {4, 4, 3});
uc::AdaptiveSequence<std::uint32_t> values({4, 4, 3}, policy);
for (std::uint32_t value = 0; value < 8; ++value) {
values.push_back(value);
}
EXPECT(values.capacity() == 8);
EXPECT(values.mode() == uc::StorageMode::vector);
// The ninth element is the next x2 capacity boundary. The representation
// and sqrt(N) leaf are selected as part of that single rebuild.
values.push_back(8);
EXPECT(values.capacity() == 16);
EXPECT(values.mode() == uc::StorageMode::tiered);
EXPECT(values.tiered_config().leaf_capacity == 4);
const auto leaf_at_16 = values.tiered_config().leaf_capacity;
for (std::uint32_t value = 9; value < 16; ++value) {
values.push_back(value);
EXPECT(values.tiered_config().leaf_capacity == leaf_at_16);
}
values.push_back(16);
EXPECT(values.capacity() == 32);
EXPECT(values.mode() == uc::StorageMode::tiered);
EXPECT(values.tiered_config().leaf_capacity == 5);
// Shrink is exactly one /2 step at 12.5% occupancy. At N=4 the same
// rebuild crosses the cutoff in the opposite direction.
while (values.size() > 4) {
values.erase(values.size() - 1);
}
EXPECT(values.capacity() == 16);
EXPECT(values.mode() == uc::StorageMode::vector);
expect_equal(values, std::vector<std::uint32_t>({0, 1, 2, 3}));
EXPECT(!values.adapt_now());
EXPECT(values.mode() == uc::StorageMode::vector);
}
void calibrated_default_cutoff_is_applied_at_resize() {
uc::AdaptiveSequence<std::uint32_t> values;
for (std::uint32_t value = 0; value < 4'096; ++value) {
values.push_back(value);
}
EXPECT(values.capacity() == 4'096);
EXPECT(values.mode() == uc::StorageMode::vector);
values.push_back(4'096);
EXPECT(values.capacity() == 8'192);
EXPECT(values.mode() == uc::StorageMode::tiered);
EXPECT(values.tiered_config().leaf_capacity == 65);
while (values.size() > 1'024) {
values.erase(values.size() - 1);
}
EXPECT(values.capacity() == 4'096);
EXPECT(values.mode() == uc::StorageMode::vector);
}
std::optional<uc::AdaptationDecision> shape_decision(
std::size_t n,
uc::TieredConfig current,
bool localized) {
uc::AdaptationConfig config;
config.evaluation_interval = 64;
config.minimum_observations = 64;
config.minimum_edit_observations = 64;
config.minimum_residency_operations = 0;
config.minimum_shape_residency_operations = 0;
config.minimum_shape_edit_fraction = 0.0;
config.required_confirmation_windows = 1;
config.minimum_tiered_size = 1;
config.forecast_operations = 1'000'000;
config.tiered_rebuild_safety = 0.0;
config.minimum_shape_improvement = 0.0;
config.vector_move_unit = 1.0;
uc::CostModelPolicy policy(config, current);
policy.on_transition(uc::StorageMode::vector,
uc::StorageMode::tiered,
current);
for (std::size_t i = 0; i < 64; ++i) {
const auto position = localized
? n / 2 + i % 17
: (i * 104'729 + 17) % n;
policy.observe({uc::OperationKind::insert, n, position, 1,
sizeof(std::uint32_t)});
}
return policy.recommended_decision(uc::StorageMode::tiered, n, current);
}
void forecast_horizon_is_bounded_by_observed_evidence() {
uc::AdaptationConfig config;
config.evaluation_interval = 64;
config.minimum_observations = 64;
config.minimum_residency_operations = 0;
config.required_confirmation_windows = 1;
config.forecast_operations = 10'000;
config.minimum_forecast_operations = 1;
config.forecast_growth_factor = 8.0;
const uc::TieredConfig tiered{64, 64, 4};
uc::CostModelPolicy policy(config, tiered);
for (std::size_t i = 0; i < 64; ++i) {
policy.observe({uc::OperationKind::insert, 10'000, i, 1,
sizeof(std::uint32_t)});
}
(void)policy.recommended_decision(uc::StorageMode::vector, 10'000, tiered);
EXPECT(policy.telemetry().last_forecast_operations == 512);
}
void confirmation_requires_consecutive_supporting_windows() {
uc::AdaptationConfig config;
config.evaluation_interval = 16;
config.edit_evaluation_interval = 8;
config.minimum_observations = 16;
config.minimum_edit_observations = 8;
config.minimum_residency_operations = 0;
config.minimum_tiered_size = 1;
config.required_confirmation_windows = 2;
config.forecast_operations = 1'000'000;
config.minimum_forecast_operations = 1;
config.vector_to_tiered_safety = 0.0;
config.vector_move_unit = 1.0;
config.tiered_move_unit = 0.01;
config.tiered_directory_unit = 0.0;
config.tiered_read_base = 2.0;
config.ewma_alpha = 1.0;
config.tiered_entry_edit_fraction = 0.50;
const uc::TieredConfig tiered{64, 64, 4};
uc::CostModelPolicy policy(config, tiered);
constexpr std::size_t n = 10'000;
auto edit_window = [&] {
for (std::size_t i = 0; i < 8; ++i) {
policy.observe({uc::OperationKind::insert, n, n / 2 + i,
1, sizeof(std::uint32_t)});
}
};
edit_window();
for (std::size_t i = 0; i < 16; ++i) {
policy.observe({uc::OperationKind::random_read, n, i,
1, sizeof(std::uint32_t)});
}
edit_window();
// Three windows accumulated, but the middle one contradicted the tiered
// proposal, so the final edit window starts a new streak of one.
EXPECT(!policy.recommended_decision(
uc::StorageMode::vector, n, tiered).has_value());
edit_window();
const auto confirmed = policy.recommended_decision(
uc::StorageMode::vector, n, tiered);
EXPECT(confirmed.has_value());
if (confirmed) {
EXPECT(confirmed->target == uc::StorageMode::tiered);
}
}
void stationary_phases_do_not_thrash() {
constexpr std::size_t operations = 30'000;
{
// This is the v12 failure shape: a stationary uniform edit phase at
// N=10k used to alternate vector/tiered dozens of times.
uc::AdaptationConfig config;
const uc::TieredConfig initial{512, 64, 4};
uc::CostModelPolicy policy(config, initial);
uc::StorageMode mode = uc::StorageMode::vector;
auto active = initial;
std::mt19937_64 random(0x7c4a'9e13'51d2'08b7ULL);
for (std::size_t observed = 0; observed < operations; observed += 4) {
const auto position = static_cast<std::size_t>(random() % 10'000);
policy.observe({uc::OperationKind::insert, 10'000, position,
4, sizeof(std::uint64_t)});
if (!policy.decision_ready()) {
continue;
}
const auto decision = policy.recommended_decision(mode, 10'000, active);
if (!decision) {
continue;
}
const auto previous = mode;
mode = decision->target;
if (mode == uc::StorageMode::tiered) {
active = decision->tiered_config;
}
policy.on_transition(previous, mode, active);
}
const auto& telemetry = policy.telemetry();
EXPECT(telemetry.vector_to_tiered + telemetry.tiered_to_vector <= 1);
}
{
// Starting tiered isolates shape selection. A stationary uniform
// phase may select a better leaf once, but must not bounce thereafter.
uc::AdaptationConfig config;
const uc::TieredConfig initial{512, 64, 4};
uc::CostModelPolicy policy(config, initial);
uc::StorageMode mode = uc::StorageMode::tiered;
auto active = initial;
policy.on_transition(uc::StorageMode::vector, mode, active);
std::mt19937_64 random(0xd1b5'4a32'09fc'77e1ULL);
for (std::size_t observed = 0; observed < operations; observed += 4) {
const auto position = static_cast<std::size_t>(random() % 100'000);
policy.observe({uc::OperationKind::insert, 100'000, position,
4, sizeof(std::uint64_t)});
if (!policy.decision_ready()) {
continue;
}
const auto decision = policy.recommended_decision(mode, 100'000, active);
if (!decision) {
continue;
}
const auto previous = mode;
mode = decision->target;
if (mode == uc::StorageMode::tiered) {
active = decision->tiered_config;
}
policy.on_transition(previous, mode, active);
}
const auto& telemetry = policy.telemetry();
EXPECT(telemetry.tiered_to_vector == 0);
EXPECT(telemetry.tiered_leaf_rebuilds <= 1);
}
}
void policy_changes_shape_with_scale_and_locality() {
const auto small_uniform = shape_decision(10'000, {512, 64, 4}, false);
EXPECT(small_uniform.has_value());
EXPECT(small_uniform->target == uc::StorageMode::tiered);
EXPECT(small_uniform->tiered_config.leaf_capacity <= 128);
const auto large_uniform = shape_decision(1'000'000, {64, 64, 4}, false);
EXPECT(large_uniform.has_value());
EXPECT(large_uniform->target == uc::StorageMode::tiered);
EXPECT(large_uniform->tiered_config.leaf_capacity >= 512);
const auto large_local = shape_decision(1'000'000, {1024, 64, 4}, true);
EXPECT(large_local.has_value());
EXPECT(large_local->target == uc::StorageMode::tiered);
EXPECT(large_local->tiered_config.leaf_capacity
< large_uniform->tiered_config.leaf_capacity);
uc::AdaptationConfig depth_config;
depth_config.evaluation_interval = 64;
depth_config.minimum_observations = 64;
depth_config.minimum_residency_operations = 0;
depth_config.minimum_shape_residency_operations = 0;
depth_config.minimum_shape_edit_fraction = 0.0;
depth_config.required_confirmation_windows = 1;
depth_config.forecast_operations = 1'000'000;
depth_config.tiered_rebuild_safety = 0.0;
depth_config.minimum_shape_improvement = 0.0;
depth_config.vector_read = 100.0;
depth_config.tiered_leaf_candidates.fill(64);
uc::CostModelPolicy depth_policy(depth_config, {64, 64, 2});
depth_policy.on_transition(uc::StorageMode::vector,
uc::StorageMode::tiered,
{64, 64, 2});
for (std::size_t i = 0; i < 64; ++i) {
depth_policy.observe({uc::OperationKind::random_read, 1'000'000, i,
1, sizeof(std::uint32_t)});
}
const auto depth = depth_policy.recommended_decision(
uc::StorageMode::tiered, 1'000'000, {64, 64, 2});
EXPECT(depth.has_value());
EXPECT(depth->target == uc::StorageMode::tiered);
EXPECT(depth->tiered_config.leaf_capacity == 64);
EXPECT(depth->tiered_config.directory_levels == 3);
}
void indexed_hash_capacity_tracks_container_capacity() {
uc::ResizePolicyConfig policy_config;
policy_config.minimum_tiered_size = 32;
uc::AdaptiveSequence<std::uint32_t, true> values(
{8, 8, 3}, uc::ResizePolicy(policy_config, {8, 8, 3}));
auto previous_capacity = values.capacity();
auto previous_buckets = values.hash_bucket_count();
for (std::uint32_t value = 0; value < 257; ++value) {
values.push_back(value * 16);
EXPECT(values.contains(value * 16));
if (values.capacity() == previous_capacity) {
EXPECT(values.hash_bucket_count() == previous_buckets);
} else {
EXPECT(values.capacity() == 1
|| values.capacity() == previous_capacity * 2);
EXPECT(values.hash_bucket_count() >= previous_buckets);
previous_capacity = values.capacity();
previous_buckets = values.hash_bucket_count();
}
}
// These keys share low hash bits and exercise backward-shift deletion in
// the linear-probing table without an intermediate rehash.
for (std::uint32_t value = 0; value < 257; value += 2) {
EXPECT(values.erase_one(value * 16));
}
for (std::uint32_t value = 0; value < 257; ++value) {
EXPECT(values.contains(value * 16) == (value % 2 != 0));
}
const auto buckets_before_shrink = values.hash_bucket_count();
while (values.size() > values.capacity() / 8) {
values.erase(values.size() - 1);
}
EXPECT(values.hash_bucket_count() <= buckets_before_shrink);
}
} // namespace
int main() {
ring_block_offsets();
randomized_differential();
indexed_duplicates_and_ids();
indexed_ids_reuse_slots_without_reviving_stale_handles();
moved_from_sequences_are_reusable_and_assignment_invalidates_proxies();
hash_backward_shift_handles_wraparound_and_duplicates();
indexed_proxy_detects_structural_invalidation();
iterator_and_contiguous_contract();
non_trivial_values();
tiered_shape_rebuild_preserves_order();
capacity_boundaries_control_mode_and_geometry();
calibrated_default_cutoff_is_applied_at_resize();
forecast_horizon_is_bounded_by_observed_evidence();
confirmation_requires_consecutive_supporting_windows();
stationary_phases_do_not_thrash();
policy_changes_shape_with_scale_and_locality();
indexed_hash_capacity_tracks_container_capacity();
if (failures != 0) {
std::cerr << failures << " test assertion(s) failed\n";
return EXIT_FAILURE;
}
std::cout << "All AdaptiveSequence tests passed\n";
return EXIT_SUCCESS;
}
Reference in New Issue View Git Blame Copy Permalink