use super::dlog2::f_log2;
use super::histogram::Histogram;
use super::huffman_tree::{HuffmanNode, create_huffman_tree};
use super::prefix_code::ALPHABET_SIZE;
use crate::adaptive_quant::dirty_log2f;
use crate::coder_scratch::CoderScratch;
use crate::thread_pool::ThreadPool;
use crate::util::heap_array;
use std::sync::OnceLock;
pub(crate) const CLUSTERS_LIMIT: usize = 128;
pub(crate) const FAST_CLUSTERS_LIMIT: usize = 16;
const MIN_DISTANCE_FOR_DISTINCT: f32 = 64.0;
pub(crate) struct FixedClusterScratch<const MAX_CONTEXTS: usize> {
symbols: Box<[u8; MAX_CONTEXTS]>,
in_costs: Box<[f32; MAX_CONTEXTS]>,
dists: Box<[f32; MAX_CONTEXTS]>,
clusters: Box<[Histogram; CLUSTERS_LIMIT]>,
cluster_costs: Box<[f32; CLUSTERS_LIMIT]>,
reordered: Box<[Histogram; CLUSTERS_LIMIT]>,
}
impl<const MAX_CONTEXTS: usize> Default for FixedClusterScratch<MAX_CONTEXTS> {
fn default() -> Self {
Self {
symbols: heap_array(0),
in_costs: heap_array(0.0),
dists: heap_array(0.0),
clusters: heap_array(Histogram::new()),
cluster_costs: heap_array(0.0),
reordered: heap_array(Histogram::new()),
}
}
}
type CountsBitCostFn = fn(&[u32; ALPHABET_SIZE], u32) -> f32;
#[inline]
#[cfg_attr(
any(
all(target_arch = "aarch64", feature = "neon"),
all(target_arch = "wasm32", feature = "wasm", target_feature = "simd128")
),
allow(dead_code)
)]
fn counts_bit_cost_scalar(counts: &[u32; ALPHABET_SIZE], total_count: u32) -> f32 {
debug_assert_ne!(total_count, 0);
let log_total = dirty_log2f(total_count as f32);
let mut cost = 0.0f32;
for &count in counts {
if count != 0 {
cost += count as f32 * (log_total - dirty_log2f(count as f32));
}
}
cost.max(0.0)
}
#[cfg(any(target_arch = "x86_64", target_arch = "x86"))]
fn select_counts_bit_cost_fn() -> CountsBitCostFn {
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
if std::is_x86_feature_detected!("avx2") && std::is_x86_feature_detected!("fma") {
return |counts, total_count| unsafe {
crate::avx::counts_bit_cost_avx2(counts, total_count)
};
}
#[cfg(all(any(target_arch = "x86_64", target_arch = "x86"), feature = "sse"))]
if std::is_x86_feature_detected!("sse4.1") {
return |counts, total_count| unsafe {
crate::sse::counts_bit_cost_sse41(counts, total_count)
};
}
counts_bit_cost_scalar
}
#[cfg(all(target_arch = "aarch64", feature = "neon"))]
fn select_counts_bit_cost_fn() -> CountsBitCostFn {
|counts, total_count| unsafe { crate::neon::counts_bit_cost_neon(counts, total_count) }
}
#[cfg(all(target_arch = "wasm32", feature = "wasm", target_feature = "simd128"))]
fn select_counts_bit_cost_fn() -> CountsBitCostFn {
crate::wasm::counts_bit_cost_wasm
}
#[cfg(not(any(
target_arch = "x86_64",
target_arch = "x86",
all(target_arch = "aarch64", feature = "neon"),
all(target_arch = "wasm32", feature = "wasm", target_feature = "simd128")
)))]
fn select_counts_bit_cost_fn() -> CountsBitCostFn {
counts_bit_cost_scalar
}
fn counts_bit_cost(counts: &[u32; ALPHABET_SIZE], total_count: u32) -> f32 {
if total_count == 0 {
return 0.0;
}
let mut used_symbols = 0usize;
for &count in counts.iter() {
if count != 0 {
used_symbols += 1;
if used_symbols > 2 {
break;
}
}
}
if used_symbols <= 1 {
return 0.0;
}
if used_symbols == 2 {
return total_count as f32;
}
static COUNTS_BIT_COST_FN: OnceLock<CountsBitCostFn> = OnceLock::new();
COUNTS_BIT_COST_FN.get_or_init(select_counts_bit_cost_fn)(counts, total_count)
}
fn exact_counts_bit_cost(
counts: &[u32; ALPHABET_SIZE],
total_count: u32,
huffman_pool: &mut Vec<HuffmanNode>,
) -> f32 {
if total_count == 0 {
return 0.0;
}
let used_symbols = counts.iter().filter(|&&count| count != 0).count();
if used_symbols <= 1 {
return 0.0;
}
if used_symbols == 2 {
return total_count as f32;
}
let mut depths = [0u8; ALPHABET_SIZE];
create_huffman_tree(counts, 15, &mut depths, huffman_pool);
counts
.iter()
.zip(depths)
.map(|(&count, depth)| count as f32 * depth as f32)
.sum()
}
#[inline]
fn histogram_bit_cost(h: &Histogram) -> f32 {
counts_bit_cost(&h.counts, h.total_count)
}
#[inline]
fn add_counts(dst: &mut [u32; ALPHABET_SIZE], src: &[u32; ALPHABET_SIZE]) {
for (dst, &src) in dst.iter_mut().zip(src.iter()) {
*dst += src;
}
}
fn histogram_add(a: &mut Histogram, b: &Histogram) {
add_counts(&mut a.counts, &b.counts);
a.total_count += b.total_count;
}
fn histogram_sub(a: &mut Histogram, b: &Histogram) {
for (dst, &src) in a.counts.iter_mut().zip(b.counts.iter()) {
*dst -= src;
}
a.total_count -= b.total_count;
}
fn histogram_distance(
a: &Histogram,
b: &Histogram,
a_cost: f32,
b_cost: f32,
scratch: &mut [u32; ALPHABET_SIZE],
) -> f32 {
if a.total_count == 0 || b.total_count == 0 {
return 0.0;
}
*scratch = a.counts;
add_counts(scratch, &b.counts);
counts_bit_cost(scratch, a.total_count + b.total_count) - a_cost - b_cost
}
#[inline]
fn histogram_merge_increment(
input: &Histogram,
cluster: &Histogram,
cluster_cost: f32,
scratch: &mut [u32; ALPHABET_SIZE],
) -> f32 {
*scratch = input.counts;
add_counts(scratch, &cluster.counts);
counts_bit_cost(scratch, input.total_count + cluster.total_count) - cluster_cost
}
fn update_exact_merge_pair(
i: usize,
j: usize,
clusters: &[Histogram],
active: &[bool; CLUSTERS_LIMIT],
costs: &[f32; CLUSTERS_LIMIT],
deltas: &mut [f32; CLUSTERS_LIMIT * CLUSTERS_LIMIT],
huffman_pool: &mut Vec<HuffmanNode>,
) {
if i == j || !active[i] || !active[j] {
return;
}
let (a, b) = if i < j { (i, j) } else { (j, i) };
let mut merged_counts = clusters[a].counts;
add_counts(&mut merged_counts, &clusters[b].counts);
let combined = exact_counts_bit_cost(
&merged_counts,
clusters[a].total_count + clusters[b].total_count,
huffman_pool,
);
deltas[a * CLUSTERS_LIMIT + b] = combined - costs[a] - costs[b] - MIN_DISTANCE_FOR_DISTINCT;
}
fn exact_merge_final_clusters(
clusters: &mut [Histogram],
symbols: &mut [u8],
huffman_pool: &mut Vec<HuffmanNode>,
) {
let n = clusters.len();
if n <= 1 {
return;
}
debug_assert!(n <= CLUSTERS_LIMIT);
let mut active = [false; CLUSTERS_LIMIT];
let mut costs = [0.0f32; CLUSTERS_LIMIT];
for (i, histogram) in clusters.iter().enumerate() {
active[i] = histogram.total_count != 0;
costs[i] = exact_counts_bit_cost(&histogram.counts, histogram.total_count, huffman_pool);
}
let mut deltas = [f32::INFINITY; CLUSTERS_LIMIT * CLUSTERS_LIMIT];
for i in 0..n {
for j in i + 1..n {
update_exact_merge_pair(i, j, clusters, &active, &costs, &mut deltas, huffman_pool);
}
}
loop {
let mut best = None;
let mut best_delta = -0.01f32;
for i in 0..n {
if !active[i] {
continue;
}
for j in i + 1..n {
let delta = deltas[i * CLUSTERS_LIMIT + j];
if active[j] && delta < best_delta {
best_delta = delta;
best = Some((i, j));
}
}
}
let Some((keep, remove)) = best else {
break;
};
let removed = clusters[remove].clone();
histogram_add(&mut clusters[keep], &removed);
clusters[remove] = Histogram::new();
active[remove] = false;
costs[keep] = exact_counts_bit_cost(
&clusters[keep].counts,
clusters[keep].total_count,
huffman_pool,
);
for symbol in symbols.iter_mut() {
if *symbol as usize == remove {
*symbol = keep as u8;
}
}
for j in 0..n {
deltas[remove * CLUSTERS_LIMIT + j] = f32::INFINITY;
deltas[j * CLUSTERS_LIMIT + remove] = f32::INFINITY;
update_exact_merge_pair(
keep,
j,
clusters,
&active,
&costs,
&mut deltas,
huffman_pool,
);
}
}
}
pub(crate) fn cluster_histograms(
histograms: &mut Vec<Histogram>,
context_map: &mut Vec<u8>,
huffman_pool: &mut Vec<HuffmanNode>,
) {
cluster_histograms_inner(
histograms,
context_map,
false,
false,
CLUSTERS_LIMIT,
huffman_pool,
None,
);
}
pub(crate) fn cluster_histograms_with_pool(
histograms: &mut Vec<Histogram>,
context_map: &mut Vec<u8>,
huffman_pool: &mut Vec<HuffmanNode>,
isolate_single_symbol: bool,
max_clusters: usize,
pool: Option<&ThreadPool>,
) {
cluster_histograms_inner(
histograms,
context_map,
false,
isolate_single_symbol,
max_clusters,
huffman_pool,
pool,
);
}
pub(crate) fn cluster_histograms_fixed<const MAX_CONTEXTS: usize>(
histograms: &mut [Histogram],
context_map: &mut [u8],
refined: bool,
max_clusters: usize,
fixed: &mut FixedClusterScratch<MAX_CONTEXTS>,
huffman_pool: &mut Vec<HuffmanNode>,
) -> usize {
let n = histograms.len();
assert!(n <= MAX_CONTEXTS);
assert!(context_map.len() >= n);
assert!((1..=CLUSTERS_LIMIT).contains(&max_clusters));
if n <= 1 {
context_map[..n].fill(0);
return n;
}
const UNMAPPED: u8 = u8::MAX;
let max_histograms = max_clusters.min(n);
let unassigned = max_histograms as u8;
let symbols = &mut fixed.symbols[..n];
symbols.fill(unassigned);
let in_costs = &mut fixed.in_costs[..n];
let dists = &mut fixed.dists[..n];
dists.fill(f32::MAX);
let mut largest_idx = 0usize;
let mut largest_count = 0u32;
for (i, (((hist, symbol), dist), cost)) in histograms
.iter()
.zip(symbols.iter_mut())
.zip(dists.iter_mut())
.zip(in_costs.iter_mut())
.enumerate()
{
let total_count = hist.total_count;
if total_count == 0 {
*symbol = 0;
*dist = 0.0;
continue;
}
*cost = histogram_bit_cost(hist);
if total_count > largest_count {
largest_count = total_count;
largest_idx = i;
}
}
if largest_count == 0 {
histograms[0] = Histogram::new();
context_map[..n].fill(0);
return 1;
}
let clusters = &mut fixed.clusters;
let cluster_costs = &mut fixed.cluster_costs;
let mut num_clusters = 0usize;
let mut counts_scratch = [0u32; ALPHABET_SIZE];
while num_clusters < max_histograms {
let candidate = largest_idx;
clusters[num_clusters] = histograms[largest_idx].clone();
cluster_costs[num_clusters] = in_costs[largest_idx];
let mut saving = if dists[largest_idx] == f32::MAX {
f32::INFINITY
} else {
dists[largest_idx]
};
dists[largest_idx] = 0.0;
let last_hist = &clusters[num_clusters];
let last_cost = cluster_costs[num_clusters];
let mut next_largest_idx = candidate;
let mut next_largest_dist = 0.0f32;
for (i, ((hist, &in_cost), dist)) in histograms
.iter()
.zip(in_costs.iter())
.zip(dists.iter_mut())
.enumerate()
{
if *dist == 0.0 {
continue;
}
let distance =
histogram_distance(hist, last_hist, in_cost, last_cost, &mut counts_scratch);
if distance < *dist {
if *dist != f32::MAX {
saving += *dist - distance;
}
*dist = distance;
}
if *dist > next_largest_dist {
next_largest_dist = *dist;
next_largest_idx = i;
}
}
if num_clusters > 0 && saving < MIN_DISTANCE_FOR_DISTINCT {
break;
}
symbols[candidate] = num_clusters as u8;
num_clusters += 1;
largest_idx = next_largest_idx;
if next_largest_dist == 0.0 {
break; }
}
if !refined {
for ((hist, &in_cost), symbol) in histograms
.iter()
.zip(in_costs.iter())
.zip(symbols.iter_mut())
{
if *symbol != unassigned {
continue;
}
let mut best = 0usize;
let mut best_dist = histogram_distance(
hist,
&clusters[0],
in_cost,
cluster_costs[0],
&mut counts_scratch,
);
for candidate in 1..num_clusters {
let distance = histogram_distance(
hist,
&clusters[candidate],
in_cost,
cluster_costs[candidate],
&mut counts_scratch,
);
if distance < best_dist {
best = candidate;
best_dist = distance;
}
}
histogram_add(&mut clusters[best], hist);
cluster_costs[best] = histogram_bit_cost(&clusters[best]);
*symbol = best as u8;
}
} else {
for ((hist, &in_cost), symbol) in histograms
.iter()
.zip(in_costs.iter())
.zip(symbols.iter_mut())
{
if *symbol != unassigned {
continue;
}
let mut best = 0usize;
let mut best_dist = histogram_distance(
hist,
&clusters[0],
in_cost,
cluster_costs[0],
&mut counts_scratch,
);
for candidate in 1..num_clusters {
let distance = histogram_distance(
hist,
&clusters[candidate],
in_cost,
cluster_costs[candidate],
&mut counts_scratch,
);
if distance < best_dist {
best = candidate;
best_dist = distance;
}
}
*symbol = best as u8;
}
clusters[..num_clusters].fill(Histogram::new());
for (hist, &symbol) in histograms.iter().zip(symbols.iter()) {
histogram_add(&mut clusters[symbol as usize], hist);
}
for cluster in 0..num_clusters {
cluster_costs[cluster] = histogram_bit_cost(&clusters[cluster]);
}
for _ in 0..2 {
let mut changed = false;
for (hist, symbol) in histograms.iter().zip(symbols.iter_mut()) {
if hist.total_count == 0 {
continue;
}
let old = *symbol as usize;
let mut old_without = clusters[old].clone();
histogram_sub(&mut old_without, hist);
let remove_delta = histogram_bit_cost(&old_without) - cluster_costs[old];
let mut best = old;
let mut best_delta = 0.0f32;
for candidate in 0..num_clusters {
if candidate == old || clusters[candidate].total_count == 0 {
continue;
}
let add_delta = histogram_merge_increment(
hist,
&clusters[candidate],
cluster_costs[candidate],
&mut counts_scratch,
);
let delta = remove_delta + add_delta;
if delta < best_delta - 0.01 {
best_delta = delta;
best = candidate;
}
}
if best != old {
histogram_sub(&mut clusters[old], hist);
histogram_add(&mut clusters[best], hist);
cluster_costs[old] = histogram_bit_cost(&clusters[old]);
cluster_costs[best] = histogram_bit_cost(&clusters[best]);
*symbol = best as u8;
changed = true;
}
}
if !changed {
break;
}
}
}
exact_merge_final_clusters(&mut clusters[..num_clusters], symbols, huffman_pool);
let mut compact = [UNMAPPED; CLUSTERS_LIMIT];
let mut compact_len = 0usize;
for (old, histogram) in clusters[..num_clusters].iter().enumerate() {
if histogram.total_count != 0 {
compact[old] = compact_len as u8;
fixed.reordered[compact_len] = histogram.clone();
compact_len += 1;
}
}
for symbol in symbols.iter_mut() {
*symbol = compact[*symbol as usize];
}
clusters[..compact_len].clone_from_slice(&fixed.reordered[..compact_len]);
num_clusters = compact_len;
let mut remap = [UNMAPPED; CLUSTERS_LIMIT];
let mut reordered_len = 0usize;
for (i, &symbol) in symbols.iter().enumerate() {
debug_assert_ne!(symbol, unassigned);
let old_index = symbol as usize;
debug_assert!(old_index < num_clusters);
if remap[old_index] == UNMAPPED {
remap[old_index] = reordered_len as u8;
fixed.reordered[reordered_len] = clusters[old_index].clone();
reordered_len += 1;
}
context_map[i] = remap[old_index];
}
histograms[..reordered_len].clone_from_slice(&fixed.reordered[..reordered_len]);
reordered_len
}
fn assign_prefix_histograms_parallel(
inp: &[Histogram],
in_costs: &[f32],
out: &mut [Histogram],
out_costs: &mut [f32],
symbols: &mut [u8],
pool: Option<&ThreadPool>,
) -> bool {
let Some(pool) = pool.filter(|pool| pool.num_threads() > 1 && out.len() >= 64) else {
return false;
};
let unassigned = CLUSTERS_LIMIT.min(inp.len()) as u8;
let pending: Vec<_> = symbols
.iter()
.enumerate()
.filter_map(|(i, &symbol)| (symbol == unassigned).then_some(i))
.collect();
if pending.len() < 1024 {
return false;
}
const BATCH: usize = 128;
let mut distances = vec![[0.0f32; CLUSTERS_LIMIT]; BATCH];
let mut caller_scratch = CoderScratch::lossless();
let mut scratch = [0u32; ALPHABET_SIZE];
for batch in pending.chunks(BATCH) {
pool.steal_for_each_mut_with_threads(
&mut caller_scratch,
&mut distances[..batch.len()],
4,
|row, distances, _| {
let i = batch[row];
let mut scratch = [0u32; ALPHABET_SIZE];
for (j, (candidate, &cost)) in out.iter().zip(out_costs.iter()).enumerate() {
distances[j] =
histogram_distance(&inp[i], candidate, in_costs[i], cost, &mut scratch);
}
},
);
let mut changed = [false; CLUSTERS_LIMIT];
for (&i, distances) in batch.iter().zip(&distances) {
let hist = &inp[i];
let mut best = 0;
let mut best_dist = f32::MAX;
for j in 0..out.len() {
let distance = if changed[j] {
histogram_distance(hist, &out[j], in_costs[i], out_costs[j], &mut scratch)
} else {
distances[j]
};
if j == 0 || distance < best_dist {
best = j;
best_dist = distance;
}
}
histogram_add(&mut out[best], hist);
out_costs[best] = histogram_bit_cost(&out[best]);
changed[best] = true;
symbols[i] = best as u8;
}
}
true
}
fn cluster_histograms_inner(
histograms: &mut Vec<Histogram>,
context_map: &mut Vec<u8>,
refined: bool,
isolate_single_symbol: bool,
max_clusters: usize,
huffman_pool: &mut Vec<HuffmanNode>,
pool: Option<&ThreadPool>,
) {
if histograms.len() <= 1 {
context_map.clear();
context_map.resize(histograms.len(), 0);
return;
}
const UNMAPPED: u8 = u8::MAX;
let max_histograms = CLUSTERS_LIMIT.min(max_clusters).min(histograms.len());
let unassigned = max_histograms as u8;
let inp = core::mem::take(histograms);
let n = inp.len();
let mut symbols: Vec<u8> = vec![unassigned; n];
let mut in_costs = vec![0.0f32; n];
let mut dists = vec![f32::MAX; n];
let mut largest_idx = 0usize;
let mut largest_count = 0u32;
for (i, (((hist, symbol), dist), cost)) in inp
.iter()
.zip(symbols.iter_mut())
.zip(dists.iter_mut())
.zip(in_costs.iter_mut())
.enumerate()
{
let total_count = hist.total_count;
if total_count == 0 {
*symbol = 0;
*dist = 0.0;
continue;
}
*cost = histogram_bit_cost(hist);
if total_count > largest_count {
largest_count = total_count;
largest_idx = i;
}
}
if largest_count == 0 {
*histograms = vec![Histogram::new()];
context_map.clear();
context_map.resize(n, 0);
return;
}
let mut out: Vec<Histogram> = Vec::with_capacity(max_histograms);
let mut out_costs: Vec<f32> = Vec::with_capacity(max_histograms);
let mut scratch = [0u32; ALPHABET_SIZE];
if isolate_single_symbol {
for (i, hist) in inp.iter().enumerate() {
if symbols[i] != unassigned || out.len() + 1 >= max_histograms {
continue;
}
let mut used = hist.counts.iter().enumerate().filter(|&(_, &c)| c != 0);
let (Some((sym, _)), None) = (used.next(), used.next()) else {
continue;
};
let j = out
.iter()
.position(|o| o.counts[sym] == o.total_count)
.unwrap_or_else(|| {
out.push(Histogram::new());
out_costs.push(0.0);
out.len() - 1
});
histogram_add(&mut out[j], hist);
symbols[i] = j as u8;
dists[i] = 0.0;
}
match (0..n)
.filter(|&i| symbols[i] == unassigned && inp[i].total_count != 0)
.max_by_key(|&i| inp[i].total_count)
{
Some(i) => largest_idx = i,
None => largest_idx = usize::MAX,
}
}
let mut workers = pool
.filter(|pool| n >= 1024 && pool.num_threads() > 1)
.map(|pool| (pool, CoderScratch::lossless(), vec![0.0f32; n]));
while largest_idx != usize::MAX && out.len() < max_histograms {
let candidate = largest_idx;
out.push(inp[candidate].clone());
out_costs.push(in_costs[candidate]);
let mut saving = if dists[candidate] == f32::MAX {
f32::INFINITY
} else {
dists[candidate]
};
dists[candidate] = 0.0;
let last_idx = out.len() - 1;
let last_hist = &out[last_idx];
let last_cost = out_costs[last_idx];
let mut next_largest_idx = candidate;
let mut next_largest_dist = 0.0f32;
if let Some((pool, caller_scratch, distances)) = &mut workers {
let mut chunks: Vec<_> = distances.chunks_mut(64).collect();
pool.steal_for_each_mut(caller_scratch, &mut chunks, |part, chunk, _| {
let mut scratch = [0u32; ALPHABET_SIZE];
for (offset, distance) in chunk.iter_mut().enumerate() {
let i = part * 64 + offset;
if dists[i] != 0.0 {
*distance = histogram_distance(
&inp[i],
last_hist,
in_costs[i],
last_cost,
&mut scratch,
);
}
}
});
}
for (i, ((hist, &in_cost), dist)) in inp
.iter()
.zip(in_costs.iter())
.zip(dists.iter_mut())
.enumerate()
{
if *dist == 0.0 {
continue;
}
let d = if let Some((_, _, distances)) = &workers {
distances[i]
} else {
histogram_distance(hist, last_hist, in_cost, last_cost, &mut scratch)
};
if d < *dist {
if *dist != f32::MAX {
saving += *dist - d;
}
*dist = d;
}
if *dist > next_largest_dist {
next_largest_dist = *dist;
next_largest_idx = i;
}
}
if out.len() > 1 && saving < MIN_DISTANCE_FOR_DISTINCT {
out.pop();
out_costs.pop();
break;
}
symbols[candidate] = (out.len() - 1) as u8;
largest_idx = next_largest_idx;
if next_largest_dist == 0.0 {
break;
}
}
if !refined {
if !assign_prefix_histograms_parallel(
&inp,
&in_costs,
&mut out,
&mut out_costs,
&mut symbols,
pool,
) {
for ((hist, &in_cost), symbol) in
inp.iter().zip(in_costs.iter()).zip(symbols.iter_mut())
{
if *symbol != unassigned {
continue;
}
let mut best = 0usize;
let mut best_dist =
histogram_distance(hist, &out[0], in_cost, out_costs[0], &mut scratch);
for (j, (candidate, &candidate_cost)) in
out.iter().zip(out_costs.iter()).enumerate().skip(1)
{
let d =
histogram_distance(hist, candidate, in_cost, candidate_cost, &mut scratch);
if d < best_dist {
best = j;
best_dist = d;
}
}
histogram_add(&mut out[best], hist);
out_costs[best] = histogram_bit_cost(&out[best]);
*symbol = best as u8;
}
}
} else {
for ((hist, &in_cost), symbol) in inp.iter().zip(in_costs.iter()).zip(symbols.iter_mut()) {
if *symbol != unassigned {
continue;
}
let mut best = 0usize;
let mut best_dist =
histogram_distance(hist, &out[0], in_cost, out_costs[0], &mut scratch);
for (j, (candidate, &candidate_cost)) in
out.iter().zip(out_costs.iter()).enumerate().skip(1)
{
let d = histogram_distance(hist, candidate, in_cost, candidate_cost, &mut scratch);
if d < best_dist {
best = j;
best_dist = d;
}
}
*symbol = best as u8;
}
out.fill(Histogram::new());
for (hist, &symbol) in inp.iter().zip(symbols.iter()) {
histogram_add(&mut out[symbol as usize], hist);
}
for (cost, hist) in out_costs.iter_mut().zip(out.iter()) {
*cost = histogram_bit_cost(hist);
}
for _ in 0..2 {
let mut changed = false;
for (hist, symbol) in inp.iter().zip(symbols.iter_mut()) {
if hist.total_count == 0 {
continue;
}
let old = *symbol as usize;
let mut old_without = out[old].clone();
histogram_sub(&mut old_without, hist);
let remove_delta = histogram_bit_cost(&old_without) - out_costs[old];
let mut best = old;
let mut best_delta = 0.0f32;
for candidate in 0..out.len() {
if candidate == old || out[candidate].total_count == 0 {
continue;
}
let add_delta = histogram_merge_increment(
hist,
&out[candidate],
out_costs[candidate],
&mut scratch,
);
let delta = remove_delta + add_delta;
if delta < best_delta - 0.01 {
best_delta = delta;
best = candidate;
}
}
if best != old {
histogram_sub(&mut out[old], hist);
histogram_add(&mut out[best], hist);
out_costs[old] = histogram_bit_cost(&out[old]);
out_costs[best] = histogram_bit_cost(&out[best]);
*symbol = best as u8;
changed = true;
}
}
if !changed {
break;
}
}
}
exact_merge_final_clusters(&mut out, &mut symbols, huffman_pool);
let mut compact = vec![UNMAPPED; out.len()];
let mut compact_out = Vec::with_capacity(out.len());
for (old, hist) in out.into_iter().enumerate() {
if hist.total_count != 0 {
compact[old] = compact_out.len() as u8;
compact_out.push(hist);
}
}
for symbol in &mut symbols {
*symbol = compact[*symbol as usize];
}
out = compact_out;
let mut remap = [UNMAPPED; CLUSTERS_LIMIT];
let mut tmp: Vec<Option<Histogram>> = out.into_iter().map(Some).collect();
let mut reordered: Vec<Histogram> = Vec::with_capacity(tmp.len());
let mut next_index = 0u8;
for &symbol in &symbols {
debug_assert_ne!(symbol, unassigned);
let old_index = symbol as usize;
debug_assert!(old_index < tmp.len());
let mapped = &mut remap[old_index];
if *mapped == UNMAPPED {
*mapped = next_index;
reordered.push(
tmp[old_index]
.take()
.expect("cluster must be reindexed once"),
);
next_index += 1;
}
}
*histograms = reordered;
context_map.clear();
context_map.reserve(symbols.len());
context_map.extend(symbols.iter().map(|&symbol| remap[symbol as usize]));
}
fn context_map_merge_saving(a: usize, b: usize) -> f64 {
if a == 0 || b == 0 {
return 0.0;
}
let (a, b) = (a as f64, b as f64);
let merged = a + b;
a * f_log2(merged / a) + b * f_log2(merged / b)
}
fn merge_final_ans_clusters(
clusters: &mut [Histogram],
cluster_costs: &mut [f64],
assignment: &mut [u8],
members: &mut [usize],
charge_context_map: bool,
mut population_cost: impl FnMut(&[u32; ALPHABET_SIZE]) -> f64,
) {
let n = clusters.len();
if n <= 1 {
return;
}
let mut active: Vec<bool> = clusters.iter().map(|c| c.total_count != 0).collect();
let mut deltas = vec![f64::INFINITY; n * (n - 1) / 2];
loop {
let mut best_pair = None;
let mut best_delta = -1e-6f64;
for a in 0..n {
if !active[a] {
continue;
}
for b in a + 1..n {
if !active[b] {
continue;
}
let delta = &mut deltas[b * (b - 1) / 2 + a];
if *delta == f64::INFINITY {
let mut merged = clusters[a].counts;
add_counts(&mut merged, &clusters[b].counts);
*delta = population_cost(&merged)
- cluster_costs[a]
- cluster_costs[b]
- if charge_context_map {
context_map_merge_saving(members[a], members[b])
} else {
0.0
};
}
if *delta < best_delta {
best_delta = *delta;
best_pair = Some((a, b));
}
}
}
let Some((a, b)) = best_pair else { break };
let bh = clusters[b].clone();
histogram_add(&mut clusters[a], &bh);
cluster_costs[a] = population_cost(&clusters[a].counts);
members[a] += members[b];
active[b] = false;
for m in assignment.iter_mut() {
if *m == b as u8 {
*m = a as u8;
}
}
for other in 0..n {
if other == a {
continue;
}
let (first, second) = if other < a { (other, a) } else { (a, other) };
deltas[second * (second - 1) / 2 + first] = f64::INFINITY;
}
}
}
pub(crate) fn cluster_histograms_ans(
histograms: &mut [Histogram],
context_map: &mut [u8],
pool: Option<&crate::thread_pool::ThreadPool>,
charge_context_map: bool,
max_clusters: usize,
refinement_passes: usize,
) -> usize {
assert!((1..=CLUSTERS_LIMIT).contains(&max_clusters));
use super::ans::{AnsCostScratch, fast_ans_population_cost_scratch};
use crate::coder_scratch::CoderScratch;
use crate::thread_pool::ThreadPool;
let n = histograms.len();
assert!(context_map.len() >= n);
if n <= 1 {
context_map[..n].fill(0);
return n;
}
fn cost_of(h: &Histogram, s: &mut AnsCostScratch) -> f64 {
if h.total_count == 0 {
0.0
} else {
fast_ans_population_cost_scratch(&h.counts, 1, s)
}
}
fn merge_cost(a: &Histogram, b: &Histogram, s: &mut AnsCostScratch) -> f64 {
let mut merged = a.counts;
add_counts(&mut merged, &b.counts);
fast_ans_population_cost_scratch(&merged, 1, s)
}
fn par_map<R: Send>(
n: usize,
workers: &mut Option<(&ThreadPool, CoderScratch)>,
f: impl Fn(usize, &mut AnsCostScratch) -> R + Sync,
) -> Vec<R> {
let Some((pool, caller_scratch)) = workers else {
let mut s = AnsCostScratch::new();
return (0..n).map(|i| f(i, &mut s)).collect();
};
let threads = pool.num_threads().min(n);
let chunk = n.div_ceil(threads * 4);
let parts = pool.steal_map(caller_scratch, n.div_ceil(chunk), |part, _| {
let begin = part * chunk;
let end = (begin + chunk).min(n);
let mut s = AnsCostScratch::new();
(begin..end).map(|i| f(i, &mut s)).collect::<Vec<R>>()
});
parts.into_iter().flatten().collect()
}
let mut workers = pool
.filter(|pool| n >= 64 && pool.num_threads() > 1)
.map(|pool| (pool, CoderScratch::lossless()));
let mut scratch = AnsCostScratch::new();
let in_costs: Vec<f64> = par_map(n, &mut workers, |i, s| cost_of(&histograms[i], s));
let mut clusters: Vec<Histogram> = Vec::new();
let mut cluster_costs: Vec<f64> = Vec::new();
let mut dists = vec![f64::MAX; n];
let mut seed = 0usize;
let mut seed_count = 0u32;
for (i, h) in histograms.iter().enumerate() {
if h.total_count > seed_count {
seed_count = h.total_count;
seed = i;
}
}
if seed_count == 0 {
histograms[0] = Histogram::new();
context_map[..n].fill(0);
return 1;
}
let mut merge = vec![f64::NAN; n * max_clusters];
while clusters.len() < max_clusters {
clusters.push(histograms[seed].clone());
cluster_costs.push(in_costs[seed]);
dists[seed] = 0.0;
let column = clusters.len() - 1;
let last = &clusters[column];
let last_cost = cluster_costs[column];
let updated: Vec<(f64, f64)> = {
let dists = &dists;
par_map(n, &mut workers, |i, s| {
let h = &histograms[i];
if h.total_count == 0 || dists[i] == 0.0 {
return (0.0, f64::NAN);
}
let merged = merge_cost(h, last, s);
let d = merged - in_costs[i] - last_cost;
(dists[i].min(d), merged)
})
};
for (i, (d, merged)) in updated.into_iter().enumerate() {
dists[i] = d;
merge[i * max_clusters + column] = merged;
}
let mut next_seed = seed;
let mut next_dist = 0.0f64;
for (i, &d) in dists.iter().enumerate() {
if d > next_dist {
next_dist = d;
next_seed = i;
}
}
if next_dist <= 0.0 {
break;
}
seed = next_seed;
}
let num_seeds = clusters.len();
let mut assignment: Vec<u8> = {
let clusters = &clusters;
let cluster_costs = &cluster_costs;
let merge = &merge;
par_map(n, &mut workers, |i, s| {
let h = &histograms[i];
if h.total_count == 0 {
return 0u8;
}
let row = &merge[i * max_clusters..][..num_seeds];
let mut best = 0usize;
let mut best_d = f64::MAX;
for (c, &cached) in row.iter().enumerate() {
let merged = if cached.is_nan() {
merge_cost(h, &clusters[c], s)
} else {
cached
};
let d = merged - cluster_costs[c];
if d < best_d {
best_d = d;
best = c;
}
}
best as u8
})
};
let rebuild = |clusters: &mut Vec<Histogram>,
cluster_costs: &mut Vec<f64>,
assignment: &[u8],
s: &mut AnsCostScratch| {
for c in clusters.iter_mut() {
*c = Histogram::new();
}
for (h, &a) in histograms.iter().zip(assignment) {
histogram_add(&mut clusters[a as usize], h);
}
for (c, cost) in clusters.iter().zip(cluster_costs.iter_mut()) {
*cost = cost_of(c, s);
}
};
rebuild(&mut clusters, &mut cluster_costs, &assignment, &mut scratch);
let mut dirty = vec![true; num_seeds];
let mut without_costs = vec![f64::NAN; n];
for _ in 0..refinement_passes {
let dirty_clusters: Vec<usize> = (0..num_seeds).filter(|&c| dirty[c]).collect();
let dirty_slot: Vec<usize> = {
let mut slot = vec![usize::MAX; num_seeds];
for (k, &c) in dirty_clusters.iter().enumerate() {
slot[c] = k;
}
slot
};
let proposals: Vec<(Option<u8>, Option<f64>, Vec<f64>)> = {
let clusters = &clusters;
let cluster_costs = &cluster_costs;
let assignment = &assignment;
let merge = &merge;
let without_costs = &without_costs;
let dirty = &dirty;
let dirty_clusters = &dirty_clusters;
let dirty_slot = &dirty_slot;
par_map(n, &mut workers, |i, s| {
let h = &histograms[i];
if h.total_count == 0 {
return (None, None, Vec::new());
}
let old = assignment[i] as usize;
let fresh: Vec<f64> = dirty_clusters
.iter()
.map(|&c| {
if c == old {
f64::NAN
} else {
merge_cost(h, &clusters[c], s)
}
})
.collect();
let without = if dirty[old] || without_costs[i].is_nan() {
let mut without = clusters[old].clone();
histogram_sub(&mut without, h);
Some(cost_of(&without, s))
} else {
None
};
let remove_delta = without.unwrap_or(without_costs[i]) - cluster_costs[old];
let row = &merge[i * max_clusters..][..num_seeds];
let mut best = old;
let mut best_delta = 0.0f64;
for c in 0..num_seeds {
if c == old {
continue;
}
let merged = if dirty[c] {
fresh[dirty_slot[c]]
} else {
row[c]
};
let delta = remove_delta + merged - cluster_costs[c];
if delta < best_delta - 0.01 {
best_delta = delta;
best = c;
}
}
((best != old).then_some(best as u8), without, fresh)
})
};
for (i, (_, without, fresh)) in proposals.iter().enumerate() {
if let Some(without) = without {
without_costs[i] = *without;
}
for (&c, &merged) in dirty_clusters.iter().zip(fresh) {
merge[i * max_clusters + c] = merged;
}
}
dirty.fill(false);
let mut changed = false;
for (i, (proposal, _, _)) in proposals.iter().enumerate() {
let Some(best) = *proposal else { continue };
let best = best as usize;
let old = assignment[i] as usize;
let h = &histograms[i];
let mut without = clusters[old].clone();
histogram_sub(&mut without, h);
let without_cost = cost_of(&without, &mut scratch);
let with_cost = merge_cost(h, &clusters[best], &mut scratch);
let remove_delta = without_cost - cluster_costs[old];
let add_delta = with_cost - cluster_costs[best];
if remove_delta + add_delta < -0.01 {
clusters[old] = without;
histogram_add(&mut clusters[best], h);
cluster_costs[old] = without_cost;
cluster_costs[best] = with_cost;
assignment[i] = best as u8;
dirty[old] = true;
dirty[best] = true;
changed = true;
}
}
if !changed {
break;
}
}
let mut members = vec![0usize; num_seeds];
for (h, &a) in histograms.iter().zip(&assignment) {
if h.total_count != 0 {
members[a as usize] += 1;
}
}
merge_final_ans_clusters(
&mut clusters,
&mut cluster_costs,
&mut assignment,
&mut members,
charge_context_map,
|counts| fast_ans_population_cost_scratch(counts, 1, &mut scratch),
);
let mut remap = vec![u8::MAX; num_seeds];
let mut ordered: Vec<Histogram> = Vec::new();
for (i, &a) in assignment.iter().enumerate() {
let a = a as usize;
if remap[a] == u8::MAX {
remap[a] = ordered.len() as u8;
ordered.push(clusters[a].clone());
}
context_map[i] = remap[a];
}
let num = ordered.len();
histograms[..num].clone_from_slice(&ordered);
num
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn single_symbol_context_does_not_derail_seeding() {
let mut histograms = Vec::new();
let mut zeros = Histogram::new();
for _ in 0..30_000 {
zeros.add(0);
}
histograms.push(zeros);
let mut tiny = Histogram::new();
for _ in 0..3 {
tiny.add(40);
}
histograms.push(tiny);
for family in 0..4u32 {
let mut h = Histogram::new();
for i in 0..2000 {
h.add(if i % 2 == 0 {
0
} else {
1 + family * 6 + (i / 2) % 3
});
}
histograms.push(h);
}
let mut map = Vec::new();
cluster_histograms_with_pool(
&mut histograms,
&mut map,
&mut Vec::new(),
true,
CLUSTERS_LIMIT,
None,
);
assert_ne!(map[0], map[1], "the single-symbol contexts merged");
let distinct: std::collections::BTreeSet<u8> = map[2..].iter().copied().collect();
assert_eq!(distinct.len(), 4, "distinct contexts merged: {map:?}");
assert!(!distinct.contains(&map[0]) && !distinct.contains(&map[1]));
}
fn reference_ans_final_merge(
clusters: &mut [Histogram],
cluster_costs: &mut [f64],
assignment: &mut [u8],
members: &mut [usize],
charge_context_map: bool,
mut population_cost: impl FnMut(&[u32; ALPHABET_SIZE]) -> f64,
) {
let mut active: Vec<bool> = clusters.iter().map(|c| c.total_count != 0).collect();
loop {
let mut best_pair = None;
let mut best_delta = -1e-6f64;
for a in 0..clusters.len() {
if !active[a] {
continue;
}
for b in a + 1..clusters.len() {
if !active[b] {
continue;
}
let delta = {
let mut merged = clusters[a].counts;
add_counts(&mut merged, &clusters[b].counts);
population_cost(&merged)
} - cluster_costs[a]
- cluster_costs[b]
- if charge_context_map {
context_map_merge_saving(members[a], members[b])
} else {
0.0
};
if delta < best_delta {
best_delta = delta;
best_pair = Some((a, b));
}
}
}
let Some((a, b)) = best_pair else { break };
let bh = clusters[b].clone();
histogram_add(&mut clusters[a], &bh);
cluster_costs[a] = population_cost(&clusters[a].counts);
members[a] += members[b];
active[b] = false;
for m in assignment.iter_mut() {
if *m == b as u8 {
*m = a as u8;
}
}
}
}
#[test]
fn cached_ans_merges_match_recomputing_every_pair() {
use super::super::ans::{AnsCostScratch, fast_ans_population_cost_scratch};
for n in [0, 1, 2, 7, 32, 64, CLUSTERS_LIMIT] {
for family in 0..4 {
let base: Vec<_> = (0..n)
.map(|i| match family {
0 => histogram(&[(0, 100), (1, 50), (2, 25)]),
1 => histogram(&[(i % ALPHABET_SIZE, 100)]),
2 if i % 7 == 0 => Histogram::new(),
_ => {
let mut h = Histogram::new();
for j in 0..12 {
let symbol = (i % 9 * 11 + j * 7) % ALPHABET_SIZE;
let count = ((i * 17 + j * 13) % 31 + 1) as u32;
h.counts[symbol] += count;
h.total_count += count;
}
h
}
})
.collect();
let mut scratch = AnsCostScratch::new();
let costs: Vec<_> = base
.iter()
.map(|h| fast_ans_population_cost_scratch(&h.counts, 1, &mut scratch))
.collect();
let members: Vec<_> = base
.iter()
.enumerate()
.map(|(i, h)| if h.total_count == 0 { 0 } else { i % 5 + 1 })
.collect();
let assignment: Vec<_> = members
.iter()
.enumerate()
.flat_map(|(i, &count)| std::iter::repeat_n(i as u8, count))
.collect();
for charge_context_map in [false, true] {
let mut expected = base.clone();
let mut expected_costs = costs.clone();
let mut expected_assignment = assignment.clone();
let mut expected_members = members.clone();
let mut expected_calls = 0usize;
reference_ans_final_merge(
&mut expected,
&mut expected_costs,
&mut expected_assignment,
&mut expected_members,
charge_context_map,
|counts| {
expected_calls += 1;
fast_ans_population_cost_scratch(counts, 1, &mut scratch)
},
);
let mut actual = base.clone();
let mut actual_costs = costs.clone();
let mut actual_assignment = assignment.clone();
let mut actual_members = members.clone();
let mut actual_calls = 0usize;
merge_final_ans_clusters(
&mut actual,
&mut actual_costs,
&mut actual_assignment,
&mut actual_members,
charge_context_map,
|counts| {
actual_calls += 1;
fast_ans_population_cost_scratch(counts, 1, &mut scratch)
},
);
assert_eq!(actual_assignment, expected_assignment);
assert_eq!(actual_members, expected_members);
for (a, b) in actual.iter().zip(&expected) {
assert_eq!(a.counts, b.counts);
assert_eq!(a.total_count, b.total_count);
}
for (a, b) in actual_costs.iter().zip(&expected_costs) {
assert_eq!(a.to_bits(), b.to_bits());
}
assert!(actual_calls <= expected_calls);
if n == 64 && family == 0 {
assert!(actual_calls * 8 < expected_calls);
}
}
}
}
}
#[test]
fn ans_clustering_is_independent_of_thread_count() {
let n = 300usize;
let mut state = 0x9E37_79B9u32;
let mut next = || {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
state
};
let base: Vec<Histogram> = (0..n)
.map(|i| {
let mut h = Histogram::new();
let total = 50 + next() % 5000;
let p_one = (i as u32 * 7 + next() % 40) % 1000;
let ones = (total as u64 * p_one as u64 / 1000) as u32;
for _ in 0..(total - ones) {
h.add(0);
}
for _ in 0..ones {
h.add(1 + next() % 3);
}
h
})
.collect();
for len in [0, 1, 63, 64, 65, n] {
let run = |threads: usize| {
let mut histograms = base[..len].to_vec();
let mut map = vec![0u8; len];
let pool = crate::thread_pool::ThreadPool::new_lossless(threads);
let num = cluster_histograms_ans(
&mut histograms,
&mut map,
Some(&pool),
true,
CLUSTERS_LIMIT,
6,
);
(num, map, histograms[..num].to_vec())
};
let (num1, map1, hist1) = run(1);
if len == n {
assert!(num1 > 2, "expected several clusters, got {num1}");
}
for threads in [0, 2, 3, 8] {
let (num, map, hist) = run(threads);
assert_eq!(
num, num1,
"cluster count differs: len={len}, threads={threads}"
);
assert_eq!(
map, map1,
"context map differs: len={len}, threads={threads}"
);
assert!(
hist.iter().zip(&hist1).all(|(a, b)| a.counts == b.counts),
"cluster histograms differ: len={len}, threads={threads}"
);
}
}
}
fn histogram(entries: &[(usize, u32)]) -> Histogram {
let mut histogram = Histogram::new();
for &(symbol, count) in entries {
histogram.counts[symbol] = count;
histogram.total_count += count;
}
histogram
}
#[allow(dead_code)]
fn assert_simd_counts_bit_cost_matches_scalar(
mut simd_cost: impl FnMut(&[u32; ALPHABET_SIZE], u32) -> f32,
) {
let mut wide_counts = [0u32; ALPHABET_SIZE];
wide_counts[0] = 0x8000_0000;
wide_counts[1] = 0x4000_0000;
wide_counts[2] = 1;
let wide_total = 0xc000_0001;
let scalar = counts_bit_cost_scalar(&wide_counts, wide_total);
let simd = simd_cost(&wide_counts, wide_total);
let tolerance = 0.05f32.max(scalar.abs() * 2e-6);
assert!(
(simd - scalar).abs() <= tolerance,
"unsigned conversion: simd={simd} scalar={scalar}"
);
let mut state = 0x1234_5678u32;
for case in 0..256 {
let mut counts = [0u32; ALPHABET_SIZE];
for count in &mut counts {
state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
*count = if state & 7 == 0 {
0
} else {
(state >> (case % 17)) & 0x3fff
};
}
let total: u32 = counts.iter().sum();
let scalar = counts_bit_cost_scalar(&counts, total);
let simd = simd_cost(&counts, total);
let tolerance = 0.05f32.max(scalar.abs() * 2e-6);
assert!(
(simd - scalar).abs() <= tolerance,
"case {case}: simd={simd} scalar={scalar}"
);
}
}
#[cfg(all(target_arch = "x86_64", feature = "avx"))]
#[test]
fn avx2_counts_bit_cost_matches_scalar() {
if !std::is_x86_feature_detected!("avx2") || !std::is_x86_feature_detected!("fma") {
return;
}
assert_simd_counts_bit_cost_matches_scalar(|counts, total| unsafe {
crate::avx::counts_bit_cost_avx2(counts, total)
});
}
#[cfg(all(any(target_arch = "x86_64", target_arch = "x86"), feature = "sse"))]
#[test]
fn sse41_counts_bit_cost_matches_scalar() {
if !std::is_x86_feature_detected!("sse4.1") {
return;
}
assert_simd_counts_bit_cost_matches_scalar(|counts, total| unsafe {
crate::sse::counts_bit_cost_sse41(counts, total)
});
}
#[cfg(all(target_arch = "aarch64", feature = "neon"))]
#[test]
fn neon_counts_bit_cost_matches_scalar() {
assert_simd_counts_bit_cost_matches_scalar(|counts, total| unsafe {
crate::neon::counts_bit_cost_neon(counts, total)
});
}
#[cfg(all(target_arch = "wasm32", feature = "wasm", target_feature = "simd128"))]
#[test]
fn wasm_counts_bit_cost_matches_scalar() {
assert_simd_counts_bit_cost_matches_scalar(|counts, total| {
crate::wasm::counts_bit_cost_wasm(counts, total)
});
}
fn exact_model_cost(histograms: &[Histogram], huffman_pool: &mut Vec<HuffmanNode>) -> f32 {
histograms
.iter()
.filter(|histogram| histogram.total_count != 0)
.map(|histogram| {
exact_counts_bit_cost(&histogram.counts, histogram.total_count, huffman_pool)
+ MIN_DISTANCE_FOR_DISTINCT
})
.sum()
}
fn inputs(n: usize) -> Vec<Histogram> {
(0..n)
.map(|context| {
let mut histogram = Histogram::new();
if context % 11 != 0 {
for symbol in 0..ALPHABET_SIZE {
let count = ((context * 17 + symbol * 13 + context * symbol) % 19) as u32;
histogram.counts[symbol] = count;
histogram.total_count += count;
}
}
histogram
})
.collect()
}
fn assert_fixed_matches_allocating(n: usize, refined: bool) {
let mut expected = inputs(n);
let mut expected_map = Vec::new();
let mut expected_pool = Vec::with_capacity(1024);
cluster_histograms_inner(
&mut expected,
&mut expected_map,
refined,
false,
CLUSTERS_LIMIT,
&mut expected_pool,
None,
);
let mut actual = inputs(n);
let mut actual_map = vec![0; n];
let mut actual_pool = Vec::with_capacity(1024);
let mut scratch = FixedClusterScratch::<221>::default();
let actual_len = cluster_histograms_fixed(
&mut actual,
&mut actual_map,
refined,
CLUSTERS_LIMIT,
&mut scratch,
&mut actual_pool,
);
assert_eq!(actual_len, expected.len());
assert_eq!(actual_map, expected_map);
for (actual, expected) in actual[..actual_len].iter().zip(expected.iter()) {
assert_eq!(actual.total_count, expected.total_count);
assert_eq!(actual.counts, expected.counts);
}
}
#[test]
fn fixed_clustering_matches_allocating_path() {
for n in [0, 1, 2, 7, 64, 65, 128, 221] {
assert_fixed_matches_allocating(n, false);
assert_fixed_matches_allocating(n, true);
}
}
#[test]
fn speculative_prefix_assignment_matches_ordered_updates() {
for (clusters, n) in [(64, 1287), (96, 2115), (128, 4129)] {
let inp: Vec<_> = (0..n)
.map(|i| {
let mut h = Histogram::new();
if i >= clusters && i % 37 == 0 {
return h;
}
let family = i % clusters / 2;
let variation = if i < clusters { family } else { i };
for j in 0..12 {
let symbol = (family * 11 + j * 7) % ALPHABET_SIZE;
let count = ((variation * 17 + j * 13) % 31 + 1) as u32;
h.counts[symbol] += count;
h.total_count += count;
}
h
})
.collect();
let in_costs: Vec<_> = inp.iter().map(histogram_bit_cost).collect();
let initial_symbols: Vec<_> = inp
.iter()
.enumerate()
.map(|(i, h)| {
if i < clusters {
i as u8
} else if h.total_count == 0 {
0
} else {
CLUSTERS_LIMIT as u8
}
})
.collect();
let mut expected = inp[..clusters].to_vec();
let mut expected_costs = in_costs[..clusters].to_vec();
let mut expected_symbols = initial_symbols.clone();
let mut scratch = [0u32; ALPHABET_SIZE];
for ((hist, &in_cost), symbol) in inp.iter().zip(&in_costs).zip(&mut expected_symbols) {
if *symbol != CLUSTERS_LIMIT as u8 {
continue;
}
let mut best = 0;
let mut best_dist = histogram_distance(
hist,
&expected[0],
in_cost,
expected_costs[0],
&mut scratch,
);
for j in 1..clusters {
let distance = histogram_distance(
hist,
&expected[j],
in_cost,
expected_costs[j],
&mut scratch,
);
if distance < best_dist {
best = j;
best_dist = distance;
}
}
histogram_add(&mut expected[best], hist);
expected_costs[best] = histogram_bit_cost(&expected[best]);
*symbol = best as u8;
}
for threads in [1, 2, 4, 12] {
let pool = ThreadPool::new_lossless(threads);
let mut actual = inp[..clusters].to_vec();
let mut costs = in_costs[..clusters].to_vec();
let mut symbols = initial_symbols.clone();
let assigned = assign_prefix_histograms_parallel(
&inp,
&in_costs,
&mut actual,
&mut costs,
&mut symbols,
Some(&pool),
);
if threads == 1 {
assert!(!assigned);
assert_eq!(symbols, initial_symbols);
continue;
}
assert!(assigned);
assert_eq!(symbols, expected_symbols);
for j in 0..clusters {
assert_eq!(actual[j].counts, expected[j].counts);
assert_eq!(actual[j].total_count, expected[j].total_count);
assert_eq!(costs[j].to_bits(), expected_costs[j].to_bits());
}
}
}
}
#[test]
fn pooled_prefix_clustering_preserves_serial_decisions() {
for n in [1023, 1024, 1089] {
let input: Vec<_> = (0..n)
.map(|i| {
let mut h = Histogram::new();
if i % 11 != 0 {
for j in 0..8 {
let symbol = (i % 17 + j * 13) % ALPHABET_SIZE;
let count = (i % 7 + j * 3 + 1) as u32;
h.counts[symbol] += count;
h.total_count += count;
}
}
h
})
.collect();
let mut expected = input.clone();
let mut expected_map = Vec::new();
cluster_histograms(&mut expected, &mut expected_map, &mut Vec::new());
for threads in [1, 2, 4] {
let pool = ThreadPool::new_lossless(threads);
let mut actual = input.clone();
let mut actual_map = Vec::new();
cluster_histograms_with_pool(
&mut actual,
&mut actual_map,
&mut Vec::new(),
false,
CLUSTERS_LIMIT,
Some(&pool),
);
assert_eq!(actual_map, expected_map, "n={n}, threads={threads}");
assert_eq!(actual.len(), expected.len());
for (actual, expected) in actual.iter().zip(&expected) {
assert_eq!(actual.counts, expected.counts);
assert_eq!(actual.total_count, expected.total_count);
}
}
}
}
#[test]
fn exact_final_pass_accepts_only_cost_reducing_merge() {
let mut clusters = [
histogram(&[(0, 100), (1, 50), (2, 25)]),
histogram(&[(0, 90), (1, 45), (2, 20)]),
];
let mut symbols = [0, 1];
let mut huffman_pool = Vec::new();
let before = exact_model_cost(&clusters, &mut huffman_pool);
exact_merge_final_clusters(&mut clusters, &mut symbols, &mut huffman_pool);
let after = exact_model_cost(&clusters, &mut huffman_pool);
assert!(after < before);
assert_eq!(symbols, [0, 0]);
assert_eq!(clusters[1].total_count, 0);
}
#[test]
fn exact_final_pass_rejects_cost_increasing_merge() {
let mut clusters = [histogram(&[(0, 100)]), histogram(&[(1, 100)])];
let mut symbols = [0, 1];
let mut huffman_pool = Vec::new();
let before = exact_model_cost(&clusters, &mut huffman_pool);
exact_merge_final_clusters(&mut clusters, &mut symbols, &mut huffman_pool);
let after = exact_model_cost(&clusters, &mut huffman_pool);
assert_eq!(after, before);
assert_eq!(symbols, [0, 1]);
assert_eq!(clusters[0].total_count, 100);
assert_eq!(clusters[1].total_count, 100);
}
}