clusterlin: randomize the SearchCandidateFinder search order

To make search non-deterministic, change the BFS logic from always picking
the first queue item to randomly picking the first or second queue item.

1 files changed, 4 insertions, 2 deletions

diff --git a/src/bench/cluster_linearize.cpp b/src/bench/cluster_linearize.cpp
index cf94580ab2..bfab5c729b 100644
--- a/src/bench/cluster_linearize.cpp
+++ b/src/bench/cluster_linearize.cpp
@@ -101,8 +101,9 @@ void BenchLinearizePerIterWorstCase(ClusterIndex ntx, benchmark::Bench& bench)
 {
     const auto depgraph = MakeHardGraph<SetType>(ntx);
     const auto iter_limit = std::min<uint64_t>(10000, uint64_t{1} << (ntx / 2 - 1));
+    uint64_t rng_seed = 0;
     bench.batch(iter_limit).unit("iters").run([&] {
-        SearchCandidateFinder finder(depgraph);
+        SearchCandidateFinder finder(depgraph, rng_seed++);
         auto [candidate, iters_performed] = finder.FindCandidateSet(iter_limit, {});
         assert(iters_performed == iter_limit);
     });
@@ -122,8 +123,9 @@ template<typename SetType>
 void BenchLinearizeNoItersWorstCase(ClusterIndex ntx, benchmark::Bench& bench)
 {
     const auto depgraph = MakeLinearGraph<SetType>(ntx);
+    uint64_t rng_seed = 0;
     bench.run([&] {
-        Linearize(depgraph, /*max_iterations=*/0);
+        Linearize(depgraph, /*max_iterations=*/0, rng_seed++);
     });
 }