Skip to content

Commit e4faea9

Browse files
sipasipa
committed
clusterlin bench: have low/high iter benchmarks instead of per-iter
1 parent cf0120f commit e4faea9

File tree

1 file changed

+36
-22
lines changed

1 file changed

+36
-22
lines changed

‎src/bench/cluster_linearize.cpp‎

Lines changed: 36 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -111,17 +111,18 @@ DepGraph<SetType> MakeHardGraph(ClusterIndex ntx)
111111
return depgraph;
112112
}
113113

114-
/** Benchmark that does search-based candidate finding with 10000 iterations.
114+
/** Benchmark that does search-based candidate finding with a specified number of iterations.
115115
*
116-
* Its goal is measuring how much time every additional search iteration in linearization costs.
116+
* Its goal is measuring how much time every additional search iteration in linearization costs,
117+
* by running with a low and a high count, subtracting the results, and divided by the number
118+
* iterations difference.
117119
*/
118120
template<typename SetType>
119-
void BenchLinearizePerIterWorstCase(ClusterIndex ntx, benchmark::Bench& bench)
121+
void BenchLinearizeWorstCase(ClusterIndex ntx, benchmark::Bench& bench, uint64_t iter_limit)
120122
{
121123
const auto depgraph = MakeHardGraph<SetType>(ntx);
122-
const auto iter_limit = std::min<uint64_t>(10000, uint64_t{1} << (ntx / 2 - 1));
123124
uint64_t rng_seed = 0;
124-
bench.batch(iter_limit).unit("iters").run([&] {
125+
bench.run([&] {
125126
SearchCandidateFinder finder(depgraph, rng_seed++);
126127
auto [candidate, iters_performed] = finder.FindCandidateSet(iter_limit, {});
127128
assert(iters_performed == iter_limit);
@@ -132,11 +133,12 @@ void BenchLinearizePerIterWorstCase(ClusterIndex ntx, benchmark::Bench& bench)
132133
*
133134
* Its goal is measuring how much time linearization may take without any search iterations.
134135
*
135-
* If P is the resulting time of BenchLinearizePerIterWorstCase, and N is the resulting time of
136-
* BenchLinearizeNoItersWorstCase*, then an invocation of Linearize with max_iterations=m should
137-
* take no more than roughly N+m*P time. This may however be an overestimate, as the worst cases
138-
* do not coincide (the ones that are worst for linearization without any search happen to be ones
139-
* that do not need many search iterations).
136+
* If P is the benchmarked per-iteration count (obtained by running BenchLinearizeWorstCase for a
137+
* high and a low iteration count, subtracting them, and dividing by the difference in count), and
138+
* N is the resulting time of BenchLinearizeNoItersWorstCase*, then an invocation of Linearize with
139+
* max_iterations=m should take no more than roughly N+m*P time. This may however be an
140+
* overestimate, as the worst cases do not coincide (the ones that are worst for linearization
141+
* without any search happen to be ones that do not need many search iterations).
140142
*
141143
* This benchmark exercises a worst case for AncestorCandidateFinder, but for which improvement is
142144
* cheap.
@@ -207,12 +209,18 @@ void BenchMergeLinearizationsWorstCase(ClusterIndex ntx, benchmark::Bench& bench
207209

208210
} // namespace
209211

210-
static void LinearizePerIter16TxWorstCase(benchmark::Bench& bench) { BenchLinearizePerIterWorstCase<BitSet<16>>(16, bench); }
211-
static void LinearizePerIter32TxWorstCase(benchmark::Bench& bench) { BenchLinearizePerIterWorstCase<BitSet<32>>(32, bench); }
212-
static void LinearizePerIter48TxWorstCase(benchmark::Bench& bench) { BenchLinearizePerIterWorstCase<BitSet<48>>(48, bench); }
213-
static void LinearizePerIter64TxWorstCase(benchmark::Bench& bench) { BenchLinearizePerIterWorstCase<BitSet<64>>(64, bench); }
214-
static void LinearizePerIter75TxWorstCase(benchmark::Bench& bench) { BenchLinearizePerIterWorstCase<BitSet<75>>(75, bench); }
215-
static void LinearizePerIter99TxWorstCase(benchmark::Bench& bench) { BenchLinearizePerIterWorstCase<BitSet<99>>(99, bench); }
212+
static void Linearize16TxWorstCase20Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<16>>(16, bench, 20); }
213+
static void Linearize16TxWorstCase120Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<16>>(16, bench, 120); }
214+
static void Linearize32TxWorstCase5000Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<32>>(32, bench, 5000); }
215+
static void Linearize32TxWorstCase15000Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<32>>(32, bench, 15000); }
216+
static void Linearize48TxWorstCase5000Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<48>>(48, bench, 5000); }
217+
static void Linearize48TxWorstCase15000Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<48>>(48, bench, 15000); }
218+
static void Linearize64TxWorstCase5000Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<64>>(64, bench, 5000); }
219+
static void Linearize64TxWorstCase15000Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<64>>(64, bench, 15000); }
220+
static void Linearize75TxWorstCase5000Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<75>>(75, bench, 5000); }
221+
static void Linearize75TxWorstCase15000Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<75>>(75, bench, 15000); }
222+
static void Linearize99TxWorstCase5000Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<99>>(99, bench, 5000); }
223+
static void Linearize99TxWorstCase15000Iters(benchmark::Bench& bench) { BenchLinearizeWorstCase<BitSet<99>>(99, bench, 15000); }
216224

217225
static void LinearizeNoIters16TxWorstCaseAnc(benchmark::Bench& bench) { BenchLinearizeNoItersWorstCaseAnc<BitSet<16>>(16, bench); }
218226
static void LinearizeNoIters32TxWorstCaseAnc(benchmark::Bench& bench) { BenchLinearizeNoItersWorstCaseAnc<BitSet<32>>(32, bench); }
@@ -242,12 +250,18 @@ static void MergeLinearizations64TxWorstCase(benchmark::Bench& bench) { BenchMer
242250
static void MergeLinearizations75TxWorstCase(benchmark::Bench& bench) { BenchMergeLinearizationsWorstCase<BitSet<75>>(75, bench); }
243251
static void MergeLinearizations99TxWorstCase(benchmark::Bench& bench) { BenchMergeLinearizationsWorstCase<BitSet<99>>(99, bench); }
244252

245-
BENCHMARK(LinearizePerIter16TxWorstCase, benchmark::PriorityLevel::HIGH);
246-
BENCHMARK(LinearizePerIter32TxWorstCase, benchmark::PriorityLevel::HIGH);
247-
BENCHMARK(LinearizePerIter48TxWorstCase, benchmark::PriorityLevel::HIGH);
248-
BENCHMARK(LinearizePerIter64TxWorstCase, benchmark::PriorityLevel::HIGH);
249-
BENCHMARK(LinearizePerIter75TxWorstCase, benchmark::PriorityLevel::HIGH);
250-
BENCHMARK(LinearizePerIter99TxWorstCase, benchmark::PriorityLevel::HIGH);
253+
BENCHMARK(Linearize16TxWorstCase20Iters, benchmark::PriorityLevel::HIGH);
254+
BENCHMARK(Linearize16TxWorstCase120Iters, benchmark::PriorityLevel::HIGH);
255+
BENCHMARK(Linearize32TxWorstCase5000Iters, benchmark::PriorityLevel::HIGH);
256+
BENCHMARK(Linearize32TxWorstCase15000Iters, benchmark::PriorityLevel::HIGH);
257+
BENCHMARK(Linearize48TxWorstCase5000Iters, benchmark::PriorityLevel::HIGH);
258+
BENCHMARK(Linearize48TxWorstCase15000Iters, benchmark::PriorityLevel::HIGH);
259+
BENCHMARK(Linearize64TxWorstCase5000Iters, benchmark::PriorityLevel::HIGH);
260+
BENCHMARK(Linearize64TxWorstCase15000Iters, benchmark::PriorityLevel::HIGH);
261+
BENCHMARK(Linearize75TxWorstCase5000Iters, benchmark::PriorityLevel::HIGH);
262+
BENCHMARK(Linearize75TxWorstCase15000Iters, benchmark::PriorityLevel::HIGH);
263+
BENCHMARK(Linearize99TxWorstCase5000Iters, benchmark::PriorityLevel::HIGH);
264+
BENCHMARK(Linearize99TxWorstCase15000Iters, benchmark::PriorityLevel::HIGH);
251265

252266
BENCHMARK(LinearizeNoIters16TxWorstCaseAnc, benchmark::PriorityLevel::HIGH);
253267
BENCHMARK(LinearizeNoIters32TxWorstCaseAnc, benchmark::PriorityLevel::HIGH);

0 commit comments

Comments
 (0)