use std::collections::BTreeMap;
use std::sync::{Arc, Mutex, OnceLock, PoisonError, RwLock};
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
use std::time::{Duration, Instant};
use vyre::MemoryOrdering;
use vyre::ir::{BufferAccess, BufferDecl, DataType, Expr, Node, Program};
use vyre_driver::{Resource, VyreBackend};
use vyre_primitives::wire::pack_u32_slice;
use crate::gpu_loop::{
CallerInput, DEAD_SLOT, FIRST_CALLER_BINDING, LOOP_WORKGROUP_WIDTH, LoopBatch, LoopOutcome,
LoopShape,
NAME_STATE_CURRENT, NAME_STATE_NEXT, OP_ID as LOOP_OP_ID, cooperative_block_ceiling,
device_loop_program, lane_is_live, merge_pass_bound, run_device_loop_borrowed,
segment_coordinates,
};
use crate::gpu_rank_table::{RankTable, SLOT_WORDS, probe_child, probe_id_var, probe_rank_var};
use crate::gpu_select::{
ARGMIN_INDEX_SLOT, ARGMIN_RANK_SLOT, ARGMIN_WORDS_PER_SEGMENT, NO_MERGE_INDEX,
};
use crate::incremental::MergeState;
use crate::pretokenize::{Span, pretokens};
#[cfg(test)]
use crate::pretokenize::spans;
use crate::reference::{MergeTable, trace_pretoken};
use crate::vocab::Vocabulary;
use crate::{Encoding, PairKey, Rank, TokenId, ExatokError, byte_token_ids};
#[must_use]
pub fn reachable_rows(
pretokens: &[Vec<TokenId>],
table: &impl MergeTable,
) -> Vec<(PairKey, TokenId, Rank)> {
let mut rows: BTreeMap<u64, (PairKey, TokenId, Rank)> = BTreeMap::new();
for tokens in pretokens {
let trace = trace_pretoken(tokens, table);
let mut states = vec![trace.initial().to_vec()];
states.extend(trace.steps().iter().map(|step| step.state.clone()));
for state in &states {
for window in state.windows(2) {
let pair = PairKey::new(window[0], window[1]);
if let Some(entry) = table.lookup(pair) {
rows.insert(pair.bits(), (pair, entry.id, entry.rank));
}
}
}
}
rows.into_values().collect()
}
const NAME_BPE_SLOTS: &str = "bpe_table_slots";
const NAME_BPE_PICK: &str = "bpe_pick";
const PROBE_RANK: &str = "wtp_rank";
const PROBE_INDEX: &str = "wtp_idx";
const PROBE_MERGED_ID: &str = "wtp_id";
fn pick_seed(segments: u32) -> Vec<u32> {
let mut words = vec![0_u32; (segments * ARGMIN_WORDS_PER_SEGMENT) as usize];
for segment in 0..segments {
let base = (segment * ARGMIN_WORDS_PER_SEGMENT) as usize;
words[base + ARGMIN_INDEX_SLOT as usize] = NO_MERGE_INDEX;
words[base + ARGMIN_RANK_SLOT as usize] = Rank::ABSENT.0;
}
words
}
fn lane() -> Expr {
Expr::gid_x()
}
fn barrier() -> Node {
Node::Barrier {
ordering: MemoryOrdering::SeqCst,
}
}
fn bpe_caller_buffers(shape: LoopShape, capacity: u32) -> Vec<BufferDecl> {
vec![
BufferDecl::storage(
NAME_BPE_SLOTS,
FIRST_CALLER_BINDING,
BufferAccess::ReadOnly,
DataType::U32,
)
.with_count(capacity * SLOT_WORDS),
BufferDecl::storage(
NAME_BPE_PICK,
FIRST_CALLER_BINDING + 1,
BufferAccess::ReadWrite,
DataType::U32,
)
.with_count(shape.segments() * ARGMIN_WORDS_PER_SEGMENT),
]
}
fn bpe_locals(shape: LoopShape) -> Vec<Node> {
let mut locals = segment_coordinates(shape);
locals.push(Node::let_bind(
"pick_at",
Expr::mul(Expr::var("seg"), Expr::u32(ARGMIN_WORDS_PER_SEGMENT)),
));
locals
}
fn probe_own_pair(prefix: &str, capacity: u32, window: u32, then: Vec<Node>) -> Node {
probe_child(
LOOP_OP_ID,
prefix,
NAME_BPE_SLOTS,
capacity,
window,
Expr::load(NAME_STATE_CURRENT, Expr::add(lane(), Expr::u32(1))),
Expr::load(NAME_STATE_CURRENT, lane()),
then,
)
}
fn heads_a_pair(body: Vec<Node>) -> Node {
Node::if_then(
Expr::ge(Expr::var("slot"), Expr::u32(1)),
vec![Node::if_then(
Expr::lt(Expr::var("slot"), Expr::var("len")),
body,
)],
)
}
fn bpe_merge_body(shape: LoopShape, capacity: u32, window: u32) -> Vec<Node> {
let pick_rank = Expr::load(
NAME_BPE_PICK,
Expr::add(Expr::var("pick_at"), Expr::u32(ARGMIN_RANK_SLOT)),
);
let pick_rank_at = || Expr::add(Expr::var("pick_at"), Expr::u32(ARGMIN_RANK_SLOT));
let pick_index_at = || Expr::add(Expr::var("pick_at"), Expr::u32(ARGMIN_INDEX_SLOT));
let mut reset = bpe_locals(shape);
reset.push(Node::if_then(
Expr::eq(Expr::var("slot"), Expr::u32(0)),
vec![
Node::store(NAME_BPE_PICK, pick_rank_at(), Expr::u32(Rank::ABSENT.0)),
Node::store(NAME_BPE_PICK, pick_index_at(), Expr::u32(NO_MERGE_INDEX)),
],
));
let mut vote_rank = bpe_locals(shape);
let rank_of_own_pair = probe_rank_var(PROBE_RANK);
vote_rank.push(heads_a_pair(vec![probe_own_pair(
PROBE_RANK,
capacity,
window,
vec![Node::if_then(
Expr::ne(
Expr::var(rank_of_own_pair.as_str()),
Expr::u32(Rank::ABSENT.0),
),
vec![Node::let_bind(
"wtp_rank_prev",
Expr::atomic_min(
NAME_BPE_PICK,
pick_rank_at(),
Expr::var(rank_of_own_pair.as_str()),
),
)],
)],
)]));
let mut vote_index = bpe_locals(shape);
let rank_at_index_vote = probe_rank_var(PROBE_INDEX);
vote_index.push(heads_a_pair(vec![probe_own_pair(
PROBE_INDEX,
capacity,
window,
vec![Node::if_then(
Expr::and(
Expr::ne(
Expr::var(rank_at_index_vote.as_str()),
Expr::u32(Rank::ABSENT.0),
),
Expr::eq(Expr::var(rank_at_index_vote.as_str()), pick_rank.clone()),
),
vec![Node::let_bind(
"wtp_idx_prev",
Expr::atomic_min(
NAME_BPE_PICK,
pick_index_at(),
Expr::sub(Expr::var("slot"), Expr::u32(1)),
),
)],
)],
)]));
let mut emit = bpe_locals(shape);
emit.extend([
Node::let_bind("pick", Expr::load(NAME_BPE_PICK, pick_index_at())),
Node::let_bind(
"new_len",
Expr::select(
Expr::ne(Expr::var("pick"), Expr::u32(NO_MERGE_INDEX)),
Expr::saturating_sub(Expr::var("len"), Expr::u32(1)),
Expr::var("len"),
),
),
Node::if_then_else(
Expr::eq(Expr::var("slot"), Expr::u32(0)),
vec![Node::store(NAME_STATE_NEXT, lane(), Expr::var("new_len"))],
vec![
Node::let_bind("token", Expr::sub(Expr::var("slot"), Expr::u32(1))),
Node::if_then_else(
Expr::ge(Expr::var("token"), Expr::var("new_len")),
vec![Node::store(NAME_STATE_NEXT, lane(), Expr::u32(DEAD_SLOT))],
vec![Node::if_then_else(
Expr::gt(Expr::var("token"), Expr::var("pick")),
vec![Node::store(
NAME_STATE_NEXT,
lane(),
Expr::load(NAME_STATE_CURRENT, Expr::add(lane(), Expr::u32(1))),
)],
vec![Node::if_then_else(
Expr::eq(Expr::var("token"), Expr::var("pick")),
vec![probe_own_pair(
PROBE_MERGED_ID,
capacity,
window,
vec![Node::store(
NAME_STATE_NEXT,
lane(),
Expr::var(probe_id_var(PROBE_MERGED_ID).as_str()),
)],
)],
vec![Node::store(
NAME_STATE_NEXT,
lane(),
Expr::load(NAME_STATE_CURRENT, lane()),
)],
)],
)],
),
],
),
]);
let guard = |body: Vec<Node>| Node::if_then(lane_is_live(shape), body);
vec![
guard(reset),
barrier(),
guard(vote_rank),
barrier(),
guard(vote_index),
barrier(),
guard(emit),
]
}
pub const MAX_PRETOKEN_TOKENS: usize = LOOP_WORKGROUP_WIDTH as usize - 1;
const COOPERATIVE_HEADROOM_PERCENT: u32 = 75;
#[must_use]
fn workgroups_within_headroom(block_ceiling: u32) -> u32 {
let reduced = u64::from(block_ceiling) * u64::from(COOPERATIVE_HEADROOM_PERCENT) / 100;
u32::try_from(reduced).unwrap_or(block_ceiling).max(1)
}
fn residency_probe_shape() -> LoopShape {
const TOKENS: u32 = 4;
let per_group = LoopShape::new(1, TOKENS, 1).segments_per_group();
LoopShape::new(per_group * 2, TOKENS, 2)
}
#[must_use]
pub fn segments_per_dispatch(longest_tokens: usize, workgroups: u32) -> usize {
let clamped = longest_tokens.max(1).min(LOOP_WORKGROUP_WIDTH as usize);
let capacity = clamped as u32;
let per_group = LoopShape::new(1, capacity, 1).segments_per_group() as usize;
workgroups.max(1) as usize * per_group
}
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
pub enum Batching {
InputOrder,
#[default]
ByLength,
}
pub const MAX_STRIDE_SPREAD: usize = 2;
#[must_use]
pub fn counting_permutation(
n: usize,
buckets: usize,
mut key: impl FnMut(usize) -> usize,
) -> Vec<usize> {
if n == 0 {
return Vec::new();
}
let mut counts = vec![0_usize; buckets];
for index in 0..n {
let bucket = key(index);
assert!(
bucket < buckets,
"key {bucket} for index {index} is past the {buckets}-bucket domain: encode_batch \
routes any pretoken longer than MAX_PRETOKEN_TOKENS to the host before batching, \
so a longer run reaching the sort is a routing defect"
);
counts[bucket] += 1;
}
let mut starts = vec![0_usize; buckets];
let mut placed = 0_usize;
for bucket in (0..buckets).rev() {
starts[bucket] = placed;
placed += counts[bucket];
}
let mut order = vec![0_usize; n];
for index in 0..n {
let bucket = key(index);
order[starts[bucket]] = index;
starts[bucket] += 1;
}
order
}
fn batches(runs: &[Run], mode: Batching, workgroups: u32) -> Vec<Vec<usize>> {
let order: Vec<usize> = if mode == Batching::ByLength {
counting_permutation(runs.len(), MAX_PRETOKEN_TOKENS + 1, |index| runs[index].len)
} else {
(0..runs.len()).collect()
};
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 = runs[index].len;
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
}
#[must_use]
pub fn batches_for_lengths(
lengths: &[usize],
mode: Batching,
workgroups: u32,
) -> Vec<Vec<usize>> {
let mut start = 0_usize;
let runs: Vec<Run> = lengths
.iter()
.map(|&len| {
let run = Run { start, len };
start += len;
run
})
.collect();
batches(&runs, mode, workgroups)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct Routing {
on_device: usize,
on_host: usize,
largest_host_tokens: usize,
}
impl Routing {
#[must_use]
pub const fn on_device(self) -> usize {
self.on_device
}
#[must_use]
pub const fn on_host(self) -> usize {
self.on_host
}
#[must_use]
pub const fn largest_host_tokens(self) -> usize {
self.largest_host_tokens
}
#[must_use]
pub const fn all_on_device(self) -> bool {
self.on_host == 0
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Encoded {
ids: Vec<Vec<TokenId>>,
routing: Routing,
}
impl Encoded {
#[must_use]
pub fn ids(&self) -> &[Vec<TokenId>] {
&self.ids
}
#[must_use]
pub fn into_ids(self) -> Vec<Vec<TokenId>> {
self.ids
}
#[must_use]
pub const fn routing(&self) -> Routing {
self.routing
}
}
impl AsRef<[Vec<TokenId>]> for Encoded {
fn as_ref(&self) -> &[Vec<TokenId>] {
&self.ids
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum EncodePhase {
Pretokenize,
ByteEncode,
HostEncode,
ResidencyQuery,
TablePack,
TableUpload,
Batching,
CallerInputs,
LoopBatchBuild,
PlanLookup,
Dispatch,
OutputAssembly,
TableFree,
IdAssembly,
Teardown,
}
impl EncodePhase {
pub const ALL: [Self; 15] = [
Self::Pretokenize,
Self::ByteEncode,
Self::HostEncode,
Self::ResidencyQuery,
Self::TablePack,
Self::TableUpload,
Self::Batching,
Self::CallerInputs,
Self::LoopBatchBuild,
Self::PlanLookup,
Self::Dispatch,
Self::OutputAssembly,
Self::TableFree,
Self::IdAssembly,
Self::Teardown,
];
#[must_use]
pub const fn index(self) -> usize {
match self {
Self::Pretokenize => 0,
Self::ByteEncode => 1,
Self::HostEncode => 2,
Self::ResidencyQuery => 3,
Self::TablePack => 4,
Self::TableUpload => 5,
Self::Batching => 6,
Self::CallerInputs => 7,
Self::LoopBatchBuild => 8,
Self::PlanLookup => 9,
Self::Dispatch => 10,
Self::OutputAssembly => 11,
Self::TableFree => 12,
Self::IdAssembly => 13,
Self::Teardown => 14,
}
}
#[must_use]
pub const fn label(self) -> &'static str {
match self {
Self::Pretokenize => "pretokenize",
Self::ByteEncode => "byte_encode",
Self::HostEncode => "host_encode",
Self::ResidencyQuery => "residency_query",
Self::TablePack => "table_pack",
Self::TableUpload => "table_upload",
Self::Batching => "batching",
Self::CallerInputs => "caller_inputs",
Self::LoopBatchBuild => "loop_batch",
Self::PlanLookup => "plan_lookup",
Self::Dispatch => "dispatch",
Self::OutputAssembly => "output_assembly",
Self::TableFree => "table_free",
Self::IdAssembly => "id_assembly",
Self::Teardown => "teardown",
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
struct EncodeCounts {
device_pretokens: usize,
host_pretokens: usize,
input_bytes: usize,
table_bytes: usize,
output_ids: usize,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct EncodeProfile {
elapsed: [Duration; EncodePhase::ALL.len()],
total: Duration,
dispatches: usize,
state_words: usize,
counts: EncodeCounts,
}
impl EncodeProfile {
#[must_use]
pub const fn phase(&self, phase: EncodePhase) -> Duration {
self.elapsed[phase.index()]
}
#[must_use]
pub fn named(&self) -> Duration {
self.elapsed.iter().sum()
}
#[must_use]
pub const fn total(&self) -> Duration {
self.total
}
#[must_use]
pub fn unattributed(&self) -> Duration {
self.total.saturating_sub(self.named())
}
#[must_use]
pub const fn dispatches(&self) -> usize {
self.dispatches
}
#[must_use]
pub const fn state_words(&self) -> usize {
self.state_words
}
#[must_use]
pub const fn device_pretokens(&self) -> usize {
self.counts.device_pretokens
}
#[must_use]
pub const fn host_pretokens(&self) -> usize {
self.counts.host_pretokens
}
#[must_use]
pub const fn input_bytes(&self) -> usize {
self.counts.input_bytes
}
#[must_use]
pub const fn table_bytes(&self) -> usize {
self.counts.table_bytes
}
#[must_use]
pub const fn output_ids(&self) -> usize {
self.counts.output_ids
}
}
trait PhaseProbe: Sized {
fn measure<T>(&mut self, phase: EncodePhase, body: impl FnOnce(&mut Self) -> T) -> T;
fn dispatched(&mut self, state_words: usize);
fn counted(&mut self, counts: EncodeCounts);
}
struct Untimed;
impl PhaseProbe for Untimed {
#[inline]
fn measure<T>(&mut self, _phase: EncodePhase, body: impl FnOnce(&mut Self) -> T) -> T {
body(self)
}
#[inline]
fn dispatched(&mut self, _state_words: usize) {}
#[inline]
fn counted(&mut self, _counts: EncodeCounts) {}
}
struct Timed {
started: Instant,
charged: Duration,
profile: EncodeProfile,
}
impl Timed {
fn start() -> Self {
Self {
started: Instant::now(),
charged: Duration::ZERO,
profile: EncodeProfile {
elapsed: [Duration::ZERO; EncodePhase::ALL.len()],
total: Duration::ZERO,
dispatches: 0,
state_words: 0,
counts: EncodeCounts::default(),
},
}
}
fn finish(mut self) -> EncodeProfile {
self.profile.total = self.started.elapsed();
self.profile
}
}
impl PhaseProbe for Timed {
fn measure<T>(&mut self, phase: EncodePhase, body: impl FnOnce(&mut Self) -> T) -> T {
let before = self.charged;
let started = Instant::now();
let value = body(self);
let elapsed = started.elapsed();
let own = elapsed.saturating_sub(self.charged.saturating_sub(before));
self.profile.elapsed[phase.index()] += own;
self.charged += own;
value
}
fn dispatched(&mut self, state_words: usize) {
self.profile.dispatches += 1;
self.profile.state_words += state_words;
}
fn counted(&mut self, counts: EncodeCounts) {
self.profile.counts = counts;
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
struct Run {
start: usize,
len: usize,
}
impl Run {
const EMPTY: Self = Self { start: 0, len: 0 };
fn append(flat: &mut Vec<u32>, words: &[u32]) -> Self {
let start = flat.len();
flat.extend_from_slice(words);
Self {
start,
len: words.len(),
}
}
fn of(self, flat: &[u32]) -> &[u32] {
&flat[self.start..self.start + self.len]
}
}
#[derive(Debug, Default)]
struct Scratch {
state: Vec<u32>,
state_runs: Vec<Run>,
ids: Vec<u32>,
id_runs: Vec<Run>,
device_slot: Vec<usize>,
host_state: Vec<TokenId>,
host_merge: MergeState,
spans: Vec<Span>,
}
impl Scratch {
fn reset(&mut self) {
self.state.clear();
self.state_runs.clear();
self.ids.clear();
self.id_runs.clear();
self.device_slot.clear();
self.host_state.clear();
self.spans.clear();
}
fn push_start_state(&mut self, bytes: &[u8], byte_token: &[TokenId; 256]) {
let start = self.state.len();
self.state
.extend(bytes.iter().map(|byte| byte_token[*byte as usize].0));
self.state_runs.push(Run {
start,
len: bytes.len(),
});
}
fn push_host_ids(
&mut self,
bytes: &[u8],
byte_token: &[TokenId; 256],
table: &impl MergeTable,
) -> Run {
self.host_state.clear();
self.host_state
.extend(bytes.iter().map(|byte| byte_token[*byte as usize]));
self.host_merge.load(&self.host_state, table);
self.host_merge.run(table);
let start = self.ids.len();
self.ids.extend(self.host_merge.tokens().iter().map(|id| id.0));
Run {
start,
len: self.ids.len() - start,
}
}
}
pub fn extend_tiling_spans(
input_len: usize,
spans: impl IntoIterator<Item = Span>,
out: &mut Vec<Span>,
) {
let mut end = 0_usize;
out.extend(spans.into_iter().inspect(|span| {
assert_eq!(
span.start, end,
"pretoken spans must be contiguous and gapless over the input: span \
{}..{} starts where the previous span ended at {}",
span.start, span.end, end
);
end = span.end;
}));
assert_eq!(
end, input_len,
"pretoken spans must be contiguous and gapless over the input: the last \
span ends at {end} of {input_len} bytes"
);
}
const SCRATCH_POOL_LIMIT: usize = 4;
#[derive(Clone, Copy)]
enum TableSource<'a> {
Session {
table: Option<&'a Resource>,
bytes: &'a [u8],
},
PerCall,
}
#[derive(Debug)]
struct DispatchPlan {
program: Program,
pick_seed: Vec<u8>,
}
impl DispatchPlan {
fn retained_bytes(&self) -> usize {
self.program
.stats()
.node_count
.saturating_mul(PLAN_BYTES_PER_IR_NODE)
.saturating_add(self.pick_seed.len())
}
}
const PLAN_BYTES_PER_IR_NODE: usize = 348;
const PLAN_CACHE_BYTES: usize = 64 << 20;
#[derive(Debug)]
pub struct DeviceTokenizer {
encoding: Encoding,
table: RankTable,
byte_token: [TokenId; 256],
batching: Batching,
dispatches: AtomicUsize,
block_ceilings: RwLock<Vec<(&'static str, u32)>>,
table_bytes: OnceLock<Vec<u8>>,
plans: RwLock<Vec<(LoopShape, Arc<DispatchPlan>)>>,
plan_hits: AtomicUsize,
plan_misses: AtomicUsize,
plan_rebuilds: AtomicU64,
output_batch_checks: AtomicU64,
output_segment_guards: AtomicU64,
host_lookups: AtomicU64,
host_merges: AtomicU64,
workgroup_override: Option<u32>,
}
impl DeviceTokenizer {
pub fn new(vocab: &Vocabulary, encoding: &Encoding) -> Result<Self, ExatokError> {
let byte_token = byte_token_ids(encoding.artifact(), vocab)?;
let rows = vocab
.merge_table()
.iter()
.map(|(pair, entry)| (pair, entry.id, entry.rank));
let table = RankTable::from_entries(encoding.artifact(), rows)?;
Ok(Self {
encoding: encoding.clone(),
table,
byte_token,
batching: Batching::default(),
dispatches: AtomicUsize::new(0),
block_ceilings: RwLock::new(Vec::new()),
plans: RwLock::new(Vec::new()),
plan_hits: AtomicUsize::new(0),
plan_misses: AtomicUsize::new(0),
plan_rebuilds: AtomicU64::new(0),
output_batch_checks: AtomicU64::new(0),
output_segment_guards: AtomicU64::new(0),
host_lookups: AtomicU64::new(0),
host_merges: AtomicU64::new(0),
table_bytes: OnceLock::new(),
workgroup_override: None,
})
}
#[must_use]
pub fn with_batching(mut self, batching: Batching) -> Self {
self.batching = batching;
self
}
#[must_use]
pub const fn batching(&self) -> Batching {
self.batching
}
#[must_use]
pub fn with_workgroups_per_dispatch(mut self, workgroups: u32) -> Self {
self.workgroup_override = Some(workgroups);
self
}
#[must_use]
pub fn workgroups_per_dispatch(&self, backend: &dyn VyreBackend) -> u32 {
self.workgroup_override
.unwrap_or_else(|| workgroups_within_headroom(self.queried_block_ceiling(backend)))
}
#[must_use]
pub fn queried_block_ceiling(&self, backend: &dyn VyreBackend) -> u32 {
let id = backend.id();
if let Some(ceiling) = self
.block_ceilings
.read()
.unwrap_or_else(PoisonError::into_inner)
.iter()
.find_map(|(cached, ceiling)| (*cached == id).then_some(*ceiling))
{
return ceiling;
}
let shape = residency_probe_shape();
let program = device_loop_program(
shape,
bpe_merge_body(shape, self.table.capacity(), self.table.window()),
bpe_caller_buffers(shape, self.table.capacity()),
);
let ceiling = cooperative_block_ceiling(backend, &program, shape);
let mut cache = self
.block_ceilings
.write()
.unwrap_or_else(PoisonError::into_inner);
if let Some((_, existing)) = cache.iter().find(|(cached, _)| *cached == id) {
return *existing;
}
cache.push((id, ceiling));
ceiling
}
#[must_use]
pub const fn encoding(&self) -> &Encoding {
&self.encoding
}
#[must_use]
pub const fn table(&self) -> &RankTable {
&self.table
}
pub fn encode(
&self,
backend: &dyn VyreBackend,
input: &[u8],
) -> Result<Vec<TokenId>, ExatokError> {
let mut per_input = self.encode_batch(backend, &[input])?.into_ids();
Ok(per_input.pop().unwrap_or_default())
}
fn run_bpe_loop<P: PhaseProbe>(
&self,
backend: &dyn VyreBackend,
words: &[&[u32]],
budget: u32,
table: CallerInput<'_>,
batch_pool: &mut Option<LoopBatch>,
probe: &mut P,
) -> Result<LoopOutcome, ExatokError> {
let batch = probe.measure(EncodePhase::LoopBatchBuild, |_| {
match batch_pool {
Some(batch) => {
batch.reseed(words, budget);
batch
}
None => batch_pool.insert(LoopBatch::new(words, budget)),
}
});
let plan = probe.measure(EncodePhase::PlanLookup, |_| self.dispatch_plan(batch.shape()));
let caller_inputs = [table, CallerInput::Host(&plan.pick_seed)];
probe.dispatched(batch.state().len());
probe.measure(EncodePhase::Dispatch, |_| {
run_device_loop_borrowed(backend, &plan.program, batch, &caller_inputs)
})
}
fn upload_resident_table(
&self,
backend: &dyn VyreBackend,
bytes: &[u8],
) -> Result<Resource, ExatokError> {
let resource = backend.allocate_resident(bytes.len()).map_err(|error| {
ExatokError::Backend(format!(
"device resident table allocation of {} byte(s) failed: {error}. \
Fix: free device memory and retry, or encode without a resident session \
so the table is bound from host memory per call",
bytes.len()
))
})?;
if let Err(error) = backend.upload_resident(&resource, bytes) {
drop(backend.free_resident(resource));
return Err(ExatokError::Backend(format!(
"device resident table upload of {} byte(s) failed: {error}. \
Fix: drop this tokenizer or session and bind a fresh one, since a buffer \
the backend just allocated refusing its upload marks the device context \
as suspect",
bytes.len()
)));
}
Ok(resource)
}
fn dispatch_plan(&self, shape: LoopShape) -> Arc<DispatchPlan> {
if let Some(plan) = self.cached_plan(shape) {
self.plan_hits.fetch_add(1, Ordering::Relaxed);
return plan;
}
self.plan_misses.fetch_add(1, Ordering::Relaxed);
let built = Arc::new(DispatchPlan {
program: device_loop_program(
shape,
bpe_merge_body(shape, self.table.capacity(), self.table.window()),
bpe_caller_buffers(shape, self.table.capacity()),
),
pick_seed: pack_u32_slice(&pick_seed(shape.segments())),
});
self.plan_rebuilds.fetch_add(1, Ordering::Relaxed);
let mut plans = self.plans.write().unwrap_or_else(PoisonError::into_inner);
if let Some((_, plan)) = plans.iter().find(|(cached, _)| *cached == shape) {
return Arc::clone(plan);
}
plans.push((shape, Arc::clone(&built)));
let mut held: usize = plans.iter().map(|(_, plan)| plan.retained_bytes()).sum();
while held > PLAN_CACHE_BYTES && plans.len() > 1 {
let victim = plans
.iter()
.enumerate()
.min_by_key(|(_, (_, plan))| plan.retained_bytes())
.map_or(0, |(index, _)| index);
let (_, evicted) = plans.remove(victim);
held -= evicted.retained_bytes();
}
built
}
#[must_use]
pub fn plan_rebuilds(&self) -> u64 {
self.plan_rebuilds.load(Ordering::Relaxed)
}
fn cached_plan(&self, shape: LoopShape) -> Option<Arc<DispatchPlan>> {
self.plans
.read()
.unwrap_or_else(PoisonError::into_inner)
.iter()
.find(|(cached, _)| *cached == shape)
.map(|(_, plan)| Arc::clone(plan))
}
#[cfg(test)]
fn plan_cache_tally(&self) -> (usize, usize) {
(
self.plan_hits.load(Ordering::Relaxed),
self.plan_misses.load(Ordering::Relaxed),
)
}
pub fn bind<'a>(
&'a self,
backend: &'a dyn VyreBackend,
) -> Result<DeviceSession<'a>, ExatokError> {
let bytes = self
.table_bytes
.get_or_init(|| pack_u32_slice(self.table.slot_words()))
.as_slice();
let table = if backend.supports_resident_dispatch() {
Some(self.upload_resident_table(backend, bytes)?)
} else {
None
};
Ok(DeviceSession {
tokenizer: self,
backend,
table,
table_bytes: bytes,
scratch: Mutex::new(Vec::new()),
})
}
pub fn encode_batch(
&self,
backend: &dyn VyreBackend,
inputs: &[&[u8]],
) -> Result<Encoded, ExatokError> {
self.encode_batch_per_call(backend, inputs, &mut Untimed)
}
pub fn encode_batch_profiled(
&self,
backend: &dyn VyreBackend,
inputs: &[&[u8]],
) -> Result<(Encoded, EncodeProfile), ExatokError> {
let mut probe = Timed::start();
let encoded = self.encode_batch_per_call(backend, inputs, &mut probe);
let profile = probe.finish();
encoded.map(|ids| (ids, profile))
}
fn encode_batch_per_call<P: PhaseProbe>(
&self,
backend: &dyn VyreBackend,
inputs: &[&[u8]],
probe: &mut P,
) -> Result<Encoded, ExatokError> {
let mut scratch = Scratch::default();
let encoded =
self.encode_batch_probed(backend, inputs, probe, TableSource::PerCall, &mut scratch);
probe.measure(EncodePhase::Teardown, |_| drop(scratch));
encoded
}
fn encode_batch_probed<P: PhaseProbe>(
&self,
backend: &dyn VyreBackend,
inputs: &[&[u8]],
probe: &mut P,
source: TableSource<'_>,
scratch: &mut Scratch,
) -> Result<Encoded, ExatokError> {
self.dispatches.store(0, Ordering::Relaxed);
probe.measure(EncodePhase::Teardown, |_| scratch.reset());
let input_bytes: usize = inputs.iter().map(|input| input.len()).sum();
scratch.state.reserve(input_bytes);
scratch.ids.reserve(input_bytes);
let mut pretokens_per_input: Vec<usize> = Vec::with_capacity(inputs.len());
let mut routing = Routing::default();
let mut host_tally = (
scratch.host_merge.lookups(),
scratch.host_merge.merges(),
);
for (input_index, input) in inputs.iter().enumerate() {
let mut span_buf = std::mem::take(&mut scratch.spans);
span_buf.clear();
probe.measure(EncodePhase::Pretokenize, |_| {
extend_tiling_spans(
input.len(),
pretokens(self.encoding.pattern(), input),
&mut span_buf,
);
});
pretokens_per_input.push(span_buf.len());
scratch.id_runs.reserve(span_buf.len());
let walked =
probe.measure(EncodePhase::ByteEncode, |probe| -> Result<(), ExatokError> {
for &span in &span_buf {
let Some(bytes) = span.bytes(input) else {
return Err(self.span_error(input_index, span, input.len()));
};
if bytes.len() > MAX_PRETOKEN_TOKENS {
routing.on_host += 1;
routing.largest_host_tokens =
routing.largest_host_tokens.max(bytes.len());
let run = probe.measure(EncodePhase::HostEncode, |_| {
scratch.push_host_ids(bytes, &self.byte_token, &self.table)
});
scratch.id_runs.push(run);
continue;
}
routing.on_device += 1;
scratch.device_slot.push(scratch.id_runs.len());
scratch.id_runs.push(Run::EMPTY);
scratch.push_start_state(bytes, &self.byte_token);
}
Ok(())
});
scratch.spans = span_buf;
walked?;
let host_tally_now = (
scratch.host_merge.lookups(),
scratch.host_merge.merges(),
);
self.host_lookups
.fetch_add(host_tally_now.0 - host_tally.0, Ordering::Relaxed);
self.host_merges
.fetch_add(host_tally_now.1 - host_tally.1, Ordering::Relaxed);
host_tally = host_tally_now;
}
let mut covered = 0_usize;
let mut dispatches = 0_usize;
let workgroups = if scratch.state_runs.is_empty() {
1
} else {
probe.measure(EncodePhase::ResidencyQuery, |_| {
self.workgroups_per_dispatch(backend)
})
};
let table_bytes: &[u8] = if scratch.state_runs.is_empty() {
&[]
} else {
match source {
TableSource::Session { bytes, .. } => bytes,
TableSource::PerCall => probe.measure(EncodePhase::TablePack, |_| {
self.table_bytes
.get_or_init(|| pack_u32_slice(self.table.slot_words()))
.as_slice()
}),
}
};
let per_call_table = match source {
TableSource::PerCall
if !table_bytes.is_empty() && backend.supports_resident_dispatch() =>
{
Some(probe.measure(EncodePhase::TableUpload, |_| {
self.upload_resident_table(backend, table_bytes)
})?)
}
_ => None,
};
let resident: Option<&Resource> = match source {
TableSource::Session { table, .. } if !table_bytes.is_empty() => table,
TableSource::Session { .. } => None,
TableSource::PerCall => per_call_table.as_ref(),
};
let table = match resident {
Some(resource) => CallerInput::Resident {
resource,
bytes: table_bytes,
},
None => CallerInput::Host(table_bytes),
};
let Scratch {
state,
state_runs,
ids,
id_runs,
device_slot,
host_state: _,
host_merge: _,
spans: _,
} = scratch;
let mut dispatch_batches = |probe: &mut P| -> Result<(), ExatokError> {
let plan = probe.measure(EncodePhase::Batching, |_| {
batches(state_runs, self.batching, workgroups)
});
let mut batch_words: Vec<&[u32]> = Vec::new();
let mut batch_pool: Option<LoopBatch> = None;
for batch_indices in plan {
let longest = probe.measure(EncodePhase::CallerInputs, |_| {
batch_words.clear();
batch_words
.extend(batch_indices.iter().map(|index| state_runs[*index].of(state)));
batch_words.iter().map(|word| word.len()).max().unwrap_or(1) as u32
});
let passes = merge_pass_bound(longest) + 1;
let outcome =
self.run_bpe_loop(backend, &batch_words, passes, table, &mut batch_pool, probe)?;
dispatches += 1;
probe.measure(EncodePhase::OutputAssembly, |_| {
self.output_batch_checks.fetch_add(1, Ordering::Relaxed);
if let Some(segments) = outcome.converged_segments() {
for (tokens, index) in segments.zip(batch_indices.iter()) {
id_runs[device_slot[*index]] = Run::append(ids, tokens);
covered += 1;
}
} else {
for (segment, index) in batch_indices.iter().enumerate() {
self.output_segment_guards.fetch_add(1, Ordering::Relaxed);
let tokens = outcome.converged_tokens(segment as u32)?;
id_runs[device_slot[*index]] = Run::append(ids, tokens);
covered += 1;
}
}
Ok::<(), ExatokError>(())
})?;
}
Ok(())
};
let dispatched = dispatch_batches(probe);
if let Some(resource) = per_call_table {
let freed = probe.measure(EncodePhase::TableFree, |_| backend.free_resident(resource));
if dispatched.is_ok() {
freed.map_err(|error| {
ExatokError::Backend(format!(
"device resident table free failed: {error}. \
Fix: retry the encode on a fresh backend, because a free that \
fails after a successful dispatch points at the device context, \
not at the input"
))
})?;
}
}
dispatched?;
assert_eq!(
covered,
state_runs.len(),
"every device pretoken must land in exactly one batch, so all {} must be covered",
state_runs.len()
);
assert_eq!(
routing.on_device + routing.on_host,
id_runs.len(),
"the routing counts must account for every pretoken, or a reported \
device share is arithmetic on the wrong denominator"
);
self.dispatches.store(dispatches, Ordering::Relaxed);
let (out, output_ids) = probe.measure(EncodePhase::IdAssembly, |_| {
let mut out = Vec::with_capacity(inputs.len());
let mut output_ids = 0_usize;
let mut remaining: &[Run] = id_runs;
assert_eq!(
pretokens_per_input.iter().sum::<usize>(),
id_runs.len(),
"the per-input pretoken counts must account for all {} runs, or ids \
are attributed to the wrong input",
id_runs.len()
);
for count in pretokens_per_input {
let (slots, rest) = remaining.split_at(count);
let mut input_ids = Vec::with_capacity(slots.iter().map(|run| run.len).sum());
for run in slots {
input_ids.extend(run.of(ids).iter().copied().map(TokenId));
}
output_ids += input_ids.len();
out.push(input_ids);
remaining = rest;
}
(out, output_ids)
});
probe.counted(EncodeCounts {
device_pretokens: routing.on_device,
host_pretokens: routing.on_host,
input_bytes,
table_bytes: table_bytes.len(),
output_ids,
});
Ok(Encoded { ids: out, routing })
}
#[must_use]
pub fn last_dispatch_count(&self) -> usize {
self.dispatches.load(Ordering::Relaxed)
}
#[must_use]
pub fn output_assembly_tally(&self) -> (u64, u64) {
(
self.output_batch_checks.load(Ordering::Relaxed),
self.output_segment_guards.load(Ordering::Relaxed),
)
}
#[must_use]
pub fn host_merge_tally(&self) -> (u64, u64) {
(
self.host_lookups.load(Ordering::Relaxed),
self.host_merges.load(Ordering::Relaxed),
)
}
fn span_error(&self, input_index: usize, span: Span, len: usize) -> ExatokError {
ExatokError::Artifact {
artifact: format!("{} input", self.encoding.artifact()),
location: format!("input {input_index}, bytes {}..{}", span.start, span.end),
detail: format!("this pretoken span falls outside the {len}-byte input"),
fix: "this is a defect in crate::pretokenize, whose spans must lie inside their \
input; report it rather than working around it"
.to_owned(),
}
}
}
pub struct DeviceSession<'a> {
tokenizer: &'a DeviceTokenizer,
backend: &'a dyn VyreBackend,
table: Option<Resource>,
table_bytes: &'a [u8],
scratch: Mutex<Vec<Scratch>>,
}
impl DeviceSession<'_> {
pub fn encode_batch(&self, inputs: &[&[u8]]) -> Result<Encoded, ExatokError> {
self.encode_probed(inputs, &mut Untimed)
}
pub fn encode_batch_profiled(
&self,
inputs: &[&[u8]],
) -> Result<(Encoded, EncodeProfile), ExatokError> {
let mut probe = Timed::start();
let encoded = self.encode_probed(inputs, &mut probe);
let profile = probe.finish();
encoded.map(|ids| (ids, profile))
}
pub fn encode(&self, input: &[u8]) -> Result<Vec<TokenId>, ExatokError> {
let mut per_input = self.encode_batch(&[input])?.into_ids();
Ok(per_input.pop().unwrap_or_default())
}
pub fn close(mut self) -> Result<(), ExatokError> {
let Some(resource) = self.table.take() else {
return Ok(());
};
self.backend.free_resident(resource).map_err(|error| {
ExatokError::Backend(format!(
"device resident table free failed: {error}. \
Fix: destroy and re-acquire the device context, and do not reuse a \
session whose table could not be freed"
))
})
}
fn encode_probed<P: PhaseProbe>(
&self,
inputs: &[&[u8]],
probe: &mut P,
) -> Result<Encoded, ExatokError> {
let mut scratch = probe.measure(EncodePhase::Teardown, |_| {
self.scratch
.lock()
.unwrap_or_else(PoisonError::into_inner)
.pop()
.unwrap_or_default()
});
let encoded = self.tokenizer.encode_batch_probed(
self.backend,
inputs,
probe,
TableSource::Session {
table: self.table.as_ref(),
bytes: self.table_bytes,
},
&mut scratch,
);
probe.measure(EncodePhase::Teardown, |_| {
let mut pool = self.scratch.lock().unwrap_or_else(PoisonError::into_inner);
if pool.len() < SCRATCH_POOL_LIMIT {
pool.push(scratch);
}
});
encoded
}
}
impl Drop for DeviceSession<'_> {
fn drop(&mut self) {
if let Some(resource) = self.table.take() {
drop(self.backend.free_resident(resource));
}
}
}
impl std::fmt::Debug for DeviceSession<'_> {
fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
formatter
.debug_struct("DeviceSession")
.field("encoding", &self.tokenizer.encoding.artifact())
.field("backend", &self.backend.id())
.field("resident_table", &self.table.is_some())
.field(
"pooled_scratch",
&self
.scratch
.lock()
.unwrap_or_else(PoisonError::into_inner)
.len(),
)
.finish()
}
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
use super::*;
#[test]
fn the_pass_body_guards_every_phase_with_the_loops_own_predicate() {
let shape = LoopShape::new(300, 4, 8);
assert!(
shape.groups() > 1 && shape.words_per_group() > shape.segments_per_group() * 5,
"the fixture must have BOTH a per-group tail and more than one group, \
or it cannot distinguish the two guards"
);
let body = bpe_merge_body(shape, 1 << 12, 8);
let expected = lane_is_live(shape);
let guards: Vec<&Expr> = body
.iter()
.filter_map(|node| match node {
Node::If { cond, .. } => Some(cond),
_ => None,
})
.collect();
assert_eq!(
guards.len(),
4,
"all four phases must be guarded; a phase spliced in unguarded is the \
defect this test exists for"
);
for (phase, guard) in guards.iter().enumerate() {
assert_eq!(
**guard, expected,
"phase {phase} must guard on lane_is_live(shape) verbatim"
);
}
}
#[test]
fn every_phase_of_the_pass_body_is_separated_by_a_barrier() {
let body = bpe_merge_body(LoopShape::new(300, 4, 8), 1 << 12, 8);
let kinds: Vec<&str> = body
.iter()
.map(|node| match node {
Node::If { .. } => "phase",
Node::Barrier { .. } => "barrier",
_ => "other",
})
.collect();
assert_eq!(
kinds,
["phase", "barrier", "phase", "barrier", "phase", "barrier", "phase"],
"reset, rank vote, index vote and emit must alternate with barriers: \
each phase reads what the previous one wrote"
);
}
#[test]
fn every_batching_mode_partitions_the_inputs_exactly_once() {
let lengths = [1_usize, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 2, 1];
let pretokens = runs_of_lengths(&lengths);
for workgroups in [1_u32, 3, 64, 765] {
for mode in [Batching::InputOrder, Batching::ByLength] {
let batches = batches(&pretokens, mode, workgroups);
let mut seen: Vec<usize> = batches.iter().flatten().copied().collect();
seen.sort_unstable();
assert_eq!(
seen,
(0..pretokens.len()).collect::<Vec<_>>(),
"{mode:?} at {workgroups} workgroups must cover every input index exactly once"
);
assert!(
batches.iter().all(|batch| !batch.is_empty()),
"{mode:?} at {workgroups} workgroups must not emit an empty dispatch"
);
}
}
}
#[test]
fn no_batch_exceeds_the_stride_spread_or_the_per_dispatch_segment_count() {
let lengths = [1_usize, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 2, 1];
let pretokens = runs_of_lengths(&lengths);
for workgroups in [1_u32, 3, 64, 765] {
for mode in [Batching::InputOrder, Batching::ByLength] {
for batch in batches(&pretokens, mode, workgroups) {
let strides: Vec<usize> =
batch.iter().map(|i| pretokens[*i].len + 1).collect();
let widest = *strides.iter().max().expect("no empty batch");
let narrowest = *strides.iter().min().expect("no empty batch");
assert!(
batch.len() == 1 || widest <= MAX_STRIDE_SPREAD * narrowest,
"{mode:?} batch {batch:?} spans strides {narrowest}..={widest}, \
past the {MAX_STRIDE_SPREAD}x spread bound"
);
assert!(
batch.len() <= segments_per_dispatch(widest - 1, workgroups),
"{mode:?} batch of {} segments exceeds what one {workgroups}-workgroup \
dispatch of stride {widest} can carry",
batch.len()
);
}
}
}
}
#[test]
fn the_longest_legal_pretoken_still_forms_one_batch_on_its_own() {
let solo = runs_of_lengths(&[MAX_PRETOKEN_TOKENS]);
for workgroups in [1_u32, 765] {
for mode in [Batching::InputOrder, Batching::ByLength] {
assert_eq!(
batches(&solo, mode, workgroups),
vec![vec![0_usize]],
"{mode:?} must place a lone cap-length pretoken in exactly one batch"
);
}
}
}
#[test]
fn the_workgroup_budget_stays_strictly_under_a_real_ceiling() {
assert_eq!(
workgroups_within_headroom(1020),
765,
"three quarters of the 1020-block thread residency this device reports"
);
assert_eq!(workgroups_within_headroom(100), 75);
assert!(
workgroups_within_headroom(1020) < 1020,
"the budget must be a REDUCTION of the ceiling, not the ceiling itself"
);
}
#[test]
fn the_workgroup_budget_is_never_zero() {
for ceiling in [0_u32, 1] {
assert_eq!(
workgroups_within_headroom(ceiling),
1,
"a ceiling of {ceiling} must still dispatch one workgroup"
);
}
assert_eq!(
workgroups_within_headroom(u32::MAX),
3_221_225_471,
"three quarters of the widest representable ceiling, computed in 64 bits: \
a 32-bit product overflows here and a saturating one would report \
42949672, a hundredth of the ceiling"
);
for ceiling in [1_u32, 2, 99, 100, 1020, 57_000_000, u32::MAX] {
assert!(
workgroups_within_headroom(ceiling) <= ceiling,
"the budget must never exceed the ceiling it reduces, at {ceiling}"
);
}
}
#[test]
fn the_residency_probe_shape_spans_more_than_one_workgroup() {
let shape = residency_probe_shape();
assert_eq!(
shape.groups(),
2,
"the probe must span two groups, or the query answers about a program \
with no grid barrier"
);
assert_eq!(
shape.words_per_group(),
LOOP_WORKGROUP_WIDTH,
"the probe must plan blocks of the loop's own workgroup width, since \
the ceiling is a function of that width"
);
}
fn plan_cache_fixture() -> DeviceTokenizer {
let table = RankTable::from_entries(
"plan cache fixture",
[(PairKey::new(TokenId(0), TokenId(1)), TokenId(2), Rank(0))],
)
.expect("a single-row table must build");
DeviceTokenizer {
encoding: Encoding::cl100k_base(),
table,
byte_token: [TokenId(0); 256],
batching: Batching::default(),
dispatches: AtomicUsize::new(0),
block_ceilings: RwLock::new(Vec::new()),
table_bytes: OnceLock::new(),
plans: RwLock::new(Vec::new()),
plan_hits: AtomicUsize::new(0),
plan_misses: AtomicUsize::new(0),
plan_rebuilds: AtomicU64::new(0),
output_batch_checks: AtomicU64::new(0),
output_segment_guards: AtomicU64::new(0),
host_lookups: AtomicU64::new(0),
host_merges: AtomicU64::new(0),
workgroup_override: None,
}
}
fn held_bytes(device: &DeviceTokenizer) -> usize {
device
.plans
.read()
.unwrap_or_else(PoisonError::into_inner)
.iter()
.map(|(_, plan)| plan.retained_bytes())
.sum()
}
fn held_shapes(device: &DeviceTokenizer) -> Vec<LoopShape> {
device
.plans
.read()
.unwrap_or_else(PoisonError::into_inner)
.iter()
.map(|(shape, _)| *shape)
.collect()
}
fn seed_heavy(segments: u32) -> LoopShape {
LoopShape::new(segments, 1, 2)
}
#[test]
fn the_plan_cache_serves_one_program_per_shape() {
let device = plan_cache_fixture();
let shape = LoopShape::new(8, 4, 5);
let first = device.dispatch_plan(shape);
let second = device.dispatch_plan(shape);
assert!(
Arc::ptr_eq(&first, &second),
"a repeated shape must return the plan already built, or construction \
is still per dispatch"
);
for other in [
LoopShape::new(9, 4, 5),
LoopShape::new(8, 5, 5),
LoopShape::new(8, 4, 6),
] {
let plan = device.dispatch_plan(other);
assert!(
!Arc::ptr_eq(&first, &plan),
"{other:?} differs from {shape:?} and must not be served that \
shape's program"
);
}
}
#[test]
fn the_plan_cache_evicts_the_cheapest_to_rebuild_past_its_byte_ceiling() {
let device = plan_cache_fixture();
let wide = [
seed_heavy(2_400_000),
seed_heavy(2_200_000),
seed_heavy(2_000_000),
seed_heavy(1_700_000),
];
let cheap = seed_heavy(400_000);
let widest = device.dispatch_plan(wide[0]);
device.dispatch_plan(wide[1]);
let cheap_plan = device.dispatch_plan(cheap);
assert!(
held_bytes(&device) <= PLAN_CACHE_BYTES,
"the fixture must still be under the ceiling before the entry that \
overflows it, or the sweep under test has already run: {} bytes",
held_bytes(&device)
);
device.dispatch_plan(wide[2]);
device.dispatch_plan(wide[3]);
assert!(
held_bytes(&device) <= PLAN_CACHE_BYTES,
"the cache must respect its own ceiling: {} bytes held against {}",
held_bytes(&device),
PLAN_CACHE_BYTES
);
assert_eq!(
held_shapes(&device),
wide.to_vec(),
"the cheapest entry is the one that goes, and it was neither the \
oldest nor the newest, so recency did not choose it"
);
assert!(
Arc::ptr_eq(&widest, &device.dispatch_plan(wide[0])),
"the widest plan must survive the sweep, since it is the one whose \
rebuild costs the most"
);
assert!(
!Arc::ptr_eq(&cheap_plan, &device.dispatch_plan(cheap)),
"an evicted shape must be rebuilt rather than resurrected, which is \
what makes the worst case merely the cost before this cache existed"
);
}
#[test]
fn the_plan_cache_keeps_a_plan_heavier_than_its_whole_ceiling() {
let device = plan_cache_fixture();
let huge = seed_heavy(PLAN_CACHE_BYTES as u32 / 8 + 1);
let first = device.dispatch_plan(huge);
assert!(
first.retained_bytes() > PLAN_CACHE_BYTES,
"the fixture must actually exceed the ceiling by itself, or this \
asserts nothing: {} bytes against {PLAN_CACHE_BYTES}",
first.retained_bytes()
);
assert!(
Arc::ptr_eq(&first, &device.dispatch_plan(huge)),
"a plan heavier than the whole ceiling must still be reused, or the \
widest dispatches pay full construction every time"
);
}
fn prose_corpus(repeats: usize) -> String {
let paragraph = "The tokenizer must agree with tiktoken byte for byte, \
which is a stronger claim than agreeing on average. A merge table \
lookup that returns the wrong rank for one pair in ten million \
still produces plausible text, and plausible is the failure mode \
that survives review. Exactness is checked against the reference \
implementation on every commit, over a corpus chosen to include \
the cases that break naive implementations: combining marks, \
zero-width joiners, unpaired surrogates written as replacement \
characters, and runs of whitespace long enough to cross a \
pretoken boundary.\n\n";
paragraph.repeat(repeats)
}
fn runs_of_lengths(lengths: &[usize]) -> Vec<Run> {
let mut start = 0_usize;
lengths
.iter()
.map(|len| {
let run = Run { start, len: *len };
start += *len;
run
})
.collect()
}
fn device_words(device: &DeviceTokenizer, corpus: &str) -> Scratch {
let mut scratch = Scratch::default();
for span in spans(device.encoding.pattern(), corpus.as_bytes()) {
let Some(bytes) = span.bytes(corpus.as_bytes()) else {
continue;
};
if bytes.len() > MAX_PRETOKEN_TOKENS {
continue;
}
scratch.push_start_state(bytes, &device.byte_token);
}
scratch
}
fn tally(device: &DeviceTokenizer, words: &Scratch, workgroups: u32) -> (usize, usize) {
for batch_indices in batches(&words.state_runs, device.batching, workgroups) {
let batch_words: Vec<&[u32]> = batch_indices
.iter()
.map(|index| words.state_runs[*index].of(&words.state))
.collect();
let longest = batch_words
.iter()
.map(|word| word.len())
.max()
.unwrap_or(1) as u32;
let shape = LoopBatch::new(&batch_words, merge_pass_bound(longest) + 1).shape();
device.dispatch_plan(shape);
}
device.plan_cache_tally()
}
const CJK_ENCODE_WORKING_SET: [LoopShape; 6] = [
LoopShape::new(1530, 91, 92),
LoopShape::new(2635, 52, 53),
LoopShape::new(1897, 25, 26),
LoopShape::new(2560, 10, 11),
LoopShape::new(3129, 4, 5),
LoopShape::new(1709, 1, 2),
];
#[test]
fn a_multi_band_encode_rebuilds_no_plan_after_the_first_encode() {
let device = plan_cache_fixture();
let budget: u32 = CJK_ENCODE_WORKING_SET
.iter()
.map(|shape| shape.max_passes())
.sum();
assert_eq!(
budget, 189,
"the fixture must be the measured working set, 189 pass waves over six \
shapes, or it no longer describes the encode that had the cliff"
);
let mut previous = (0_usize, 0_usize);
let mut per_round: Vec<(usize, usize)> = Vec::new();
for _ in 0..3 {
for shape in CJK_ENCODE_WORKING_SET {
device.dispatch_plan(shape);
}
let now = device.plan_cache_tally();
per_round.push((now.0 - previous.0, now.1 - previous.1));
previous = now;
}
assert_eq!(
per_round,
vec![(0, 6), (6, 0), (6, 0)],
"the first encode must build all six plans and no later encode may \
build any: (hits, misses) per encode was {per_round:?}"
);
assert!(
held_bytes(&device) < PLAN_CACHE_BYTES,
"reuse must not have come from an unbounded cache: {} bytes held \
against {PLAN_CACHE_BYTES}",
held_bytes(&device)
);
assert_eq!(
held_shapes(&device),
CJK_ENCODE_WORKING_SET.to_vec(),
"the whole working set must be resident, in insertion order, with \
nothing evicted"
);
}
#[test]
fn a_working_set_under_the_ceiling_never_evicts() {
let device = plan_cache_fixture();
for shape in CJK_ENCODE_WORKING_SET {
device.dispatch_plan(shape);
}
assert_eq!(
held_bytes(&device),
8_793_760,
"the measured working set's host weight is pinned, so a change in plan \
size or in PLAN_BYTES_PER_IR_NODE has to be acknowledged here"
);
assert!(
held_bytes(&device) * 4 < PLAN_CACHE_BYTES,
"the measured working set must clear the ceiling by at least 4x, or the \
cliff is one corpus away: {} bytes against {PLAN_CACHE_BYTES}",
held_bytes(&device)
);
assert_eq!(
held_shapes(&device).len(),
CJK_ENCODE_WORKING_SET.len(),
"every shape must still be resident, which is what proves the sweep \
never fired: eviction is the only thing that removes an entry"
);
}
#[test]
fn a_working_set_past_the_ceiling_keeps_reusing_its_widest_plans() {
let device = plan_cache_fixture();
let working_set = [
seed_heavy(2_400_000),
seed_heavy(2_200_000),
seed_heavy(2_000_000),
seed_heavy(1_800_000),
seed_heavy(1_600_000),
];
let weight: usize = working_set
.iter()
.map(|shape| {
let device = plan_cache_fixture();
device.dispatch_plan(*shape).retained_bytes()
})
.sum();
assert!(
weight > PLAN_CACHE_BYTES,
"the fixture must not fit, or there is nothing to degrade: {weight} \
bytes against {PLAN_CACHE_BYTES}"
);
let mut previous = (0_usize, 0_usize);
let mut per_round: Vec<(usize, usize)> = Vec::new();
for _ in 0..3 {
for shape in working_set {
device.dispatch_plan(shape);
}
let now = device.plan_cache_tally();
per_round.push((now.0 - previous.0, now.1 - previous.1));
previous = now;
}
assert_eq!(
per_round[1..],
[(3, 2), (3, 2)],
"a working set past the ceiling must settle at three reused plans and \
two rebuilt, not at zero reused: (hits, misses) per round was \
{per_round:?}"
);
assert_eq!(
held_shapes(&device)[..3],
working_set[..3],
"the three widest plans must be the resident ones, since they are the \
three whose rebuild costs the most"
);
assert!(
held_bytes(&device) <= PLAN_CACHE_BYTES,
"degrading must still respect the ceiling: {} bytes held",
held_bytes(&device)
);
}
#[test]
fn plan_cache_misses_do_not_grow_with_the_corpus() {
for (workgroups, reuse_expected) in [(1_u32, true), (3, true), (64, false)] {
let small = plan_cache_fixture();
let large = plan_cache_fixture();
let small_words = device_words(&small, &prose_corpus(16));
let large_words = device_words(&large, &prose_corpus(64));
let (small_hits, small_misses) = tally(&small, &small_words, workgroups);
let (large_hits, large_misses) = tally(&large, &large_words, workgroups);
let small_dispatches = small_hits + small_misses;
let large_dispatches = large_hits + large_misses;
println!(
"{workgroups} workgroups: {small_hits}/{small_dispatches} reused \
then {large_hits}/{large_dispatches} at four times the corpus, \
{small_misses} then {large_misses} built"
);
assert!(
large_dispatches > small_dispatches,
"the larger corpus must actually cost more dispatches or this \
measures nothing: {small_dispatches} then {large_dispatches} at \
{workgroups} workgroups"
);
assert!(
large_misses <= small_misses + 4,
"misses must be bounded by the shapes a corpus spans, not its \
size: {small_misses} misses over {small_dispatches} dispatches \
grew to {large_misses} over {large_dispatches} at {workgroups} \
workgroups"
);
if reuse_expected {
assert!(
large_hits > large_misses,
"the cache must reuse more than it builds at {workgroups} \
workgroups, where the dispatch count exceeds the shape count: \
{large_hits} hits against {large_misses} misses"
);
} else {
assert_eq!(
large_misses, large_dispatches,
"with no shape recurring, every dispatch must be a first build \
and none may be built twice: {large_misses} misses over \
{large_dispatches} dispatches at {workgroups} workgroups"
);
}
}
}
#[test]
fn every_phase_owns_exactly_one_row_of_the_table() {
let mut seen = [false; EncodePhase::ALL.len()];
for phase in EncodePhase::ALL {
let slot = phase.index();
assert!(
slot < seen.len(),
"{} indexes slot {slot}, past the {} the profile allocates",
phase.label(),
seen.len()
);
assert!(
!std::mem::replace(&mut seen[slot], true),
"{} shares slot {slot} with an earlier phase, so their costs add \
into one row and some other row can only ever read zero",
phase.label()
);
}
let labels: BTreeMap<&str, ()> = EncodePhase::ALL
.iter()
.map(|phase| (phase.label(), ()))
.collect();
assert_eq!(
labels.len(),
EncodePhase::ALL.len(),
"two phases print the same label, so a report cannot say which one a \
row belongs to"
);
}
#[test]
fn a_nested_phase_is_charged_once_rather_than_to_both_rows() {
let inner_body = Duration::from_millis(20);
let mut probe = Timed::start();
probe.measure(EncodePhase::ByteEncode, |probe| {
probe.measure(EncodePhase::HostEncode, |_| {
std::thread::sleep(inner_body);
});
});
let profile = probe.finish();
assert!(
profile.phase(EncodePhase::HostEncode) >= inner_body,
"the inner phase must carry the sleep: {:?}",
profile.phase(EncodePhase::HostEncode)
);
assert!(
profile.phase(EncodePhase::ByteEncode) < inner_body / 2,
"the enclosing phase must keep only its OWN time, not the inner \
body's: {:?} against an inner body of {inner_body:?}",
profile.phase(EncodePhase::ByteEncode)
);
assert!(
profile.named() <= profile.total(),
"the named rows may never sum past the call they were measured \
inside: {:?} named against {:?} total",
profile.named(),
profile.total()
);
}
#[test]
fn time_outside_every_phase_lands_in_the_remainder() {
let unmeasured = Duration::from_millis(20);
let mut probe = Timed::start();
probe.measure(EncodePhase::Batching, |_| {});
std::thread::sleep(unmeasured);
let profile = probe.finish();
assert!(
profile.unattributed() >= unmeasured,
"time no phase measured must show up as the remainder: {:?} against \
{unmeasured:?} spent outside every phase",
profile.unattributed()
);
assert_eq!(
profile.named() + profile.unattributed(),
profile.total(),
"the named rows plus the remainder must be the observed call, or the \
table is not a breakdown of anything"
);
}
fn merging_fixture() -> DeviceTokenizer {
let mut byte_token = [TokenId(0); 256];
for (byte, token) in byte_token.iter_mut().enumerate() {
*token = TokenId(byte as u32);
}
let table = RankTable::from_entries(
"session fixture",
[
(PairKey::new(TokenId(b't' as u32), TokenId(b'h' as u32)), TokenId(256), Rank(0)),
(PairKey::new(TokenId(256), TokenId(b'e' as u32)), TokenId(257), Rank(1)),
(PairKey::new(TokenId(257), TokenId(b' ' as u32)), TokenId(258), Rank(2)),
(PairKey::new(TokenId(b'e' as u32), TokenId(b'r' as u32)), TokenId(259), Rank(3)),
(PairKey::new(TokenId(b'o' as u32), TokenId(b'o' as u32)), TokenId(260), Rank(4)),
],
)
.expect("the fixture's five rows must build");
DeviceTokenizer {
encoding: Encoding::cl100k_base(),
table,
byte_token,
batching: Batching::default(),
dispatches: AtomicUsize::new(0),
block_ceilings: RwLock::new(Vec::new()),
table_bytes: OnceLock::new(),
plans: RwLock::new(Vec::new()),
plan_hits: AtomicUsize::new(0),
plan_misses: AtomicUsize::new(0),
plan_rebuilds: AtomicU64::new(0),
output_batch_checks: AtomicU64::new(0),
output_segment_guards: AtomicU64::new(0),
host_lookups: AtomicU64::new(0),
host_merges: AtomicU64::new(0),
workgroup_override: None,
}
}
fn cpu() -> vyre_driver_reference::CpuRefBackend {
vyre_driver_reference::CpuRefBackend
}
const SESSION_CORPUS: &[&[u8]] = &[
b"theresoooo therefore the other",
b"the there theresoooo",
b"other",
b"the",
b"",
];
fn per_call_ids(device: &DeviceTokenizer, inputs: &[&[u8]]) -> Vec<Vec<TokenId>> {
device
.encode_batch(&cpu(), inputs)
.expect("the reference backend must encode the fixture corpus")
.into_ids()
}
fn pooled(session: &DeviceSession<'_>) -> usize {
session
.scratch
.lock()
.unwrap_or_else(PoisonError::into_inner)
.len()
}
#[test]
fn a_session_returns_the_unbound_paths_ids() {
let device = merging_fixture();
let backend = cpu();
let expected = per_call_ids(&device, SESSION_CORPUS);
assert!(
expected.iter().any(|ids| ids.iter().any(|id| id.0 >= 256)),
"the fixture must actually merge, or this compares two encoders that \
both just copy bytes: got {expected:?}"
);
let session = device.bind(&backend).expect("binding must succeed");
for round in 0..3 {
let ids = session
.encode_batch(SESSION_CORPUS)
.expect("a session encode must succeed")
.into_ids();
assert_eq!(
ids, expected,
"session encode {round} must return the unbound path's ids exactly"
);
}
}
#[test]
fn a_sessions_single_input_encode_matches_the_tokenizers() {
let device = merging_fixture();
let backend = cpu();
let session = device.bind(&backend).expect("binding must succeed");
for input in SESSION_CORPUS {
let unbound = device
.encode(&backend, input)
.expect("the unbound single-input encode must succeed");
let bound = session
.encode(input)
.expect("the session single-input encode must succeed");
assert_eq!(
bound,
unbound,
"a session's encode of {} bytes must equal the tokenizer's",
input.len()
);
}
}
#[test]
fn an_encode_after_a_larger_one_matches_that_encode_alone() {
let device = merging_fixture();
let backend = cpu();
let second: &[&[u8]] = &[b"the other", b"theresoooo"];
let alone = per_call_ids(&device, second);
let session = device.bind(&backend).expect("binding must succeed");
session
.encode_batch(SESSION_CORPUS)
.expect("the priming encode must succeed");
let after = session
.encode_batch(second)
.expect("the second encode must succeed")
.into_ids();
assert_eq!(
after, alone,
"an encode on used buffers must equal the same encode on fresh ones, \
or a stale word from the previous encode is reaching an id"
);
}
#[test]
fn a_scratch_dirtied_on_one_thread_answers_exactly_on_another() {
let device = merging_fixture();
let backend = cpu();
let second: &[&[u8]] = &[b"the other", b"theresoooo"];
let alone = per_call_ids(&device, second);
let session = device.bind(&backend).expect("binding must succeed");
session
.encode_batch(SESSION_CORPUS)
.expect("the priming encode must succeed");
assert_eq!(
pooled(&session),
1,
"the primed scratch must be back in the pool, or the next encode \
cannot be the one that reuses it"
);
let after = std::thread::scope(|scope| {
scope
.spawn(|| {
session
.encode_batch(second)
.expect("the borrowed-thread encode must succeed")
.into_ids()
})
.join()
.expect("the encoding thread must not panic")
});
assert_eq!(
after, alone,
"a scratch dirtied on another thread must answer exactly, or the \
reset is thread-local in a way the pool does not honour"
);
}
#[test]
fn overlapping_encodes_hold_distinct_scratches() {
const THREADS: usize = 4;
const ROUNDS: usize = 8;
let device = merging_fixture();
let backend = cpu();
let expected = per_call_ids(&device, SESSION_CORPUS);
let session = device.bind(&backend).expect("binding must succeed");
let start = std::sync::Barrier::new(THREADS);
std::thread::scope(|scope| {
for _ in 0..THREADS {
scope.spawn(|| {
start.wait();
for _ in 0..ROUNDS {
let ids = session
.encode_batch(SESSION_CORPUS)
.expect("a concurrent session encode must succeed")
.into_ids();
assert_eq!(
ids, expected,
"a concurrent encode must return the same ids as a \
lone one"
);
}
});
}
});
assert!(
pooled(&session) >= 2,
"{THREADS} threads running {ROUNDS} encodes each past a barrier must \
have held at least two scratches at once, so the pool must retain at \
least two; it holds {}, which is what a single scratch guarded across \
the whole encode would leave",
pooled(&session)
);
assert!(
pooled(&session) <= SCRATCH_POOL_LIMIT,
"the pool must stay inside its own bound: {} sets retained past a \
limit of {SCRATCH_POOL_LIMIT}",
pooled(&session)
);
}
#[test]
fn a_session_keeps_the_capacity_its_encodes_grew() {
let device = merging_fixture();
let backend = cpu();
let session = device.bind(&backend).expect("binding must succeed");
session
.encode_batch(SESSION_CORPUS)
.expect("the first encode must succeed");
let device_bytes: usize = SESSION_CORPUS
.iter()
.flat_map(|input| spans(device.encoding.pattern(), input))
.map(|span| span.len())
.filter(|len| *len <= MAX_PRETOKEN_TOKENS)
.sum();
let grown = {
let pool = session.scratch.lock().unwrap_or_else(PoisonError::into_inner);
let scratch = pool.first().expect("the encode must return its scratch");
assert!(
!scratch.state.is_empty() && !scratch.ids.is_empty(),
"a pooled scratch holds the previous encode's words: the reset is \
on entry, so that the error paths are covered by it too"
);
(scratch.state.capacity(), scratch.ids.capacity())
};
assert!(
grown.0 >= device_bytes,
"the state buffer must retain room for the {device_bytes} start-state \
words the encode wrote, not {} ",
grown.0
);
session
.encode_batch(SESSION_CORPUS)
.expect("the second encode must succeed");
let pool = session.scratch.lock().unwrap_or_else(PoisonError::into_inner);
let scratch = pool.first().expect("the encode must return its scratch");
assert_eq!(
(scratch.state.capacity(), scratch.ids.capacity()),
grown,
"an identical second encode must reuse the capacity the first grew \
rather than allocating again"
);
}
#[test]
fn batching_mode_does_not_change_a_sessions_ids() {
let backend = cpu();
let mut expected = None;
for mode in [Batching::InputOrder, Batching::ByLength] {
let mut device = merging_fixture();
device.batching = mode;
let session = device.bind(&backend).expect("binding must succeed");
let ids = session
.encode_batch(SESSION_CORPUS)
.expect("a session encode must succeed")
.into_ids();
match &expected {
None => expected = Some(ids),
Some(first) => assert_eq!(
&ids, first,
"{mode:?} must return the same ids as the first mode: a \
grouping change may reorder DISPATCHES and may never reorder \
ids"
),
}
}
}
#[test]
fn a_session_on_a_backend_without_resident_dispatch_still_encodes() {
let device = merging_fixture();
let backend = cpu();
assert!(
!backend.supports_resident_dispatch(),
"this test is about the no-resident-dispatch path; the reference \
backend having gained one makes it vacuous"
);
let expected = per_call_ids(&device, SESSION_CORPUS);
let session = device.bind(&backend).expect("binding must succeed");
assert!(
session.table.is_none(),
"a backend with no resident dispatch must hold no resident table"
);
let ids = session
.encode_batch(SESSION_CORPUS)
.expect("the encode must succeed with a host-input table")
.into_ids();
assert_eq!(ids, expected, "the ids must not depend on where the table sat");
session
.close()
.expect("closing a session that holds no buffer must succeed");
}
#[cfg(feature = "cuda")]
#[test]
fn a_session_charges_nothing_for_the_merge_table() {
let backend = vyre_driver_cuda::cuda_factory()
.expect("a CUDA device is required by this test and must not be skipped past");
assert!(
backend.supports_resident_dispatch(),
"the CUDA backend must offer resident dispatch, or this asserts nothing"
);
let device = merging_fixture();
let (_, unbound) = device
.encode_batch_profiled(backend.as_ref(), SESSION_CORPUS)
.expect("the unbound encode must succeed");
assert!(
unbound.phase(EncodePhase::TableUpload) > Duration::ZERO,
"the unbound path must still upload the table, or this test would \
pass on a path that stopped dispatching at all"
);
let session = device.bind(backend.as_ref()).expect("binding must succeed");
assert!(
session.table.is_some(),
"a resident-dispatch backend must leave the session holding the table"
);
for round in 0..2 {
let (_, profile) = session
.encode_batch_profiled(SESSION_CORPUS)
.expect("a session encode must succeed");
for phase in [
EncodePhase::TablePack,
EncodePhase::TableUpload,
EncodePhase::TableFree,
] {
assert_eq!(
profile.phase(phase),
Duration::ZERO,
"session encode {round} must not enter {}, which the bind \
already paid for",
phase.label()
);
}
}
session
.close()
.expect("the backend must accept its own resident buffer back");
}
}