Skip to main content

linkcell/
pop.rs

1//! POP3 timing for a scaling run.
2//!
3//! [POP3](https://pop-coe.eu/) is the multiplicative hierarchy. Useful
4//! time is time inside the user loops, not time spent waiting on other
5//! workers. Load balance is the average useful time over the maximum.
6//! Communication efficiency is that maximum over the wall time.
7//! Parallel efficiency is their product. Computation scaling and
8//! global efficiency need a 1-thread reference, which
9//! `scripts/pop-report.py` applies. Instruction, IPC, and frequency
10//! scaling need a PMU, and this host has none.
11//!
12//! Set `LINKCELL_POP`, or call [`engage`], and the mesh build and the
13//! walk record useful time on each rayon worker. The scale probes call
14//! [`engage`] so a profile always uses this hierarchy.
15
16use std::sync::atomic::{AtomicU64, AtomicU8, AtomicUsize, Ordering};
17use std::sync::OnceLock;
18use std::time::Instant;
19
20const MAX_THREADS: usize = 128;
21
22fn slots() -> &'static [AtomicU64] {
23    static SLOTS: OnceLock<Box<[AtomicU64]>> = OnceLock::new();
24    SLOTS.get_or_init(|| (0..MAX_THREADS).map(|_| AtomicU64::new(0)).collect())
25}
26
27thread_local! {
28    static SLOT: std::cell::Cell<usize> = const { std::cell::Cell::new(usize::MAX) };
29    static IN_POOL: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
30}
31
32static NEXT: AtomicUsize = AtomicUsize::new(0);
33static NTHREADS: AtomicUsize = AtomicUsize::new(1);
34
35static FLAG: AtomicU8 = AtomicU8::new(0);
36
37pub(crate) fn enabled() -> bool {
38    match FLAG.load(Ordering::Relaxed) {
39        1 => false,
40        2 => true,
41        _ => {
42            let on = std::env::var_os("LINKCELL_POP").is_some();
43            let _ = FLAG.compare_exchange(
44                0,
45                if on { 2 } else { 1 },
46                Ordering::Relaxed,
47                Ordering::Relaxed,
48            );
49            FLAG.load(Ordering::Relaxed) == 2
50        }
51    }
52}
53
54/// Turn POP3 counters on for this process.
55///
56/// Scale probes call this before [`prepare`] so the run records useful
57/// time even when `LINKCELL_POP` is unset. A later call wins over an
58/// earlier read of the environment.
59pub fn engage() {
60    FLAG.store(2, Ordering::Relaxed);
61}
62
63/// POP3 factors for one run: load balance, communication efficiency,
64/// parallel efficiency.
65///
66/// `useful` is one nanosecond total per worker. `wall_ns` is the
67/// elapsed time of the same repetitions.
68pub fn efficiencies(useful: &[u64], wall_ns: u64) -> (f64, f64, f64) {
69    if useful.is_empty() {
70        return (0.0, 0.0, 0.0);
71    }
72    let sum: u64 = useful.iter().copied().sum();
73    let max = useful.iter().copied().max().unwrap_or(0);
74    let avg = sum as f64 / useful.len() as f64;
75    let lb = if max == 0 { 0.0 } else { avg / max as f64 };
76    let ce = if wall_ns == 0 {
77        0.0
78    } else {
79        max as f64 / wall_ns as f64
80    };
81    (lb, ce, lb * ce)
82}
83
84fn slot() -> usize {
85    SLOT.with(|cell| {
86        let cur = cell.get();
87        if cur != usize::MAX {
88            return cur;
89        }
90        let id = NEXT.fetch_add(1, Ordering::Relaxed);
91        cell.set(id);
92        id
93    })
94}
95
96/// Worker slot for this thread. A caller outside the pool folds its
97/// serial time into worker 0, which is the master in the POP model.
98fn worker_slot() -> usize {
99    let in_pool = IN_POOL.with(|cell| cell.get());
100    if in_pool {
101        slot()
102    } else {
103        0
104    }
105}
106
107/// Give every worker a slot. Call once before the timed repetitions.
108///
109/// Does nothing until [`engage`] or `LINKCELL_POP`.
110pub fn prepare() {
111    if !enabled() {
112        return;
113    }
114    #[cfg(feature = "parallel")]
115    {
116        rayon::broadcast(|_| {
117            IN_POOL.with(|cell| cell.set(true));
118            let _ = slot();
119        });
120        NTHREADS.store(crate::pool_width(), Ordering::Relaxed);
121    }
122    #[cfg(not(feature = "parallel"))]
123    {
124        let _ = slot();
125        NTHREADS.store(1, Ordering::Relaxed);
126    }
127}
128
129/// Zero the useful-time counters. Slot assignment stays.
130///
131/// Does nothing until [`engage`] or `LINKCELL_POP`.
132pub fn reset() {
133    if !enabled() {
134        return;
135    }
136    for entry in slots() {
137        entry.store(0, Ordering::Relaxed);
138    }
139}
140
141fn add_slot(slot_id: usize, ns: u64) {
142    if slot_id < slots().len() {
143        slots()[slot_id].fetch_add(ns, Ordering::Relaxed);
144    }
145}
146
147/// Record `ns` of useful work on worker `slot`.
148///
149/// The fused k-nearest team calls this with its slot, which is not a
150/// rayon worker. No-op until [`engage`] or `LINKCELL_POP`.
151#[cfg(all(feature = "parallel", linkcell_openmp))]
152pub(crate) fn add_useful(slot: usize, ns: u64) {
153    if enabled() {
154        add_slot(slot, ns);
155    }
156}
157
158/// How many worker slots [`snapshot`] keeps.
159///
160/// The fused query sets this to the k-nearest team. A later [`prepare`]
161/// overwrites it with the rayon pool size.
162#[cfg(all(feature = "parallel", linkcell_openmp))]
163pub(crate) fn set_threads(n: usize) {
164    if enabled() {
165        NTHREADS.store(n.clamp(1, MAX_THREADS), Ordering::Relaxed);
166    }
167}
168
169/// Useful nanoseconds on each worker, in slot order.
170///
171/// Empty until [`engage`] or `LINKCELL_POP`.
172pub fn snapshot() -> Vec<u64> {
173    if !enabled() {
174        return Vec::new();
175    }
176    let n = NTHREADS.load(Ordering::Relaxed).clamp(1, MAX_THREADS);
177    (0..n).map(|i| slots()[i].load(Ordering::Relaxed)).collect()
178}
179
180/// Times one rayon job, or one serial section, and adds it on drop.
181pub(crate) struct JobTimer {
182    start: Option<Instant>,
183    slot: usize,
184}
185
186impl JobTimer {
187    pub(crate) fn new() -> Self {
188        if !enabled() {
189            return Self {
190                start: None,
191                slot: 0,
192            };
193        }
194        Self {
195            start: Some(Instant::now()),
196            slot: worker_slot(),
197        }
198    }
199}
200
201impl Drop for JobTimer {
202    fn drop(&mut self) {
203        if let Some(start) = self.start.take() {
204            add_slot(self.slot, start.elapsed().as_nanos() as u64);
205        }
206    }
207}
208
209#[cfg(test)]
210mod tests {
211    use super::*;
212
213    #[test]
214    fn efficiencies_match_pop3() {
215        let (lb, ce, pe) = efficiencies(&[2, 4], 8);
216        assert!((lb - 0.75).abs() < 1e-12);
217        assert!((ce - 0.5).abs() < 1e-12);
218        assert!((pe - 0.375).abs() < 1e-12);
219    }
220}