use crate::atomic_dist::{atomic_dist_parent_vec, atomic_dist_parent_vec_int, AtomicDistParent};
use crate::connectivity_graph::ConnectivityGraph;
use crate::dijkstra::{checked_int_distance_bound, select_dist_width, Dist, DistWidth, IntQueue};
use crate::halo::PaddedShape;
use crate::neighborhood::{neighborhood_masks, neighborhood_offsets, DIRECTIONS_26};
use crate::queue::binary_heap::BinaryHeapQueue;
use crate::queue::bucket::BucketQueue;
use crate::queue::PriorityQueue;
use crate::voxel::{ToU64Fast, VolumeShape, VoxelSource};
use crate::{Connectivity, Dijkstra3dError, Result};
use num_traits::ToPrimitive;
use rayon::prelude::*;
use std::collections::VecDeque;
pub struct NeighborhoodContext {
pub offsets: [i64; 26],
pub masks: [u32; 26],
pub neighbor_count: usize,
}
impl NeighborhoodContext {
pub fn new(shape: &VolumeShape, connectivity: Connectivity) -> Self {
let sx = shape.sx as i64;
let sxy = (shape.sx * shape.sy) as i64;
Self {
offsets: neighborhood_offsets(sx, sxy),
masks: neighborhood_masks(),
neighbor_count: connectivity.count(),
}
}
}
#[inline]
pub(crate) fn is_neighbor_in_bounds(
x: u64,
y: u64,
z: u64,
dx: i32,
dy: i32,
dz: i32,
sx: i64,
sy: i64,
sz: i64,
) -> bool {
let nx = x as i64 + dx as i64;
let ny = y as i64 + dy as i64;
let nz = z as i64 + dz as i64;
nx >= 0 && nx < sx && ny >= 0 && ny < sy && nz >= 0 && nz < sz
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct UpstreamCompatEntry<T> {
pub(crate) priority: f32,
pub(crate) payload: T,
}
#[derive(Debug)]
pub(crate) struct LibstdcxxCompatHeap<T> {
entries: Vec<UpstreamCompatEntry<T>>,
}
impl<T> Default for LibstdcxxCompatHeap<T> {
fn default() -> Self {
Self {
entries: Vec::new(),
}
}
}
impl<T: Copy> LibstdcxxCompatHeap<T> {
pub(crate) fn push(&mut self, entry: UpstreamCompatEntry<T>) {
self.entries.push(entry);
let mut hole = self.entries.len() - 1;
while hole > 0 {
let parent = (hole - 1) / 2;
if self.entries[parent].priority < entry.priority {
break;
}
self.entries[hole] = self.entries[parent];
hole = parent;
}
self.entries[hole] = entry;
}
pub(crate) fn pop(&mut self) -> Option<UpstreamCompatEntry<T>> {
let result = self.entries.first().copied()?;
let replacement = self.entries.pop()?;
let len = self.entries.len();
if len == 0 {
return Some(result);
}
let top = 0usize;
let mut hole = top;
let mut second_child = hole;
while second_child < (len - 1) / 2 {
second_child = 2 * (second_child + 1);
if self.entries[second_child].priority >= self.entries[second_child - 1].priority {
second_child -= 1;
}
self.entries[hole] = self.entries[second_child];
hole = second_child;
}
if len % 2 == 0 && second_child == (len - 2) / 2 {
second_child = 2 * (second_child + 1);
self.entries[hole] = self.entries[second_child - 1];
hole = second_child - 1;
}
while hole > top {
let parent = (hole - 1) / 2;
if self.entries[parent].priority < replacement.priority {
break;
}
self.entries[hole] = self.entries[parent];
hole = parent;
}
self.entries[hole] = replacement;
Some(result)
}
}
pub(crate) const UPSTREAM_DIRECTIONS_26: [(i32, i32, i32); 26] = [
(-1, 0, 0),
(1, 0, 0),
(0, -1, 0),
(0, 1, 0),
(0, 0, -1),
(0, 0, 1),
(-1, -1, 0),
(-1, 1, 0),
(1, -1, 0),
(1, 1, 0),
(0, -1, -1),
(0, -1, 1),
(0, 1, -1),
(0, 1, 1),
(-1, 0, -1),
(-1, 0, 1),
(1, 0, -1),
(1, 0, 1),
(-1, -1, -1),
(1, -1, -1),
(-1, 1, -1),
(-1, -1, 1),
(1, 1, -1),
(1, -1, 1),
(-1, 1, 1),
(1, 1, 1),
];
#[inline]
fn try_relax_neighbor<V>(
field: &V,
_loc: u64,
neighbor: u64,
current_dist: f32,
distances: &[f32],
total: u64,
) -> Result<Option<f32>>
where
V: VoxelSource,
V::Item: ToPrimitive,
{
let neighbor_cost = field.get(neighbor)?;
let neighbor_cost_f32 = neighbor_cost.to_f32().ok_or(Dijkstra3dError::OutOfBounds {
idx: neighbor,
volume_size: total,
})?;
let new_dist = current_dist + neighbor_cost_f32;
if new_dist < distances[neighbor as usize] {
Ok(Some(new_dist))
} else {
Ok(None)
}
}
pub fn parental_field<V>(
field: &V,
source: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u32>>
where
V: VoxelSource,
V::Item: num_traits::ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
let mut distances = vec![f32::INFINITY; total as usize];
let mut parents = vec![0u32; total as usize];
distances[source as usize] = 0.0;
let mut queue = BinaryHeapQueue::<f32, u64>::new();
queue.push(0.0, source);
let ctx = NeighborhoodContext::new(&shape, connectivity);
let sx = shape.sx as i64;
let sy = shape.sy as i64;
let sz = shape.sz as i64;
while let Some((dist, loc)) = queue.pop() {
if dist > distances[loc as usize] {
continue;
}
let (x, y, z) = shape.coords(loc);
let current_dist = distances[loc as usize];
for i in 0..ctx.neighbor_count {
let (dx, dy, dz) = DIRECTIONS_26[i];
if !is_neighbor_in_bounds(x, y, z, dx, dy, dz, sx, sy, sz) {
continue;
}
let neighbor = (loc as i64 + ctx.offsets[i]) as u64;
if let Some(ref g) = graph {
if !g.allows(loc, ctx.masks[i]) {
continue;
}
}
if let Some(new_dist) =
try_relax_neighbor(field, loc, neighbor, current_dist, &distances, total)?
{
distances[neighbor as usize] = new_dist;
parents[neighbor as usize] = (loc + 1) as u32; queue.push(new_dist, neighbor);
}
}
}
Ok(parents)
}
pub fn parental_field_upstream_compat<V>(
field: &V,
source: u64,
connectivity: Connectivity,
) -> Result<Vec<u32>>
where
V: VoxelSource,
V::Item: ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
let mut distances = vec![f32::INFINITY; total as usize];
let mut parents = vec![0u32; total as usize];
let mut queue = LibstdcxxCompatHeap::<u64>::default();
distances[source as usize] = 0.0;
queue.push(UpstreamCompatEntry {
priority: 0.0,
payload: source,
});
while let Some(entry) = queue.pop() {
let loc = entry.payload;
if entry.priority > distances[loc as usize] {
continue;
}
let (x, y, z) = shape.coords(loc);
let current_dist = distances[loc as usize];
for &(dx, dy, dz) in &UPSTREAM_DIRECTIONS_26[..connectivity.count()] {
if !is_neighbor_in_bounds(
x,
y,
z,
dx,
dy,
dz,
shape.sx as i64,
shape.sy as i64,
shape.sz as i64,
) {
continue;
}
let neighbor = shape.linear(
(x as i64 + dx as i64) as u64,
(y as i64 + dy as i64) as u64,
(z as i64 + dz as i64) as u64,
);
let neighbor_cost =
field
.get(neighbor)?
.to_f32()
.ok_or(Dijkstra3dError::OutOfBounds {
idx: neighbor,
volume_size: total,
})?;
let new_dist = current_dist + neighbor_cost;
if new_dist < distances[neighbor as usize] {
distances[neighbor as usize] = new_dist;
parents[neighbor as usize] = (loc + 1) as u32;
queue.push(UpstreamCompatEntry {
priority: new_dist,
payload: neighbor,
});
}
}
}
Ok(parents)
}
pub fn parental_field_upstream_compat_slice<T>(
field: &[T],
shape: VolumeShape,
source: u64,
connectivity: Connectivity,
) -> Result<Vec<u32>>
where
T: ToPrimitive,
{
let total = shape.total();
if field.len() as u64 != total {
return Err(Dijkstra3dError::InvalidInput(format!(
"parental_field_upstream_compat_slice: slice length {} != shape.total() {total}",
field.len()
)));
}
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if total > u32::MAX as u64 {
return Err(Dijkstra3dError::InvalidInput(format!(
"parental_field_upstream_compat_slice: volume {total} exceeds u32::MAX voxels"
)));
}
let mut distances = vec![f32::INFINITY; total as usize];
let mut parents = vec![0u32; total as usize];
let mut queue = LibstdcxxCompatHeap::<u32>::default();
let stride_y = shape.sx as i64;
let stride_z = (shape.sx * shape.sy) as i64;
let offsets = UPSTREAM_DIRECTIONS_26
.map(|(dx, dy, dz)| dx as i64 + dy as i64 * stride_y + dz as i64 * stride_z);
let neighbor_count = connectivity.count();
distances[source as usize] = 0.0;
queue.push(UpstreamCompatEntry {
priority: 0.0,
payload: source as u32,
});
while let Some(entry) = queue.pop() {
let loc = entry.payload as usize;
if entry.priority > distances[loc] {
continue;
}
let (x, y, z) = shape.coords(loc as u64);
let interior =
x > 0 && x + 1 < shape.sx && y > 0 && y + 1 < shape.sy && z > 0 && z + 1 < shape.sz;
let current_dist = distances[loc];
for (direction, &offset) in UPSTREAM_DIRECTIONS_26[..neighbor_count]
.iter()
.zip(&offsets[..neighbor_count])
{
let (dx, dy, dz) = *direction;
if !interior
&& !is_neighbor_in_bounds(
x,
y,
z,
dx,
dy,
dz,
shape.sx as i64,
shape.sy as i64,
shape.sz as i64,
)
{
continue;
}
let neighbor = (loc as i64 + offset) as usize;
let neighbor_cost = field[neighbor]
.to_f32()
.ok_or(Dijkstra3dError::OutOfBounds {
idx: neighbor as u64,
volume_size: total,
})?;
let new_dist = current_dist + neighbor_cost;
if new_dist < distances[neighbor] {
distances[neighbor] = new_dist;
parents[neighbor] = (loc + 1) as u32;
queue.push(UpstreamCompatEntry {
priority: new_dist,
payload: neighbor as u32,
});
}
}
}
Ok(parents)
}
pub fn parental_field_slice_int<T: ToU64Fast>(
field: &[T],
shape: VolumeShape,
source: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u32>> {
let total = shape.total();
if field.len() as u64 != total {
return Err(Dijkstra3dError::InvalidInput(format!(
"parental_field_slice_int: slice length {} != shape.total() {}",
field.len(),
total
)));
}
if total > u32::MAX as u64 {
return Err(Dijkstra3dError::InvalidInput(format!(
"parental_field_slice_int: volume {total} exceeds u32::MAX voxels; \
parent indices must fit in u32 — use the trait/f32 path"
)));
}
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
let max_weight = field.iter().map(|&v| v.to_u64_fast()).max().unwrap_or(0);
let dist_bound = checked_int_distance_bound(shape, max_weight)?;
let width = select_dist_width(dist_bound);
let use_bucket = max_weight < 65_536;
let padded = PaddedShape::new(shape.sx, shape.sy, shape.sz);
if graph.is_none() && padded.ptotal() <= u32::MAX as u64 {
return match (use_bucket, width) {
(true, DistWidth::U16) => parental_slice_int_search_padded::<_, u16>(
field,
shape,
padded,
source,
connectivity,
BucketQueue::with_capacity(max_weight as u32),
),
(true, DistWidth::U32) => parental_slice_int_search_padded::<_, u32>(
field,
shape,
padded,
source,
connectivity,
BucketQueue::with_capacity(max_weight as u32),
),
(true, DistWidth::U64) => parental_slice_int_search_padded::<_, u64>(
field,
shape,
padded,
source,
connectivity,
BucketQueue::with_capacity(max_weight as u32),
),
(false, DistWidth::U16) => parental_slice_int_search_padded::<_, u16>(
field,
shape,
padded,
source,
connectivity,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, DistWidth::U32) => parental_slice_int_search_padded::<_, u32>(
field,
shape,
padded,
source,
connectivity,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, DistWidth::U64) => parental_slice_int_search_padded::<_, u64>(
field,
shape,
padded,
source,
connectivity,
BinaryHeapQueue::<u64, u32>::new(),
),
};
}
match (use_bucket, width) {
(true, DistWidth::U16) => parental_slice_int_search::<_, u16>(
field,
shape,
source,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
),
(true, DistWidth::U32) => parental_slice_int_search::<_, u32>(
field,
shape,
source,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
),
(true, DistWidth::U64) => parental_slice_int_search::<_, u64>(
field,
shape,
source,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
),
(false, DistWidth::U16) => parental_slice_int_search::<_, u16>(
field,
shape,
source,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, DistWidth::U32) => parental_slice_int_search::<_, u32>(
field,
shape,
source,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, DistWidth::U64) => parental_slice_int_search::<_, u64>(
field,
shape,
source,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
),
}
}
fn parental_slice_int_search<T: ToU64Fast, D: Dist>(
field: &[T],
shape: VolumeShape,
source: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
mut queue: impl IntQueue,
) -> Result<Vec<u32>> {
let total = shape.total() as usize;
let mut distances = vec![D::MAX; total];
let mut parents = vec![0u32; total];
distances[source as usize] = D::ZERO;
queue.push_i(0, source as u32);
let ctx = NeighborhoodContext::new(&shape, connectivity);
let sx = shape.sx as i64;
let sy = shape.sy as i64;
let sz = shape.sz as i64;
while let Some((dist, loc)) = queue.pop_i() {
let loc_us = loc as usize;
if dist > distances[loc_us].to_priority() {
continue;
}
let (x, y, z) = shape.coords(loc as u64);
let current_dist = distances[loc_us];
for i in 0..ctx.neighbor_count {
let (dx, dy, dz) = DIRECTIONS_26[i];
if !is_neighbor_in_bounds(x, y, z, dx, dy, dz, sx, sy, sz) {
continue;
}
let neighbor = (loc as i64 + ctx.offsets[i]) as u64;
if let Some(ref g) = graph {
if !g.allows(loc as u64, ctx.masks[i]) {
continue;
}
}
let neighbor_cost = field[neighbor as usize].to_u64_fast();
let new_dist = current_dist.add_cost(neighbor_cost);
if new_dist < distances[neighbor as usize] {
distances[neighbor as usize] = new_dist;
parents[neighbor as usize] = loc + 1; queue.push_i(new_dist.to_priority(), neighbor as u32);
}
}
}
Ok(parents)
}
#[doc(hidden)]
pub fn parental_field_slice_int_unpadded<T: ToU64Fast>(
field: &[T],
shape: VolumeShape,
source: u64,
connectivity: Connectivity,
) -> Result<Vec<u32>> {
let total = shape.total();
if field.len() as u64 != total || total > u32::MAX as u64 || source >= total {
return Err(Dijkstra3dError::InvalidInput(
"parental_field_slice_int_unpadded: invalid input".into(),
));
}
let max_weight = field.iter().map(|&v| v.to_u64_fast()).max().unwrap_or(0);
let dist_bound = checked_int_distance_bound(shape, max_weight)?;
let use_u32 = dist_bound <= u32::MAX as u64;
let use_bucket = max_weight < 65_536;
match (use_bucket, use_u32) {
(true, true) => parental_slice_int_search::<_, u32>(
field,
shape,
source,
connectivity,
None,
BucketQueue::with_capacity(max_weight as u32),
),
(true, false) => parental_slice_int_search::<_, u64>(
field,
shape,
source,
connectivity,
None,
BucketQueue::with_capacity(max_weight as u32),
),
(false, true) => parental_slice_int_search::<_, u32>(
field,
shape,
source,
connectivity,
None,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, false) => parental_slice_int_search::<_, u64>(
field,
shape,
source,
connectivity,
None,
BinaryHeapQueue::<u64, u32>::new(),
),
}
}
#[allow(clippy::too_many_arguments)]
fn parental_slice_int_search_padded<T: ToU64Fast, D: Dist>(
field: &[T],
shape: VolumeShape,
padded: PaddedShape,
source: u64,
connectivity: Connectivity,
mut queue: impl IntQueue,
) -> Result<Vec<u32>> {
let psx = padded.psx;
let psy = padded.psy;
let psz = padded.psz;
let psxy = padded.psxy();
let ptotal = padded.ptotal() as usize;
let field_pad = crate::halo::pad_field(field, shape.sx, shape.sy, shape.sz, padded);
let mut distances = vec![D::MAX; ptotal];
let mut parents = vec![0u32; ptotal];
crate::halo::set_halo_zero::<D>(&mut distances, psx as usize, psy as usize, psz as usize);
let (sxc, syc, szc) = shape.coords(source);
let source_pad = crate::halo::to_padded_index(sxc, syc, szc, padded) as u32;
distances[source_pad as usize] = D::ZERO;
queue.push_i(0, source_pad);
let offsets = neighborhood_offsets(psx as i64, psxy as i64);
let neighbor_count = connectivity.count();
while let Some((dist, loc)) = queue.pop_i() {
let loc_us = loc as usize;
let current_dist = unsafe { *distances.get_unchecked(loc_us) };
if dist > current_dist.to_priority() {
continue;
}
for &off in &offsets[..neighbor_count] {
let neighbor = (loc as i64 + off) as usize;
let neighbor_cost = unsafe { field_pad.get_unchecked(neighbor).to_u64_fast() };
let new_dist = current_dist.add_cost(neighbor_cost);
let dn = unsafe { distances.get_unchecked_mut(neighbor) };
if new_dist < *dn {
*dn = new_dist;
unsafe {
*parents.get_unchecked_mut(neighbor) = loc + 1; }
queue.push_i(new_dist.to_priority(), neighbor as u32);
}
}
}
let sx = shape.sx;
let sy = shape.sy;
let sz = shape.sz;
let sxy = sx * sy;
let mut out = vec![0u32; (sx * sy * sz) as usize];
for z in 0..sz {
for y in 0..sy {
let pad_base = (z + 1) * psxy + (y + 1) * psx + 1;
let orig_base = z * sxy + y * sx;
for x in 0..sx {
let par_pad = parents[(pad_base + x) as usize];
if par_pad != 0 {
let orig_par =
crate::halo::from_padded_index((par_pad - 1) as u64, sx, sxy, psx, psxy);
out[(orig_base + x) as usize] = (orig_par + 1) as u32;
}
}
}
}
Ok(out)
}
pub fn path_from_parents(parents: &[u32], target: u64) -> Result<Vec<u64>> {
if target >= parents.len() as u64 {
return Err(Dijkstra3dError::OutOfBounds {
idx: target,
volume_size: parents.len() as u64,
});
}
let mut path = vec![target];
let mut current = target;
for _ in 0..parents.len() {
let parent = parents[current as usize];
if parent == 0 {
path.reverse();
return Ok(path);
}
current = (parent - 1) as u64; if current >= parents.len() as u64 {
return Err(Dijkstra3dError::InvalidInput(format!(
"parental field references voxel {current} outside volume of size {}",
parents.len()
)));
}
path.push(current);
}
Err(Dijkstra3dError::InvalidInput(
"parental field contains a cycle".into(),
))
}
const PARENTAL_FUSION_THRESHOLD: usize = 2048;
trait ParAcc: Copy + Send + Sync {
fn init_vec(n: usize) -> Vec<AtomicDistParent>;
fn read_cost<V: VoxelSource>(field: &V, idx: u64) -> Option<Self>
where
V::Item: ToPrimitive;
fn add(self, cost: Self) -> Self;
fn load_dist(dp: &AtomicDistParent) -> Self;
fn is_reached(self) -> bool;
fn relax(dp: &AtomicDistParent, new: Self, parent: u32) -> bool;
}
impl ParAcc for f32 {
#[inline]
fn init_vec(n: usize) -> Vec<AtomicDistParent> {
atomic_dist_parent_vec(n)
}
#[inline]
fn read_cost<V: VoxelSource>(field: &V, idx: u64) -> Option<Self>
where
V::Item: ToPrimitive,
{
field.get(idx).ok().and_then(|v| v.to_f32())
}
#[inline]
fn add(self, cost: Self) -> Self {
self + cost
}
#[inline]
fn load_dist(dp: &AtomicDistParent) -> Self {
dp.load_dist()
}
#[inline]
fn is_reached(self) -> bool {
self.is_finite()
}
#[inline]
fn relax(dp: &AtomicDistParent, new: Self, parent: u32) -> bool {
dp.relax_with_parent(new, parent)
}
}
impl ParAcc for u32 {
#[inline]
fn init_vec(n: usize) -> Vec<AtomicDistParent> {
atomic_dist_parent_vec_int(n)
}
#[inline]
fn read_cost<V: VoxelSource>(field: &V, idx: u64) -> Option<Self>
where
V::Item: ToPrimitive,
{
field
.get(idx)
.ok()
.and_then(|v| v.to_u64())
.map(|w| w as u32)
}
#[inline]
fn add(self, cost: Self) -> Self {
self.saturating_add(cost)
}
#[inline]
fn load_dist(dp: &AtomicDistParent) -> Self {
dp.load_dist_int()
}
#[inline]
fn is_reached(self) -> bool {
self != u32::MAX
}
#[inline]
fn relax(dp: &AtomicDistParent, new: Self, parent: u32) -> bool {
dp.relax_with_parent_int(new, parent)
}
}
fn scan_field_integer<V>(field: &V, total: u64) -> (u64, bool)
where
V: VoxelSource + Sync,
V::Item: ToPrimitive,
{
(0..total)
.into_par_iter()
.fold(
|| (0u64, true),
|(mx, ok), i| match field.get(i) {
Ok(v) => match v.to_f64() {
Some(f)
if f.is_finite()
&& f >= 0.0
&& f.fract() == 0.0
&& f <= u32::MAX as f64 =>
{
let w = v.to_u64().unwrap_or(u64::MAX);
(mx.max(w), ok)
}
_ => (mx, false),
},
Err(_) => (mx, false),
},
)
.reduce(|| (0u64, true), |a, b| (a.0.max(b.0), a.1 && b.1))
}
#[derive(Default, Debug, Clone, Copy)]
#[doc(hidden)]
pub struct FusionRunStats {
pub parallel_rounds: usize,
pub fused_phases: usize,
pub fused_pops: u64,
}
fn parental_parallel_run<V, D>(
field: &V,
source: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
shape: VolumeShape,
fusion_enabled: bool,
stats: Option<&mut FusionRunStats>,
) -> Vec<u32>
where
V: VoxelSource + Sync,
V::Item: ToPrimitive,
D: ParAcc,
{
let total = shape.total() as usize;
let dist_parent = D::init_vec(total);
dist_parent[source as usize].store_source();
let ctx = NeighborhoodContext::new(&shape, connectivity);
let sx = shape.sx as i64;
let sy = shape.sy as i64;
let sz = shape.sz as i64;
let graph_ref = graph.as_ref();
let nthreads = rayon::current_num_threads().max(1);
let threshold = PARENTAL_FUSION_THRESHOLD.max(nthreads * 256);
let mut frontier: Vec<u64> = vec![source];
let mut fused: VecDeque<u64> = VecDeque::new();
let mut buf: Vec<u64> = Vec::with_capacity(64);
let mut s = FusionRunStats::default();
while !frontier.is_empty() {
if fusion_enabled && frontier.len() < threshold {
s.fused_phases += 1;
fused.clear();
fused.extend(frontier.drain(..));
loop {
if fused.len() >= threshold {
break;
}
let loc = match fused.pop_front() {
Some(l) => l,
None => break,
};
s.fused_pops += 1;
buf.clear();
expand_voxel_parental_generic::<V, D>(
field,
loc,
&dist_parent,
&ctx,
graph_ref,
&shape,
sx,
sy,
sz,
&mut buf,
);
for &nb in &buf {
fused.push_back(nb);
}
}
frontier.clear();
frontier.extend(fused.drain(..));
} else {
s.parallel_rounds += 1;
let min_len = (frontier.len() / (nthreads * 4)).max(1);
let mut next_buffers: Vec<Vec<u64>> = frontier
.par_iter()
.with_min_len(min_len)
.fold(
|| Vec::with_capacity(64),
|mut acc, &loc| {
expand_voxel_parental_generic::<V, D>(
field,
loc,
&dist_parent,
&ctx,
graph_ref,
&shape,
sx,
sy,
sz,
&mut acc,
);
acc
},
)
.collect();
let total_next: usize = next_buffers.iter().map(Vec::len).sum();
let mut next_frontier: Vec<u64> = Vec::with_capacity(total_next);
for b in &mut next_buffers {
next_frontier.append(b);
}
frontier = next_frontier;
}
}
if let Some(out) = stats {
*out = s;
}
dist_parent.iter().map(|dp| dp.load().0).collect()
}
#[inline]
#[allow(clippy::too_many_arguments)]
fn expand_voxel_parental_generic<V, D>(
field: &V,
loc: u64,
dist_parent: &[AtomicDistParent],
ctx: &NeighborhoodContext,
graph: Option<&ConnectivityGraph<'_>>,
shape: &VolumeShape,
sx: i64,
sy: i64,
sz: i64,
out: &mut Vec<u64>,
) where
V: VoxelSource,
V::Item: ToPrimitive,
D: ParAcc,
{
let current_dist = D::load_dist(&dist_parent[loc as usize]);
if !current_dist.is_reached() {
return;
}
let (x, y, z) = shape.coords(loc);
for i in 0..ctx.neighbor_count {
let (dx, dy, dz) = DIRECTIONS_26[i];
if !is_neighbor_in_bounds(x, y, z, dx, dy, dz, sx, sy, sz) {
continue;
}
let neighbor = (loc as i64 + ctx.offsets[i]) as u64;
if let Some(g) = graph {
if !g.allows(loc, ctx.masks[i]) {
continue;
}
}
let cost = match D::read_cost(field, neighbor) {
Some(c) => c,
None => continue,
};
let new_dist = current_dist.add(cost);
if D::relax(&dist_parent[neighbor as usize], new_dist, loc as u32) {
out.push(neighbor);
}
}
}
pub fn parental_field_parallel<V>(
field: &V,
source: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u32>>
where
V: VoxelSource + Sync,
V::Item: ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if total > (u32::MAX as u64 - 1) {
return Err(Dijkstra3dError::InvalidInput(format!(
"parental_field_parallel: volume too large ({} voxels); \
parent indices must fit in u32 (max {})",
total,
u32::MAX - 1
)));
}
let (max_weight, all_integer) = scan_field_integer(field, total);
let use_int = if all_integer {
checked_int_distance_bound(shape, max_weight)? < u32::MAX as u64
} else {
false
};
let parents = if use_int {
parental_parallel_run::<V, u32>(field, source, connectivity, graph, shape, true, None)
} else {
parental_parallel_run::<V, f32>(field, source, connectivity, graph, shape, true, None)
};
Ok(parents)
}
#[doc(hidden)]
pub fn parental_field_parallel_ablation<V>(
field: &V,
source: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
fusion_enabled: bool,
) -> Result<Vec<u32>>
where
V: VoxelSource + Sync,
V::Item: ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if total > (u32::MAX as u64 - 1) {
return Err(Dijkstra3dError::InvalidInput(format!(
"parental ablation volume has {total} voxels; maximum is {}",
u32::MAX - 1
)));
}
let (max_weight, all_integer) = scan_field_integer(field, total);
let use_int = if all_integer {
checked_int_distance_bound(shape, max_weight)? < u32::MAX as u64
} else {
false
};
let parents = if use_int {
parental_parallel_run::<V, u32>(
field,
source,
connectivity,
graph,
shape,
fusion_enabled,
None,
)
} else {
parental_parallel_run::<V, f32>(
field,
source,
connectivity,
graph,
shape,
fusion_enabled,
None,
)
};
Ok(parents)
}
#[doc(hidden)]
pub struct BspStats {
pub round_frontier_sizes: Vec<usize>,
pub total_pushed: u64,
}
#[doc(hidden)]
pub fn parental_field_parallel_instrumented<V>(
field: &V,
source: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<BspStats>
where
V: VoxelSource + Sync,
V::Item: ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
let dist_parent = atomic_dist_parent_vec(total as usize);
dist_parent[source as usize].store_source();
let mut frontier: Vec<u64> = vec![source];
let ctx = NeighborhoodContext::new(&shape, connectivity);
let sx = shape.sx as i64;
let sy = shape.sy as i64;
let sz = shape.sz as i64;
let graph_ref = graph.as_ref();
let mut round_frontier_sizes = Vec::new();
let mut total_pushed = 0u64;
while !frontier.is_empty() {
round_frontier_sizes.push(frontier.len());
let next_frontier: Vec<u64> = frontier
.par_iter()
.fold(Vec::new, |mut acc, &loc| {
expand_voxel_into(
field,
loc,
&dist_parent,
&ctx,
graph_ref,
&shape,
sx,
sy,
sz,
&mut acc,
);
acc
})
.reduce(Vec::new, |mut a, mut b| {
a.append(&mut b);
a
});
total_pushed += next_frontier.len() as u64;
frontier = next_frontier;
}
Ok(BspStats {
round_frontier_sizes,
total_pushed,
})
}
#[doc(hidden)]
pub fn parental_field_parallel_fused_stats<V>(
field: &V,
source: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<FusionRunStats>
where
V: VoxelSource + Sync,
V::Item: ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
let (max_weight, all_integer) = scan_field_integer(field, total);
let use_int = if all_integer {
checked_int_distance_bound(shape, max_weight)? < u32::MAX as u64
} else {
false
};
let mut stats = FusionRunStats::default();
if use_int {
let _ = parental_parallel_run::<V, u32>(
field,
source,
connectivity,
graph,
shape,
true,
Some(&mut stats),
);
} else {
let _ = parental_parallel_run::<V, f32>(
field,
source,
connectivity,
graph,
shape,
true,
Some(&mut stats),
);
}
Ok(stats)
}
#[inline]
#[allow(clippy::too_many_arguments)]
fn expand_voxel_into<V>(
field: &V,
loc: u64,
dist_parent: &[AtomicDistParent],
ctx: &NeighborhoodContext,
graph: Option<&ConnectivityGraph<'_>>,
shape: &VolumeShape,
sx: i64,
sy: i64,
sz: i64,
out: &mut Vec<u64>,
) where
V: VoxelSource,
V::Item: ToPrimitive,
{
let current_dist = dist_parent[loc as usize].load_dist();
if !current_dist.is_finite() {
return;
}
let (x, y, z) = shape.coords(loc);
for i in 0..ctx.neighbor_count {
let (dx, dy, dz) = DIRECTIONS_26[i];
if !is_neighbor_in_bounds(x, y, z, dx, dy, dz, sx, sy, sz) {
continue;
}
let neighbor = (loc as i64 + ctx.offsets[i]) as u64;
if let Some(g) = graph {
if !g.allows(loc, ctx.masks[i]) {
continue;
}
}
let neighbor_cost_f32 = match field.get(neighbor) {
Ok(v) => match v.to_f32() {
Some(f) => f,
None => continue,
},
Err(_) => continue,
};
let new_dist = current_dist + neighbor_cost_f32;
let did_relax = dist_parent[neighbor as usize].relax_with_parent(new_dist, loc as u32);
if did_relax {
out.push(neighbor);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::voxel::ArrayView3Source;
use ndarray::{Array3, ShapeBuilder};
#[test]
fn path_from_parents_returns_out_of_bounds_for_invalid_target() {
let err = path_from_parents(&[0; 8], 8).unwrap_err();
assert_eq!(
err,
Dijkstra3dError::OutOfBounds {
idx: 8,
volume_size: 8,
}
);
}
#[test]
fn path_from_parents_rejects_parent_outside_field() {
let err = path_from_parents(&[0, 9], 1).unwrap_err();
assert_eq!(
err,
Dijkstra3dError::InvalidInput(
"parental field references voxel 8 outside volume of size 2".into()
)
);
}
#[test]
fn path_from_parents_rejects_parent_cycle() {
let err = path_from_parents(&[2, 1], 0).unwrap_err();
assert_eq!(
err,
Dijkstra3dError::InvalidInput("parental field contains a cycle".into())
);
}
#[test]
fn upstream_compat_selects_pinned_upstream_parent_when_f32_costs_tie() {
let field = Array3::<f32>::from_elem((1, 2, 3), 1.0);
let source = ArrayView3Source::new(field.view());
let shape = source.shape();
let parents =
parental_field_upstream_compat(&source, shape.linear(0, 0, 0), Connectivity::TwentySix)
.unwrap();
let path = path_from_parents(&parents, shape.linear(0, 0, 2)).unwrap();
assert_eq!(
path,
[
shape.linear(0, 0, 0),
shape.linear(0, 1, 1),
shape.linear(0, 0, 2),
]
);
}
#[test]
fn upstream_compat_slice_matches_generic_for_all_connectivities() {
let shape = VolumeShape::new(4, 3, 5);
let field = (0..shape.total())
.map(|index| (index % 7 + 1) as f32)
.collect::<Vec<_>>();
let array = Array3::from_shape_vec(
(shape.sx as usize, shape.sy as usize, shape.sz as usize).f(),
field.clone(),
)
.unwrap();
let source = ArrayView3Source::new(array.view());
for connectivity in [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
] {
let generic = parental_field_upstream_compat(&source, 0, connectivity).unwrap();
let contiguous =
parental_field_upstream_compat_slice(&field, shape, 0, connectivity).unwrap();
assert_eq!(contiguous, generic, "connectivity={connectivity:?}");
}
}
#[test]
fn upstream_compat_slice_rejects_length_mismatch() {
let shape = VolumeShape::new(2, 2, 2);
let error =
parental_field_upstream_compat_slice(&[1.0f32; 7], shape, 0, Connectivity::TwentySix)
.unwrap_err();
assert_eq!(
error,
Dijkstra3dError::InvalidInput(
"parental_field_upstream_compat_slice: slice length 7 != shape.total() 8".into()
)
);
}
#[test]
fn parental_parallel_matches_sequential_uniform() {
let arr = Array3::<u32>::from_elem((8, 8, 8), 1);
let source = ArrayView3Source::new(arr.view());
let src = source.shape().linear(0, 0, 0);
let seq = parental_field(&source, src, Connectivity::TwentySix, None).unwrap();
let par = parental_field_parallel(&source, src, Connectivity::TwentySix, None).unwrap();
let cost_via = |parents: &[u32], tgt: u64| -> f32 {
let path = path_from_parents(parents, tgt).unwrap();
path.iter()
.skip(1)
.map(|&v| arr.as_slice_memory_order().unwrap()[v as usize] as f32)
.sum()
};
for tgt in 0..source.shape().total() {
if tgt == src {
continue;
}
let seq_reachable = seq[tgt as usize] != 0;
let par_reachable = par[tgt as usize] != 0;
assert_eq!(
seq_reachable, par_reachable,
"voxel {} reachability mismatch",
tgt
);
if !seq_reachable {
continue;
}
let cost_seq = cost_via(&seq, tgt);
let cost_par = cost_via(&par, tgt);
assert!(
(cost_seq - cost_par).abs() < 1e-5,
"voxel {}: seq cost {} != par cost {}",
tgt,
cost_seq,
cost_par
);
}
}
#[test]
fn parental_slice_int_matches_trait_cost() {
use ndarray::ShapeBuilder; use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let (sx, sy, sz) = (6u64, 5u64, 4u64);
let shape = VolumeShape::new(sx, sy, sz);
let total = shape.total();
let conns = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
];
macro_rules! check_dtype {
($t:ty, $lo:expr, $hi:expr, $seed_base:expr) => {{
for seed in 0..6u64 {
let mut rng = StdRng::seed_from_u64($seed_base + seed);
let slice: Vec<$t> = (0..total)
.map(|_| rng.random_range($lo..=$hi) as $t)
.collect();
let arr = ndarray::Array3::from_shape_vec(
(sx as usize, sy as usize, sz as usize).f(),
slice.clone(),
)
.unwrap();
let trait_src = ArrayView3Source::new(arr.view());
let sources = [
shape.linear(0, 0, 0),
shape.linear(sx - 1, sy - 1, sz - 1),
shape.linear(sx / 2, sy / 2, sz / 2),
shape.linear(sx - 1, 0, sz / 2),
];
for &source in &sources {
for &conn in &conns {
let a = parental_field(&trait_src, source, conn, None).unwrap();
let b = parental_field_slice_int(&slice, shape, source, conn, None)
.unwrap();
let cost = |p: &[u64]| -> u64 {
p.iter().skip(1).map(|&v| slice[v as usize] as u64).sum()
};
for target in 0..total {
let pa = path_from_parents(&a, target).unwrap();
let pb = path_from_parents(&b, target).unwrap();
assert_eq!(
cost(&pa),
cost(&pb),
"cost mismatch dtype={} seed={} source={} conn={:?} target={}",
stringify!($t),
seed,
source,
conn,
target
);
}
}
}
}
}};
}
check_dtype!(u8, 1u32, 255u32, 1000);
check_dtype!(u16, 1u32, 4000u32, 2000);
check_dtype!(u32, 1u32, 5000u32, 3000);
}
#[test]
fn parental_slice_int_padded_matches_unpadded() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let (sx, sy, sz) = (6u64, 5u64, 4u64);
let shape = VolumeShape::new(sx, sy, sz);
let total = shape.total();
let conns = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
];
let allow_all = vec![u32::MAX; total as usize];
macro_rules! check_dtype {
($t:ty, $lo:expr, $hi:expr, $seed_base:expr) => {{
for seed in 0..6u64 {
let mut rng = StdRng::seed_from_u64($seed_base + seed);
let slice: Vec<$t> = (0..total)
.map(|_| rng.random_range($lo..=$hi) as $t)
.collect();
let sources = [
shape.linear(0, 0, 0),
shape.linear(sx - 1, sy - 1, sz - 1),
shape.linear(sx / 2, sy / 2, sz / 2),
shape.linear(sx - 1, 0, sz / 2),
];
for &source in &sources {
for &conn in &conns {
let padded =
parental_field_slice_int(&slice, shape, source, conn, None)
.unwrap();
let g = ConnectivityGraph::new(&allow_all, shape).unwrap();
let unpadded =
parental_field_slice_int(&slice, shape, source, conn, Some(g))
.unwrap();
assert_eq!(
padded,
unpadded,
"padded != unpadded dtype={} seed={} source={} conn={:?}",
stringify!($t),
seed,
source,
conn
);
}
}
}
}};
}
check_dtype!(u8, 1u32, 255u32, 4000); check_dtype!(u16, 1u32, 4_000u32, 5000); check_dtype!(u32, 1u32, 5_000u32, 6000); check_dtype!(u32, 70_000u32, 100_000u32, 7000); }
#[test]
fn parental_slice_int_rejects_oob_source() {
let shape = VolumeShape::new(4, 4, 4);
let field = vec![1u32; shape.total() as usize];
let result = parental_field_slice_int(&field, shape, 1000, Connectivity::TwentySix, None);
assert!(matches!(result, Err(Dijkstra3dError::OutOfBounds { .. })));
}
#[test]
fn parental_slice_int_rejects_len_mismatch() {
let shape = VolumeShape::new(4, 4, 4);
let field = vec![1u32; 10];
let result = parental_field_slice_int(&field, shape, 0, Connectivity::Six, None);
assert!(matches!(result, Err(Dijkstra3dError::InvalidInput(_))));
}
#[test]
fn parental_int_slice_rejects_unrepresentable_distance_bound() {
let shape = VolumeShape::new(2, 2, 2);
let field = vec![u64::MAX; shape.total() as usize];
let error =
parental_field_slice_int(&field, shape, 0, Connectivity::Six, None).unwrap_err();
assert!(matches!(error, Dijkstra3dError::InvalidInput(_)));
}
#[test]
fn parental_parallel_rejects_oob_source() {
let arr = Array3::<u32>::from_elem((4, 4, 4), 1);
let source = ArrayView3Source::new(arr.view());
let result = parental_field_parallel(&source, 1000, Connectivity::TwentySix, None);
assert!(matches!(result, Err(Dijkstra3dError::OutOfBounds { .. })));
}
#[test]
fn parental_u16_matches_u32_and_u64_parents() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let n = 14u64;
let shape = VolumeShape::new(n, n, n);
let src = shape.linear(0, 0, 0);
let conns = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
];
for seed in 0..16u64 {
let mut rng = StdRng::seed_from_u64(0x9A5E_0000 + seed);
let field: Vec<u32> = (0..shape.total())
.map(|_| rng.random_range(1..=6u32))
.collect();
let max_w = field.iter().copied().max().unwrap() as u64;
let dist_bound = (shape.sx + shape.sy + shape.sz + 1) * max_w;
assert_eq!(select_dist_width(dist_bound), DistWidth::U16);
let cap = max_w as u32;
for &conn in &conns {
let p16 = parental_slice_int_search::<_, u16>(
&field,
shape,
src,
conn,
None,
BucketQueue::with_capacity(cap),
)
.unwrap();
let p32 = parental_slice_int_search::<_, u32>(
&field,
shape,
src,
conn,
None,
BucketQueue::with_capacity(cap),
)
.unwrap();
let p64 = parental_slice_int_search::<_, u64>(
&field,
shape,
src,
conn,
None,
BucketQueue::with_capacity(cap),
)
.unwrap();
assert_eq!(
p16, p32,
"u16 vs u32 parents differ seed={seed} conn={conn:?}"
);
assert_eq!(
p16, p64,
"u16 vs u64 parents differ seed={seed} conn={conn:?}"
);
let pub_parents = parental_field_slice_int(&field, shape, src, conn, None).unwrap();
assert_eq!(
pub_parents, p16,
"public parents != u16 seed={seed} conn={conn:?}"
);
}
}
}
fn parental_path_cost<T>(source: &ArrayView3Source<'_, T>, parents: &[u32], tgt: u64) -> u64
where
T: Copy + ToPrimitive,
{
path_from_parents(parents, tgt)
.unwrap()
.iter()
.skip(1)
.map(|&v| source.get(v).unwrap().to_u64().unwrap())
.sum()
}
#[test]
fn parental_parallel_int_matches_sequential_random_weights() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let (sx, sy, sz) = (10usize, 9, 8);
for seed in 0..4u64 {
let mut rng = StdRng::seed_from_u64(1000 + seed);
let arr =
Array3::<u32>::from_shape_simple_fn((sx, sy, sz), || rng.random_range(1..=50u32));
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let src = shape.linear(sx as u64 / 2, sy as u64 / 2, sz as u64 / 2);
for &conn in &[
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
] {
let seq = parental_field(&source, src, conn, None).unwrap();
let par = parental_field_parallel(&source, src, conn, None).unwrap();
for tgt in 0..shape.total() {
if tgt == src {
continue;
}
let sr = seq[tgt as usize] != 0;
let pr = par[tgt as usize] != 0;
assert_eq!(sr, pr, "reachability seed={seed} conn={conn:?} tgt={tgt}");
if !sr {
continue;
}
assert_eq!(
parental_path_cost(&source, &seq, tgt),
parental_path_cost(&source, &par, tgt),
"cost seed={seed} conn={conn:?} tgt={tgt}"
);
}
}
}
}
#[test]
fn parental_parallel_narrow_frontier_matches_sequential() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let mut rng = StdRng::seed_from_u64(4242);
let arr = Array3::<u32>::from_shape_simple_fn((2, 2, 200), || rng.random_range(1..=9u32));
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let src = shape.linear(0, 0, 0);
let conn = Connectivity::TwentySix;
let seq = parental_field(&source, src, conn, None).unwrap();
let par = parental_field_parallel(&source, src, conn, None).unwrap();
for tgt in 0..shape.total() {
if tgt == src {
continue;
}
assert_eq!(
parental_path_cost(&source, &seq, tgt),
parental_path_cost(&source, &par, tgt),
"narrow-frontier cost mismatch tgt={tgt}"
);
}
}
#[test]
fn parental_parallel_cost_deterministic_across_threads() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
use rayon::ThreadPoolBuilder;
let n = 32usize;
let mut rng = StdRng::seed_from_u64(77);
let arr = Array3::<u32>::from_shape_simple_fn((n, n, n), || rng.random_range(1..=17u32));
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let total = shape.total();
let src = shape.linear(n as u64 / 2, n as u64 / 2, n as u64 / 2);
let conn = Connectivity::TwentySix;
let seq = parental_field(&source, src, conn, None).unwrap();
let cost_vec = |parents: &[u32]| -> Vec<u64> {
(0..total)
.map(|t| {
if t == src || parents[t as usize] == 0 {
0
} else {
parental_path_cost(&source, parents, t)
}
})
.collect()
};
let seq_costs = cost_vec(&seq);
let mut reference: Option<Vec<u64>> = None;
for &threads in &[1usize, 2, 4, 8, 12] {
let pool = ThreadPoolBuilder::new()
.num_threads(threads)
.build()
.unwrap();
let par = pool.install(|| parental_field_parallel(&source, src, conn, None).unwrap());
for t in 0..total {
if t == src {
continue;
}
assert_eq!(
seq[t as usize] != 0,
par[t as usize] != 0,
"threads={threads} tgt={t} reachability"
);
}
let costs = cost_vec(&par);
assert_eq!(costs, seq_costs, "threads={threads}: cost vs sequential");
match &reference {
None => reference = Some(costs),
Some(r) => assert_eq!(
r, &costs,
"threads={threads}: parallel cost differs across thread counts (race)"
),
}
}
}
#[test]
fn parental_parallel_f32_fallback_matches_sequential() {
let arr = Array3::<f32>::from_shape_fn((6, 5, 4), |(x, y, z)| {
1.0 + 0.5 * (((x + y + z) % 3) as f32)
});
let source = ArrayView3Source::new(arr.view());
let shape = source.shape();
let src = shape.linear(0, 0, 0);
let conn = Connectivity::TwentySix;
let seq = parental_field(&source, src, conn, None).unwrap();
let par = parental_field_parallel(&source, src, conn, None).unwrap();
let cost = |parents: &[u32], tgt: u64| -> f32 {
path_from_parents(parents, tgt)
.unwrap()
.iter()
.skip(1)
.map(|&v| source.get(v).unwrap())
.sum()
};
for tgt in 0..shape.total() {
if tgt == src {
continue;
}
assert!(
(cost(&seq, tgt) - cost(&par, tgt)).abs() < 1e-4,
"f32 fallback cost mismatch tgt={tgt}: {} vs {}",
cost(&seq, tgt),
cost(&par, tgt)
);
}
}
#[test]
fn parental_fusion_cuts_barriers_on_narrow_frontier() {
let arr = Array3::<u32>::from_elem((4, 4, 500), 1u32);
let source = ArrayView3Source::new(arr.view());
let src = source.shape().linear(0, 0, 0);
let conn = Connectivity::TwentySix;
let pure_bsp = parental_field_parallel_instrumented(&source, src, conn, None).unwrap();
let fused = parental_field_parallel_fused_stats(&source, src, conn, None).unwrap();
let pure_bsp_barriers = pure_bsp.round_frontier_sizes.len();
assert!(
fused.parallel_rounds * 10 < pure_bsp_barriers,
"fusion should cut global barriers >10x: pure-BSP={pure_bsp_barriers} fused={}",
fused.parallel_rounds
);
}
#[test]
fn parental_fusion_ablation_preserves_target_costs() {
let shape = VolumeShape::new(12, 11, 10);
let values: Vec<u16> = (0..shape.total())
.map(|index| 1 + ((index * 13 + 5) % 8) as u16)
.collect();
let array = Array3::from_shape_fn((12, 11, 10), |(x, y, z)| {
values[shape.linear(x as u64, y as u64, z as u64) as usize]
});
let field = ArrayView3Source::new(array.view());
let source = shape.linear(0, 0, 0);
let fused = parental_field_parallel_ablation(&field, source, Connectivity::Six, None, true)
.unwrap();
let pure = parental_field_parallel_ablation(&field, source, Connectivity::Six, None, false)
.unwrap();
for target in [
shape.linear(11, 10, 9),
shape.linear(7, 4, 8),
shape.linear(3, 9, 2),
] {
let fused_path = path_from_parents(&fused, target).unwrap();
let pure_path = path_from_parents(&pure, target).unwrap();
let fused_cost: u64 = fused_path
.iter()
.skip(1)
.map(|&index| values[index as usize] as u64)
.sum();
let pure_cost: u64 = pure_path
.iter()
.skip(1)
.map(|&index| values[index as usize] as u64)
.sum();
assert_eq!(fused_cost, pure_cost);
}
}
}