flynnel 0.6.0

K-aware NUMA-aware work-stealing scheduler with extended-Flynn-taxonomy dispatch (MIMD / SIMC / MIMC / MISD / SIMT / MIMT): a rayon-shaped pool reshaped around per-call execution-class plans with first-class CPU+GPU hybrid (join_hybrid, hybrid_pipeline) and per-call dispatch profiles.
Documentation
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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
//! Public scheduler entry points: `join` and the `join_default` /
//! `join_context` conveniences.
//!
//! The dispatch surface that algorithm code (Karatsuba, NTT,
//! transcendentals) calls. Picks a [`SchedTier`] from
//! the [`JobPlan`] + cached NUMA topology and runs the work on the
//! corresponding execution path.
//!
//! ## Tier status
//!
//! - **Inline**: serial in caller, K <= 4.
//! - **Local**: work-stealing across the worker pool (unpinned by
//!   default; see `FLYNNEL_SCHED_PIN` below) with cooperative wait
//!   (parent steals while child runs). K = 5..7.
//! - **Hierarchical**: per-NUMA arenas with leader-driven cross-
//!   NUMA steal. Currently routes through the same Local
//!   dispatch path.
//! - **Federated**: FLINT-style pull pool. Currently routes
//!   through the same Local dispatch path.
//!
//! ## Worker count
//!
//! Default `global_local_arena()` worker count = all logical
//! threads per node (= 16 on R7 2700), matching rayon's
//! convention; SMT-2 siblings gain 10-30% on latency-bound work
//! and break even on most other shapes. For IMUL-saturated work
//! where a sibling contests the same execution port, restrict to
//! physical cores via env:
//!
//! - `FLYNNEL_SCHED_WORKERS=N` - exact count per node
//! - `FLYNNEL_SCHED_PHYSICAL_ONLY=on` (or `FLYNNEL_SCHED_SMT=off`)
//!   - physical cores only
//! - `FLYNNEL_SCHED_PIN=on|1|true` - enable per-worker CPU pinning
//!   (default is unpinned). The rayon-crossover bench measured
//!   unpinned workers 1.2-1.6x faster than pinned under any
//!   competing system load, because the OS places threads on idle
//!   SMT siblings. Cache-locality wins from pinning only realize
//!   on dedicated bench hardware with zero competing load; set
//!   this env var when running on such a rig.
//!

use std::sync::{Arc, OnceLock};
use std::sync::atomic::{AtomicU64, Ordering::Relaxed};

use crate::sched::arena_local::{WorkerCtx, current_worker_ctx};
use crate::sched::arena_numa::NumaArena;
use crate::sched::job::{JobRef, NUMA_HINT_ANY, StackJob};
use crate::sched::latch::{JoinLatch, LockLatch, SpinLatch};
use crate::sched::sleep::Parker;
use crate::sched::plan::{JobPlan, SchedTier, pick_tier};
use crate::numa_topology::numa_topology;

/// Fork-join primitive: run `a` and `b` and return both results.
///
/// A plan capped at one worker ([`JobPlan::with_workers`]`(1)`) runs
/// `a` then `b` serially on the calling thread whatever its tier, and
/// never reads or starts the pool. Otherwise, dispatch behavior per
/// tier (as selected by [`pick_tier`]):
///
/// - `SchedTier::Inline` runs `a` then `b` serially in the caller
///   (see [`inline_join_context`]).
/// - `SchedTier::Local`, `SchedTier::Hierarchical`, and
///   `SchedTier::Federated` all route through
///   [`local_join_context`], which pushes the right half onto a
///   worker deque and runs the left half cooperatively while
///   waiting on the right's latch.
///
/// # Determinism contract
///
/// The returned `(RA, RB)` tuple preserves **algebraic** order
/// (left-half first, right-half second) for non-commutative
/// reductions regardless of which thread executed which half, so
/// bit-exact reproducibility holds across the serial and
/// work-stealing tiers.
pub fn join<A, B, RA, RB>(plan: &JobPlan, a: A, b: B) -> (RA, RB)
where
    A: FnOnce() -> RA + Send,
    B: FnOnce() -> RB + Send,
    RA: Send,
    RB: Send,
{
    // `join` is a convenience wrapper over `join_context` for
    // callers that don't care about the migrated/stolen flag.
    join_context(plan, move |_| a(), move |_| b())
}

/// Fork-join variant that exposes the `migrated`/`stolen` flag to
/// each closure. Mirrors rayon-core's `join_context`.
///
/// `a` is called with `injected: bool` - `true` iff this entire
/// `join_context` was cold-injected from outside the worker pool
/// (rayon's "in_worker_cold" pattern). For nested in-worker calls
/// `injected` is `false`.
///
/// `b` is called with `stolen: bool` - `true` iff `b` was dequeued
/// and executed by a peer worker (i.e., somebody stole the
/// right-half job). `false` iff the originating worker popped the
/// job back from its own local deque and ran it inline.
///
/// The flag is the key signal for adaptive splitters: when work is
/// being stolen there is steal pressure, so the splitter should
/// subdivide more aggressively to feed hungry workers. See
/// `par_iter::for_each_chunk` for the bisect-side use of this.
pub fn join_context<A, B, RA, RB>(plan: &JobPlan, a: A, b: B) -> (RA, RB)
where
    A: FnOnce(bool) -> RA + Send,
    B: FnOnce(bool) -> RB + Send,
    RA: Send,
    RB: Send,
{
    if plan.capped_to_caller() {
        return inline_join_context(a, b);
    }
    let tier = pick_tier(plan, numa_topology());
    match tier {
        SchedTier::Inline => inline_join_context(a, b),
        SchedTier::Local => local_join_context(plan, a, b),
        SchedTier::Hierarchical | SchedTier::Federated => local_join_context(plan, a, b),
    }
}

/// Lazily-initialized process-global NUMA-aware arena. On single-
/// NUMA hosts this is a single sub-arena; on multi-NUMA hosts
/// (Colab Genoa, dual-socket Xeon / Threadripper) it has one
/// sub-arena per NUMA node, each pinned to its node's CPUs.
///
/// Worker count per node picked from [`crate::cpu_info`]
/// + per-node CPU mask with env overrides (see module doc).
pub fn global_local_arena() -> &'static Arc<NumaArena> {
    GLOBAL_ARENA.get_or_init(|| {
        let per_node_override = pick_worker_count_per_node();
        NumaArena::new(per_node_override)
    })
}

/// Whether [`global_local_arena`] has started in this process, read
/// without starting it. A library that links the crate beside another
/// module's pool, and must not start a second one, can hold itself to
/// that with this.
pub fn global_local_arena_started() -> bool {
    GLOBAL_ARENA.get().is_some()
}

/// The arena [`global_local_arena`] starts on first use.
static GLOBAL_ARENA: OnceLock<Arc<NumaArena>> = OnceLock::new();

/// Decide how many workers each NUMA sub-arena should spawn.
///
/// 1. `FLYNNEL_SCHED_WORKERS=N` (explicit positive integer) means
///    N PER NODE (so total = N * num_nodes).
/// 2. `FLYNNEL_SCHED_PHYSICAL_ONLY=on|1|true` => `None`
///    (NumaArena uses physical cores in each node). Use this for
///    IMUL-saturated workloads where the SMT sibling contests the
///    same execution port and adds no architectural throughput
///    (e.g., multi-precision arithmetic, tight Karatsuba loops).
/// 3. `FLYNNEL_SCHED_SMT=off|0|false` => same as
///    `FLYNNEL_SCHED_PHYSICAL_ONLY=on` (back-compat alias).
/// 4. Default: `Some(logical_threads_per_node)`. Matches rayon's
///    convention of using all logical threads. SMT-2 siblings
///    typically gain 10-30% on latency-bound work and break even
///    on most other workloads on modern Zen / Skylake silicon.
fn pick_worker_count_per_node() -> Option<usize> {
    if let Ok(v) = std::env::var("FLYNNEL_SCHED_WORKERS")
        && let Ok(n) = v.parse::<usize>()
        && n >= 1
    {
        return Some(n);
    }
    let physical_only = std::env::var("FLYNNEL_SCHED_PHYSICAL_ONLY")
        .map(|v| v.eq_ignore_ascii_case("on") || v == "1" || v.eq_ignore_ascii_case("true"))
        .unwrap_or(false);
    let smt_explicitly_off = std::env::var("FLYNNEL_SCHED_SMT")
        .map(|v| {
            let lv = v.to_ascii_lowercase();
            lv == "off" || lv == "0" || lv == "false"
        })
        .unwrap_or(false);
    if physical_only || smt_explicitly_off {
        return None;
    }
    let topo = numa_topology();
    // Use number of CPUs in node 0 as the per-node sizing hint. On
    // asymmetric NUMA hosts this may over- or under-allocate for
    // other nodes; for symmetric hosts (the common case) it's
    // exact. NumaArena clamps to >= 1.
    let cpus_node0 = topo.cpus_in_node(0).len();
    Some(cpus_node0.max(1))
}

/// Local-tier fork-join: submit the right half to the worker pool,
/// run the left half inline, wait on the right's latch.
///
/// # Dispatch
///
/// Two paths, picked by `current_worker_ctx()`:
///
/// **Fast (in-worker) path.** The calling thread is a Flynnel
/// scheduler worker. Push `job_b` onto the caller's own local
/// Chase-Lev deque (LIFO, ~5 ns), run `a` inline, then look for
/// `job_b` back on the local deque. If it's still there nobody
/// stole it; execute it inline. If a thief took it, drain other
/// local work (LIFO) and steal until the latch is set. This is
/// the rayon `join_context` shape (rayon-core/src/join/mod.rs:132)
/// and the primary perf win of in-worker dispatch.
///
/// **Slow (external) path.** The calling thread is not a worker
/// (typical from Criterion main, application code, etc.). Push
/// `job_b` to the NUMA arena's injector (~5-30 µs), run `a`,
/// then cooperatively steal via `arena.try_run_one` until the
/// latch is set.
///
/// # Lifetime + panic safety
///
/// The right-half `StackJob` lives on this function's stack frame
/// while its `JobRef` is in the arena. To ensure the worker never
/// dereferences a freed StackJob, we wait on the latch before
/// returning **on every path**, including panic. `catch_unwind`
/// around `a()` makes the panic path explicit: catch -> wait ->
/// resume.
fn local_join_context<A, B, RA, RB>(plan: &JobPlan, a: A, b: B) -> (RA, RB)
where
    A: FnOnce(bool) -> RA + Send,
    B: FnOnce(bool) -> RB + Send,
    RA: Send,
    RB: Send,
{
    let ctx_ptr = current_worker_ctx();
    if !ctx_ptr.is_null() {
        // Fast path: already in a worker. Push job_b to our own
        // local Chase-Lev deque, run a inline, drain.
        // SAFETY: ctx_ptr was set by worker_loop on this same
        // thread and is valid until worker_loop returns.
        let ctx = unsafe { &*ctx_ptr };
        // `injected = false` because the caller is already a
        // running worker (this is a nested in-worker join).
        return join_in_worker(ctx, plan, a, b, false);
    }
    external_dispatch(plan, a, b)
}

/// Push a job to the worker's local deque, honoring any
/// caller-supplied `deque_tier_hint` in the plan. `None` falls
/// through to `WorkerCtx::push` (default tier = Public per
/// `DequeTier::default`); `Some(tier)` routes via `push_tier`
/// so the steal discipline pins the work to peers at the chosen
/// distance or wider.
#[inline]
/// Pushes `job` to the hinted tier (Public by default). `Err(job)`
/// when that deque is full: the caller runs the job inline instead
/// of waiting for a thief.
fn push_with_tier_hint(ctx: &WorkerCtx, job: JobRef, plan: &JobPlan) -> Result<(), JobRef> {
    match plan.deque_tier_hint {
        Some(tier) => ctx.try_push_tier(job, tier)?,
        None => ctx.try_push(job)?,
    }
    // External slot ctx: broadcast-wake all primaries after the
    // push. A single-sleeper wake random-picks the slot's deque
    // at ~1/36 and may re-sleep without finding the right-half;
    // waking N primaries multiplies the first-round hit
    // probability by N. Without the broadcast, slot-pushed
    // right-halves sit unstolen (measured as full serialization
    // on an n=5 heavy fan-out: 227s = 5 x 45s).
    if ctx.is_external_slot {
        ctx.sleep.new_internal_jobs(ctx.stealers.len() as u32, false);
    }
    Ok(())
}

/// Fast-path body: run `join(a, b)` from within a worker that is
/// already in `WorkerCtx`. Push `job_b` to the worker's local
/// Chase-Lev deque (LIFO, single-owner-writer, ~5 ns), run `a`
/// inline, then drain the local deque until `job_b.latch` is set.
///
/// # Lifetime + panic safety
///
/// `job_b` lives on this function's stack frame. We wait on its
/// latch before returning on every path, including panic. A panic
/// from `a` is captured via `catch_unwind`; we still complete the
/// latch wait so the worker that may have stolen `job_b` doesn't
/// dereference freed memory, then resume the panic for the caller.
// === Per-join_in_worker dispatch trace (FLYNNEL_TRACE_DISPATCH=1) ===
//
// Three counters accumulated process-wide for diagnostic attribution
// of where the bisect's wall-clock per iter goes:
//
//   JOIN_CALL_COUNT        - number of join_in_worker invocations
//   JOIN_A_BODY_NS         - sum of cycles spent in `a()` (left half work
//                            for this frame, which for reduce_inner is
//                            itself the recursive sub-tree)
//   JOIN_WAIT_NS           - sum of cycles spent in the wait loop after
//                            `a()` returned (find_work probing + stolen
//                            job execution + the idle latch poll)
//
// Compute "wait fraction" = JOIN_WAIT_NS / (JOIN_A_BODY_NS + JOIN_WAIT_NS).
// High fraction == dispatch overhead is the bottleneck. Low fraction ==
// the bisect is balanced and dispatch is amortized fine.
//
// Zero overhead when env var unset: `if traced` short-circuits before
// any TSC read.
static JOIN_CALL_COUNT: AtomicU64 = AtomicU64::new(0);
static JOIN_A_BODY_NS: AtomicU64 = AtomicU64::new(0);
static JOIN_WAIT_NS: AtomicU64 = AtomicU64::new(0);
// Sub-split of JOIN_WAIT_NS: time inside `unsafe { job.execute() }`
// (productive stealing of cross-worker jobs while waiting) vs time
// in the idle path (no work available: the latch poll, a spin until
// the wait exceeds the host's collapse threshold and a yield per
// round after). Together these sum to JOIN_WAIT_NS minus the small
// `is_set()` poll cost and the small `find_work()` probe cost itself.
static JOIN_WAIT_STEAL_NS: AtomicU64 = AtomicU64::new(0);
static JOIN_WAIT_IDLE_NS: AtomicU64 = AtomicU64::new(0);

// Process-wide cache for FLYNNEL_TRACE_DISPATCH. The env-var lookup
// itself acquires a process-wide env lock and walks the env vector;
// per-call cost ~100-300 ns measured. Caching to a OnceLock<bool>
// reduces it to a single Acquire load on subsequent calls. join_in_worker
// is on the bisect hot path (10^4+ calls per inline_collapse bench cell)
// so the per-call save compounds.
static DISPATCH_TRACE_ENABLED: OnceLock<bool> = OnceLock::new();

#[inline(always)]
fn dispatch_trace_enabled() -> bool {
    *DISPATCH_TRACE_ENABLED.get_or_init(|| {
        std::env::var_os("FLYNNEL_TRACE_DISPATCH").is_some()
    })
}

#[inline(always)]
fn dispatch_tsc() -> u64 {
    #[cfg(target_arch = "x86_64")]
    unsafe {
        // SAFETY: _rdtsc has no preconditions on x86_64.
        std::arch::x86_64::_rdtsc()
    }
    #[cfg(not(target_arch = "x86_64"))]
    {
        std::time::Instant::now().elapsed().as_nanos() as u64
    }
}

/// Snapshot + reset the dispatch trace counters. Returns
/// `(calls, a_body_cycles_total, wait_cycles_total)`. Useful as a
/// per-bench-group accessor that prints the cumulative state then
/// clears it for the next bench group.
pub fn dispatch_trace_snapshot() -> (u64, u64, u64) {
    (
        JOIN_CALL_COUNT.swap(0, Relaxed),
        JOIN_A_BODY_NS.swap(0, Relaxed),
        JOIN_WAIT_NS.swap(0, Relaxed),
    )
}

/// Snapshot + reset the wait-loop sub-counters: returns
/// `(steal_cycles, idle_cycles)` accumulated since the previous
/// snapshot. Sum of these two plus the small `is_set()` /
/// `find_work()` probe cost adds up to `JOIN_WAIT_NS` from
/// `dispatch_trace_snapshot()`. The split tells us how much of
/// the wait time is productive cross-worker rebalancing vs pure
/// dispatch waste (the idle latch poll).
pub fn dispatch_trace_wait_snapshot() -> (u64, u64) {
    (
        JOIN_WAIT_STEAL_NS.swap(0, Relaxed),
        JOIN_WAIT_IDLE_NS.swap(0, Relaxed),
    )
}

/// Join waits that reached the kernel park, process-wide.
static JOIN_PARKS: AtomicU64 = AtomicU64::new(0);

/// How many join waits have parked in the kernel since the process
/// started, which is zero unless `FLYNNEL_LEVER_JOIN_PARK` is on. A run
/// that sets the lever and reads zero here never reached the park.
pub fn total_join_parks() -> u64 {
    JOIN_PARKS.load(Relaxed)
}

/// Parks the calling worker until the half's latch is set or something
/// else unparks its thread, through the latch's sleep handshake, so a set
/// that lands before the park ends it rather than being missed. Returns
/// with the latch set, or unset after a wake that was not its set, for
/// the caller's loop to look for work again.
fn park_for_half(latch: &JoinLatch) {
    if !latch.get_sleepy() {
        return;
    }
    if !latch.fall_asleep() {
        return;
    }
    JOIN_PARKS.fetch_add(1, Relaxed);
    let _unparked = latch.parker().park_until(|| latch.is_set());
    latch.wake_up();
}

/// One round of a join waiter whose spin budget is spent: a park in the
/// kernel under either park lever, and a yield otherwise. Returns the
/// yield's length in microseconds when the trace ring is on, and `None`
/// after a park or with the trace off.
///
/// Under either park lever a worker parks until the thief sets the
/// half's latch, because a yield among more runnable threads than cores
/// gives the core away for the rest of another thread's time slice.
/// join_park parks always; join_park_oversubscribed only while some
/// yield in the process has lately lost its core, and otherwise times
/// this yield, so the waiter's own reading counts as well. An external
/// slot yields: its join parker belongs to the arena's thread, not the
/// caller's.
///
/// Out of line and not generic, so each instantiation of
/// `join_in_worker` carries only its spin, its search and its latch
/// poll.
#[cold]
#[inline(never)]
fn wait_after_spin_budget(ctx: &WorkerCtx, latch: &JoinLatch) -> Option<u32> {
    let reading = crate::sched::levers::join_park_oversubscribed();
    if !ctx.is_external_slot
        && (crate::sched::levers::join_park()
            || (reading && crate::sched::oversubscription::recently()))
    {
        park_for_half(latch);
        None
    } else if reading {
        let took = crate::sched::oversubscription::timed_yield();
        crate::sched::trace::is_enabled().then(|| took.as_micros().min(u128::from(u32::MAX)) as u32)
    } else {
        let yield_started = crate::sched::trace::is_enabled().then(std::time::Instant::now);
        std::thread::yield_now();
        yield_started.map(|started| started.elapsed().as_micros().min(u128::from(u32::MAX)) as u32)
    }
}

#[inline]
fn join_in_worker<A, B, RA, RB>(
    ctx: &WorkerCtx,
    plan: &JobPlan,
    a: A,
    b: B,
    a_injected: bool,
) -> (RA, RB)
where
    A: FnOnce(bool) -> RA + Send,
    B: FnOnce(bool) -> RB + Send,
    RA: Send,
    RB: Send,
{
    // Per-fork latch: a JoinLatch. The thief sets it, and it unparks
    // this worker's join parker when the worker parked on it, which
    // only the idle round below does and only under
    // levers::join_park. It names the parker by address, so a set pays
    // one pointer load and no Arc clone. A SpinLatch parked on the
    // pool's idle Parker measured 1.5-1.8x slower on bisect-heavy work:
    // wake_one_peer's wakes for the idle sleeper landed on join waiters
    // at about 1 us each. The join parker is a separate Parker, but both
    // park this thread, so such a wake still ends a join park, and the
    // waiter then looks for work, which is what the wake was for.
    let job_b = StackJob::new(b, JoinLatch::new(&ctx.join_parker));
    // SAFETY: job_b lives on this stack frame; the latch-wait
    // below keeps it alive until the worker finishes touching it.
    let job_b_ref = unsafe {
        job_b.as_job_ref(
            plan.k_outer,
            plan.numa_hint.unwrap_or(NUMA_HINT_ANY as u32) as u8,
            plan.variant,
        )
    };
    let job_b_id = job_b_ref.id();
    // SIMC/MIMC mailbox routing for the right-half of join, gated
    // on a cheap is_empty() check against the SMT sibling's
    // mailbox. The intuition:
    //
    // - When the sibling's mailbox is EMPTY, the sibling is either
    //   idle (parked / spinning) or executing - in either case it
    //   has no other queued mailbox work, so handing it the
    //   right-half via mailbox jumps the queue ahead of any deque
    //   tier and consumes the caller's L1d-warm state with zero
    //   coherence transfer (the SMT pair shares L1d).
    // - When the sibling's mailbox is NON-EMPTY, the sibling is
    //   backlogged. Forcing more work into the mailbox concentrates
    //   load on one SMT pair and starves the other workers. The
    //   right-half goes to the owner's own deque instead, where the
    //   full pool can steal from it.
    //
    // The unconditional version of this routing regressed
    // realistic_bench Compute/100k 2.27x because every join right-
    // half got pinned to one specific worker; the is_empty() gate
    // restores broad-steal semantics for backlogged-sibling cases.
    let sibling = ctx.index ^ 1;
    // Mailbox-route only when the caller opted in via
    // `plan.use_mailbox_routing` and the sibling has truly nothing
    // queued (mailbox empty and SmtLocal deque empty). Without the
    // opt-in flag, the default path is a regular deque push so
    // broad work-stealing is preserved for latency-bound + IMUL-
    // saturated workloads where mailbox concentration hurts.
    let try_mailbox = plan.use_mailbox_routing
        && sibling < ctx.peer_mailboxes.len()
        && sibling < ctx.stealers.len()
        && ctx.peer_mailboxes[sibling].is_empty()
        && ctx.stealers[sibling][crate::sched::deque_tier::DequeTier::SmtLocal.idx()].is_empty();
    let refused = if try_mailbox {
        match ctx.push_to_mailbox(sibling, job_b_ref) {
            Ok(()) => None,
            // Mailbox full - fall through to deque push, honoring
            // any caller-supplied deque_tier_hint.
            Err(returned_job) => push_with_tier_hint(ctx, returned_job, plan).err(),
        }
    } else {
        push_with_tier_hint(ctx, job_b_ref, plan).err()
    };
    if refused.is_some() {
        // Deque full: run both halves here. Waiting for a thief to
        // free a slot deadlocks when every thief is an owner waiting
        // on its own full deque (measured: all 16 rings at 256 on a
        // 65,536-item min_leaf=1 collect).
        let a_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| a(a_injected)));
        // SAFETY: the refused JobRef was never published, so job_b
        // is untouched and uniquely ours to consume.
        let rb = unsafe { job_b.run_inline(false) };
        return match a_result {
            Ok(ra) => (ra, rb),
            Err(payload) => {
                drop(rb);
                std::panic::resume_unwind(payload);
            }
        };
    }
    crate::sched::trace::emit(crate::sched::trace::TraceEvent::JoinPush, 0);

    let traced = dispatch_trace_enabled();
    let t_a_start = if traced { dispatch_tsc() } else { 0 };
    let a_result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| a(a_injected)));
    let t_a_end = if traced { dispatch_tsc() } else { 0 };
    crate::sched::trace::emit(crate::sched::trace::TraceEvent::JoinWaitBegin, 0);

    // Wait loop. The most likely outcome (LIFO, no thief): the
    // first ctx.find_work() returns our own job_b. We special-case
    // that via `id()` match and run it inline (stolen=false). If a
    // thief stole job_b first, we keep finding work until either
    // we observe job_b.latch set (the thief ran it) or we find
    // another job to execute.
    let mut idle_since: Option<std::time::Instant> = None;
    // The last yield's length in microseconds, recorded only while the
    // trace ring is on.
    let mut last_yield_us: Option<u32> = None;
    let spin_budget_ns = plan.effective_spin_before_yield_ns();
    loop {
        if job_b.latch.is_set() {
            if let Some(us) = last_yield_us {
                crate::sched::trace::emit(crate::sched::trace::TraceEvent::JoinLastYield, us);
            }
            crate::sched::trace::emit(crate::sched::trace::TraceEvent::JoinWaitEnd, 1);
            if traced {
                let t_wait_end = dispatch_tsc();
                JOIN_CALL_COUNT.fetch_add(1, Relaxed);
                JOIN_A_BODY_NS.fetch_add(t_a_end.wrapping_sub(t_a_start), Relaxed);
                JOIN_WAIT_NS.fetch_add(t_wait_end.wrapping_sub(t_a_end), Relaxed);
            }
            // Latch set by a thief that already executed job_b.
            // SAFETY: latch is set => StackJob::execute finished
            // => result slot populated.
            let rb = unsafe { job_b.into_result() };
            return match a_result {
                Ok(ra) => (ra, rb),
                Err(payload) => {
                    drop(rb);
                    std::panic::resume_unwind(payload);
                }
            };
        }
        if let Some(job) = ctx.find_work() {
            if job.id() == job_b_id {
                if let Some(us) = last_yield_us {
                    crate::sched::trace::emit(crate::sched::trace::TraceEvent::JoinLastYield, us);
                }
                crate::sched::trace::emit(crate::sched::trace::TraceEvent::JoinWaitEnd, 0);
                if traced {
                    let t_wait_end = dispatch_tsc();
                    JOIN_CALL_COUNT.fetch_add(1, Relaxed);
                    JOIN_A_BODY_NS.fetch_add(t_a_end.wrapping_sub(t_a_start), Relaxed);
                    JOIN_WAIT_NS.fetch_add(t_wait_end.wrapping_sub(t_a_end), Relaxed);
                }
                // Got our own job_b back. Run inline with
                // stolen=false to signal "no thief touched this".
                // SAFETY: the JobRef matches job_b's data
                // pointer; nobody else holds a JobRef for it
                // (we just popped the unique copy out of the
                // local deque), so consuming job_b is sound.
                let rb = unsafe { job_b.run_inline(false) };
                return match a_result {
                    Ok(ra) => (ra, rb),
                    Err(payload) => {
                        drop(rb);
                        std::panic::resume_unwind(payload);
                    }
                };
            }
            // Productive stealing: bracket the execute call so
            // dispatch_trace_wait_snapshot() can attribute cycles
            // to JOIN_WAIT_STEAL_NS.
            let t_steal_start = if traced { dispatch_tsc() } else { 0 };
            // SAFETY: JobRef contract; execute the popped job
            // exactly once.
            // SAFETY: JobRef contract; execute the popped job
            unsafe { job.execute() };
            if traced {
                JOIN_WAIT_STEAL_NS.fetch_add(
                    dispatch_tsc().wrapping_sub(t_steal_start),
                    Relaxed,
                );
            }
        } else {
            // Idle path: find_work returned None, no work to
            // steal. The poll is pure dispatch waste; its cycles
            // go to JOIN_WAIT_IDLE_NS so the breakdown
            // distinguishes productive stealing from worker
            // starvation.
            let t_idle_start = if traced { dispatch_tsc() } else { 0 };
            // Poll the latch in a spin for the plan's budget, the
            // span a stolen half of a dispatch this size completes
            // within, then yield each round so a thief the OS
            // preempted gets its core back. A plan whose single item
            // outlasts that span budgets zero, because the half being
            // waited on is then not about to finish and the spin
            // would only deny a core to the thief running it.
            let idle_since = idle_since.get_or_insert_with(std::time::Instant::now);
            if idle_since.elapsed().as_nanos() >= u128::from(spin_budget_ns) {
                if let Some(us) = wait_after_spin_budget(ctx, &job_b.latch) {
                    last_yield_us = Some(us);
                }
            } else {
                std::hint::spin_loop();
            }
            if traced {
                JOIN_WAIT_IDLE_NS.fetch_add(
                    dispatch_tsc().wrapping_sub(t_idle_start),
                    Relaxed,
                );
            }
        }
    }
}

/// Slow-path body: dispatch a join from outside the worker pool.
///
/// Builds a single wrapper [`StackJob`] whose closure runs the
/// entire `join_in_worker(ctx, plan, a, b)` body, hands it to the
/// pool, and waits on its latch. The caller runs none of the join's
/// work: a worker takes the wrapper and the rest of the pool steals
/// from it, while the caller spins for the plan's budget and then
/// parks until the latch sets. So the call returns only once every
/// leaf has finished, including one whose worker the OS has
/// preempted.
///
/// Every recursive `sched::join` issued from inside `a` or `b`
/// will then be inside a worker context and use the fast path.
/// This is rayon's `in_worker_cold` pattern.
fn external_dispatch<A, B, RA, RB>(plan: &JobPlan, a: A, b: B) -> (RA, RB)
where
    A: FnOnce(bool) -> RA + Send,
    B: FnOnce(bool) -> RB + Send,
    RA: Send,
    RB: Send,
{
    let arena = global_local_arena();
    // Consult `effective_use_smt` (not raw `use_smt`) so the
    // observer's measured per-leaf variance can suppress SMT
    // activation on uniform-cost workloads where SMT siblings
    // contest the same execution unit. The plan's `use_smt` is
    // the prior (set by the DispatchProfile); the observer
    // corrects it based on measured leaf cv^2.
    //
    // When the result is false the call is a no-op - no siblings
    // wake, the pool runs at primary-only width.
    //
    // SMT-on dispatch fires per external_dispatch + is on the per-
    // join hot path. To avoid a Vec::with_capacity allocation on
    // every SMT-on call (single-NUMA hosts = 99% of dev / laptop /
    // single-socket-server hardware), we hold the guard inline on
    // the stack via `try_acquire_smt_single` when possible and only
    // fall back to the allocating multi-NUMA Vec path on multi-node
    // hosts. Both bindings live until end-of-scope so the guards
    // remain held for the duration of the wrapper job.
    let _smt_guard_inline: Option<crate::sched::arena_local::SmtGuard>;
    let _smt_guards_multi: Vec<crate::sched::arena_local::SmtGuard>;
    if plan.effective_use_smt() {
        if arena.is_single_numa() {
            _smt_guard_inline = arena.try_acquire_smt_single();
            _smt_guards_multi = Vec::new();
        } else {
            _smt_guard_inline = None;
            _smt_guards_multi = arena.acquire_smt();
        }
    } else {
        _smt_guard_inline = None;
        _smt_guards_multi = Vec::new();
    }

    // Slot-pool wrap-and-park fast path. Build the join body as a
    // single StackJob with a SpinLatch wired to a caller-thread
    // Parker. Push the job to the slot's deque (whose stealer is
    // registered in arena.stealers so primaries can see + steal
    // it). Broadcast-wake all primaries. Park the caller on the
    // SpinLatch handshake until a primary completes the join.
    //
    // The body runs entirely on the primary that steals it, using
    // the primary's own WorkerCtx (8MB stack). Running it on the
    // caller instead (caller temporarily becomes a worker via TLS
    // ctx install) overflows the caller's 1MB Windows stack when
    // nested join_in_worker recurses on deep bisects.
    //
    // For an NMFD-shape workload (5 items x 45s, depth 2 bisect):
    // 1 primary runs probe + leftmost item, 3 other primaries
    // steal the bisect right-halves via the slot's registered
    // stealer + normal find_work scanning. Critical path
    // approaches 90s (probe 45s + parallel bisect 45s).
    //
    // Falls through to the legacy wrapper-job + injector +
    // LockLatch path if all slots are currently claimed.
    let arena_for_slot: Arc<crate::sched::arena_local::LocalArena> = arena
        .single_node_arc()
        .unwrap_or_else(|| arena.node_arc(plan.numa_hint));
    if let Some(_guard) = arena_for_slot.try_claim_external_slot() {
        let slot_ctx = _guard.ctx_ref();
        // Caller-thread Parker for the SpinLatch wake. Captures
        // the calling thread's Thread handle at construction;
        // SpinLatch::set unparks this exact thread when the
        // primary completes the job.
        //
        // Wrap-and-park unconditionally: no depth-switch to a
        // caller-as-worker variant on small batch_size. Measured
        // on the NMFD workload, wrap-and-park runs 96s vs the
        // caller-as-worker path's 161s. Criterion's continuous-
        // iter pattern keeps primaries hot, which flatters
        // caller-as-worker on small N; a real one-off workload
        // (NMFD) has primaries parked between calls, where
        // caller-as-worker's eager own-pop loses the race vs
        // broadcast-wake + primary steal. Caller-parks-while-
        // primary-runs is strictly better for the cold-cache case.
        // Under levers::slot_park_now the parker takes no yield rounds,
        // since the loop below has already spun for the plan's budget.
        let parker = Arc::new(Parker::new(if crate::sched::levers::slot_park_now() {
            0
        } else {
            crate::sched::arena_local::LOCAL_SPIN_ROUNDS
        }));
        let job = StackJob::new(
            move |_stolen: bool| -> (RA, RB) {
                let primary_ctx_ptr = current_worker_ctx();
                debug_assert!(
                    !primary_ctx_ptr.is_null(),
                    "wrap-and-park body must run on a worker thread"
                );
                // SAFETY: ctx lives for the duration of the
                // worker that runs this job.
                let primary_ctx = unsafe { &*primary_ctx_ptr };
                crate::sched::trace::emit(crate::sched::trace::TraceEvent::SlotJobStart, 0);
                let out = join_in_worker(primary_ctx, plan, a, b, true);
                crate::sched::trace::emit(crate::sched::trace::TraceEvent::SlotJobEnd, 0);
                out
            },
            SpinLatch::new(parker.clone()),
        );
        unsafe {
            let r = job.as_job_ref(
                plan.k_outer,
                plan.numa_hint.unwrap_or(NUMA_HINT_ANY as u32) as u8,
                plan.variant,
            );
            // Push to slot's Public deque. Slot's stealer is in
            // arena.stealers from arena init -- primaries' random
            // victim pick can land on this slot and steal the job.
            slot_ctx.workers
                [crate::sched::deque_tier::DequeTier::Public.idx()]
                .push(r);
        }
        // Broadcast-wake all primaries so they wake and scan at
        // once; a scanning worker probes the held slots' deques
        // before any peer, so the job is taken within a round.
        slot_ctx.sleep.new_internal_jobs(
            slot_ctx.stealers.len() as u32,
            false,
        );
        // Park the caller on the SpinLatch via the sleep handshake
        // (unset, sleepy, sleeping, then set wakes it).
        // The caller spins for the plan's budget before it parks: a
        // call that finishes within the spin never pays the park's
        // wake, and a plan whose single item outlasts the budget
        // spins none, its wait being far longer than a wake costs.
        // Below the budget
        // the spin is still floored at a fixed count, so a plan that
        // budgets zero absorbs a fast-completion race here rather
        // than parking for a job already done.
        const SLOT_WAIT_SPIN: usize = 256;
        crate::sched::trace::emit(crate::sched::trace::TraceEvent::SlotPush, 0);
        let spin_budget_ns = plan.effective_spin_before_yield_ns();
        // Cycles one monitor wait covers, or zero where the lever is
        // off or the host has no monitor that holds. Read once, so the
        // arm a wait takes cannot change partway through this loop.
        // The budget above still bounds the whole spin either way; what
        // this changes is what the thread does between its polls, which
        // is a PAUSE that issues into the pipeline or a wait on the
        // latch's own line that issues nothing.
        let monitor_cycles = if crate::sched::levers::latch_monitor()
            && crate::sched::sleep::monitor_wait_available()
        {
            crate::sched::par_iter::installed_dispatch_cost_ns()
                .saturating_mul(crate::sched::par_iter::tsc_per_ns_16())
                / 16
        } else {
            0
        };
        let wait_started = std::time::Instant::now();
        let mut spun = 0usize;
        let mut parked = false;
        loop {
            if job.latch.is_set() {
                break;
            }
            let keep_spinning = spun < SLOT_WAIT_SPIN
                || wait_started.elapsed().as_nanos() < u128::from(spin_budget_ns);
            if keep_spinning {
                // The fixed floor stays a PAUSE spin, so a set already
                // in flight is caught by the polls it was sized for;
                // only the budget-driven remainder waits on the line.
                if monitor_cycles > 0 && spun >= SLOT_WAIT_SPIN {
                    if spun == SLOT_WAIT_SPIN {
                        crate::sched::sleep::note_latch_monitor_wait(true);
                    }
                    crate::sched::sleep::note_latch_monitor_arm();
                    // SAFETY: the line is this job's own latch state,
                    // which outlives the wait because the caller does
                    // not return until the latch is set, and the wait
                    // is issued only where CPUID reported the pair.
                    unsafe {
                        crate::sched::sleep::monitor_wait_once(
                            job.latch.core.line(),
                            monitor_cycles,
                            || job.latch.is_set(),
                        );
                    }
                } else {
                    std::hint::spin_loop();
                }
                spun += 1;
                continue;
            }
            if !job.latch.get_sleepy() {
                spun = 0;
                continue;
            }
            if job.latch.is_set() {
                job.latch.wake_up();
                break;
            }
            if !job.latch.fall_asleep() {
                spun = 0;
                continue;
            }
            let _unparked = parker.park_until(|| job.latch.is_set());
            parked = true;
            job.latch.wake_up();
            spun = 0;
        }
        crate::sched::trace::emit(crate::sched::trace::TraceEvent::SlotWaitEnd, u32::from(!parked));
        // SAFETY: latch is set => StackJob::execute finished =>
        // result slot populated.
        let result = unsafe { job.into_result() };
        drop(_guard);
        return result;
    }

    // Slot pool exhausted: fall through to the wrapper-job path
    // (the original external_dispatch design). Rare under normal
    // load -- only triggers when >32 caller threads concurrently
    // call sched::join from outside the pool. Tag with
    // core::hint::cold_path so LLVM (>= 21 since rust 1.96) reorders
    // basic blocks to keep the slot-pool fast path icache-warm and
    // pushes this wrapper-allocation + LockLatch park-handshake
    // sequence into a cold section.
    core::hint::cold_path();
    let wrapper = StackJob::new(
        move |_stolen: bool| -> (RA, RB) {
            let ctx_ptr = current_worker_ctx();
            debug_assert!(
                !ctx_ptr.is_null(),
                "external_dispatch wrapper must run on a worker thread"
            );
            let ctx = unsafe { &*ctx_ptr };
            join_in_worker(ctx, plan, a, b, true)
        },
        LockLatch::new(),
    );
    unsafe {
        let r = wrapper.as_job_ref(
            plan.k_outer,
            plan.numa_hint.unwrap_or(NUMA_HINT_ANY as u32) as u8,
            plan.variant,
        );
        arena.submit(r, plan.numa_hint);
    }
    let predicted_ns = plan.estimated_per_item_ns
        .map(|n| (n as u64).saturating_mul(plan.batch_size.max(1) as u64));
    let spin_cycles = match predicted_ns {
        Some(ns) => (ns / 3).clamp(1_000, 500_000) as usize,
        None => 200_000,
    };
    wrapper.latch.wait_spin_then_monitor(spin_cycles);
    unsafe { wrapper.into_result() }
}

/// Run both closures serially on the caller thread. No scheduler
/// state touched. Cheapest possible join: zero allocations, zero
/// atomics, zero context switches. Both closures receive
/// `false` for their migrated/stolen flag (serial execution = no
/// steal pressure).
#[inline]
fn inline_join_context<A, B, RA, RB>(a: A, b: B) -> (RA, RB)
where
    A: FnOnce(bool) -> RA,
    B: FnOnce(bool) -> RB,
{
    let ra = a(false);
    let rb = b(false);
    (ra, rb)
}

/// Convenience: build a default plan for `(k_outer, batch_size)`
/// and call [`join`]. Use this when you do not need to customize
/// hw_class / variant / numa_hint.
pub fn join_default<A, B, RA, RB>(
    k_outer: u8,
    batch_size: u32,
    a: A,
    b: B,
) -> (RA, RB)
where
    A: FnOnce() -> RA + Send,
    B: FnOnce() -> RB + Send,
    RA: Send,
    RB: Send,
{
    let plan = JobPlan::new(k_outer, batch_size);
    join(&plan, a, b)
}

/// Silence the unused-import warning when no caller has reached
/// for `NUMA_HINT_ANY` from this module. The constant is re-
/// exported at the crate root via `crate::sched::NUMA_HINT_ANY`.
#[allow(dead_code)]
const _NUMA_HINT_ANY_REEXPORT: u8 = NUMA_HINT_ANY;

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    use std::sync::Arc;
    use std::sync::atomic::{AtomicU32, Ordering};

    use crate::foundation::Variant;
    use crate::sched::plan::HwClass;

    #[test]
    fn inline_join_returns_both_results() {
        let plan = JobPlan::new(2, 1);
        let (ra, rb) = join(&plan, || 10u32, || 20u32);
        assert_eq!(ra, 10);
        assert_eq!(rb, 20);
    }

    #[test]
    fn inline_join_runs_a_before_b_when_serial() {
        // The serial dispatch runs a first, then b. Closures that
        // observe shared state must see the order (10, 20).
        // A hint-less plan of 32 items or fewer is classed latency-
        // bound, which activates SMT and routes even one item to the
        // pool, where a peer may steal b and run it first. An explicit
        // light estimate classes the plan fine-grain and keeps the
        // join inline, which is the tier this test is about.
        let order = Arc::new(AtomicU32::new(0));
        let order_a = Arc::clone(&order);
        let order_b = Arc::clone(&order);
        let plan = JobPlan::new(2, 1).with_estimated_per_item_ns(10);
        assert_eq!(pick_tier(&plan, numa_topology()), SchedTier::Inline);
        let (ra, rb) = join(
            &plan,
            move || order_a.fetch_add(10, Ordering::SeqCst),
            move || order_b.fetch_add(20, Ordering::SeqCst),
        );
        // a saw 0 (the original); b saw 10 (after a added 10).
        assert_eq!(ra, 0);
        assert_eq!(rb, 10);
        assert_eq!(order.load(Ordering::SeqCst), 30);
    }

    #[test]
    fn inline_join_propagates_panic_from_a() {
        let plan = JobPlan::new(2, 1);
        let r = std::panic::catch_unwind(|| {
            join::<_, _, u32, u32>(&plan, || panic!("a-side panic"), || 7u32)
        });
        assert!(r.is_err(), "a-side panic must propagate to caller");
    }

    #[test]
    fn join_default_builds_plan_and_runs() {
        let (ra, rb) = join_default(8, 1024, || 1u32, || 2u32);
        assert_eq!((ra, rb), (1, 2));
    }

    #[test]
    fn join_with_each_tier_band_dispatches_correctly() {
        // K = 2 (Inline band), K = 6 (Local band), K = 9
        // (Hierarchical or Local depending on NUMA), K = 13
        // (Federated band). All four tiers currently route through
        // the inline path; the contract is "results returned, no
        // crash" for each band.
        for k in [2u8, 6, 9, 13] {
            let plan = JobPlan::new(k, 1024)
                .with_hw_class(HwClass::Scalar)
                .with_variant(Variant::Faithful);
            let (ra, rb) = join(&plan, || k as u32, || (k as u32) << 1);
            assert_eq!(ra, k as u32);
            assert_eq!(rb, (k as u32) << 1);
        }
    }

    #[test]
    fn join_with_numa_hint_does_not_crash_single_node_host() {
        // The numa_hint is currently a tag; on a single-NUMA host
        // it is recorded in the JobPlan and ignored by the
        // dispatcher. Verify no crash.
        let plan = JobPlan::new(6, 1024).with_numa_hint(0);
        let (ra, rb) = join(&plan, || 1u32, || 2u32);
        assert_eq!((ra, rb), (1, 2));
    }
}