henad_compute/cpu/field/
ca.rs

1//! A [`GridModel`] gather rule as a [`FieldLayer`].
2
3use std::marker::PhantomData;
4
5use henad_core::authoring::model::field::{Extent, FieldLayer};
6use henad_core::authoring::model::grid_model::GridModel;
7use henad_core::grid::Grid2D;
8use henad_core::params::{ParamDescriptor, ParamValue};
9use henad_core::topology::NeighborhoodKind;
10use henad_core::view::GridView;
11
12use crate::cpu::primitives::chunked::{advance_tick_seed, chunk_seed};
13use crate::for_each_chunk_mut;
14
15/// State a grid model's random number generator (RNG) starts from when a run has no seed.
16pub const GRID_INIT_SEED: u64 = 0xDEAD_BEEF_CAFE_1234;
17
18/// Returns the state a grid model's RNG starts from: `seed` mixed, or [`GRID_INIT_SEED`] when it is `None`.
19///
20/// A GPU port that reproduces its CPU model's tick 0 starts from the same state.
21pub fn grid_init_rng(seed: Option<u64>) -> u64 {
22    seed.map_or(GRID_INIT_SEED, henad_core::authoring::primitives::rng::mix_seed)
23}
24
25/// Double-buffered `u8` cells stepped by `M`'s neighbourhood rule.
26pub struct CaField<M: GridModel> {
27    grid: Grid2D<u8>,
28    /// Base seed, advanced once per tick and fanned out per row by `chunk_seed`.
29    seed: u64,
30    _marker: PhantomData<M>,
31}
32
33/// Prints the model's name and the grid's size, not its cells.
34impl<M: GridModel> std::fmt::Debug for CaField<M> {
35    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
36        f.debug_struct("CaField")
37            .field("model", &M::NAME)
38            .field("grid", &self.grid)
39            .finish_non_exhaustive()
40    }
41}
42
43impl<M: GridModel> CaField<M> {
44    /// Read access for tests and for `M::stats`.
45    pub fn grid(&self) -> &Grid2D<u8> {
46        &self.grid
47    }
48
49    /// Write access, for an action that rewrites the cells.
50    pub fn grid_mut(&mut self) -> &mut Grid2D<u8> {
51        &mut self.grid
52    }
53
54    /// Number of rayon jobs one tick splits into.
55    pub fn parallel_jobs(&self) -> usize {
56        let width = self.grid.width() as usize;
57        let height = self.grid.height() as usize;
58        height.div_ceil(rows_per_leaf(width, height))
59    }
60
61    /// Builds a field seeded from `seed`, or from [`GRID_INIT_SEED`] when it is `None`.
62    pub fn with_seed(extent: Extent, params: &[ParamValue], seed: Option<u64>) -> Self {
63        let (width, height) = extent.cells();
64        let mut grid = Grid2D::new(width, height);
65        let mut seed = grid_init_rng(seed);
66        M::init(&mut grid, params, &mut seed);
67        Self {
68            grid,
69            seed,
70            _marker: PhantomData,
71        }
72    }
73
74    /// Builds a field holding `cells`, seeded from [`GRID_INIT_SEED`].
75    ///
76    /// Returns `None` unless `cells` is exactly the length `extent` implies.
77    pub fn from_cells(extent: Extent, cells: &[u8]) -> Option<Self> {
78        let (width, height) = extent.cells();
79        if cells.len() != width as usize * height as usize {
80            return None;
81        }
82        let mut grid = Grid2D::new(width, height);
83        grid.current_mut().copy_from_slice(cells);
84        Some(Self {
85            grid,
86            seed: GRID_INIT_SEED,
87            _marker: PhantomData,
88        })
89    }
90}
91
92impl<M: GridModel> FieldLayer for CaField<M> {
93    const KIND: &'static str = "Cellular automaton";
94
95    type Params = M::Params;
96    type Read<'a> = &'a [u8];
97    type DepositLanes = ();
98
99    fn param_descriptors() -> Vec<ParamDescriptor> {
100        M::param_descriptors()
101    }
102
103    fn from_params(params: &[ParamValue]) -> M::Params {
104        M::from_params(params)
105    }
106
107    fn new(extent: Extent, params: &[ParamValue]) -> Self {
108        Self::with_seed(extent, params, None)
109    }
110
111    fn read(&self) -> &[u8] {
112        self.grid.current()
113    }
114
115    fn alloc_deposits(&self, _n: usize) {}
116
117    fn update(&mut self, (): &(), p: &M::Params, tick: u64) {
118        step_grid::<M>(&mut self.grid, p, self.seed, tick);
119        self.seed = advance_tick_seed(self.seed, tick);
120        self.grid.swap();
121    }
122
123    fn grid_view(&self) -> Option<GridView<'_>> {
124        Some(GridView {
125            width: self.grid.width(),
126            height: self.grid.height(),
127            cells: self.grid.current(),
128            palette: M::PALETTE,
129        })
130    }
131
132    fn cell_count(&self) -> usize {
133        self.grid.len()
134    }
135
136    fn heap_bytes(&self) -> usize {
137        self.grid.heap_bytes()
138    }
139}
140
141/// Floor on the number of cells one rayon leaf takes. Below this the split tree and the wake-up cost more
142/// than the rows do.
143///
144/// A row's cost varies with what its cells hold, and a larger floor stops rayon balancing that by stealing.
145const MIN_LEAF_CELLS: usize = 8_192;
146
147/// Returns the floor on the number of rows one rayon leaf takes, at least one and at most the grid's height.
148///
149/// A grid with rows to spare still splits down to it, and rayon balances the rest by stealing. A small grid is a
150/// single job. The floor does not depend on the worker count.
151fn rows_per_leaf(width: usize, height: usize) -> usize {
152    MIN_LEAF_CELLS.div_ceil(width.max(1)).min(height).max(1)
153}
154
155fn step_grid<M: GridModel>(grid: &mut Grid2D<u8>, hot: &M::Params, seed: u64, tick: u64) {
156    let h = grid.height();
157    let ws = grid.width() as usize;
158    let leaf = rows_per_leaf(ws, h as usize);
159    let (current, next) = grid.current_and_next_mut();
160
161    match M::NEIGHBORHOOD {
162        NeighborhoodKind::Moore => {
163            for_each_chunk_mut!(next, ws, min_leaf leaf, |y, _base, next_row| {
164                let mut rng = chunk_seed(seed, tick, y);
165                step_row_moore::<M>(neighbor_rows(current, ws, y, h), next_row, hot, &mut rng);
166            });
167        }
168        NeighborhoodKind::VonNeumann => {
169            for_each_chunk_mut!(next, ws, min_leaf leaf, |y, _base, next_row| {
170                let mut rng = chunk_seed(seed, tick, y);
171                step_row_vn::<M>(neighbor_rows(current, ws, y, h), next_row, hot, &mut rng);
172            });
173        }
174    }
175}
176
177/// Returns the rows above, at and below `y`, wrapped vertically.
178///
179/// Each slice is exactly one row wide. A neighbour access is then a single index instead of a `row * stride + x`
180/// multiply-add.
181#[inline]
182fn neighbor_rows(current: &[u8], ws: usize, y: usize, h: u32) -> [&[u8]; 3] {
183    let hs = h as usize;
184    let ym = if y == 0 { hs - 1 } else { y - 1 };
185    let yp = if y + 1 == hs { 0 } else { y + 1 };
186    [
187        &current[ym * ws..ym * ws + ws],
188        &current[y * ws..y * ws + ws],
189        &current[yp * ws..yp * ws + ws],
190    ]
191}
192
193#[inline(always)]
194fn moore_cell<M: GridModel>(rows: [&[u8]; 3], xm: usize, x: usize, xp: usize, hot: &M::Params, rng: &mut u64) -> u8 {
195    let [up, mid, down] = rows;
196    let neighbors = [up[xm], up[x], up[xp], mid[xm], mid[xp], down[xm], down[x], down[xp]];
197    M::step_cell(mid[x], &neighbors, hot, rng)
198}
199
200#[inline(always)]
201fn vn_cell<M: GridModel>(rows: [&[u8]; 3], xm: usize, x: usize, xp: usize, hot: &M::Params, rng: &mut u64) -> u8 {
202    let [up, mid, down] = rows;
203    let neighbors = [up[x], mid[xm], mid[xp], down[x]];
204    M::step_cell(mid[x], &neighbors, hot, rng)
205}
206
207/// Steps one row of a Moore grid into `next_row`.
208///
209/// Only the first and last column wrap in x. Both columns are peeled off, and the interior runs an `enumerate()`
210/// loop without a per-cell modulo. Keep that shape on this hot path. `last.min(1)` covers a one-column grid, where
211/// both wraps land on x 0.
212#[inline(always)]
213fn step_row_moore<M: GridModel>(rows: [&[u8]; 3], next_row: &mut [u8], hot: &M::Params, rng: &mut u64) {
214    let Some(last) = next_row.len().checked_sub(1) else {
215        return;
216    };
217    next_row[0] = moore_cell::<M>(rows, last, 0, last.min(1), hot, rng);
218    if let Some(interior) = next_row.get_mut(1..last) {
219        for (i, out) in interior.iter_mut().enumerate() {
220            let x = i + 1;
221            *out = moore_cell::<M>(rows, x - 1, x, x + 1, hot, rng);
222        }
223    }
224    if last > 0 {
225        next_row[last] = moore_cell::<M>(rows, last - 1, last, 0, hot, rng);
226    }
227}
228
229/// Von Neumann counterpart of [`step_row_moore`].
230#[inline(always)]
231fn step_row_vn<M: GridModel>(rows: [&[u8]; 3], next_row: &mut [u8], hot: &M::Params, rng: &mut u64) {
232    let Some(last) = next_row.len().checked_sub(1) else {
233        return;
234    };
235    next_row[0] = vn_cell::<M>(rows, last, 0, last.min(1), hot, rng);
236    if let Some(interior) = next_row.get_mut(1..last) {
237        for (i, out) in interior.iter_mut().enumerate() {
238            let x = i + 1;
239            *out = vn_cell::<M>(rows, x - 1, x, x + 1, hot, rng);
240        }
241    }
242    if last > 0 {
243        next_row[last] = vn_cell::<M>(rows, last - 1, last, 0, hot, rng);
244    }
245}
246
247#[cfg(test)]
248mod tests {
249    use henad_core::authoring::primitives::space::{MOORE_ROW_MAJOR, VON_NEUMANN};
250    use henad_core::view::{StatDescriptor, StatValue};
251
252    use super::*;
253
254    /// Each cell holds its own offset from the centre, so a neighbour slice spells out the order.
255    fn encode(dx: i32, dy: i32) -> u8 {
256        ((dx + 1) * 3 + (dy + 1)) as u8
257    }
258
259    const CENTER: u8 = 4;
260
261    macro_rules! order_probe {
262        ($name:ident, $kind:expr, $table:expr) => {
263            struct $name;
264
265            impl GridModel for $name {
266                const NAME: &'static str = "order probe";
267                const ID: &'static str = "order_probe";
268                const DESCRIPTION: &'static str = "";
269                const PALETTE: &'static [[u8; 4]] = &[[0, 0, 0, 255]];
270                const NEIGHBORHOOD: NeighborhoodKind = $kind;
271                const STATS: &'static [StatDescriptor] = &[];
272                type Params = ();
273
274                fn param_descriptors() -> Vec<ParamDescriptor> {
275                    Vec::new()
276                }
277
278                fn from_params(_params: &[ParamValue]) {}
279
280                fn init(_grid: &mut Grid2D<u8>, _params: &[ParamValue], _rng: &mut u64) {}
281
282                fn step_cell(cell: u8, neighbors: &[u8], (): &(), _rng: &mut u64) -> u8 {
283                    if cell == CENTER {
284                        let want: Vec<u8> = $table.iter().map(|&(dx, dy)| encode(dx, dy)).collect();
285                        assert_eq!(
286                            neighbors,
287                            want.as_slice(),
288                            "step_cell's neighbour order must match the published table"
289                        );
290                    }
291                    cell
292                }
293
294                fn stats(_grid: &Grid2D<u8>) -> Vec<StatValue> {
295                    Vec::new()
296                }
297            }
298        };
299    }
300
301    order_probe!(MooreProbe, NeighborhoodKind::Moore, MOORE_ROW_MAJOR);
302    order_probe!(VonNeumannProbe, NeighborhoodKind::VonNeumann, VON_NEUMANN);
303
304    fn probe_grid() -> Grid2D<u8> {
305        let mut grid = Grid2D::new(3, 3);
306        let cells = grid.current_mut();
307        for dy in -1..=1 {
308            for dx in -1..=1 {
309                cells[((dy + 1) * 3 + (dx + 1)) as usize] = encode(dx, dy);
310            }
311        }
312        grid
313    }
314
315    /// A model indexes its `neighbors` slice by position, so the engine's gather order is API.
316    /// The assertion itself lives inside the probe's `step_cell`.
317    #[test]
318    fn the_gather_order_matches_the_published_moore_table() {
319        step_grid::<MooreProbe>(&mut probe_grid(), &(), 1, 0);
320    }
321
322    #[test]
323    fn the_gather_order_matches_the_published_von_neumann_table() {
324        step_grid::<VonNeumannProbe>(&mut probe_grid(), &(), 1, 0);
325    }
326
327    /// A grid under the leaf floor runs on one worker however wide the pool is, and the benchmark
328    /// CSV carries this number so such a run is not mistaken for a full-width one.
329    #[test]
330    fn a_grid_under_the_leaf_floor_is_one_job() {
331        let small = CaField::<MooreProbe>::with_seed(Extent { w: 64.0, h: 64.0 }, &[], None);
332        assert_eq!(small.parallel_jobs(), 1);
333
334        // 8192 cells is two rows at this width.
335        let wide = CaField::<MooreProbe>::with_seed(Extent { w: 4096.0, h: 100.0 }, &[], None);
336        assert_eq!(wide.parallel_jobs(), 50);
337    }
338
339    /// The field implements `Debug` for a model that does not, and prints its size alone. A derive would bound its
340    /// impl on the model and print every cell.
341    #[test]
342    fn the_field_prints_its_size_for_any_model() {
343        let field = CaField::<MooreProbe>::with_seed(Extent { w: 64.0, h: 32.0 }, &[], None);
344        assert_eq!(
345            format!("{field:?}"),
346            "CaField { model: \"order probe\", grid: Grid2D { width: 64, height: 32, .. }, .. }"
347        );
348    }
349}
henad_compute/cpu/field/ca.rs

henad_compute/cpu/field/
ca.rs
