facett-grid/tests/perf.rs
//! **Virtualization perf** — prove building the visible window is **O(visible)**,
//! not O(total). We compute the row window over 10k, 1M, and 10M rows and assert
//! (a) the visible count is identical (bounded by the viewport, not the dataset)
//! and (b) the time to compute it doesn't scale with the row count. This measures
//! window calculation, not full frame rate. See `examples/grid_bench.rs` for
//! layout/paint/tessellation, scrolling, sorting and incremental filtering.
//!
//! The sort budget tests at the bottom hold a 100k-row header-click sort (Float64,
//! Int64, UInt64, Utf8) to the pre-PR #2 sort, measured in the same run.
use std::hint::black_box;
use std::sync::Arc;
use std::time::Instant;
use arrow_array::{Float64Array, Int64Array, RecordBatch, StringArray, UInt64Array};
use arrow_schema::{DataType, Field, Schema};
use facett_grid::Grid;
fn grid(n: usize) -> Grid {
let batch = RecordBatch::try_new(
Arc::new(Schema::new(vec![Field::new("id", DataType::Int64, false)])),
vec![Arc::new(Int64Array::from((0..n as i64).collect::<Vec<_>>()))],
)
.unwrap();
Grid::from_record_batch("perf", &batch)
}
#[test]
fn visible_window_is_constant_across_dataset_size() {
let viewport_h = 600.0;
let scroll_y = 5_000.0;
let mut counts = Vec::new();
for &n in &[10_000usize, 1_000_000, 10_000_000] {
let mut g = grid(n);
let win = g.row_window_at(scroll_y, viewport_h);
counts.push(win.count);
}
// The visible count is the same regardless of 10k vs 10M total rows.
assert!(counts.windows(2).all(|w| w[0] == w[1]), "window size must not depend on total rows: {counts:?}");
assert!(counts[0] < 64, "a 600px viewport shows ~25 rows, not the whole dataset");
}
#[test]
fn building_the_window_is_o_visible_not_o_total() {
// Build the window many times for a 10M-row grid and a 10k-row grid; the
// per-call time must be comparable (both touch only the visible slice).
let iters = 100_000;
let mut small = grid(10_000);
let t0 = Instant::now();
let mut sink = 0usize;
for k in 0..iters {
let win = std::hint::black_box(small.row_window_at((k % 500) as f32 * 10.0, 600.0));
sink = sink.wrapping_add(win.count);
}
let small_ns = t0.elapsed().as_nanos() as f64 / iters as f64;
let mut big = grid(10_000_000);
let t1 = Instant::now();
for k in 0..iters {
let win = std::hint::black_box(big.row_window_at((k % 500) as f32 * 10.0, 600.0));
sink = sink.wrapping_add(win.count);
}
let big_ns = t1.elapsed().as_nanos() as f64 / iters as f64;
eprintln!("row_window: 10k={small_ns:.1}ns 10M={big_ns:.1}ns (sink={sink})");
// O(visible) means the 1000×-larger dataset is not meaningfully slower. Allow
// generous noise headroom (cache effects, CI jitter): big must be < 4× small
// and well under a microsecond either way.
assert!(big_ns < small_ns * 4.0 + 200.0, "window build scaled with total rows: 10k={small_ns:.1}ns 10M={big_ns:.1}ns");
assert!(big_ns < 5_000.0, "even at 10M rows, building the visible window is sub-5µs");
}
#[test]
fn ingest_of_a_million_rows_is_quick() {
// A sanity bound on Arrow ingest (one-time materialisation): a 1M-row int
// batch should build in well under a second on any modern box.
let t = Instant::now();
let g = grid(1_000_000);
let dt = t.elapsed();
assert_eq!(g.data().nrows(), 1_000_000);
eprintln!("ingest 1M rows: {dt:?}");
assert!(dt.as_secs() < 5, "1M-row ingest took too long: {dt:?}");
}
#[test]
fn typed_column_copy_is_zero_copy_no_materialisation() {
use std::sync::Arc;
use facett_grid::Grid as G;
// Build directly from a shared 1M-row batch (no buffer copy at ingest).
let batch = Arc::new(
RecordBatch::try_new(
Arc::new(Schema::new(vec![Field::new("id", DataType::Int64, false)])),
vec![Arc::new(Int64Array::from((0..1_000_000i64).collect::<Vec<_>>()))],
)
.unwrap(),
);
let src_ptr = Arc::as_ptr(batch.column(0)) as *const ();
let big = G::from_record_batch_arc("z", batch);
let t = Instant::now();
let cols = big.copy_columns().expect("typed columns");
let dt = t.elapsed();
assert_eq!(cols.len(), 1);
assert_eq!(cols[0].array.len(), 1_000_000);
// The handed-out array IS the source buffer (Arc), never a re-materialised Vec.
assert_eq!(Arc::as_ptr(&cols[0].array) as *const (), src_ptr, "column copy shares the source buffer");
// And it is therefore sub-millisecond regardless of row count (no per-cell work).
eprintln!("copy_columns(1M rows): {dt:?}");
assert!(dt.as_micros() < 5_000, "typed column copy must be zero-copy (sub-5ms), got {dt:?}");
}
// ── Sort budget: no slower than the pre-PR #2 sort, measured in the same run ──
//
// PR #2 (`a294d344`) moved the grid onto shared Arrow buffers. Its sort then read
// every comparison through `Column::value` (edit-overlay lookup, null bitmap,
// variant match), twice per comparison: `grid_bench 100000` measured the Float64
// sort at 9.36 ms before and 32.87 ms after on loki (`.nornir/facett-benchmarks.md`).
//
// The baseline is the pre-PR sort itself (`pre_pr`, below), run in the same
// process and interleaved with the grid rounds so box load cancels out of the
// ratio, over the column the pre-PR grid materialised at ingest (not timed). The
// grid side is the public header click on a fresh grid, which is what
// `grid_bench` times as `sort_ms`. Best of `ROUNDS` on both sides.
const SORT_ROWS: usize = 100_000;
const ROUNDS: usize = 7;
/// The owner's budget: the sort may cost at most ~1.1x the pre-PR sort.
const SORT_BUDGET: f64 = 1.1;
/// The pre-PR #2 sort, copied from `facett-grid/src/{data,sort}.rs` at `2478f9d1`
/// (only what one sort reads): the column as owned vectors, a stable `sort_by`
/// over row indices with one `cmp_cell` per key per comparison, nulls last, the
/// source row as the final tie-break.
mod pre_pr {
use std::cmp::Ordering;
#[allow(dead_code)] // every variant, so `cmp_cell` matches as it did
pub enum Column {
Int { v: Vec<i64>, nulls: Vec<bool> },
Float { v: Vec<f64>, nulls: Vec<bool> },
Text { v: Vec<String>, nulls: Vec<bool> },
Bool { v: Vec<bool>, nulls: Vec<bool> },
Date { v: Vec<String>, nulls: Vec<bool> },
}
impl Column {
fn is_null(&self, i: usize) -> bool {
let nulls = match self {
Column::Int { nulls, .. }
| Column::Float { nulls, .. }
| Column::Text { nulls, .. }
| Column::Bool { nulls, .. }
| Column::Date { nulls, .. } => nulls,
};
nulls.get(i).copied().unwrap_or(false)
}
}
fn cmp_cell(col: &Column, a: usize, b: usize) -> Ordering {
let (an, bn) = (col.is_null(a), col.is_null(b));
match (an, bn) {
(true, true) => Ordering::Equal,
(true, false) => Ordering::Greater, // null after
(false, true) => Ordering::Less,
(false, false) => match col {
Column::Int { v, .. } => v[a].cmp(&v[b]),
Column::Float { v, .. } => v[a].partial_cmp(&v[b]).unwrap_or(Ordering::Equal),
Column::Bool { v, .. } => v[a].cmp(&v[b]),
Column::Text { v, .. } | Column::Date { v, .. } => v[a].cmp(&v[b]),
},
}
}
/// `keys`: (column, descending).
pub fn sorted_order(columns: &[Column], keys: &[(usize, bool)]) -> Vec<usize> {
let n = columns.first().map_or(0, |c| match c {
Column::Int { v, .. } => v.len(),
Column::Float { v, .. } => v.len(),
Column::Text { v, .. } | Column::Date { v, .. } => v.len(),
Column::Bool { v, .. } => v.len(),
});
let mut order: Vec<usize> = (0..n).collect();
if keys.is_empty() {
return order;
}
order.sort_by(|&a, &b| {
for &(col, desc) in keys {
let Some(col) = columns.get(col) else { continue };
let mut o = cmp_cell(col, a, b);
if desc {
o = o.reverse();
}
if o != Ordering::Equal {
return o;
}
}
// Final tiebreak on source index keeps it stable & deterministic.
a.cmp(&b)
});
order
}
}
/// Deterministic pseudo-random stream (no `rand` dependency).
fn lcg(seed: u64) -> impl Iterator<Item = u64> {
std::iter::successors(Some(seed), |s| {
Some(s.wrapping_mul(6_364_136_223_846_793_005).wrapping_add(1_442_695_040_888_963_407))
})
.map(|s| s >> 11)
}
fn one_column(field: Field, array: arrow_array::ArrayRef) -> RecordBatch {
RecordBatch::try_new(Arc::new(Schema::new(vec![field])), vec![array]).unwrap()
}
fn ms(t: Instant) -> f64 {
t.elapsed().as_secs_f64() * 1000.0
}
/// Time the grid's header-click sort of `batch`'s only column against the pre-PR
/// sort of `materialised`, best of `ROUNDS` interleaved, and hold the grid to
/// `SORT_BUDGET` of it. The orders must also agree: a fast sort that sorts
/// differently is not a fix.
fn assert_sort_budget(what: &str, batch: &RecordBatch, materialised: pre_pr::Column) {
let columns = [materialised];
let (mut grid_ms, mut ref_ms) = (f64::INFINITY, f64::INFINITY);
for round in 0..ROUNDS {
let mut g = Grid::from_record_batch("sort", batch);
let t = Instant::now();
g.click_header(0, false);
grid_ms = grid_ms.min(ms(t));
let t = Instant::now();
let expected = black_box(pre_pr::sorted_order(&columns, &[(0, false)]));
ref_ms = ref_ms.min(ms(t));
if round == 0 {
assert!(g.order() == expected.as_slice(), "{what}: the grid sorted differently from the pre-PR sort");
}
}
let ratio = grid_ms / ref_ms;
eprintln!("{what} sort, {SORT_ROWS} rows, best of {ROUNDS}: grid {grid_ms:.2} ms, pre-PR #2 {ref_ms:.2} ms ({ratio:.2}x)");
assert!(
ratio <= SORT_BUDGET,
"{what} sort at {SORT_ROWS} rows costs {ratio:.2}x the pre-PR #2 sort (grid {grid_ms:.2} ms vs {ref_ms:.2} ms); budget {SORT_BUDGET}x"
);
}
#[test]
fn float64_sort_at_100k_stays_within_budget_of_the_pre_pr_sort() {
// The column grid_bench sorts (`amount`). Pre-PR compared floats with
// `partial_cmp`, the same order as `total_cmp` here: no NaN, no -0.0.
let v: Vec<f64> = (0..SORT_ROWS).map(|i| ((i * 37) % 10_000) as f64 / 10.0).collect();
let batch = one_column(Field::new("amount", DataType::Float64, false), Arc::new(Float64Array::from(v.clone())));
assert_sort_budget("Float64", &batch, pre_pr::Column::Float { v, nulls: vec![false; SORT_ROWS] });
}
#[test]
fn int64_sort_at_100k_stays_within_budget_of_the_pre_pr_sort() {
let v: Vec<i64> = lcg(1).take(SORT_ROWS).map(|x| (x % 1_000_000) as i64 - 500_000).collect();
let batch = one_column(Field::new("n", DataType::Int64, false), Arc::new(Int64Array::from(v.clone())));
assert_sort_budget("Int64", &batch, pre_pr::Column::Int { v, nulls: vec![false; SORT_ROWS] });
}
#[test]
fn uint64_sort_at_100k_stays_within_budget_of_the_pre_pr_sort() {
// The pre-PR grid read UInt64 as i64 clamped at i64::MAX, so the values stay
// below 2^63 here to sort the same way; above it, the order PR #2 made correct
// is pinned in `sort.rs`.
let v: Vec<u64> = lcg(2).take(SORT_ROWS).map(|x| x.wrapping_mul(0x9E37_79B9_7F4A_7C15) >> 1).collect();
let batch = one_column(Field::new("n", DataType::UInt64, false), Arc::new(UInt64Array::from(v.clone())));
let v = v.into_iter().map(|x| x.min(i64::MAX as u64) as i64).collect();
assert_sort_budget("UInt64", &batch, pre_pr::Column::Int { v, nulls: vec![false; SORT_ROWS] });
}
#[test]
fn utf8_sort_at_100k_stays_within_budget_of_the_pre_pr_sort() {
let v: Vec<String> = lcg(3).take(SORT_ROWS).map(|x| format!("item-{:06}", x % 1_000_000)).collect();
let batch = one_column(Field::new("s", DataType::Utf8, false), Arc::new(StringArray::from(v.clone())));
assert_sort_budget("Utf8", &batch, pre_pr::Column::Text { v, nulls: vec![false; SORT_ROWS] });
}