use crate::adaptive_quant::dirty_log2f;
use crate::coder_scratch::CoderScratch;
use crate::entropy::{pack_signed, uint_encode};
use crate::thread_pool::ThreadPool;
use crate::util::heap_array;
use std::sync::OnceLock;
mod properties;
pub(crate) use properties::{
MaProperties, MaProperty, MaPropertySlice, with_ma_properties, write_property_row,
};
pub(crate) const MA_REF_CHANNELS: usize = 2;
pub(crate) const NUM_MA_PROPS: usize = 16 + 4 * MA_REF_CHANNELS;
pub(crate) const NUM_MA_PREDS: usize = 14;
static SPLIT_PROPS: [u8; NUM_MA_PROPS] = {
let mut props = [0u8; NUM_MA_PROPS];
let mut i = 0;
while i < 15 {
props[i] = i as u8;
i += 1;
}
let mut r = 16;
while r < NUM_MA_PROPS {
props[r - 1] = r as u8;
r += 1;
}
props[NUM_MA_PROPS - 1] = 15;
props
};
fn split_props(allow_wp: bool) -> &'static [u8] {
if !allow_wp {
&SPLIT_PROPS[..SPLIT_PROPS.len() - 1]
} else {
&SPLIT_PROPS
}
}
pub(crate) const PRED_ZERO: usize = 0;
pub(crate) const PRED_WEIGHTED: usize = 6;
const MAX_CANDIDATES: usize = 32;
const MAX_QUANTILE_PROBE: usize = 1024;
const PROBE_BITMAP_BITS: usize = 4096;
const MAX_DEPTH: usize = 26;
const PARALLEL_SCAN_MIN_SAMPLES: usize = 1 << 17;
const PARALLEL_SCAN_CHUNK_SAMPLES: usize = 8192;
const SERIAL_MULTI_SCAN_MIN_SAMPLES: usize = 1 << 14;
const PARALLEL_PLAN_MIN_SAMPLES: usize = 1024;
const PARALLEL_CHILD_MIN_SAMPLES: usize = 64;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum MaNode {
Split {
prop: u8,
val: i32,
gt: u32,
le: u32,
},
Leaf {
pred: u32,
offset: i32,
},
}
#[derive(Clone)]
pub(crate) struct LearnedTree {
pub(crate) nodes: Vec<MaNode>,
pub(crate) est_bits: f64,
pub(crate) flat_bits: f64,
}
impl LearnedTree {
#[inline]
pub(crate) fn lookup<T: MaProperty>(&self, p: &[T; NUM_MA_PROPS]) -> (u32, u32) {
let mut i = 0usize;
loop {
match self.nodes[i] {
MaNode::Split { prop, val, gt, le } => {
i = if p[prop as usize].into() > val {
gt
} else {
le
} as usize;
}
MaNode::Leaf { pred, .. } => return (i as u32, pred),
}
}
}
}
pub(crate) struct MaSamples {
pub(crate) props: MaProperties,
pub(crate) tok: Vec<[u8; NUM_MA_PREDS]>,
pub(crate) val: Vec<i32>,
}
fn select_rows<T: Copy>(rows: &[T], indices: &[u32]) -> Vec<T> {
indices.iter().map(|&i| rows[i as usize]).collect()
}
impl MaSamples {
#[cfg(test)]
pub(crate) fn new() -> Self {
Self::with_capacity(0)
}
pub(crate) fn with_capacity(capacity: usize) -> Self {
Self {
props: MaProperties::with_capacity(capacity),
tok: Vec::with_capacity(capacity),
val: Vec::new(),
}
}
#[inline]
pub(crate) fn push(&mut self, props: [i32; NUM_MA_PROPS], tok: [u8; NUM_MA_PREDS]) {
self.props.push(props);
self.tok.push(tok);
}
#[inline]
pub(crate) fn push_val(
&mut self,
props: [i32; NUM_MA_PROPS],
tok: [u8; NUM_MA_PREDS],
val: i32,
) {
self.props.push(props);
self.tok.push(tok);
self.val.push(val);
}
pub(crate) fn len(&self) -> usize {
self.props.len()
}
pub(crate) fn append(&mut self, other: &Self) {
debug_assert!(self.val.is_empty() && other.val.is_empty());
self.props.append(&other.props);
self.tok.extend_from_slice(&other.tok);
}
fn select(&self, indices: &[u32]) -> Self {
Self {
props: self.props.select(indices),
tok: select_rows(&self.tok, indices),
val: if self.val.is_empty() {
Vec::new()
} else {
select_rows(&self.val, indices)
},
}
}
fn into_permuted(mut self, mut indices: Vec<u32>) -> Self {
assert_eq!(indices.len(), self.len());
with_ma_properties!(&mut self.props, |rows| {
permute_sample_rows(rows, &mut self.tok, &mut self.val, &mut indices)
});
self
}
#[allow(clippy::useless_conversion)]
fn partition(&mut self, start: usize, end: usize, prop: u8, threshold: i32) -> usize {
with_ma_properties!(&mut self.props, |rows| {
let tokens = &mut self.tok[start..end];
let values = val_range(&mut self.val, start, end);
partition_by(
&mut rows[start..end],
|row| i32::from(row[prop as usize]) > threshold,
|a, b| {
tokens.swap(a, b);
if !values.is_empty() {
values.swap(a, b);
}
},
)
})
}
#[allow(clippy::useless_conversion)]
fn partition_indices(
&self,
start: usize,
end: usize,
prop: u8,
threshold: i32,
) -> (Vec<u32>, usize) {
let mut indices: Vec<_> = (start as u32..end as u32).collect();
let split = with_ma_properties!(&self.props, |rows| {
partition_by(
&mut indices,
|&i| i32::from(rows[i as usize][prop as usize]) > threshold,
|_, _| {},
)
});
(indices, split)
}
pub(crate) fn evenly_sampled_indices(&self, target: usize) -> Vec<u32> {
let selected = self.len().min(target);
(0..selected)
.map(|sample| (sample * self.len() / selected) as u32)
.collect()
}
}
fn permute_sample_rows<T: Copy>(
props: &mut [[T; NUM_MA_PROPS]],
tok: &mut [[u8; NUM_MA_PREDS]],
val: &mut [i32],
indices: &mut [u32],
) {
for start in 0..indices.len() {
if indices[start] as usize == start {
continue;
}
let first_props = props[start];
let first_tok = tok[start];
let first_val = val.get(start).copied();
let mut dst = start;
loop {
let src = indices[dst] as usize;
indices[dst] = dst as u32;
if src == start {
props[dst] = first_props;
tok[dst] = first_tok;
if let Some(first_val) = first_val {
val[dst] = first_val;
}
break;
}
props[dst] = props[src];
tok[dst] = tok[src];
if first_val.is_some() {
val[dst] = val[src];
}
dst = src;
}
}
}
pub(crate) struct MaLearnParams {
pub(crate) alphabet: usize,
pub(crate) max_leaves: usize,
pub(crate) split_cost_bits: f32,
pub(crate) min_node: usize,
pub(crate) allow_wp: bool,
pub(crate) allowed_preds: u16,
pub(crate) side_preds: usize,
pub(crate) max_candidates: usize,
pub(crate) modal_offsets: bool,
pub(crate) prune_leaf_bits: f32,
}
pub(crate) struct MaPropertyScratch {
probe: Vec<i32>,
probe_bitmap: Box<[u64; PROBE_BITMAP_BITS / 64]>,
cands: Vec<i32>,
plans: Vec<SplitPlan>,
luts: Vec<u8>,
multi_hist: Vec<u32>,
multi_bin_count: Vec<u32>,
left_hist: Vec<u32>,
node_hist: Vec<u32>,
node_nbits: Vec<u64>,
node_costs: [f32; NUM_MA_PREDS],
flat_hist: Vec<u32>,
}
impl Default for MaPropertyScratch {
fn default() -> Self {
Self {
probe: Vec::with_capacity(MAX_QUANTILE_PROBE + 1),
probe_bitmap: heap_array(0),
cands: Vec::with_capacity(MAX_CANDIDATES),
plans: Vec::with_capacity(NUM_MA_PROPS),
luts: Vec::new(),
multi_hist: Vec::new(),
multi_bin_count: Vec::new(),
left_hist: Vec::new(),
node_hist: Vec::new(),
node_nbits: vec![0; NUM_MA_PREDS],
node_costs: [f32::INFINITY; NUM_MA_PREDS],
flat_hist: Vec::new(),
}
}
}
impl MaPropertyScratch {
fn prepare(&mut self, alphabet: usize) {
if self.left_hist.len() < NUM_MA_PREDS * alphabet {
self.left_hist.resize(NUM_MA_PREDS * alphabet, 0);
}
if self.node_hist.len() < NUM_MA_PREDS * alphabet {
self.node_hist.resize(NUM_MA_PREDS * alphabet, 0);
}
}
}
struct Learner<'a> {
s: &'a mut MaSamples,
p: MaLearnParams,
nodes: Vec<MaNode>,
info: Vec<NodeInfo>,
leaves: u32,
est_bits: f64,
}
#[derive(Clone, Copy)]
struct NodeInfo {
base_bits: f32,
pred: u32,
offset: i32,
}
impl NodeInfo {
fn of(pending: &Pending) -> Self {
Self {
base_bits: pending.base_bits,
pred: pending.pred,
offset: pending.offset,
}
}
}
#[inline]
fn hist_entropy_bits(hist: &[u32], total: u32) -> f32 {
if total == 0 {
return 0.0;
}
let log_total = dirty_log2f(total as f32);
let mut bits = 0.0f32;
for &c in hist {
if c != 0 {
bits += c as f32 * (log_total - dirty_log2f(c as f32));
}
}
bits
}
fn count_log2_table() -> &'static [f32; 4096] {
static LOGS: OnceLock<Box<[f32; 4096]>> = OnceLock::new();
LOGS.get_or_init(|| Box::new(core::array::from_fn(|i| dirty_log2f(i as f32))))
}
#[inline]
fn count_log2(count: u32, logs: &[f32; 4096]) -> f32 {
logs.get(count as usize)
.copied()
.unwrap_or_else(|| dirty_log2f(count as f32))
}
fn sort_unique_probe(probe: &mut Vec<i32>, bitmap: &mut [u64; PROBE_BITMAP_BITS / 64]) {
if probe.len() < 32 {
probe.sort_unstable();
probe.dedup();
return;
}
let (min, max) = probe.iter().fold((i32::MAX, i32::MIN), |(min, max), &v| {
(min.min(v), max.max(v))
});
if min == max {
probe.truncate(1);
return;
}
let span = max as i64 - min as i64;
if span >= PROBE_BITMAP_BITS as i64 {
probe.sort_unstable();
probe.dedup();
return;
}
let words = span as usize / 64 + 1;
bitmap[..words].fill(0);
for &v in probe.iter() {
let bit = (v - min) as usize;
bitmap[bit / 64] |= 1 << (bit % 64);
}
let mut output = probe.iter_mut();
let mut len = 0;
for (word, &bits) in bitmap[..words].iter().enumerate() {
let mut bits = bits;
while bits != 0 {
let offset = word * 64 + bits.trailing_zeros() as usize;
*output.next().unwrap() = min + offset as i32;
len += 1;
bits &= bits - 1;
}
}
probe.truncate(len);
}
fn pick_candidates<T: MaProperty>(
properties: &[[T; NUM_MA_PROPS]],
prop: usize,
max_candidates: usize,
scratch: &mut MaPropertyScratch,
) -> usize {
scratch.probe.clear();
let mut stride = (properties.len() / MAX_QUANTILE_PROBE).max(1);
if stride > 1 && stride.is_multiple_of(2) {
stride += 1;
}
scratch.probe.extend(
properties
.iter()
.step_by(stride)
.map(|props| Into::<i32>::into(props[prop])),
);
sort_unique_probe(&mut scratch.probe, &mut scratch.probe_bitmap);
if scratch.probe.len() < 2 {
return 0;
}
scratch.cands.clear();
let distinct = scratch.probe.len() - 1;
let n = distinct.min(max_candidates.min(MAX_CANDIDATES));
for k in 0..n {
let pos = k * distinct / n;
let v = scratch.probe[pos];
if scratch.cands.last() != Some(&v) {
scratch.cands.push(v);
}
}
scratch.cands.len()
}
const LUT_MAX_SPAN: usize = 4096;
#[derive(Clone, Copy)]
struct SplitPlan {
prop: u8,
ncand: u8,
use_lut: bool,
lo_v: i32,
hi_v: i32,
lut_start: u32,
hist_start: u32,
bin_stride: u32,
cands: [i32; MAX_CANDIDATES],
}
impl SplitPlan {
#[inline]
fn bin_for(&self, v: i32, luts: &[u8]) -> usize {
if self.use_lut {
let offset = (v.max(self.lo_v).min(self.hi_v) - self.lo_v) as usize;
luts[self.lut_start as usize + offset] as usize
} else {
self.cands[..self.ncand as usize].partition_point(|&c| c < v)
}
}
fn hist_len(&self) -> usize {
(self.ncand as usize + 1) * self.bin_stride as usize
}
}
struct SymbolWindow {
bin_stride: usize,
spans: Vec<PredictorSpan>,
}
struct PredictorSpan {
first: usize,
width: usize,
offset: usize,
raw_syms: Vec<(u16, u8)>,
}
impl PredictorSpan {
#[inline]
fn slot(&self, token: u8) -> usize {
self.offset + (token as usize - self.first)
}
}
impl SymbolWindow {
fn new(preds: &[usize], alphabet: usize, all_hist: &[u32]) -> Self {
let mut bin_stride = 0;
let mut spans = Vec::with_capacity(preds.len());
for &p in preds {
let h = &all_hist[p * alphabet..(p + 1) * alphabet];
let first = h.iter().position(|&count| count != 0).unwrap_or(0);
let end = h.iter().rposition(|&count| count != 0).map_or(0, |s| s + 1);
let width = end - first;
let raw_syms = (first.max(16)..end)
.filter(|&s| h[s] != 0)
.map(|s| ((s - first) as u16, ((s >> 2) - 2) as u8))
.collect();
spans.push(PredictorSpan {
first,
width,
offset: bin_stride,
raw_syms,
});
bin_stride += width;
}
Self {
bin_stride: bin_stride.max(1),
spans,
}
}
}
#[allow(clippy::too_many_arguments)]
fn plan_split<T: MaProperty>(
properties: &[[T; NUM_MA_PROPS]],
prop: usize,
max_candidates: usize,
bin_stride: usize,
hist_start: u32,
luts: &mut Vec<u8>,
scratch: &mut MaPropertyScratch,
) -> Option<SplitPlan> {
let ncand = pick_candidates(properties, prop, max_candidates, scratch);
if ncand == 0 {
return None;
}
let cands_src = &scratch.cands;
let lo_v = cands_src[0];
let hi_v = cands_src[ncand - 1] + 1;
let span = (hi_v as i64 - lo_v as i64) as usize;
let use_lut = span <= LUT_MAX_SPAN && span <= 4 * properties.len() + 64;
let lut_start = luts.len() as u32;
if use_lut {
let mut k = 0usize;
luts.extend((0..=span).map(|off| {
let v = lo_v + off as i32;
while k < ncand && cands_src[k] < v {
k += 1;
}
k as u8
}));
}
let mut cands = [0i32; MAX_CANDIDATES];
cands[..ncand].copy_from_slice(cands_src);
Some(SplitPlan {
prop: prop as u8,
ncand: ncand as u8,
use_lut,
lo_v,
hi_v,
lut_start,
hist_start,
bin_stride: bin_stride as u32,
cands,
})
}
fn scan_split_plans<T: MaProperty>(
properties: &[[T; NUM_MA_PROPS]],
tokens: &[[u8; NUM_MA_PREDS]],
plans: &[SplitPlan],
luts: &[u8],
preds: &[usize],
window: &SymbolWindow,
hist: &mut [u32],
) {
debug_assert_eq!(properties.len(), tokens.len());
if let &[p0, p1, p2, p3] = preds {
let [s0, s1, s2, s3] = &window.spans[..] else {
unreachable!("one span per side predictor");
};
for (props, toks) in properties.iter().zip(tokens) {
let t0 = s0.slot(toks[p0]);
let t1 = s1.slot(toks[p1]);
let t2 = s2.slot(toks[p2]);
let t3 = s3.slot(toks[p3]);
for plan in plans {
let bin = plan.bin_for(props[plan.prop as usize].into(), luts);
let base = plan.hist_start as usize + bin * plan.bin_stride as usize;
hist[base + t0] += 1;
hist[base + t1] += 1;
hist[base + t2] += 1;
hist[base + t3] += 1;
}
}
} else {
for (props, toks) in properties.iter().zip(tokens) {
for plan in plans {
let bin = plan.bin_for(props[plan.prop as usize].into(), luts);
let base = plan.hist_start as usize + bin * plan.bin_stride as usize;
for (&p, span) in preds.iter().zip(&window.spans) {
hist[base + span.slot(toks[p])] += 1;
}
}
}
}
}
#[inline]
fn raw_bits_windowed(bin: &[u32], syms: &[(u16, u8)]) -> u64 {
syms.iter()
.map(|&(s, bits)| bin[s as usize] as u64 * u64::from(bits))
.sum()
}
#[allow(clippy::too_many_arguments)]
fn score_split_plan(
plan: &SplitPlan,
preds: &[usize],
alphabet: usize,
window: &SymbolWindow,
hist: &[u32],
all_hist: &[u32],
all_nbits: &[u64; NUM_MA_PREDS],
total_count: u32,
scratch: &mut MaPropertyScratch,
) -> Option<(i32, f32)> {
let ncand = plan.ncand as usize;
let stride = plan.bin_stride as usize;
let left_hist = &mut scratch.left_hist[..stride];
left_hist.fill(0);
let mut left_nbits = [0; NUM_MA_PREDS];
let logs = count_log2_table();
let mut left_count = 0u32;
let mut best: Option<(i32, f32)> = None;
for (&candidate, bin) in plan.cands[..ncand].iter().zip(hist.chunks_exact(stride)) {
left_count += bin[..window.spans[0].width].iter().sum::<u32>();
if left_count == 0 {
continue;
}
if left_count == total_count {
break;
}
let log_left = count_log2(left_count, logs);
let log_right = count_log2(total_count - left_count, logs);
let mut best_l = f32::INFINITY;
let mut best_r = f32::INFINITY;
for (i, (&p, span)) in preds.iter().zip(&window.spans).enumerate() {
let range = span.offset..span.offset + span.width;
let bin = &bin[range.clone()];
left_nbits[i] += raw_bits_windowed(bin, &span.raw_syms);
let left = &mut left_hist[range];
let node = &all_hist[p * alphabet + span.first..][..span.width];
let mut cost_l = 0.0f32;
let mut cost_r = 0.0f32;
for ((left, &b), &n) in left.iter_mut().zip(bin).zip(node) {
let l = *left + b;
*left = l;
if l != 0 {
cost_l += l as f32 * (log_left - count_log2(l, logs));
}
let c = n - l;
if c != 0 {
cost_r += c as f32 * (log_right - count_log2(c, logs));
}
}
cost_l += left_nbits[i] as f32;
cost_r += (all_nbits[p] - left_nbits[i]) as f32;
best_l = best_l.min(cost_l);
best_r = best_r.min(cost_r);
}
let cost = best_l + best_r;
if best.is_none() || cost < best.unwrap().1 {
best = Some((candidate, cost));
}
}
best
}
#[cfg(test)]
#[allow(clippy::too_many_arguments)]
fn best_split_on_prop<T: MaProperty>(
properties: &[[T; NUM_MA_PROPS]],
tokens: &[[u8; NUM_MA_PREDS]],
prop: usize,
preds: &[usize],
alphabet: usize,
max_candidates: usize,
all_hist: &[u32],
all_nbits: &[u64; NUM_MA_PREDS],
scratch: &mut MaPropertyScratch,
) -> Option<(i32, f32)> {
assert_eq!(properties.len(), tokens.len());
scratch.prepare(alphabet);
let window = SymbolWindow::new(preds, alphabet, all_hist);
let mut luts = Vec::new();
let plan = plan_split(
properties,
prop,
max_candidates,
window.bin_stride,
0,
&mut luts,
scratch,
)?;
let mut hist = vec![0u32; plan.hist_len()];
scan_split_plans(
properties,
tokens,
std::slice::from_ref(&plan),
&luts,
preds,
&window,
&mut hist,
);
score_split_plan(
&plan,
preds,
alphabet,
&window,
&hist,
all_hist,
all_nbits,
properties.len() as u32,
scratch,
)
}
#[inline]
fn raw_bits_from_hist(hist: &[u32]) -> u64 {
hist.iter()
.enumerate()
.skip(16)
.map(|(token, &count)| count as u64 * ((token >> 2) - 2) as u64)
.sum()
}
fn node_cost_all<'a>(
tokens: impl ExactSizeIterator<Item = &'a [u8; NUM_MA_PREDS]>,
params: &MaLearnParams,
scratch: &mut MaPropertyScratch,
) -> (f32, usize) {
let alpha = params.alphabet;
scratch.prepare(alpha);
let MaPropertyScratch {
node_hist,
node_nbits,
node_costs,
..
} = scratch;
let hist = &mut node_hist[..NUM_MA_PREDS * alpha];
hist.fill(0);
let total = tokens.len() as u32;
for toks in tokens {
count_predictor_tokens(hist, alpha, toks);
}
predictor_costs(hist, total, params, node_nbits, node_costs)
}
#[inline]
fn count_predictor_tokens(hist: &mut [u32], alphabet: usize, tokens: &[u8; NUM_MA_PREDS]) {
for (pred_hist, &token) in hist.chunks_exact_mut(alphabet).zip(tokens) {
pred_hist[token as usize] += 1;
}
}
fn predictor_costs(
hist: &[u32],
total: u32,
params: &MaLearnParams,
node_nbits: &mut [u64],
node_costs: &mut [f32; NUM_MA_PREDS],
) -> (f32, usize) {
let alpha = params.alphabet;
node_costs.fill(f32::INFINITY);
for (nbits, pred_hist) in node_nbits.iter_mut().zip(hist.chunks_exact(alpha)) {
*nbits = raw_bits_from_hist(pred_hist);
}
let skip_wp = !params.allow_wp;
let mut best = f32::INFINITY;
let mut best_pred = 0usize;
for (p, ((cost, &nbits), pred_hist)) in node_costs
.iter_mut()
.zip(node_nbits.iter())
.zip(hist.chunks_exact(alpha))
.enumerate()
{
if skip_wp && p == PRED_WEIGHTED {
continue;
}
if params.allowed_preds & (1 << p) == 0 {
continue;
}
let bits = hist_entropy_bits(pred_hist, total) + nbits as f32;
*cost = bits;
if bits < best {
best = bits;
best_pred = p;
}
}
(best, best_pred)
}
impl Learner<'_> {
#[allow(clippy::too_many_arguments)]
fn evaluate(
&self,
node_id: u32,
start: usize,
end: usize,
depth: u16,
zero_offset: i32,
score_split: bool,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Pending {
self.evaluate_rows(
node_id,
start,
end,
self.s.props.slice(start..end),
&self.s.tok[start..end],
depth,
zero_offset,
score_split,
pool,
scratch,
)
}
fn rebase(&mut self, start: usize, end: usize, scratch: &mut CoderScratch) -> i32 {
if !self.p.modal_offsets || self.s.val.is_empty() {
return 0;
}
rebase_zero(
&mut self.s.tok[start..end],
&self.s.val[start..end],
&mut scratch.ma_property.multi_bin_count,
)
}
#[allow(clippy::too_many_arguments)]
fn evaluate_rows(
&self,
node_id: u32,
start: usize,
end: usize,
properties: MaPropertySlice<'_>,
tokens: &[[u8; NUM_MA_PREDS]],
depth: u16,
zero_offset: i32,
score_split: bool,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Pending {
match properties {
MaPropertySlice::Narrow(rows) => self.evaluate_rows_typed(
node_id,
start,
end,
rows,
tokens,
depth,
zero_offset,
score_split,
pool,
scratch,
),
MaPropertySlice::Wide(rows) => self.evaluate_rows_typed(
node_id,
start,
end,
rows,
tokens,
depth,
zero_offset,
score_split,
pool,
scratch,
),
}
}
#[allow(clippy::too_many_arguments)]
fn evaluate_rows_typed<T: MaProperty>(
&self,
node_id: u32,
start: usize,
end: usize,
properties: &[[T; NUM_MA_PROPS]],
tokens: &[[u8; NUM_MA_PREDS]],
depth: u16,
zero_offset: i32,
score_split: bool,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> Pending {
debug_assert_eq!(properties.len(), end - start);
let (base_bits, base_pred) =
node_cost_all(tokens.iter(), &self.p, &mut scratch.ma_property);
let mut split = None;
let mut gain = 0.0f32;
if score_split
&& properties.len() >= self.p.min_node
&& (depth as usize) < MAX_DEPTH
&& base_bits > self.p.split_cost_bits
{
let mut best: Option<(usize, i32, f32)> = None; let alphabet = self.p.alphabet;
let all_hist = scratch.ma_property.node_hist[..NUM_MA_PREDS * alphabet].to_vec();
let mut all_nbits = [0u64; NUM_MA_PREDS];
all_nbits.copy_from_slice(&scratch.ma_property.node_nbits[..NUM_MA_PREDS]);
let mut preds: Vec<usize> = (0..NUM_MA_PREDS)
.filter(|&p| {
(self.p.allow_wp || p != PRED_WEIGHTED) && self.p.allowed_preds & (1 << p) != 0
})
.collect();
crate::util::sort_small_by(&mut preds, |&a, &b| {
scratch.ma_property.node_costs[a].total_cmp(&scratch.ma_property.node_costs[b])
});
preds.truncate(self.p.side_preds.max(1));
let window = SymbolWindow::new(&preds, alphabet, &all_hist);
let props = split_props(self.p.allow_wp);
let max_candidates = self.p.max_candidates;
let n = properties.len();
let MaPropertyScratch {
plans,
luts,
multi_hist: hist,
..
} = &mut scratch.ma_property;
let mut plans = std::mem::take(plans);
let mut luts = std::mem::take(luts);
let mut hist = std::mem::take(hist);
plans.clear();
luts.clear();
let mut hist_len = 0usize;
let mut planned = 0u32;
for &prop in props {
let absolute = match prop {
6 | 7 => Some(prop - 2),
17 | 19 | 21 | 23 => Some(prop - 1),
_ => None,
};
if let Some(absolute) = absolute
&& planned & (1 << absolute) != 0
&& properties.iter().all(|row| {
let a: i32 = row[absolute as usize].into();
let b: i32 = row[prop as usize].into();
a == b
})
{
continue;
}
if let Some(plan) = plan_split(
properties,
prop as usize,
max_candidates,
window.bin_stride,
hist_len as u32,
&mut luts,
&mut scratch.ma_property,
) {
hist_len += plan.hist_len();
plans.push(plan);
planned |= 1 << prop;
}
}
let multi_scan = if pool.num_threads() > 1 {
n >= PARALLEL_SCAN_MIN_SAMPLES
} else {
n >= SERIAL_MULTI_SCAN_MIN_SAMPLES
};
if multi_scan {
hist.clear();
hist.resize(hist_len, 0);
let (plans_ref, luts_ref, preds_ref) = (&plans, &luts, &preds);
if pool.num_threads() > 1 {
let chunks = (n / PARALLEL_SCAN_CHUNK_SAMPLES).clamp(2, pool.num_threads());
let parts = pool.steal_map(scratch, chunks, |c, _worker_scratch| {
let start = c * n / chunks;
let end = (c + 1) * n / chunks;
let mut hist = vec![0u32; hist_len];
scan_split_plans(
&properties[start..end],
&tokens[start..end],
plans_ref,
luts_ref,
preds_ref,
&window,
&mut hist,
);
hist
});
for part_hist in &parts {
for (a, &b) in hist.iter_mut().zip(part_hist) {
*a += b;
}
}
} else {
scan_split_plans(
properties, tokens, plans_ref, luts_ref, preds_ref, &window, &mut hist,
);
}
for plan in plans.iter() {
let start = plan.hist_start as usize;
let end = start + plan.hist_len();
let score = score_split_plan(
plan,
&preds,
alphabet,
&window,
&hist[start..end],
&all_hist,
&all_nbits,
n as u32,
&mut scratch.ma_property,
);
if let Some((t, bits)) = score
&& (best.is_none() || bits < best.unwrap().2)
{
best = Some((plan.prop as usize, t, bits));
}
}
} else {
let one_plan = |plan: &SplitPlan, sc: &mut MaPropertyScratch| {
sc.prepare(alphabet);
let mut local = *plan;
local.hist_start = 0;
let mut hist = std::mem::take(&mut sc.multi_hist);
hist.clear();
hist.resize(plan.hist_len(), 0);
scan_split_plans(
properties,
tokens,
std::slice::from_ref(&local),
&luts,
&preds,
&window,
&mut hist,
);
let score = score_split_plan(
&local, &preds, alphabet, &window, &hist, &all_hist, &all_nbits, n as u32,
sc,
);
sc.multi_hist = hist;
score
};
let scores: Vec<Option<(i32, f32)>> =
if n >= PARALLEL_PLAN_MIN_SAMPLES && pool.num_threads() > 1 {
let plans_ref = &plans;
pool.steal_map(scratch, plans.len(), |k, worker_scratch| {
one_plan(&plans_ref[k], &mut worker_scratch.ma_property)
})
} else {
plans
.iter()
.map(|plan| one_plan(plan, &mut scratch.ma_property))
.collect()
};
for (plan, score) in plans.iter().zip(scores) {
if let Some((t, bits)) = score
&& (best.is_none() || bits < best.unwrap().2)
{
best = Some((plan.prop as usize, t, bits));
}
}
}
scratch.ma_property.plans = plans;
scratch.ma_property.luts = luts;
scratch.ma_property.multi_hist = hist;
if let Some((prop, threshold, bits)) = best {
let g = base_bits - bits - self.p.split_cost_bits;
if g > 0.0 {
split = Some((prop as u8, threshold));
gain = g;
}
}
}
Pending {
node_id,
start,
end,
depth,
base_bits,
split,
gain,
pred: base_pred as u32,
offset: if base_pred == PRED_ZERO {
zero_offset
} else {
0
},
}
}
}
struct Pending {
node_id: u32,
pred: u32,
offset: i32,
start: usize,
end: usize,
depth: u16,
base_bits: f32,
split: Option<(u8, i32)>,
gain: f32,
}
impl PartialEq for Pending {
fn eq(&self, other: &Self) -> bool {
self.gain == other.gain
}
}
impl Eq for Pending {}
impl PartialOrd for Pending {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Pending {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.gain.total_cmp(&other.gain)
}
}
fn new_learner(samples: &mut MaSamples, params: MaLearnParams, nodes: Vec<MaNode>) -> Learner<'_> {
let leaves = nodes
.iter()
.filter(|node| matches!(node, MaNode::Leaf { .. }))
.count() as u32;
let info = nodes
.iter()
.map(|node| match *node {
MaNode::Leaf { pred, offset } => NodeInfo {
base_bits: 0.0,
pred,
offset,
},
MaNode::Split { .. } => NodeInfo {
base_bits: f32::INFINITY,
pred: 0,
offset: 0,
},
})
.collect();
Learner {
s: samples,
nodes,
info,
leaves,
est_bits: 0.0,
p: params,
}
}
fn flat_cost(learner: &Learner<'_>, scratch: &mut CoderScratch) -> f64 {
let samples = &*learner.s;
let alphabet = learner.p.alphabet;
let channel_stride = NUM_MA_PREDS * alphabet;
let MaPropertyScratch {
flat_hist,
node_nbits,
node_costs,
..
} = &mut scratch.ma_property;
flat_hist.clear();
flat_hist.resize(4 * channel_stride, 0);
let mut counts = [0u32; 4];
with_ma_properties!(&samples.props, |rows| {
for (props, tokens) in rows.iter().zip(&samples.tok) {
let c = props[0].clamp(0, 3) as usize;
counts[c] += 1;
let hist = &mut flat_hist[c * channel_stride..][..channel_stride];
count_predictor_tokens(hist, alphabet, tokens);
}
});
let mut flat_bits = 0.0;
for (hist, count) in flat_hist.chunks_exact(channel_stride).zip(counts) {
if count != 0 {
let (bits, _) = predictor_costs(hist, count, &learner.p, node_nbits, node_costs);
flat_bits += bits as f64;
}
}
flat_bits
}
struct Ahead {
children: Option<(usize, Pending, Pending)>,
}
fn speculative_splits(pool: &ThreadPool) -> usize {
match pool.num_threads() {
1 => 1,
threads => (2 * threads).min(SPECULATE_MAX_WINDOW),
}
}
const SPECULATE_MAX_WINDOW: usize = 8;
const SPECULATE_MAX_ROWS: usize = 1 << 16;
fn partition_by<T>(
rows: &mut [T],
is_gt: impl Fn(&T) -> bool,
mut swap_parallel_rows: impl FnMut(usize, usize),
) -> usize {
let mut lo = 0;
let mut hi = rows.len();
while lo < hi {
if is_gt(&rows[lo]) {
lo += 1;
} else {
hi -= 1;
rows.swap(lo, hi);
swap_parallel_rows(lo, hi);
}
}
lo
}
fn val_range(val: &mut [i32], start: usize, end: usize) -> &mut [i32] {
let n = val.len();
&mut val[start.min(n)..end.min(n)]
}
const MODAL_MAX_SPAN: i64 = 4096;
fn rebase_zero(tok: &mut [[u8; NUM_MA_PREDS]], val: &[i32], hist: &mut Vec<u32>) -> i32 {
let (Some(&lo), Some(&hi)) = (val.iter().min(), val.iter().max()) else {
return 0;
};
let span = i64::from(hi) - i64::from(lo) + 1;
let mode = if span > MODAL_MAX_SPAN {
0
} else {
hist.clear();
hist.resize(span as usize, 0);
for &v in val {
hist[(v - lo) as usize] += 1;
}
let (best, _) =
hist.iter().enumerate().fold(
(0usize, 0u32),
|acc, (i, &c)| if c > acc.1 { (i, c) } else { acc },
);
lo + best as i32
};
for (t, &v) in tok.iter_mut().zip(val) {
let (token, _, _) = uint_encode(pack_signed(v - mode));
t[PRED_ZERO] = token.min(u8::MAX as u32) as u8;
}
mode
}
fn grow_tree(
mut learner: Learner<'_>,
mut heap: std::collections::BinaryHeap<Pending>,
flat_bits: f64,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> LearnedTree {
let window = speculative_splits(pool);
let mut ahead: std::collections::HashMap<u32, Ahead> = std::collections::HashMap::new();
let modal = learner.p.modal_offsets && !learner.s.val.is_empty();
while learner.leaves < learner.p.max_leaves as u32 {
let Some(p) = heap.pop() else { break };
let remaining = (learner.p.max_leaves as u32 - learner.leaves) as usize;
let (prop, threshold) = p.split.expect("only splittable nodes are queued");
if !ahead.contains_key(&p.node_id) {
let lo = p.start + learner.s.partition(p.start, p.end, prop, threshold);
let offsets = (
learner.rebase(p.start, lo, scratch),
learner.rebase(lo, p.end, scratch),
);
let committed_live = lo != p.start && lo != p.end;
let mut speculated: Vec<(u32, usize, usize, u8, i32, u16)> = Vec::new();
let speculate = window.min(remaining) - 1;
if speculate > 0 {
let mut next: Vec<&Pending> = heap
.iter()
.filter(|q| {
!ahead.contains_key(&q.node_id) && q.end - q.start <= SPECULATE_MAX_ROWS
})
.collect();
next.sort_by(|a, b| b.gain.total_cmp(&a.gain));
for q in next.into_iter().take(speculate) {
let (prop, threshold) = q.split.expect("only splittable nodes are queued");
speculated.push((q.node_id, q.start, q.end, prop, threshold, q.depth + 1));
}
}
let committed_tasks = if committed_live { 2 } else { 0 };
let learner_ref = &learner;
let speculated_ref = &speculated;
let score = |k: usize, worker_scratch: &mut CoderScratch| -> Option<(usize, Pending)> {
if k < committed_tasks {
let (start, end, offset) = if k == 0 {
(p.start, lo, offsets.0)
} else {
(lo, p.end, offsets.1)
};
let pending = learner_ref.evaluate(
0,
start,
end,
p.depth + 1,
offset,
remaining > 1,
pool,
worker_scratch,
);
return Some((lo, pending));
}
let j = (k - committed_tasks) / 2;
let (_, start, end, prop, threshold, depth) = speculated_ref[j];
let (indices, split_at) =
learner_ref.s.partition_indices(start, end, prop, threshold);
if split_at == 0 || split_at == indices.len() {
return None;
}
let rows = if (k - committed_tasks).is_multiple_of(2) {
0..split_at
} else {
split_at..indices.len()
};
let mut copy = learner_ref.s.select(&indices[rows.clone()]);
let offset = if modal {
rebase_zero(
&mut copy.tok,
©.val,
&mut worker_scratch.ma_property.multi_bin_count,
)
} else {
0
};
let pending = learner_ref.evaluate_rows(
0,
start + rows.start,
start + rows.end,
copy.props.slice(0..copy.len()),
©.tok,
depth,
offset,
true,
pool,
worker_scratch,
);
Some((start + split_at, pending))
};
let tasks = committed_tasks + 2 * speculated.len();
let smallest = if committed_live {
(lo - p.start).min(p.end - lo)
} else {
0
};
let scored: Vec<Option<(usize, Pending)>> = if pool.num_threads() > 1
&& (tasks > 2 || smallest >= PARALLEL_CHILD_MIN_SAMPLES)
{
pool.steal_map(scratch, tasks, score)
} else {
(0..tasks).map(|k| score(k, scratch)).collect()
};
let mut scored = scored.into_iter();
let children = committed_live.then(|| {
let (_, gt) = scored.next().expect("gt child").expect("committed gt");
let (_, le) = scored.next().expect("le child").expect("committed le");
(lo, gt, le)
});
ahead.insert(p.node_id, Ahead { children });
for &(node_id, ..) in &speculated {
let gt = scored.next().expect("gt child");
let le = scored.next().expect("le child");
let children = match (gt, le) {
(Some((lo, gt)), Some((_, le))) => Some((lo, gt, le)),
_ => None,
};
ahead.insert(node_id, Ahead { children });
}
} else {
let lo = p.start + learner.s.partition(p.start, p.end, prop, threshold);
learner.rebase(p.start, lo, scratch);
learner.rebase(lo, p.end, scratch);
}
let Some((_, mut gt, mut le)) = ahead.remove(&p.node_id).expect("scored ahead").children
else {
continue;
};
let gt_id = learner.nodes.len() as u32;
learner.nodes.push(MaNode::Leaf {
pred: gt.pred,
offset: gt.offset,
});
let le_id = learner.nodes.len() as u32;
learner.nodes.push(MaNode::Leaf {
pred: le.pred,
offset: le.offset,
});
learner.nodes[p.node_id as usize] = MaNode::Split {
prop,
val: threshold,
gt: gt_id,
le: le_id,
};
learner.info[p.node_id as usize] = NodeInfo::of(&p);
learner.info.push(NodeInfo::of(>));
learner.info.push(NodeInfo::of(&le));
learner.leaves += 1;
gt.node_id = gt_id;
le.node_id = le_id;
learner.est_bits += (gt.base_bits + le.base_bits - p.base_bits) as f64;
if gt.split.is_some() {
heap.push(gt);
}
if le.split.is_some() {
heap.push(le);
}
}
if learner.p.prune_leaf_bits > 0.0 {
learner.est_bits = prune_tree(&mut learner.nodes, &learner.info, learner.p.prune_leaf_bits);
}
LearnedTree {
est_bits: learner.est_bits,
flat_bits,
nodes: learner.nodes,
}
}
fn prune_tree(nodes: &mut Vec<MaNode>, info: &[NodeInfo], leaf_bits: f32) -> f64 {
let n = nodes.len();
let mut subtree_bits = vec![0.0f64; n];
let mut priced_bits = vec![0.0f64; n];
for i in (0..n).rev() {
match nodes[i] {
MaNode::Leaf { .. } => {
subtree_bits[i] = info[i].base_bits as f64;
priced_bits[i] = subtree_bits[i];
}
MaNode::Split { gt, le, .. } => {
let kept = priced_bits[gt as usize] + priced_bits[le as usize] + leaf_bits as f64;
if info[i].base_bits as f64 <= kept {
nodes[i] = MaNode::Leaf {
pred: info[i].pred,
offset: info[i].offset,
};
subtree_bits[i] = info[i].base_bits as f64;
priced_bits[i] = subtree_bits[i];
} else {
subtree_bits[i] = subtree_bits[gt as usize] + subtree_bits[le as usize];
priced_bits[i] = kept;
}
}
}
}
let mut new_index = vec![u32::MAX; n];
let mut order = Vec::with_capacity(n);
let mut stack = vec![0u32];
while let Some(i) = stack.pop() {
new_index[i as usize] = order.len() as u32;
order.push(i);
if let MaNode::Split { gt, le, .. } = nodes[i as usize] {
stack.push(le);
stack.push(gt);
}
}
let compact = order
.iter()
.map(|&i| match nodes[i as usize] {
MaNode::Split { prop, val, gt, le } => MaNode::Split {
prop,
val,
gt: new_index[gt as usize],
le: new_index[le as usize],
},
leaf => leaf,
})
.collect();
*nodes = compact;
subtree_bits[0]
}
pub(crate) fn learn_ma_tree(
samples: &MaSamples,
params: MaLearnParams,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> LearnedTree {
let idx: Vec<u32> = (0..samples.len() as u32).collect();
learn_ma_tree_indexed(samples, idx, params, pool, scratch)
}
pub(crate) fn learn_ma_tree_indexed(
samples: &MaSamples,
idx: Vec<u32>,
params: MaLearnParams,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> LearnedTree {
let mut compact = {
let selection = idx;
samples.select(&selection)
};
learn_ma_tree_in_place(&mut compact, params, pool, scratch)
}
pub(crate) fn learn_ma_tree_in_place(
samples: &mut MaSamples,
params: MaLearnParams,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> LearnedTree {
let n = samples.len();
let mut learner = new_learner(samples, params, vec![MaNode::Leaf { pred: 0, offset: 0 }]);
let flat_bits = flat_cost(&learner, scratch);
let mut heap = std::collections::BinaryHeap::new();
let offset = learner.rebase(0, n, scratch);
let root = learner.evaluate(
0,
0,
n,
0,
offset,
learner.p.max_leaves as u32 > 1,
pool,
scratch,
);
learner.nodes[0] = MaNode::Leaf {
pred: root.pred,
offset: root.offset,
};
learner.info[0] = NodeInfo::of(&root);
learner.est_bits = root.base_bits as f64;
if root.split.is_some() {
heap.push(root);
}
grow_tree(learner, heap, flat_bits, pool, scratch)
}
pub(crate) fn deepen_ma_tree(
samples: MaSamples,
params: MaLearnParams,
seed: LearnedTree,
pool: &ThreadPool,
scratch: &mut CoderScratch,
) -> (LearnedTree, MaSamples) {
let depths = {
let mut depths = vec![0u16; seed.nodes.len()];
let mut stack = vec![0usize];
while let Some(node) = stack.pop() {
if let MaNode::Split { gt, le, .. } = seed.nodes[node] {
depths[gt as usize] = depths[node] + 1;
depths[le as usize] = depths[node] + 1;
stack.push(gt as usize);
stack.push(le as usize);
}
}
depths
};
let (counts, offsets, idx) = {
let mut leaf_for_sample = Vec::with_capacity(samples.len());
let mut counts = vec![0usize; seed.nodes.len()];
with_ma_properties!(&samples.props, |rows| {
for props in rows {
let (leaf, _) = seed.lookup(props);
leaf_for_sample.push(leaf);
counts[leaf as usize] += 1;
}
});
let mut offsets = vec![0usize; seed.nodes.len() + 1];
let mut total = 0;
for (offset, &count) in offsets.iter_mut().skip(1).zip(&counts) {
total += count;
*offset = total;
}
let mut cursors = offsets[..seed.nodes.len()].to_vec();
let mut idx = vec![0u32; samples.len()];
for (sample, &leaf) in leaf_for_sample.iter().enumerate() {
let cursor = &mut cursors[leaf as usize];
idx[*cursor] = sample as u32;
*cursor += 1;
}
(counts, offsets, idx)
};
let mut compact = samples.into_permuted(idx);
let mut learner = new_learner(&mut compact, params, seed.nodes);
let flat_bits = flat_cost(&learner, scratch);
let mut heap = std::collections::BinaryHeap::new();
let seed_leaves: Vec<usize> = (0..learner.nodes.len())
.filter(|&node| matches!(learner.nodes[node], MaNode::Leaf { .. }) && counts[node] != 0)
.collect();
let modal_offsets: Vec<i32> = seed_leaves
.iter()
.map(|&node| learner.rebase(offsets[node], offsets[node + 1], scratch))
.collect();
let pendings = {
let learner_ref = &learner;
pool.steal_map(scratch, seed_leaves.len(), |k, worker_scratch| {
let node = seed_leaves[k];
learner_ref.evaluate(
node as u32,
offsets[node],
offsets[node + 1],
depths[node],
modal_offsets[k],
learner_ref.leaves < learner_ref.p.max_leaves as u32,
pool,
worker_scratch,
)
})
};
for pending in pendings {
learner.nodes[pending.node_id as usize] = MaNode::Leaf {
pred: pending.pred,
offset: pending.offset,
};
learner.info[pending.node_id as usize] = NodeInfo::of(&pending);
learner.est_bits += pending.base_bits as f64;
if pending.split.is_some() {
heap.push(pending);
}
}
let tree = grow_tree(learner, heap, flat_bits, pool, scratch);
(tree, compact)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn narrow_learning_and_deepening_match_wide_cost_bits_and_row_order() {
let params = |leaves| MaLearnParams {
alphabet: 64,
max_leaves: leaves,
split_cost_bits: 4.,
min_node: 32,
allow_wp: true,
allowed_preds: u16::MAX,
side_preds: 4,
max_candidates: 16,
modal_offsets: true,
prune_leaf_bits: 2.,
};
let assert_tree = |a: &LearnedTree, b: &LearnedTree| {
assert_eq!(a.nodes, b.nodes);
assert_eq!(a.est_bits.to_bits(), b.est_bits.to_bits());
assert_eq!(a.flat_bits.to_bits(), b.flat_bits.to_bits());
};
for count in [4096, PARALLEL_SCAN_MIN_SAMPLES + 33] {
let mut samples = MaSamples::with_capacity(count);
for i in 0..count {
let mut props =
core::array::from_fn(|p| ((i * (2 * p + 1)) % (17 + 3 * p)) as i32 - 16);
props[0] = (i / 256 % 4) as i32;
props[4] = (i / 64 % 2 * 100 + i % 8) as i32;
props[23] = if i % 2 == 0 {
i16::MIN as i32
} else {
i16::MAX as i32
};
let val = (i % 27) as i32 - 13;
let tokens = core::array::from_fn(|p| {
let residual = if p == 0 {
val
} else if p == i / 64 % 3 + 1 {
(i % 3) as i32 - 1
} else {
((i * 7 + p * 13) % 211) as i32 - 105
};
uint_encode(pack_signed(residual)).0 as u8
});
samples.push_val(props, tokens, val);
}
assert!(matches!(&samples.props, MaProperties::Narrow(_)));
let mut wide = MaSamples {
props: MaProperties::Wide(samples.props.iter().collect()),
tok: samples.tok.clone(),
val: samples.val.clone(),
};
let mut serial: Option<(LearnedTree, MaSamples)> = None;
for threads in [1, 4] {
let pool = ThreadPool::new(threads);
if threads == 4 {
let a = learn_ma_tree(&samples, params(8), &pool, &mut CoderScratch::default());
let b = learn_ma_tree(&wide, params(8), &pool, &mut CoderScratch::default());
assert_tree(&a, &b);
}
let indices = samples.evenly_sampled_indices(1024);
let seed = learn_ma_tree_indexed(
&samples,
indices.clone(),
params(8),
&pool,
&mut CoderScratch::default(),
);
let wide_seed = learn_ma_tree_indexed(
&wide,
indices,
params(8),
&pool,
&mut CoderScratch::default(),
);
assert_tree(&seed, &wide_seed);
let (narrow_tree, narrow_rows) = deepen_ma_tree(
samples.select(&(0..count as u32).collect::<Vec<_>>()),
params(24),
seed,
&pool,
&mut CoderScratch::default(),
);
let (wide_tree, wide_rows) = deepen_ma_tree(
wide.select(&(0..count as u32).collect::<Vec<_>>()),
params(24),
wide_seed,
&pool,
&mut CoderScratch::default(),
);
assert_tree(&narrow_tree, &wide_tree);
assert_eq!(
narrow_rows.props.iter().collect::<Vec<_>>(),
wide_rows.props.iter().collect::<Vec<_>>()
);
assert_eq!(narrow_rows.tok, wide_rows.tok);
assert_eq!(narrow_rows.val, wide_rows.val);
if let Some((tree, rows)) = &serial {
assert_tree(&narrow_tree, tree);
assert_eq!(narrow_rows.props, rows.props);
assert_eq!(narrow_rows.tok, rows.tok);
assert_eq!(narrow_rows.val, rows.val);
} else {
serial = Some((narrow_tree, narrow_rows));
}
}
wide.props.map_rows(|row| row[4] *= 100_000);
let wide_tree = learn_ma_tree_in_place(
&mut wide,
params(8),
&ThreadPool::new(1),
&mut CoderScratch::default(),
);
assert!(wide_tree.est_bits.is_finite());
}
}
#[test]
fn sample_permutation_matches_gather() {
let mut state = 0x739feb12u32;
for len in [0, 1, 2, 3, 31, 64, 257, 4096] {
for kind in 0..4 {
let mut samples = MaSamples::new();
for i in 0..len {
samples.push(
core::array::from_fn(|p| (i * 101 + p) as i32),
core::array::from_fn(|p| (i * 13 + p) as u8),
);
}
let mut indices: Vec<u32> = (0..len as u32).collect();
match kind {
1 => indices.reverse(),
2 if len > 0 => indices.rotate_left(1),
3 => {
for i in (1..len).rev() {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
indices.swap(i, state as usize % (i + 1));
}
}
_ => {}
}
let expected = samples.select(&indices);
let props_ptr = samples.props.as_ptr();
let tok_ptr = samples.tok.as_ptr();
let actual = samples.into_permuted(indices);
assert_eq!(actual.props, expected.props);
assert_eq!(actual.tok, expected.tok);
assert_eq!(actual.props.as_ptr(), props_ptr);
assert_eq!(actual.tok.as_ptr(), tok_ptr);
}
}
}
#[test]
fn probe_bitmap_matches_sort_dedup() {
let mut state = 0x83d2eaf1u32;
let mut bitmap = [u64::MAX; PROBE_BITMAP_BITS / 64];
for len in [0, 1, 2, 31, 32, 33, 63, 64, 65, 1024, 2047] {
for range in [1i64, 2, 63, 64, 65, 256, 4095, 4096, 4097, 65536, 1 << 32] {
for min in [i32::MIN as i64, -(range / 2), i32::MAX as i64 - range + 1] {
let mut input = Vec::with_capacity(len);
for i in 0..len {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
let offset = match i {
0 => 0,
1 => range - 1,
_ => state as i64 % range,
};
input.push((min + offset) as i32);
}
let mut expected = input.clone();
expected.sort_unstable();
expected.dedup();
for order in 0..3 {
if order == 1 {
input.sort_unstable();
} else if order == 2 {
input.reverse();
}
let mut actual = input.clone();
sort_unique_probe(&mut actual, &mut bitmap);
assert_eq!(actual, expected, "len={len}, range={range}, min={min}");
}
}
}
}
}
#[test]
fn cached_count_logs_match_direct_approximation() {
let logs = count_log2_table();
for count in (1..8192).chain([16_777_215, 16_777_216, 16_777_217, u32::MAX]) {
assert_eq!(
count_log2(count, logs).to_bits(),
dirty_log2f(count as f32).to_bits(),
"count={count}",
);
}
}
#[test]
fn split_scoring_matches_direct_threshold_histograms() {
let mut state = 0x83d2eaf1u32;
let mut next = || {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
state
};
let mut scratch = MaPropertyScratch::default();
for n in [
1, 63, 64, 65, 255, 256, 257, 1023, 1024, 1025, 4095, 4096, 4097, 16385,
] {
let mut samples = MaSamples::new();
for _ in 0..n {
let mut props = [0; NUM_MA_PROPS];
props[2] = (next() % 83) as i32 - 41;
props[3] = next() as i32;
let symbols = if n > 1025 { 2 } else { 56 };
samples.push(
props,
core::array::from_fn(|p| {
if matches!(n, 257 | 1025) {
9 + (p % 4) as u8 * 10 + 2 * (next() % 5) as u8
} else {
(next() % symbols) as u8
}
}),
);
}
let idx: Vec<u32> = (0..n).map(|_| next() % n as u32).collect();
let selected = samples.select(&idx);
let alphabet = 64;
let mut all_hist = vec![0u32; NUM_MA_PREDS * alphabet];
for &i in &idx {
for (p, &token) in samples.tok[i as usize].iter().enumerate() {
all_hist[p * alphabet + token as usize] += 1;
}
}
let all_nbits = core::array::from_fn(|p| {
raw_bits_from_hist(&all_hist[p * alphabet..(p + 1) * alphabet])
});
for prop in [2, 3] {
for max_candidates in [16, 32] {
for preds in [&[6][..], &[13, 0][..], &[3, 0, 2, 1][..]] {
let actual =
with_ma_properties!(&selected.props, |properties| best_split_on_prop(
properties,
&selected.tok,
prop,
preds,
alphabet,
max_candidates,
&all_hist,
&all_nbits,
&mut scratch,
));
let mut expected = None;
for &threshold in &scratch.cands {
let mut left_hist = vec![0u32; all_hist.len()];
let mut left_count = 0;
for &i in &idx {
if samples.props.get(i as usize)[prop] <= threshold {
left_count += 1;
for &p in preds {
left_hist
[p * alphabet + samples.tok[i as usize][p] as usize] +=
1;
}
}
}
if left_count == 0 || left_count == n as u32 {
continue;
}
let mut best_l = f32::INFINITY;
let mut best_r = f32::INFINITY;
for &p in preds {
let left = &left_hist[p * alphabet..(p + 1) * alphabet];
let right: Vec<u32> = all_hist[p * alphabet..(p + 1) * alphabet]
.iter()
.zip(left)
.map(|(&a, &l)| a - l)
.collect();
best_l = best_l.min(
hist_entropy_bits(left, left_count)
+ raw_bits_from_hist(left) as f32,
);
best_r = best_r.min(
hist_entropy_bits(&right, n as u32 - left_count)
+ raw_bits_from_hist(&right) as f32,
);
}
let cost = best_l + best_r;
if expected.is_none_or(|(_, best)| cost < best) {
expected = Some((threshold, cost));
}
}
let to_bits = |(threshold, bits): (i32, f32)| (threshold, bits.to_bits());
assert_eq!(
actual.map(to_bits),
expected.map(to_bits),
"n={n}, prop={prop}, candidates={max_candidates}, preds={preds:?}"
);
}
}
}
}
}
use crate::entropy::{pack_signed, uint_encode};
#[test]
fn selected_rows_keep_properties_and_predictors_together() {
let mut samples = MaSamples::new();
for i in 0..32u8 {
samples.push(
[i as i32 - 16; NUM_MA_PROPS],
std::array::from_fn(|p| i + p as u8),
);
}
let mut selected = samples.select(&[31, 4, 17, 4]);
selected.props.swap(0, 2);
selected.tok.swap(0, 2);
for (row, source) in [17, 4, 31, 4].into_iter().enumerate() {
assert_eq!(selected.props.get(row), samples.props.get(source));
assert_eq!(selected.tok[row], samples.tok[source]);
}
}
#[test]
fn histogram_raw_bits_match_encoded_values() {
let mut hist = [0u32; 128];
let mut expected = 0u64;
let mut add = |value| {
let (token, nbits, _) = uint_encode(value);
hist[token as usize] += 1;
expected += nbits as u64;
};
for value in 0..65_536 {
add(value);
}
for bit in 0..32 {
let value = 1u32 << bit;
for delta in 0..8 {
add(value.saturating_sub(delta));
add(value.saturating_add(delta));
}
}
add(u32::MAX);
assert_eq!(raw_bits_from_hist(&hist), expected);
}
#[test]
fn learns_a_discriminating_split() {
let mut s = MaSamples::new();
let mut push = |prop4: i32, good_pred: usize| {
let mut props = [0i32; NUM_MA_PROPS];
props[4] = prop4;
props[6] = prop4;
let mut tok = [0u8; NUM_MA_PREDS];
for p in 0..NUM_MA_PREDS {
let res = if p == good_pred { 0 } else { 200 };
let (t, _, _) = uint_encode(pack_signed(res));
tok[p] = t as u8;
}
s.push(props, tok);
};
for i in 0..8192 {
push(i % 8, 1); push(64 + i % 8, 5); }
let mut serial_scratch = CoderScratch::default();
let serial_pool = ThreadPool::new(1);
let serial = learn_ma_tree(
&s,
MaLearnParams {
alphabet: 64,
max_leaves: 8,
split_cost_bits: 10.0,
min_node: 64,
allow_wp: true,
allowed_preds: u16::MAX,
side_preds: NUM_MA_PREDS,
max_candidates: MAX_CANDIDATES,
modal_offsets: false,
prune_leaf_bits: 0.0,
},
&serial_pool,
&mut serial_scratch,
);
let mut parallel_scratch = CoderScratch::default();
let parallel_pool = ThreadPool::new(4);
let tree = learn_ma_tree(
&s,
MaLearnParams {
alphabet: 64,
max_leaves: 8,
split_cost_bits: 10.0,
min_node: 64,
allow_wp: true,
allowed_preds: u16::MAX,
side_preds: NUM_MA_PREDS,
max_candidates: MAX_CANDIDATES,
modal_offsets: false,
prune_leaf_bits: 0.0,
},
¶llel_pool,
&mut parallel_scratch,
);
assert_eq!(serial.nodes, tree.nodes);
assert_eq!(serial.est_bits, tree.est_bits);
assert_eq!(serial.flat_bits, tree.flat_bits);
assert!(tree.est_bits < tree.flat_bits);
assert!(matches!(tree.nodes[0], MaNode::Split { prop: 4, .. }));
for i in 0..s.len() {
let (_, pred) = tree.lookup(&s.props.get(i));
let expected = if s.props.get(i)[4] < 32 { 1 } else { 5 };
assert_eq!(pred, expected, "sample {i} routed to wrong predictor");
}
}
#[test]
fn uniform_samples_stay_single_leaf() {
let mut s = MaSamples::new();
for _ in 0..2048 {
let props = [0i32; NUM_MA_PROPS];
let mut tok = [0u8; NUM_MA_PREDS];
for p in 0..NUM_MA_PREDS {
let (t, _, _) = uint_encode(pack_signed(3));
tok[p] = t as u8;
}
s.push(props, tok);
}
let tree = learn_ma_tree(
&s,
MaLearnParams {
alphabet: 64,
max_leaves: 8,
split_cost_bits: 10.0,
min_node: 64,
allow_wp: true,
allowed_preds: u16::MAX,
side_preds: NUM_MA_PREDS,
max_candidates: MAX_CANDIDATES,
modal_offsets: false,
prune_leaf_bits: 0.0,
},
&ThreadPool::new(1),
&mut CoderScratch::default(),
);
assert_eq!(tree.nodes.len(), 1);
assert!(matches!(tree.nodes[0], MaNode::Leaf { .. }));
}
#[test]
fn indexed_learning_matches_materialized_selection() {
let mut samples = MaSamples::new();
for i in 0..4096 {
let mut props = [0i32; NUM_MA_PROPS];
props[0] = i % 4;
props[4] = i % 97;
props[7] = (i * 13) % 211 - 105;
let mut tok = [0u8; NUM_MA_PREDS];
for pred in 0..NUM_MA_PREDS {
let residual = props[4] - pred as i32 * 3;
let (token, _, _) = uint_encode(pack_signed(residual));
tok[pred] = token as u8;
}
samples.push(props, tok);
}
let indices = samples.evenly_sampled_indices(1024);
let mut copied = MaSamples::with_capacity(indices.len());
for &index in &indices {
let index = index as usize;
copied.push(samples.props.get(index), samples.tok[index]);
}
let params = || MaLearnParams {
alphabet: 64,
max_leaves: 16,
split_cost_bits: 10.0,
min_node: 64,
allow_wp: true,
allowed_preds: u16::MAX,
side_preds: NUM_MA_PREDS,
max_candidates: MAX_CANDIDATES,
modal_offsets: false,
prune_leaf_bits: 0.0,
};
let pool = ThreadPool::new(1);
let indexed = learn_ma_tree_indexed(
&samples,
indices,
params(),
&pool,
&mut CoderScratch::default(),
);
let materialized = learn_ma_tree(&copied, params(), &pool, &mut CoderScratch::default());
assert_eq!(indexed.nodes, materialized.nodes);
assert_eq!(indexed.est_bits, materialized.est_bits);
assert_eq!(indexed.flat_bits, materialized.flat_bits);
let in_place =
learn_ma_tree_in_place(&mut copied, params(), &pool, &mut CoderScratch::default());
assert_eq!(in_place.nodes, materialized.nodes);
assert_eq!(in_place.est_bits.to_bits(), materialized.est_bits.to_bits());
assert_eq!(
in_place.flat_bits.to_bits(),
materialized.flat_bits.to_bits()
);
}
#[test]
fn prune_merges_sibling_leaves_bottom_up_and_compacts() {
let leaf = |pred: u32| MaNode::Leaf { pred, offset: 0 };
let split = |gt: u32, le: u32| MaNode::Split {
prop: 2,
val: 0,
gt,
le,
};
let info = |base_bits: f32, pred: u32, offset: i32| NodeInfo {
base_bits,
pred,
offset,
};
let grown = vec![split(1, 2), split(3, 4), leaf(1), leaf(2), leaf(3)];
let infos = [
info(200.0, 5, 0),
info(100.0, 0, 7),
info(50.0, 1, 0),
info(40.0, 2, 0),
info(45.0, 3, 0),
];
let mut nodes = grown.clone();
let est = prune_tree(&mut nodes, &infos, 20.0);
assert_eq!(
nodes,
vec![split(1, 2), MaNode::Leaf { pred: 0, offset: 7 }, leaf(1)]
);
assert_eq!(est, 150.0);
let mut nodes = grown.clone();
let est = prune_tree(&mut nodes, &infos, 60.0);
assert_eq!(nodes, vec![leaf(5)]);
assert_eq!(est, 200.0);
let mut nodes = grown;
let mut infos = infos;
infos[0].base_bits = 150.0;
let est = prune_tree(&mut nodes, &infos, 10.0);
assert_eq!(nodes, vec![leaf(5)]);
assert_eq!(est, 150.0);
}
}