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/c++/probe_search.hpp | |
| parent | 0c0087ef9482634273ec1a23d3a915754f94926d (diff) | |
| download | libs-lbm-e821d617802ebbfff756844e4d9720342fc78a4e.tar.gz | |
Swarm POCdev
Diffstat (limited to 'modules/swarm/c++/probe_search.hpp')
| -rw-r--r-- | modules/swarm/c++/probe_search.hpp | 198 |
1 files changed, 198 insertions, 0 deletions
diff --git a/modules/swarm/c++/probe_search.hpp b/modules/swarm/c++/probe_search.hpp new file mode 100644 index 0000000..f678937 --- /dev/null +++ b/modules/swarm/c++/probe_search.hpp @@ -0,0 +1,198 @@ +#pragma once + +#include <cstdint> + +/** + * Finding out how much a device will actually give you. + * + * WebGL2 reports limits but not capacity. MAX_TEXTURE_SIZE on a typical desktop + * implies something like 25 GB of lattice, roughly a hundred times what the GPU + * will really hand over, and there is no query for the real figure -- + * navigator.deviceMemory is system RAM and unrelated. So capacity is measured: + * try an allocation, see whether it survives, adjust. + * + * The strategy lives here rather than next to the GL calls because it is + * ordinary arithmetic and deserves to be tested as such. The caller owns the + * part that cannot be tested without a browser -- actually allocating -- and + * feeds the answers back in: + * + * allocation_search search{cfg}; + * while(not search.done()){ + * search.report(try_allocate(search.candidate())); + * } + * use(search.best_cells()); + * + * Grow by doubling until something fails, then bisect. Doubling finds the right + * order of magnitude in a handful of steps even when devices differ by a factor + * of a thousand; bisecting then tightens it without the linear crawl a pure + * step search would need. + */ +namespace kel { +namespace lbm { +namespace swarm { + +class allocation_search { +public: + struct config { + /** + * First attempt. Deliberately small: the opening trial should succeed + * on anything that can run at all, because a failure here means the + * device is unusable rather than merely modest. + */ + uint64_t start_cells = 65536u; + + /** + * Hard ceiling from the texture dimension, in cells. Zero means no + * ceiling. Reaching it is a different answer from running out of + * memory and is reported separately. + */ + uint64_t ceiling_cells = 0u; + + /// Bisection steps once a failure has bracketed the answer. Four gets + /// within about a sixteenth of the bracket, which is finer than the + /// figure deserves given it is a moving target anyway. + uint64_t bisect_steps = 4u; + + /// Backstop so a device that answers inconsistently cannot spin. + uint64_t max_trials = 32u; + }; + + explicit allocation_search(config cfg) : cfg_{cfg} { + candidate_ = cfg_.start_cells; + + if(cfg_.ceiling_cells > 0u and candidate_ > cfg_.ceiling_cells){ + candidate_ = cfg_.ceiling_cells; + } + + if(candidate_ == 0u){ + phase_ = phase::finished; + } + } + + bool done() const { return phase_ == phase::finished; } + + /// The cell count to attempt next. Meaningless once done(). + uint64_t candidate() const { return candidate_; } + + /// Largest allocation that survived. Zero means nothing did. + uint64_t best_cells() const { return best_; } + + uint64_t trials() const { return trials_; } + + /** + * True when the search stopped because the texture dimension ran out + * rather than because memory did. Worth distinguishing: one says the + * device is small, the other says it is oddly shaped. + */ + bool hit_ceiling() const { return hit_ceiling_; } + + void report(bool ok){ + if(phase_ == phase::finished){ + return; + } + + ++trials_; + + if(phase_ == phase::grow){ + report_grow(ok); + } else { + report_bisect(ok); + } + + if(trials_ >= cfg_.max_trials){ + phase_ = phase::finished; + } + } + +private: + enum class phase { grow, bisect, finished }; + + void report_grow(bool ok){ + if(not ok){ + failed_at_ = candidate_; + + if(best_ == 0u){ + // Even the opening attempt failed. There is nothing to + // bisect between, and the honest answer is zero. + phase_ = phase::finished; + return; + } + + phase_ = phase::bisect; + advance_bisect(); + return; + } + + best_ = candidate_; + + if(cfg_.ceiling_cells > 0u and candidate_ >= cfg_.ceiling_cells){ + // The texture dimension, not memory, is what stopped us. + hit_ceiling_ = true; + phase_ = phase::finished; + return; + } + + uint64_t next = candidate_ * 2u; + if(next < candidate_){ + // Overflow. Nothing sane gets here, but silently wrapping to a + // tiny candidate would turn a huge device into a small one. + phase_ = phase::finished; + return; + } + if(cfg_.ceiling_cells > 0u and next > cfg_.ceiling_cells){ + next = cfg_.ceiling_cells; + } + if(next == candidate_){ + phase_ = phase::finished; + return; + } + + candidate_ = next; + } + + void report_bisect(bool ok){ + if(ok){ + best_ = candidate_; + } else { + failed_at_ = candidate_; + } + advance_bisect(); + } + + void advance_bisect(){ + if(bisects_done_ >= cfg_.bisect_steps){ + phase_ = phase::finished; + return; + } + if(failed_at_ <= best_ + 1u){ + // Bracket closed; there is nothing left between them. + phase_ = phase::finished; + return; + } + + const uint64_t mid = best_ + ((failed_at_ - best_) / 2u); + if(mid == best_ or mid == failed_at_){ + phase_ = phase::finished; + return; + } + + candidate_ = mid; + ++bisects_done_; + } + + config cfg_; + + phase phase_ = phase::grow; + uint64_t candidate_ = 0u; + /// Largest known good. + uint64_t best_ = 0u; + /// Smallest known bad. + uint64_t failed_at_ = 0u; + uint64_t trials_ = 0u; + uint64_t bisects_done_ = 0u; + bool hit_ceiling_ = false; +}; + +} // namespace swarm +} // namespace lbm +} // namespace kel |
