1#![expect(
2 clippy::cast_possible_truncation,
3 clippy::cast_possible_wrap,
4 reason = "tournament indices and iteration counts are bounded by the protobuf job contract"
5)]
6
7use std::{cmp::Reverse, collections::BinaryHeap};
8
9use prost::Message;
10use roaring::RoaringBitmap;
11use wowlab_analytics as merge;
12use wowlab_common::{
13 RuntimeWorkFidelity, RuntimeWorkItem, RuntimeWorkItemKind, RuntimeWorkResult,
14 sim::derive::permutation_picks,
15};
16use wowlab_types::proto::{
17 self, JobResult, JobTimeline, PermutationSummary, SlotDiff, TournamentPayload,
18 TournamentResult, TournamentStats, TournamentTimeline,
19};
20
21use super::job::{ProgressSnapshot, TopPermutation};
22use crate::{
23 scheduler::{runtime_breakdown::RuntimeMemoryBreakdown, runtime_factorial::FactorialRuntime},
24 strategy::{FinalOutput, StrategyError, encode_and_check},
25};
26
27const MIN_SURVIVORS: u32 = 10;
28const TOP_N_RESULTS: u32 = 10;
29const KEEP_DENOMINATOR: u32 = 100;
30const FNV_OFFSET_BASIS: u32 = 0x811C_9DC5;
31const FNV_PRIME: u32 = 0x0100_0193;
32const RESULT_BUDGET: usize = 32_768;
33const PROGRESS_TOP_K: usize = 20;
34const PHASE_COUNTER_FIELDS: usize = 4;
35
36fn hash_bonus_ids(bonus_ids: &[u32]) -> u32 {
37 let mut h: u32 = FNV_OFFSET_BASIS;
38
39 for &b in bonus_ids {
40 h ^= b;
41 h = h.wrapping_mul(FNV_PRIME);
42 }
43
44 h
45}
46
47fn compute_diffs(payload: &TournamentPayload, perm_idx: u32) -> Vec<SlotDiff> {
48 let base_picks = permutation_picks(payload, 0);
49 let picks = permutation_picks(payload, perm_idx);
50 let mut diffs = Vec::new();
51
52 for ((slot_idx, item_idx), (_, base_item_idx)) in picks.iter().zip(base_picks.iter()) {
53 if item_idx == base_item_idx {
54 continue;
55 }
56
57 let Some(sc) = payload.slot_candidates.get(*slot_idx) else {
58 continue;
59 };
60 let Some(item) = sc.items.get(*item_idx) else {
61 continue;
62 };
63
64 diffs.push(SlotDiff {
65 slot_index: *slot_idx as u32,
66 item_id: item.item_id,
67 bonus_id_hash: hash_bonus_ids(&item.bonus_ids),
68 });
69 }
70
71 diffs
72}
73
74#[derive(Clone, Copy, Debug)]
75pub struct Phase {
77 pub iterations: u32,
78 pub keep_fraction_x100: u32,
80}
81
82#[derive(Clone, Copy, Debug, Eq, PartialEq)]
83struct HeapEntry {
84 dps_x10: u32,
85 perm: u32,
86}
87
88impl Ord for HeapEntry {
89 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
90 self.dps_x10
91 .cmp(&other.dps_x10)
92 .then(self.perm.cmp(&other.perm))
93 }
94}
95
96impl PartialOrd for HeapEntry {
97 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
98 Some(self.cmp(other))
99 }
100}
101
102#[derive(Clone, Copy, Debug, Eq, PartialEq)]
103enum TournamentStage {
104 Factorial,
105 Phase,
106 WinnerRerun,
107 Done,
108}
109
110#[derive(Debug)]
111pub(super) struct TournamentRuntime {
112 phases: Vec<Phase>,
113 current_phase: usize,
114 stage: TournamentStage,
115 payload_bytes: Vec<u8>,
116 to_test: RoaringBitmap,
117 phase_size: u32,
118 completed_in_phase: u32,
119 keep_count: u32,
120 top_k: BinaryHeap<Reverse<HeapEntry>>,
121 final_top: Vec<HeapEntry>,
122 winner_perm: Option<u32>,
123 winner_telemetry: Option<Vec<u8>>,
124 baseline_dps_x10: Option<u32>,
125 total_permutations: u32,
126 total_iterations: u64,
127 factorial: Option<FactorialRuntime>,
128}
129
130fn bounded_top_k(keep_count: u32) -> BinaryHeap<Reverse<HeapEntry>> {
132 BinaryHeap::with_capacity(keep_count as usize + 1)
133}
134
135impl TournamentRuntime {
136 pub(super) fn new(phases: Vec<Phase>, to_test: RoaringBitmap, payload_bytes: Vec<u8>) -> Self {
137 let phase_size = to_test.len() as u32;
138 let keep_count = keep_count_for(&phases, 0, phase_size);
139
140 Self {
141 phases,
142 current_phase: 0,
143 stage: TournamentStage::Phase,
144 payload_bytes,
145 to_test,
146 phase_size,
147 completed_in_phase: 0,
148 keep_count,
149 top_k: bounded_top_k(keep_count),
150 final_top: Vec::new(),
151 winner_perm: None,
152 winner_telemetry: None,
153 baseline_dps_x10: None,
154 total_permutations: phase_size,
155 total_iterations: 0,
156 factorial: None,
157 }
158 }
159
160 pub(super) fn with_factorial(
161 phases: Vec<Phase>,
162 payload_bytes: Vec<u8>,
163 factorial: FactorialRuntime,
164 ) -> Self {
165 let total_permutations = factorial.total_permutations().min(u64::from(u32::MAX)) as u32;
166
167 Self {
168 phases,
169 current_phase: 0,
170 stage: TournamentStage::Factorial,
171 payload_bytes,
172 to_test: RoaringBitmap::new(),
173 phase_size: 0,
174 completed_in_phase: 0,
175 keep_count: 0,
176 top_k: BinaryHeap::new(),
177 final_top: Vec::new(),
178 winner_perm: None,
179 winner_telemetry: None,
180 baseline_dps_x10: None,
181 total_permutations,
182 total_iterations: 0,
183 factorial: Some(factorial),
184 }
185 }
186
187 pub(super) fn next_work(
188 &mut self,
189 max_items: usize,
190 next_item_id: &mut u64,
191 ) -> Vec<RuntimeWorkItem> {
192 match self.stage {
193 TournamentStage::Factorial => self
194 .factorial
195 .as_mut()
196 .map(|f| f.next_work(max_items, next_item_id))
197 .unwrap_or_default(),
198 TournamentStage::Phase => {
199 let iterations = self.current_iterations();
200 let mut items = Vec::new();
201 let perms: Vec<u32> = self.to_test.iter().take(max_items).collect();
202
203 for perm in perms {
204 self.to_test.remove(perm);
205 let item_id = *next_item_id;
206
207 *next_item_id += 1;
208 items.push(RuntimeWorkItem {
209 item_id,
210 kind: RuntimeWorkItemKind::Tournament { perm_idx: perm },
211 tag: u64::from(perm),
212 iterations,
213 seed_offset: u64::from(perm) * u64::from(iterations),
214 fidelity: RuntimeWorkFidelity::DpsOnly,
215 });
216 }
217
218 items
219 }
220 TournamentStage::WinnerRerun => {
221 let Some(perm) = self.winner_perm.take() else {
222 return Vec::new();
223 };
224 let iterations = self.phases.last().map(|p| p.iterations).unwrap_or_default();
225 let item_id = *next_item_id;
226
227 *next_item_id += 1;
228
229 vec![RuntimeWorkItem {
230 item_id,
231 kind: RuntimeWorkItemKind::Tournament { perm_idx: perm },
232 tag: u64::from(perm),
233 iterations,
234 seed_offset: u64::from(perm) * u64::from(iterations),
235 fidelity: RuntimeWorkFidelity::Full,
236 }]
237 }
238 TournamentStage::Done => Vec::new(),
239 }
240 }
241
242 pub(super) fn ingest(&mut self, results: &[RuntimeWorkResult]) {
243 match self.stage {
244 TournamentStage::Factorial => {
245 for r in results {
246 self.total_iterations += u64::from(r.iterations);
247 }
248
249 if let Some(f) = self.factorial.as_mut() {
250 f.ingest(results);
251
252 if f.is_screening_ready() {
253 self.seed_phase_from_factorial();
254 }
255 }
256 }
257 TournamentStage::Phase => {
258 for r in results {
259 let perm = r.tag as u32;
260
261 self.total_iterations += u64::from(r.iterations);
262
263 if self.current_phase == 0 && perm == 0 {
264 self.baseline_dps_x10 = Some(r.mean_dps_x10);
265 }
266
267 self.top_k.push(Reverse(HeapEntry {
268 dps_x10: r.mean_dps_x10,
269 perm,
270 }));
271
272 while self.top_k.len() as u32 > self.keep_count {
273 self.top_k.pop();
274 }
275
276 self.completed_in_phase += 1;
277 }
278
279 if self.completed_in_phase >= self.phase_size {
280 self.advance_phase();
281 }
282 }
283 TournamentStage::WinnerRerun => {
284 if let Some(r) = results.iter().find(|r| r.telemetry_pb.is_some()) {
285 self.total_iterations += u64::from(r.iterations);
286 self.winner_telemetry.clone_from(&r.telemetry_pb);
287 }
288
289 self.stage = TournamentStage::Done;
290 }
291 TournamentStage::Done => {}
292 }
293 }
294
295 pub(super) fn is_complete(&self) -> bool {
296 self.stage == TournamentStage::Done
297 }
298
299 pub(super) fn peek_next_work_shape(&self) -> (u32, bool) {
300 match self.stage {
301 TournamentStage::Factorial => {
302 let iters = self
303 .factorial
304 .as_ref()
305 .map_or(0, FactorialRuntime::next_iterations);
306
307 (iters, false)
308 }
309 TournamentStage::Phase => (self.current_iterations(), false),
310 TournamentStage::WinnerRerun => {
311 let iters = self.phases.last().map_or(0, |p| p.iterations);
312
313 (iters, true)
314 }
315 TournamentStage::Done => (0, false),
316 }
317 }
318
319 pub(super) fn progress(&self) -> ProgressSnapshot {
320 let iterations = self.current_iterations();
321 let mut top: Vec<HeapEntry> = self.top_k.iter().map(|Reverse(e)| *e).collect();
322
323 top.sort_by(|a, b| b.cmp(a));
324 let top_k: Vec<TopPermutation> = top
325 .iter()
326 .take(PROGRESS_TOP_K)
327 .map(|e| TopPermutation {
328 perm_idx: e.perm,
329 mean_dps_x10: e.dps_x10,
330 iterations,
331 })
332 .collect();
333 let top_mean_dps_x10 = top_k.first().map_or(0, |e| e.mean_dps_x10);
334
335 ProgressSnapshot {
336 phase: self.current_phase as u32,
337 phase_count: self.phases.len() as u32,
338 permutations_active: self.phase_size,
339 top_mean_dps_x10,
340 top_k,
341 }
342 }
343
344 pub(super) fn finalize(&self) -> Result<FinalOutput, StrategyError> {
345 let payload = if self.payload_bytes.is_empty() {
346 None
347 } else {
348 match TournamentPayload::decode(self.payload_bytes.as_slice()) {
349 Ok(payload) => Some(payload),
350 Err(source) => return Err(StrategyError::tournament_payload_decode(source)),
351 }
352 };
353
354 let winner_dps = self.final_top.first().map_or(0, |e| e.dps_x10);
355 let baseline_dps = self.baseline_dps_x10.unwrap_or(0);
356
357 let top_permutations: Vec<PermutationSummary> = self
358 .final_top
359 .iter()
360 .take(TOP_N_RESULTS as usize)
361 .enumerate()
362 .map(|(rank, e)| PermutationSummary {
363 rank: rank as u32,
364 mean_dps_x10: e.dps_x10,
365 ci95_half_x10: 0,
366 diffs: payload
367 .as_ref()
368 .map(|p| compute_diffs(p, e.perm))
369 .unwrap_or_default(),
370 })
371 .collect();
372
373 let winner_telemetry = self
374 .winner_telemetry
375 .as_ref()
376 .and_then(|bytes| proto::ChunkTelemetry::decode(bytes.as_slice()).ok());
377
378 let winner_result = winner_telemetry.as_ref().map(|telem| {
379 let mut merge_state = merge::new_running_state(1);
380 let _ = merge::merge_chunk(&mut merge_state, telem);
381
382 merge::emit_result_snapshot(&merge_state)
383 });
384
385 let winner_timeline = winner_telemetry.as_ref().map(|telem| {
386 let mut merge_state = merge::new_running_state(1);
387 let _ = merge::merge_chunk(&mut merge_state, telem);
388
389 merge::emit_timeline_snapshot(&merge_state)
390 });
391
392 let result_pb = encode_and_check(
393 &JobResult {
394 strategy: "tournament".into(),
395 total_iterations: self.total_iterations,
396 duration_ms: 0,
397 result: Some(proto::job_result::Result::Tournament(TournamentResult {
398 slot_rankings: vec![],
399 winner_result,
400 top_permutations,
401 stats: Some(TournamentStats {
402 winner_dps_x10: winner_dps,
403 baseline_dps_x10: baseline_dps,
404 total_permutations: self.total_permutations,
405 total_iterations: self.total_iterations,
406 phases_completed: self.current_phase as u32 + 1,
407 dps_gain_x10: winner_dps as i32 - baseline_dps as i32,
408 }),
409 })),
410 },
411 RESULT_BUDGET,
412 )?;
413
414 let timeline_pb = winner_timeline.map(|tl| {
415 JobTimeline {
416 strategy: "tournament".into(),
417 timeline: Some(proto::job_timeline::Timeline::Tournament(
418 TournamentTimeline {
419 winner_timeline: Some(tl),
420 },
421 )),
422 }
423 .encode_to_vec()
424 });
425
426 Ok(FinalOutput {
427 result_pb,
428 timeline_pb,
429 })
430 }
431
432 pub(super) fn memory_breakdown(&self) -> RuntimeMemoryBreakdown {
433 let heap_entry = size_of::<Reverse<HeapEntry>>();
434
435 RuntimeMemoryBreakdown {
436 top_k_heap_bytes: self.top_k.capacity() * heap_entry,
437 final_top_bytes: self.final_top.capacity() * size_of::<HeapEntry>(),
438 untested_set_bytes: self.to_test.serialized_size(),
439 progress_tracking_bytes: size_of::<u32>() * PHASE_COUNTER_FIELDS,
440 in_flight_bytes: 0,
441 completion_log_bytes: 0,
442 in_flight_items: 0,
443 }
444 }
445
446 fn seed_phase_from_factorial(&mut self) {
447 let survivors = self
448 .factorial
449 .as_ref()
450 .map(FactorialRuntime::take_survivors)
451 .unwrap_or_default();
452
453 self.to_test = survivors;
454 self.phase_size = self.to_test.len() as u32;
455 self.completed_in_phase = 0;
456 self.current_phase = 0;
457 self.keep_count = keep_count_for(&self.phases, 0, self.phase_size);
458 self.top_k = bounded_top_k(self.keep_count);
459 self.stage = if self.phase_size == 0 {
460 TournamentStage::Done
461 } else {
462 TournamentStage::Phase
463 };
464 }
465
466 fn current_iterations(&self) -> u32 {
467 self.phases
468 .get(self.current_phase)
469 .map_or(0, |p| p.iterations)
470 }
471
472 fn is_final_phase(&self) -> bool {
473 self.current_phase + 1 >= self.phases.len()
474 }
475
476 fn advance_phase(&mut self) {
477 let mut survivors: Vec<HeapEntry> = self.top_k.drain().map(|Reverse(e)| e).collect();
478
479 survivors.sort_by(|a, b| b.cmp(a));
480
481 if self.is_final_phase() {
482 self.final_top = survivors;
483 self.winner_perm = self.final_top.first().map(|e| e.perm);
484 self.stage = if self.winner_perm.is_some() {
485 TournamentStage::WinnerRerun
486 } else {
487 TournamentStage::Done
488 };
489
490 return;
491 }
492
493 let mut next = RoaringBitmap::new();
494
495 for e in &survivors {
496 next.insert(e.perm);
497 }
498
499 self.current_phase += 1;
500 self.phase_size = next.len() as u32;
501 self.to_test = next;
502 self.completed_in_phase = 0;
503 self.keep_count = keep_count_for(&self.phases, self.current_phase, self.phase_size);
504 self.top_k = bounded_top_k(self.keep_count);
505 }
506}
507
508fn keep_count_for(phases: &[Phase], phase_idx: usize, phase_size: u32) -> u32 {
509 let is_final = phase_idx + 1 >= phases.len();
510
511 if is_final {
512 return TOP_N_RESULTS.max(1);
513 }
514
515 let frac = phases.get(phase_idx).map_or(0, |p| p.keep_fraction_x100);
516
517 ((u64::from(phase_size) * u64::from(frac) / u64::from(KEEP_DENOMINATOR)) as u32)
518 .max(MIN_SURVIVORS)
519}