use std::fmt;
use std::ops::Range;
use std::sync::atomic::{AtomicU8, Ordering};
use std::sync::{Mutex, MutexGuard, OnceLock};
mod arrays;
mod descriptor;
mod files;
mod simd;
mod text;
use simd::{Block, OneCopy};
pub use arrays::{
DotProductJob, Element, Histogram, HistogramBin, HistogramJob, MapJob, MapOp, MapOperands,
PrefixSumJob, ReduceJob, ReduceOp, Reduction, SortJob, ZipJob, ZipOp, dot_product, histogram,
map, prefix_sum, reduce, sort, zip,
};
pub use descriptor::{
AnswerKind, DESCRIPTORS, InputKind, KernelDescriptor, ParamDescriptor, ParamType,
descriptor_for,
};
pub use files::{
FileByteJob, FileLineJob, FileMatch, FileMeasure, SearchFileJob, file_byte, file_line,
search_file,
};
#[cfg(feature = "verify-chain")]
pub use files::{
FileHash, FileHashCheckJob, FileHashJob, HashCheck, HashChecked, file_hash, file_hash_check,
file_hash_streamed,
};
pub use text::{
SearchTextJob, SplitTextJob, TextCountJob, TextMatch, TextMeasure, TextTransform,
UpdateTextJob, search_text, split_text, text_count, update_text,
};
pub const REVISION: u32 = 2;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum RefusalId {
Argument,
Unreadable,
Internal,
}
impl RefusalId {
pub const fn as_str(self) -> &'static str {
match self {
Self::Argument => "FlynnelArgument",
Self::Unreadable => "FlynnelUnreadable",
Self::Internal => "FlynnelInternal",
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Refusal {
pub id: RefusalId,
pub message: String,
}
impl Refusal {
pub(crate) fn argument(message: impl Into<String>) -> Self {
Self {
id: RefusalId::Argument,
message: message.into(),
}
}
pub(crate) fn unreadable(path: &str, detail: impl fmt::Display) -> Self {
Self {
id: RefusalId::Unreadable,
message: format!("{path} could not be read: {detail}"),
}
}
pub(crate) fn internal(what: impl fmt::Display) -> Self {
Self {
id: RefusalId::Internal,
message: format!("{what}; this is a defect in the kernel, not in the input"),
}
}
pub(crate) fn misdriven(what: impl fmt::Display) -> Self {
Self {
id: RefusalId::Internal,
message: what.to_string(),
}
}
}
impl fmt::Display for Refusal {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&self.message)
}
}
impl std::error::Error for Refusal {}
pub fn refusal_tally(refused: usize, total: usize) -> Option<String> {
(refused > 0).then(|| {
format!(
"{refused} of {total} input(s) could not be read; each one has an error record above"
)
})
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum BlockState {
NotRun,
Started,
Done,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum BlockError {
AlreadyRan {
phase: usize,
block: usize,
found: BlockState,
},
NotThisPhase {
phase: usize,
open: Option<usize>,
},
OutOfRange {
phase: usize,
block: usize,
blocks: usize,
},
}
impl fmt::Display for BlockError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match *self {
Self::AlreadyRan {
phase,
block,
found,
} => write!(
f,
"block {block} of phase {phase} was already claimed and is {found:?}"
),
Self::NotThisPhase {
phase,
open: Some(open),
} => write!(f, "phase {phase} was asked for while phase {open} is open"),
Self::NotThisPhase { phase, open: None } => {
write!(f, "phase {phase} was asked for after every phase ended")
}
Self::OutOfRange {
phase,
block,
blocks,
} => write!(
f,
"block {block} of phase {phase} was asked for and the phase has {blocks}"
),
}
}
}
impl std::error::Error for BlockError {}
pub trait Job: Sync {
type Answer: Send;
fn blocks(&self, phase: usize) -> Option<usize>;
fn state(&self, phase: usize, block: usize) -> Option<BlockState>;
fn run(&self, phase: usize, block: usize) -> Result<(), BlockError>;
fn end_phase(&mut self, phase: usize) -> Result<(), Refusal>;
fn finish(self) -> Result<Self::Answer, Refusal>
where
Self: Sized;
}
pub fn drive<J, R>(mut job: J, mut run_blocks: R) -> Result<J::Answer, Refusal>
where
J: Job,
R: FnMut(usize, &(dyn Fn(usize) -> Result<(), BlockError> + Sync)) -> Result<(), BlockError>,
{
let mut phase = 0;
while let Some(n) = job.blocks(phase) {
let ran = {
let body = |b: usize| job.run(phase, b);
run_blocks(n, &body)
};
if let Err(e) = ran {
return Err(Refusal::misdriven(e));
}
job.end_phase(phase)?;
phase += 1;
}
job.finish()
}
pub fn drive_serial<J: Job>(job: J) -> Result<J::Answer, Refusal> {
drive(job, |n, body| {
for b in 0..n {
body(b)?;
}
Ok(())
})
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Blocks {
n: usize,
len: usize,
count: usize,
}
impl Blocks {
pub(crate) fn new(n: usize, min_len: usize, max_blocks: usize) -> Self {
if n == 0 {
return Self {
n,
len: 0,
count: 0,
};
}
let wanted = (n / min_len.max(1)).clamp(1, max_blocks.max(1));
let len = n.div_ceil(wanted);
Self {
n,
len,
count: n.div_ceil(len),
}
}
pub(crate) fn count(&self) -> usize {
self.count
}
pub(crate) fn block_len(&self) -> usize {
self.len
}
pub(crate) fn range(&self, b: usize) -> Range<usize> {
let start = b.saturating_mul(self.len).min(self.n);
start..start.saturating_add(self.len).min(self.n)
}
}
pub(crate) const ARRAY_BLOCK_MIN: usize = 2048;
pub(crate) const MAX_BLOCKS: usize = 256;
const NOT_RUN: u8 = 0;
const STARTED: u8 = 1;
const DONE: u8 = 2;
fn decode(word: u8) -> BlockState {
if word == NOT_RUN {
BlockState::NotRun
} else if word == STARTED {
BlockState::Started
} else {
BlockState::Done
}
}
fn fresh(n: usize) -> Vec<AtomicU8> {
std::iter::repeat_with(|| AtomicU8::new(NOT_RUN))
.take(n)
.collect()
}
pub(crate) struct Tracker {
phase: usize,
states: Vec<AtomicU8>,
finished: bool,
level: simd::Level,
}
impl Tracker {
pub(crate) fn new(blocks: Option<usize>) -> Self {
let level = simd::for_new_job();
match blocks {
Some(n) => Self {
phase: 0,
states: fresh(n),
finished: false,
level,
},
None => Self {
phase: 0,
states: Vec::new(),
finished: true,
level,
},
}
}
fn open(&self) -> Option<usize> {
(!self.finished).then_some(self.phase)
}
pub(crate) fn blocks(&self, phase: usize) -> Option<usize> {
(self.open() == Some(phase)).then_some(self.states.len())
}
pub(crate) fn state(&self, phase: usize, block: usize) -> Option<BlockState> {
if self.open() != Some(phase) {
return None;
}
self.states
.get(block)
.map(|s| decode(s.load(Ordering::Acquire)))
}
pub(crate) fn run<B: Block>(
&self,
phase: usize,
block: usize,
work: &B,
) -> Result<(), BlockError> {
if self.open() != Some(phase) {
return Err(BlockError::NotThisPhase {
phase,
open: self.open(),
});
}
let Some(state) = self.states.get(block) else {
return Err(BlockError::OutOfRange {
phase,
block,
blocks: self.states.len(),
});
};
if let Err(held) =
state.compare_exchange(NOT_RUN, STARTED, Ordering::AcqRel, Ordering::Acquire)
{
return Err(BlockError::AlreadyRan {
phase,
block,
found: decode(held),
});
}
simd::run_at(self.level, work, phase, block);
state.store(DONE, Ordering::Release);
Ok(())
}
pub(crate) fn check_ended(&self, phase: usize) -> Result<(), Refusal> {
match self.open() {
Some(open) if open == phase => {}
Some(open) => {
return Err(Refusal::misdriven(format!(
"phase {phase} was ended while phase {open} is open"
)));
}
None => {
return Err(Refusal::misdriven(format!(
"phase {phase} was ended after every phase ended"
)));
}
}
for (block, state) in self.states.iter().enumerate() {
match decode(state.load(Ordering::Acquire)) {
BlockState::Done => {}
BlockState::NotRun => {
return Err(Refusal::misdriven(format!(
"block {block} of phase {phase} never ran"
)));
}
BlockState::Started => {
return Err(Refusal::misdriven(format!(
"block {block} of phase {phase} started and did not finish, so its \
output is partly written and the job cannot resume"
)));
}
}
}
Ok(())
}
pub(crate) fn advance(&mut self, blocks: Option<usize>) {
self.phase += 1;
match blocks {
Some(n) => self.states = fresh(n),
None => {
self.states = Vec::new();
self.finished = true;
}
}
}
pub(crate) fn check_finished(&self) -> Result<(), Refusal> {
match self.open() {
None => Ok(()),
Some(open) => Err(Refusal::misdriven(format!(
"the answer was asked for while phase {open} is open"
))),
}
}
}
pub(crate) struct Slots<T> {
cells: Vec<OnceLock<T>>,
}
impl<T> Slots<T> {
pub(crate) fn new(n: usize) -> Self {
Self {
cells: std::iter::repeat_with(OnceLock::new).take(n).collect(),
}
}
pub(crate) fn put(&self, b: usize, value: T) {
if let Err(second) = self.cells[b].set(value) {
drop(second);
panic!("block {b}'s result was stored twice, which its claim rules out");
}
}
pub(crate) fn take_all(&mut self) -> Result<Vec<T>, Refusal> {
self.cells
.iter_mut()
.enumerate()
.map(|(b, cell)| {
cell.take()
.ok_or_else(|| Refusal::internal(format!("block {b} finished with no result")))
})
.collect()
}
}
pub(crate) struct Parts<'a, T> {
parts: Vec<Mutex<&'a mut [T]>>,
}
impl<'a, T> Parts<'a, T> {
pub(crate) fn new(data: &'a mut [T], blocks: &Blocks) -> Self {
let len = blocks.block_len().max(1);
Self {
parts: data.chunks_mut(len).map(Mutex::new).collect(),
}
}
pub(crate) fn lock(&self, b: usize) -> MutexGuard<'_, &'a mut [T]> {
match self.parts[b].lock() {
Ok(guard) => guard,
Err(poisoned) => {
panic!("block {b}'s range was reached after a panic in it: {poisoned}")
}
}
}
}
macro_rules! tracked {
() => {
fn blocks(&self, phase: usize) -> Option<usize> {
self.tracker.blocks(phase)
}
fn state(&self, phase: usize, block: usize) -> Option<$crate::kernels::BlockState> {
self.tracker.state(phase, block)
}
fn run(&self, phase: usize, block: usize) -> Result<(), $crate::kernels::BlockError> {
self.tracker.run(phase, block, self)
}
};
}
pub(crate) use tracked;
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_cut_depends_on_the_length_alone() {
let b = Blocks::new(200_000, ARRAY_BLOCK_MIN, MAX_BLOCKS);
assert_eq!(b.count(), 97);
assert_eq!(b.range(0), 0..2062);
assert_eq!(b.range(96).end, 200_000);
let covered: usize = (0..b.count()).map(|i| b.range(i).len()).sum();
assert_eq!(covered, 200_000);
assert_eq!(Blocks::new(0, ARRAY_BLOCK_MIN, MAX_BLOCKS).count(), 0);
assert_eq!(Blocks::new(5, ARRAY_BLOCK_MIN, MAX_BLOCKS).count(), 1);
assert_eq!(
Blocks::new(100_000_000, ARRAY_BLOCK_MIN, MAX_BLOCKS).count(),
256
);
}
#[test]
fn no_cut_leaves_an_empty_block() {
for n in 1..5000 {
let b = Blocks::new(n, 7, 13);
for i in 0..b.count() {
assert!(!b.range(i).is_empty(), "n {n} block {i}");
}
assert_eq!(b.range(b.count() - 1).end, n);
}
}
#[test]
fn a_block_runs_once_and_a_phase_ends_only_when_every_block_finished() {
let nothing = OneCopy(|_phase, _block| ());
let mut t = Tracker::new(Some(3));
assert_eq!(t.blocks(0), Some(3));
assert_eq!(t.blocks(1), None);
t.run(0, 1, ¬hing).expect("block 1 runs");
assert_eq!(
t.run(0, 1, ¬hing),
Err(BlockError::AlreadyRan {
phase: 0,
block: 1,
found: BlockState::Done
})
);
assert_eq!(
t.run(0, 3, ¬hing),
Err(BlockError::OutOfRange {
phase: 0,
block: 3,
blocks: 3
})
);
assert_eq!(
t.run(1, 0, ¬hing),
Err(BlockError::NotThisPhase {
phase: 1,
open: Some(0)
})
);
let refused = t.check_ended(0).expect_err("blocks 0 and 2 never ran");
assert_eq!(refused.message, "block 0 of phase 0 never ran");
assert_eq!(t.state(0, 2), Some(BlockState::NotRun));
t.run(0, 0, ¬hing).expect("block 0 runs");
t.run(0, 2, ¬hing).expect("block 2 runs");
t.check_ended(0).expect("every block of phase 0 finished");
t.advance(None);
assert_eq!(t.blocks(1), None);
t.check_finished().expect("every phase ended");
}
#[test]
fn a_block_that_panicked_stays_started_and_its_phase_cannot_end() {
let t = Tracker::new(Some(1));
let outcome = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
t.run(0, 0, &OneCopy(|_phase, _block| panic!("mid-block")))
}));
match outcome {
Ok(returned) => panic!("the block's panic did not reach the caller: {returned:?}"),
Err(payload) => assert_eq!(payload.downcast_ref::<&str>(), Some(&"mid-block")),
}
assert_eq!(t.state(0, 0), Some(BlockState::Started));
assert_eq!(
t.run(0, 0, &OneCopy(|_phase, _block| ())),
Err(BlockError::AlreadyRan {
phase: 0,
block: 0,
found: BlockState::Started
})
);
let refused = t.check_ended(0).expect_err("the block did not finish");
assert!(refused.message.contains("started and did not finish"));
assert_eq!(refused.id, RefusalId::Internal);
}
#[test]
fn the_tally_speaks_only_when_something_was_refused() {
assert_eq!(refusal_tally(0, 10), None);
assert_eq!(
refusal_tally(1, 2).as_deref(),
Some("1 of 2 input(s) could not be read; each one has an error record above")
);
}
#[test]
#[ignore = "a timing, read by hand in a floor build"]
fn ladder_timing() {
use std::hint::black_box;
use std::time::{Duration, Instant};
const ROUNDS: usize = 15;
let x: Vec<f64> = (0..1_000_000u64)
.map(|i| ((i * 7919) % 1_000_003) as f64 * 0.37 - 1.0e5)
.collect();
let y: Vec<f64> = x.iter().map(|v| v * 0.5 + 1.0).collect();
let mut text = String::new();
let mut line = 0u64;
while text.len() < 4_000_000 {
text.push_str(&format!("line {line} has ERROR and ERRORERROR\r\n"));
line += 1;
}
let operands = MapOperands {
min: Some(-10.0),
max: Some(10.0),
factor: Some(2.5),
addend: Some(-3.0),
};
let (xs, ys, ts) = (&x, &y, text.as_str());
type Timed<'a> = Box<dyn FnMut() -> Duration + 'a>;
let mut kernels: Vec<(String, Timed<'_>)> = Vec::new();
for op in MapOp::ALL {
let mut buf = xs.clone();
let run: Timed<'_> = Box::new(move || {
buf.copy_from_slice(xs);
let start = Instant::now();
drive_serial(map(&mut buf, op, operands).expect("operands")).expect("map");
start.elapsed()
});
kernels.push((format!("map {op:?}"), run));
}
for op in ZipOp::ALL {
let mut buf = xs.clone();
let run: Timed<'_> = Box::new(move || {
buf.copy_from_slice(xs);
let start = Instant::now();
drive_serial(zip(&mut buf, ys, op).expect("lengths")).expect("zip");
start.elapsed()
});
kernels.push((format!("zip {op:?}"), run));
}
for op in ReduceOp::ALL {
let run: Timed<'_> = Box::new(move || {
let start = Instant::now();
let r = drive_serial(reduce(xs, op, Some(-1.0e5), Some(1.0e5)).expect("bounds"));
let elapsed = start.elapsed();
black_box(r.expect("reduce"));
elapsed
});
kernels.push((format!("reduce {op:?}"), run));
}
let mut scan = xs.clone();
let run: Timed<'_> = Box::new(move || {
scan.copy_from_slice(xs);
let start = Instant::now();
drive_serial(prefix_sum(&mut scan)).expect("prefix sum");
start.elapsed()
});
kernels.push(("prefix sum".to_string(), run));
let answers: [(&str, Timed<'_>); 7] = [
(
"histogram",
Box::new(move || {
let start = Instant::now();
let h = drive_serial(histogram(xs, 64, None, None).expect("bins"));
let elapsed = start.elapsed();
black_box(h.expect("histogram"));
elapsed
}),
),
(
"dot product",
Box::new(move || {
let start = Instant::now();
let d = drive_serial(dot_product(xs, ys).expect("lengths"));
let elapsed = start.elapsed();
black_box(d.expect("dot product"));
elapsed
}),
),
(
"sort",
Box::new(move || {
let start = Instant::now();
let s = drive_serial(sort(xs, false));
let elapsed = start.elapsed();
black_box(s.expect("sort"));
elapsed
}),
),
(
"text search",
Box::new(move || {
let start = Instant::now();
let found = drive_serial(search_text(ts, "ERROR").expect("pattern"));
let elapsed = start.elapsed();
black_box(found.expect("search"));
elapsed
}),
),
(
"text count",
Box::new(move || {
let start = Instant::now();
let counted =
drive_serial(text_count(ts, Some("ERRORERROR")).expect("pattern"));
let elapsed = start.elapsed();
black_box(counted.expect("count"));
elapsed
}),
),
(
"text split",
Box::new(move || {
let start = Instant::now();
let parts = drive_serial(split_text(ts, "ERROR", false).expect("separator"));
let elapsed = start.elapsed();
black_box(parts.expect("split"));
elapsed
}),
),
(
"text lower",
Box::new(move || {
let start = Instant::now();
let job =
update_text(ts, TextTransform::ToLower, None, None).expect("no operand");
let lowered = drive_serial(job);
let elapsed = start.elapsed();
black_box(lowered.expect("lower"));
elapsed
}),
),
];
for (name, run) in answers {
kernels.push((name.to_string(), run));
}
let offered = simd::levels_offered();
let mut arms: Vec<(String, simd::Level)> =
offered.iter().map(|&l| (format!("{l:?}"), l)).collect();
arms.push(("control".to_string(), simd::Level::Base));
let logical = std::thread::available_parallelism()
.map(std::num::NonZeroUsize::get)
.expect("logical processor count");
println!(
"LADDER_LEVELS offered={offered:?} process={:?} rounds={ROUNDS} logical={logical}",
simd::process_level()
);
for spinners in [0, logical] {
let stop = std::sync::Arc::new(std::sync::atomic::AtomicBool::new(false));
let load: Vec<std::thread::JoinHandle<u64>> = (0..spinners)
.map(|_| {
let stop = std::sync::Arc::clone(&stop);
std::thread::spawn(move || {
let mut spins = 0u64;
while !stop.load(std::sync::atomic::Ordering::Relaxed) {
spins = black_box(spins.wrapping_add(1));
}
spins
})
})
.collect();
for (name, run) in &mut kernels {
let mut times: Vec<Vec<Duration>> = vec![Vec::new(); arms.len()];
for round in 0..ROUNDS {
for k in 0..arms.len() {
let arm = (k + round) % arms.len();
times[arm].push(simd::with_level(arms[arm].1, &mut *run));
}
}
let medians: Vec<f64> = times
.iter_mut()
.map(|t| {
t.sort_unstable();
t[t.len() / 2].as_secs_f64()
})
.collect();
let ratios: Vec<String> = arms
.iter()
.zip(&medians)
.skip(1)
.map(|((arm, _level), m)| format!("{arm}={:.3}", m / medians[0]))
.collect();
println!(
"LADDER {name:<22} spinners={spinners:<3} base_us={:.1} {}",
medians[0] * 1e6,
ratios.join(" ")
);
}
stop.store(true, std::sync::atomic::Ordering::Relaxed);
for spinner in load {
black_box(spinner.join().expect("a spinner thread ends"));
}
}
}
}