diff options
| author | Claudius "keldu" Holeksa <mail@keldu.de> | 2026-11-13 14:12:49 +0100 |
|---|---|---|
| committer | Claudius "keldu" Holeksa <mail@keldu.de> | 2026-11-13 14:12:49 +0100 |
| commit | e821d617802ebbfff756844e4d9720342fc78a4e (patch) | |
| tree | 1dcf33b84698b5074218e44ea491b77a9c23ee66 /modules/swarm/tests/probe_search.cpp | |
| parent | 0c0087ef9482634273ec1a23d3a915754f94926d (diff) | |
| download | libs-lbm-e821d617802ebbfff756844e4d9720342fc78a4e.tar.gz | |
Swarm POCdev
Diffstat (limited to 'modules/swarm/tests/probe_search.cpp')
| -rw-r--r-- | modules/swarm/tests/probe_search.cpp | 202 |
1 files changed, 202 insertions, 0 deletions
diff --git a/modules/swarm/tests/probe_search.cpp b/modules/swarm/tests/probe_search.cpp new file mode 100644 index 0000000..42f852b --- /dev/null +++ b/modules/swarm/tests/probe_search.cpp @@ -0,0 +1,202 @@ +#include <forstio/test/suite.hpp> + +#include "../c++/capacity.hpp" +#include "../c++/probe_search.hpp" + +#include <string> + +namespace { +using namespace kel::lbm::swarm; + +/** + * Runs a search against a simulated device whose real capacity is `truth`, + * returning the outcome. This is the whole point of keeping the strategy apart + * from the GL calls: a device that would take a browser and several seconds to + * interrogate is a predicate here. + */ +struct probe_outcome { + uint64_t best; + uint64_t trials; + bool hit_ceiling; +}; + +probe_outcome run_against(uint64_t truth, allocation_search::config cfg = {}){ + allocation_search search{cfg}; + + while(not search.done()){ + search.report(search.candidate() <= truth); + } + + return probe_outcome{search.best_cells(), search.trials(), + search.hit_ceiling()}; +} + +SAW_TEST("Probe / never reports more than the device can do"){ + // The property that matters most. Over-reporting means the orchestrator + // hands out a domain that does not fit, and the worker fails at the point + // where it is least convenient. + const uint64_t truths[] = { + 65536u, 100000u, 1000000u, 2097152u, 5600000u, 12345678u, + 99999999u, 1u << 28, + }; + + for(uint64_t truth : truths){ + const auto out = run_against(truth); + SAW_EXPECT(out.best <= truth, + "A probe must never claim more than the device allows"); + } +} + +SAW_TEST("Probe / gets close to the real capacity"){ + // Within a quarter is plenty: the figure is a planning estimate against a + // budget that shifts as other tabs come and go. + const uint64_t truths[] = { + 200000u, 1000000u, 3000000u, 5600000u, 22000000u, + }; + + for(uint64_t truth : truths){ + const auto out = run_against(truth); + SAW_EXPECT(out.best * 4u >= truth * 3u, + std::string{"Probe landed too far below the truth for "} + + std::to_string(truth)); + } +} + +SAW_TEST("Probe / converges in a handful of trials"){ + // Doubling then bisecting should cost a dozen or so attempts even across + // three orders of magnitude of device. + allocation_search::config cfg; + + for(uint64_t truth = 65536u; truth < (1ull << 30); truth *= 3u){ + const auto out = run_against(truth, cfg); + SAW_EXPECT(out.trials <= cfg.max_trials, + "The backstop must hold"); + SAW_EXPECT(out.trials <= 20u, + std::string{"Too many trials for truth "} + std::to_string(truth)); + } +} + +SAW_TEST("Probe / a device that cannot do the opening attempt reports zero"){ + allocation_search::config cfg; + cfg.start_cells = 65536u; + + const auto out = run_against(1000u, cfg); + SAW_EXPECT(out.best == 0u, + "Failing the smallest attempt must report no capacity, not a guess"); + SAW_EXPECT(out.trials == 1u, "and must not keep trying"); +} + +SAW_TEST("Probe / the texture ceiling is reported, not confused with memory"){ + allocation_search::config cfg; + cfg.ceiling_cells = 1000000u; + + // Memory is effectively unlimited here, so the ceiling is what stops it. + const auto out = run_against(1ull << 40, cfg); + SAW_EXPECT(out.best == cfg.ceiling_cells, "It reaches the ceiling exactly"); + SAW_EXPECT(out.hit_ceiling, + "and says the texture dimension stopped it, not memory"); + + // Whereas a device that runs out of memory first must not claim the + // ceiling stopped it -- those are different things to report upstream. + const auto mem = run_against(300000u, cfg); + SAW_EXPECT(not mem.hit_ceiling, + "Running out of memory below the ceiling is not a ceiling hit"); + SAW_EXPECT(mem.best <= 300000u, "and still must not over-report"); +} + +SAW_TEST("Probe / a ceiling below the opening attempt is clamped"){ + allocation_search::config cfg; + cfg.start_cells = 65536u; + cfg.ceiling_cells = 1024u; + + allocation_search search{cfg}; + SAW_EXPECT(search.candidate() == 1024u, + "The first attempt must not exceed the ceiling"); + + const auto out = run_against(1ull << 30, cfg); + SAW_EXPECT(out.best == 1024u, "and the answer is the ceiling"); + SAW_EXPECT(out.hit_ceiling, "reported as such"); +} + +SAW_TEST("Probe / a zero ceiling means no capacity at all"){ + allocation_search::config cfg; + cfg.ceiling_cells = 0u; + cfg.start_cells = 0u; + + allocation_search search{cfg}; + SAW_EXPECT(search.done(), "Nothing to try means the search is already over"); + SAW_EXPECT(search.best_cells() == 0u, "and the answer is zero"); +} + +SAW_TEST("Probe / reporting after completion is ignored"){ + allocation_search search{allocation_search::config{}}; + while(not search.done()){ + search.report(false); + } + + const uint64_t trials = search.trials(); + search.report(true); + SAW_EXPECT(search.trials() == trials, + "A late answer must not restart a finished search"); + SAW_EXPECT(search.best_cells() == 0u, "nor change the result"); +} + +/** + * A device that answers inconsistently -- which a real one can, since memory + * pressure moves while you are measuring -- must still terminate. + */ +SAW_TEST("Probe / an unreliable device still terminates"){ + allocation_search::config cfg; + + // Alternating yes/no regardless of size. + { + allocation_search search{cfg}; + bool flip = true; + uint64_t guard = 0u; + while(not search.done()){ + search.report(flip); + flip = not flip; + SAW_EXPECT(++guard < 1000u, "The search must terminate"); + } + SAW_EXPECT(search.trials() <= cfg.max_trials, "within the backstop"); + } + + // Always yes, unbounded device: the doubling has to stop somewhere. + { + allocation_search search{cfg}; + uint64_t guard = 0u; + while(not search.done()){ + search.report(true); + SAW_EXPECT(++guard < 1000u, "Unbounded success must still terminate"); + } + SAW_EXPECT(search.trials() <= cfg.max_trials, "within the backstop"); + } +} + +/** + * The probe answers in cells; the orchestrator wants a domain. Checking the + * two compose means the number that comes off a device is usable as it stands. + */ +SAW_TEST("Probe / the measured capacity feeds the domain fitting"){ + constexpr uint64_t bpc = packing_math::bytes_per_cell(9u, 2u, 1u, true); + const uint64_t max_tex = 16384u; + + // A device good for about 512MB of lattice. + const uint64_t truth = capacity_math::cells_from_bytes( + 512ull * 1024ull * 1024ull, bpc); + + allocation_search::config cfg; + cfg.ceiling_cells = capacity_math::texture_bound_cells_2d(max_tex, 0u); + + const auto out = run_against(truth, cfg); + SAW_EXPECT(out.best <= truth, "Measured capacity must not exceed the truth"); + SAW_EXPECT(not out.hit_ceiling, + "Memory binds well before the texture dimension on a device like this"); + + const auto dom = capacity_math::fit_domain_2d(out.best, 4u, 1u, max_tex, 0u); + SAW_EXPECT(dom.cells() <= out.best, + "The fitted domain must fit what was actually measured"); + SAW_EXPECT(dom.cells() * bpc <= 512ull * 1024ull * 1024ull, + "and therefore fit in the memory the device really had"); +} +} |
