pretokie 0.0.1

Fast, zero-allocation pretokenizers for BPE tokenizers
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246

//! Test if callback-based pretokenization (no Iterator overhead) is faster.
//!
//! Instead of yielding one piece at a time via next() → Option<&str>,
//! use an inline callback: for_each_piece(text, |piece| { ... }).
//! The compiler can inline the callback, eliminating per-piece function-call overhead.
//!
//! Usage: cargo run -p pretokie --example bench_callback --release

use pretokie::Gpt2;
use pretokie::util::{decode_utf8, is_ascii_letter, is_digit};
use std::time::Instant;

#[cfg(target_arch = "aarch64")]
use std::arch::aarch64::*;

#[cfg(target_arch = "aarch64")]
#[inline(always)]
unsafe fn first_non_letter_16(ptr: *const u8) -> usize {
    let chunk = vld1q_u8(ptr);
    let lowered = vorrq_u8(chunk, vdupq_n_u8(0x20));
    let offset = vsubq_u8(lowered, vdupq_n_u8(b'a'));
    let is_letter = vcltq_u8(offset, vdupq_n_u8(26));
    if vminvq_u8(is_letter) == 0xFF { return 16; }
    let not_letter = vmvnq_u8(is_letter);
    static POWERS: [u8; 16] = [1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8, 16, 32, 64, 128];
    let powers = vld1q_u8(POWERS.as_ptr());
    let bits = vandq_u8(not_letter, powers);
    let lo = vaddv_u8(vget_low_u8(bits)) as u16;
    let hi = vaddv_u8(vget_high_u8(bits)) as u16;
    let bitmask = lo | (hi << 8);
    bitmask.trailing_zeros() as usize
}

// ---------------------------------------------------------------------------
// Callback-based pretokenizer
// ---------------------------------------------------------------------------

#[inline(always)]
fn scan_letters(bytes: &[u8], mut pos: usize, len: usize) -> usize {
    #[cfg(target_arch = "aarch64")]
    unsafe {
        while pos + 16 <= len {
            let n = first_non_letter_16(bytes.as_ptr().add(pos));
            pos += n;
            if n < 16 {
                if pos < len && *bytes.get_unchecked(pos) >= 0x80 {
                    let (ch, cl) = decode_utf8(&bytes[pos..]);
                    if ch.is_alphabetic() { pos += cl; continue; }
                }
                return pos;
            }
        }
    }
    while pos < len {
        let b = unsafe { *bytes.get_unchecked(pos) };
        if is_ascii_letter(b) { pos += 1; }
        else if b >= 0x80 {
            let (ch, cl) = decode_utf8(&bytes[pos..]);
            if ch.is_alphabetic() { pos += cl; } else { return pos; }
        } else { return pos; }
    }
    pos
}

#[inline(always)]
fn scan_digits(bytes: &[u8], mut pos: usize, len: usize) -> usize {
    while pos < len && is_digit(unsafe { *bytes.get_unchecked(pos) }) {
        pos += 1;
    }
    pos
}

#[inline(always)]
fn check_contraction(bytes: &[u8], pos: usize, len: usize) -> usize {
    if pos >= len || bytes[pos] != b'\'' { return 0; }
    let rem = len - pos;
    if rem < 2 { return 0; }
    let b1 = bytes[pos + 1];
    if matches!(b1, b's' | b't' | b'd' | b'm') {
        if rem == 2 || !is_ascii_letter(bytes[pos + 2]) { return 2; }
    }
    if rem < 3 { return 0; }
    let b2 = bytes[pos + 2];
    if (b1 == b'l' && b2 == b'l') || (b1 == b'v' && b2 == b'e') || (b1 == b'r' && b2 == b'e') {
        return 3;
    }
    0
}

#[inline(always)]
fn scan_punct(bytes: &[u8], mut pos: usize, len: usize) -> usize {
    while pos < len {
        let b = unsafe { *bytes.get_unchecked(pos) };
        if is_ascii_letter(b) || is_digit(b) || b == b' ' || b == b'\n' || b == b'\r' || b >= 0x80 {
            break;
        }
        pos += 1;
    }
    pos
}

/// Process all pieces via inline callback. No Iterator, no Option, no per-piece dispatch overhead.
#[inline(always)]
fn for_each_piece<F: FnMut(usize, usize)>(text: &str, mut f: F) {
    let bytes = text.as_bytes();
    let len = bytes.len();
    let mut pos = 0;

    while pos < len {
        let start = pos;
        let b = unsafe { *bytes.get_unchecked(pos) };

        if is_ascii_letter(b) {
            pos = scan_letters(bytes, pos + 1, len);
            if check_contraction(bytes, pos, len) > 0 {
                f(start, pos);
                continue;
            }
        } else if b == b' ' {
            pos += 1;
            if pos < len {
                let next = unsafe { *bytes.get_unchecked(pos) };
                if is_ascii_letter(next) {
                    pos = scan_letters(bytes, pos + 1, len);
                    if check_contraction(bytes, pos, len) > 0 {
                        f(start, pos);
                        continue;
                    }
                } else if next >= 0x80 {
                    let (ch, _) = decode_utf8(&bytes[pos..]);
                    if ch.is_alphabetic() {
                        pos = scan_letters(bytes, pos, len);
                    }
                } else if is_digit(next) {
                    pos = scan_digits(bytes, pos + 1, len);
                }
            }
        } else if b == b'\'' {
            let clen = check_contraction(bytes, pos, len);
            if clen > 0 {
                pos += clen;
            } else {
                pos = scan_punct(bytes, pos + 1, len);
            }
        } else if is_digit(b) {
            pos = scan_digits(bytes, pos + 1, len);
        } else if b == b'\n' || b == b'\r' {
            pos += 1;
            while pos < len {
                let c = unsafe { *bytes.get_unchecked(pos) };
                if c == b'\n' || c == b'\r' || c == b' ' { pos += 1; }
                else { break; }
            }
        } else if b >= 0x80 {
            let (ch, cl) = decode_utf8(&bytes[pos..]);
            pos += cl;
            if ch.is_alphabetic() {
                pos = scan_letters(bytes, pos, len);
            } else if ch.is_whitespace() {
                while pos < len {
                    let c = unsafe { *bytes.get_unchecked(pos) };
                    if c == b' ' || c == b'\n' || c == b'\r' { pos += 1; }
                    else if c >= 0x80 {
                        let (ch2, cl2) = decode_utf8(&bytes[pos..]);
                        if ch2.is_whitespace() { pos += cl2; } else { break; }
                    } else { break; }
                }
            }
        } else {
            pos = scan_punct(bytes, pos + 1, len);
        }

        f(start, pos);
    }
}

fn main() {
    let path = std::env::var("ENWIK8_PATH")
        .unwrap_or_else(|_| "crates/tokie/benches/data/enwik8".to_string());
    let text = std::fs::read_to_string(&path).expect("need enwik8");
    let mb = text.len() as f64 / (1024.0 * 1024.0);
    println!("Input: {:.2} MB\n", mb);

    // Correctness: count with callback vs iterator
    let ref_count = Gpt2::new(&text).count();
    let mut cb_count = 0usize;
    for_each_piece(&text, |_, _| { cb_count += 1; });
    println!("Iterator:  {ref_count} pieces");
    println!("Callback:  {cb_count} pieces");
    if ref_count != cb_count {
        println!("MISMATCH! Finding divergence...");
        let mut iter = Gpt2::new(&text);
        let mut pieces = Vec::new();
        for_each_piece(&text, |s, e| { pieces.push((s, e)); });
        for (i, &(s, e)) in pieces.iter().enumerate() {
            let cb_piece = &text[s..e];
            let it_piece = iter.next();
            if it_piece != Some(cb_piece) {
                println!("  at {i}: iter={it_piece:?} cb={cb_piece:?}");
                break;
            }
        }
        return;
    }
    println!("Correctness: OK\n");

    let iters = 20;

    // Benchmark: iterator count
    {
        let _ = Gpt2::new(&text).count();
        let start = Instant::now();
        let mut c = 0;
        for _ in 0..iters { c = Gpt2::new(&text).count(); }
        let t = mb * iters as f64 / start.elapsed().as_secs_f64();
        println!("Iterator:    {t:>8.1} MB/s  ({c} pieces)");
    }

    // Benchmark: callback count
    {
        let mut c = 0usize;
        for_each_piece(&text, |_, _| { c += 1; });
        c = 0;
        let start = Instant::now();
        for _ in 0..iters {
            c = 0;
            for_each_piece(&text, |_, _| { c += 1; });
        }
        let t = mb * iters as f64 / start.elapsed().as_secs_f64();
        println!("Callback:    {t:>8.1} MB/s  ({c} pieces)");
    }

    // Benchmark: callback producing Vec<(u32,u32)> of boundaries
    {
        let mut bounds: Vec<(u32, u32)> = Vec::with_capacity(25_000_000);
        for_each_piece(&text, |s, e| { bounds.push((s as u32, e as u32)); });
        bounds.clear();
        let start = Instant::now();
        for _ in 0..iters {
            bounds.clear();
            for_each_piece(&text, |s, e| { bounds.push((s as u32, e as u32)); });
        }
        let t = mb * iters as f64 / start.elapsed().as_secs_f64();
        println!("CB+Vec:      {t:>8.1} MB/s  ({} pieces)", bounds.len());
    }
}