summaryrefslogtreecommitdiff
path: root/modules/swarm/tests/probe_search.cpp
blob: 42f852b359854cb7ada86ec2bf2b71d213245e06 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
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");
}
}