#![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
use std::cmp::Reverse;
use std::panic::{AssertUnwindSafe, catch_unwind};
use exatok::device::{
Batching, MAX_PRETOKEN_TOKENS, MAX_STRIDE_SPREAD, batches_for_lengths, counting_permutation,
extend_tiling_spans, segments_per_dispatch,
};
use exatok::pretokenize::Span;
struct XorShift(u64);
impl XorShift {
fn next(&mut self) -> u64 {
let mut x = self.0;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
self.0 = x;
x.wrapping_mul(0x2545_F491_4F6C_DD1D)
}
fn length(&mut self) -> usize {
(self.next() % 255 + 1) as usize
}
}
fn reference_batches(lengths: &[usize], mode: Batching, workgroups: u32) -> Vec<Vec<usize>> {
let mut order: Vec<usize> = (0..lengths.len()).collect();
if mode == Batching::ByLength {
order.sort_by_key(|index| (Reverse(lengths[*index]), *index));
}
let mut out: Vec<Vec<usize>> = Vec::new();
let mut current: Vec<usize> = Vec::new();
let mut longest = 0_usize;
let mut shortest = usize::MAX;
for index in order {
let len = lengths[index];
let widened = longest.max(len);
let narrowed = shortest.min(len);
let spread_broken = widened + 1 > MAX_STRIDE_SPREAD * (narrowed + 1);
let count_broken = current.len() + 1 > segments_per_dispatch(widened, workgroups);
if !current.is_empty() && (spread_broken || count_broken) {
out.push(std::mem::take(&mut current));
longest = 0;
shortest = usize::MAX;
}
longest = longest.max(len);
shortest = shortest.min(len);
current.push(index);
}
if !current.is_empty() {
out.push(current);
}
out
}
fn distributions() -> Vec<(&'static str, Vec<usize>)> {
let mut rng = XorShift(0x9E37_79B9_7F4A_7C15);
let mut one_maximum = vec![1_usize; 64];
one_maximum[31] = MAX_PRETOKEN_TOKENS;
vec![
("empty", vec![]),
("one run", vec![7]),
("one run at the cap", vec![MAX_PRETOKEN_TOKENS]),
("all equal", vec![5; 97]),
("all at the cap", vec![MAX_PRETOKEN_TOKENS; 33]),
("one maximum among minima", one_maximum),
("ascending", (1..=64).collect()),
("descending", (1..=64).rev().collect()),
(
"cap boundary alternating",
(0..64).map(|i| MAX_PRETOKEN_TOKENS - (i % 2)).collect(),
),
(
"heavy ties on three lengths",
(0..2048).map(|_| (rng.next() % 3 + 1) as usize).collect(),
),
(
"shuffled across the whole domain",
(0..4096).map(|_| rng.length()).collect(),
),
]
}
#[test]
fn the_counting_sort_matches_the_comparison_sort_on_adversarial_lengths() {
for (name, lengths) in distributions() {
for mode in [Batching::InputOrder, Batching::ByLength] {
for workgroups in [1, 8, 4096] {
assert_eq!(
batches_for_lengths(&lengths, mode, workgroups),
reference_batches(&lengths, mode, workgroups),
"{name} ({} runs, {mode:?}, {workgroups} workgroups) grouped \
differently under the counting sort than under the comparison sort",
lengths.len()
);
}
}
}
}
#[test]
fn the_new_order_reads_each_key_twice_where_the_old_sort_read_n_log_n_times() {
let mut rng = XorShift(0xDEAD_BEEF_1234_5678);
let lengths: Vec<usize> = (0..4096).map(|_| rng.length()).collect();
let n = lengths.len();
let ceil_log2 = (usize::BITS - (n - 1).leading_zeros()) as usize;
let mut new_reads = 0_usize;
let new_order = counting_permutation(n, MAX_PRETOKEN_TOKENS + 1, |index| {
new_reads += 1;
lengths[index]
});
assert_eq!(
new_reads,
2 * n,
"the counting sort must read each key exactly twice, once per pass: a \
superlinear count means a comparison crept back in"
);
let mut old_reads = 0_usize;
let mut reference: Vec<usize> = (0..n).collect();
reference.sort_by_key(|index| {
old_reads += 1;
(Reverse(lengths[*index]), *index)
});
assert!(
old_reads >= n * ceil_log2,
"the comparison sort must extract keys at least n*ceil(log2(n)) times \
({n}*{ceil_log2}) on shuffled data; it extracted {old_reads}"
);
assert_eq!(
new_order, reference,
"the counting permutation and the counted comparison sort disagree"
);
}
#[test]
fn the_tiling_check_still_fires_when_the_invariant_is_broken() {
let gap = [Span { start: 0, end: 2 }, Span { start: 3, end: 5 }];
let overlap = [Span { start: 0, end: 3 }, Span { start: 2, end: 5 }];
let short_end = [Span { start: 0, end: 2 }];
for (name, broken) in [("a gap", &gap[..]), ("an overlap", &overlap[..])] {
let mut out = Vec::new();
let payload = catch_unwind(AssertUnwindSafe(|| {
extend_tiling_spans(5, broken.iter().copied(), &mut out);
}))
.expect_err(&format!("{name} must trip the tiling assertion"));
let message = payload
.downcast_ref::<String>()
.map(String::as_str)
.or_else(|| payload.downcast_ref::<&str>().copied())
.unwrap_or("");
assert!(
message.contains("contiguous and gapless"),
"{name} panicked with the wrong message: {message}"
);
}
for (name, spans, input_len) in [
("a stream ending early", &short_end[..], 5_usize),
("no spans over a nonempty input", &[][..], 3),
] {
let mut out = Vec::new();
catch_unwind(AssertUnwindSafe(|| {
extend_tiling_spans(input_len, spans.iter().copied(), &mut out);
}))
.expect_err(&format!("{name} must trip the tiling assertion"));
}
let mut out = Vec::new();
extend_tiling_spans(5, [Span { start: 0, end: 2 }, Span { start: 2, end: 5 }], &mut out);
assert_eq!(out, [Span { start: 0, end: 2 }, Span { start: 2, end: 5 }]);
extend_tiling_spans(0, [], &mut out);
assert_eq!(out.len(), 2, "an empty input must append nothing");
}
#[test]
fn a_length_past_the_host_routing_guarantee_is_refused() {
assert_eq!(
batches_for_lengths(&[MAX_PRETOKEN_TOKENS], Batching::ByLength, 8),
vec![vec![0]],
"a lone cap-length run must still batch"
);
catch_unwind(|| {
let _ = batches_for_lengths(&[MAX_PRETOKEN_TOKENS + 1], Batching::ByLength, 8);
})
.expect_err("a run past MAX_PRETOKEN_TOKENS must be refused, not mis-ordered");
}
mod span_buffer_reuse {
use std::alloc::{GlobalAlloc, Layout, System};
use std::cell::Cell;
use std::sync::LazyLock;
use exatok::Encoding;
use exatok::device::{DeviceTokenizer, MAX_PRETOKEN_TOKENS};
use exatok::vocab::{Vocabulary, artifact_dir};
thread_local! {
static ALLOCATIONS: Cell<usize> = const { Cell::new(0) };
}
fn record_allocation() {
let _ = ALLOCATIONS.try_with(|count| count.set(count.get().wrapping_add(1)));
}
struct Counting;
unsafe impl GlobalAlloc for Counting {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
record_allocation();
unsafe { System.alloc(layout) }
}
unsafe fn dealloc(&self, pointer: *mut u8, layout: Layout) {
unsafe { System.dealloc(pointer, layout) }
}
unsafe fn realloc(&self, pointer: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
record_allocation();
unsafe { System.realloc(pointer, layout, new_size) }
}
}
#[global_allocator]
static ALLOCATOR: Counting = Counting;
fn allocations<T>(body: impl FnOnce() -> T) -> (T, usize) {
let before = ALLOCATIONS.get();
let value = body();
(value, ALLOCATIONS.get() - before)
}
static CL100K: LazyLock<Vocabulary> = LazyLock::new(|| {
Vocabulary::load_tiktoken_path(&artifact_dir().join("cl100k_base.tiktoken"))
.unwrap_or_else(|error| {
panic!(
"Fix: place the real cl100k_base rank file at $EXATOK_VOCAB_DIR \
(default ~/.cache/exatok-vocab), got: {error}"
)
})
});
#[test]
fn a_warm_session_allocates_no_span_vector_per_input() {
let tokenizer = DeviceTokenizer::new(&CL100K, &Encoding::cl100k_base())
.expect("the real cl100k_base artifact must build a device merge table");
let backend = vyre_driver_reference::CpuRefBackend;
let session = tokenizer
.bind(&backend)
.expect("session bind must succeed on the interpreter backend");
let one = "a".repeat(MAX_PRETOKEN_TOKENS + 1);
let two = format!("{} {}", "a".repeat(MAX_PRETOKEN_TOKENS + 1), "b".repeat(MAX_PRETOKEN_TOKENS + 1));
let eight_inputs: Vec<&[u8]> = vec![one.as_bytes(); 8];
let four_inputs: Vec<&[u8]> = vec![two.as_bytes(); 4];
for _ in 0..2 {
let _ = session.encode_batch(&eight_inputs).expect("warmup encode failed");
let _ = session.encode_batch(&four_inputs).expect("warmup encode failed");
}
let (encoded_eight, allocs_eight) =
allocations(|| session.encode_batch(&eight_inputs).expect("eight-input encode failed"));
let (encoded_four, allocs_four) =
allocations(|| session.encode_batch(&four_inputs).expect("four-input encode failed"));
assert_eq!(
encoded_eight.routing().on_host(),
8,
"the one-pretoken fixture must route all eight pretokens to the host"
);
assert_eq!(
encoded_four.routing().on_host(),
8,
"the two-pretoken fixture must route all eight pretokens to the host"
);
assert_eq!(encoded_eight.routing().on_device(), 0);
assert_eq!(encoded_four.routing().on_device(), 0);
assert_eq!(
tokenizer.last_dispatch_count(),
0,
"an all-host encode must not dispatch, or driver costs enter the margin"
);
assert_eq!(
allocs_eight - allocs_four,
4,
"four more inputs at a constant pretoken count must cost exactly \
ONE allocation each, the output id vector: a second would be a \
per-input buffer back in the walk ({allocs_four} for four inputs, \
{allocs_eight} for eight)"
);
}
}