Meningkatkan Performa CPU Tokenizer Unigram

Kami mengimplementasikan ulang tokenizer Unigram kami dari awal sebagai proyek fokus performa. Pada panjang input produksi, encoder baru memotong latensi p50 sekitar 5× dibandingkan dengan crate tokenizer Hugging Face, ~2× dibandingkan SentencePiece (C++), dan ~1.5× dibandingkan tokenizer IREE (C), dengan alokasi heap status-stabil nol. Dalam produksi, ini mengurangi utilisasi CPU pada tumpukan inferensi kami sebesar 5-6× dan memangkas latensi reranker sebesar puluhan milidetik.

Biaya inferensi LLM biasanya dibingkai sebagai pekerjaan GPU: cache KV, kernel attention, perutean pakar. Namun, sebagian besar lalu lintas produksi berjalan pada model yang jauh lebih kecil, dua hingga tiga tingkat besaran lebih kecil daripada transformer teratas. Model embedding, pengklasifikasi, dan reranker tetap berjalan di GPU, tetapi lolosan maju (forward pass) cukup singkat sehingga segala hal di sekitarnya mulai menjadi penting.

Kasus yang paling jelas adalah reranker yang menilai ratusan dokumen kandidat per permintaan. Dengan model kecil, komputasi GPU biasanya selesai dalam milidetik satu digit, tetapi setiap input tetap harus melalui tokenisasi sisi CPU terlebih dahulu, mengubah teks menjadi ID kosakata. Ketika batch besar, itu dapat menyumbang sebagian besar dari total latensi permintaan.

Pekerjaan ini menargetkan XLM-RoBERTa, kosakata Unigram 250K token yang dilatih dengan SentencePiece. Encoder keluarga RoBERTa yang disetel halus (fine-tuned) adalah pilihan umum untuk tugas peringkat, peng Pengecekan, dan kemiripan. Kami melaporkan latensi per-encode berulir tunggal (single-threaded) secara keseluruhan; dalam produksi, kami melakukan paralelisasi di seluruh inti menggunakan rayon.

Sepanjang postingan ini, kami memperlakukan tokenizers crate Hugging Face sebagai referensi yang kami jadikan tolok ukur, karena ini adalah tokenizer Rust default yang biasa digunakan oleh sebagian besar tim. SentencePiece (C++) dan IREE (C) disertakan untuk perbandingan sebagai dua implementasi produksi utama lainnya.

Tokenisasi unigram, yang diperkenalkan oleh Kudo pada tahun 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) dan dikirimkan di SentencePiece, membingkai segmentasi sebagai masalah jalur-paling-mungkin (most-probable-path): setiap token kosakata memiliki log-probabilitas yang dipelajari, dan encoder memilih segmentasi yang skor tokennya dijumlahkan ke nilai tertinggi. Masalah ini diselesaikan dengan algoritma Viterbi (1967), dengan posisi byte sebagai lapisan grafik dan token kosakata sebagai sisi yang merentang pada rentang byte yang berdekatan. Rekurensi tersebut adalah pemrograman dinamis (DP) satu dimensi atas posisi byte:

python

best = [-inf] * (n + 1)
best[0] = 0
back = [None] * (n + 1)

for i in 0..n:
    if best[i] == -inf:
        continue
    if byte i is a UTF-8 continuation byte:
        continue

    walk the vocabulary trie from byte position i:
        for each matching token t ending at position j:
            cand = best[i] + score(t)
            if cand > best[j]:
                best[j] = cand
                back[j] = (i, token_id(t))

    if no token matched, fall back to <unk>

backtrack from position n using back[] to recover token IDs

Perulangan luar bersifat linier terhadap panjang input, dibatasi pada setiap posisi oleh token kosakata terpanjang (48 byte UTF-8 untuk XLM-RoBERTa). Penelusuran trie bagian dalam adalah jalur panas (hot path): pada input 16k token, program ini menjalankan ratusan ribu transisi dan mempensiunkan puluhan juta instruksi per encode.

Tokenizers v0.22 Hugging Face mengimplementasikan rekurensi secara langsung, dengan peta hash untuk pencarian terbalik dan anak peta-hash di setiap simpul trie:

rust

vocab:        Vec<(String, f64)>           // indexed by token ID
token_to_ids: AHashMap<String, u32>        // reverse lookup
trie:         Trie<u8>                     // byte-level prefix trie

struct Node<Label> {
    is_leaf: bool,
    children: AHashMap<Label, Node<Label>>, // heap-allocated map per node
}

Dan perulangan bagian dalam (disederhanakan) – setiap kecocokan pencarian awalan mengalokasikan string baru lalu menyelidiki peta hash:

rust

fn encode_optimized(&self, sentence: &str) -> Result<Vec<String>> {
    // alloc
    let mut best = vec![BestPathNode::default(); sentence.len() + 1];

    let mut starts_at = 0;
    while starts_at < sentence.len() {
        for tok_bytes in self.trie.common_prefix_search(sentence.bytes().skip(starts_at)) {
            // alloc per match
            let token: String = String::from_utf8(tok_bytes).unwrap();
            // hash lookup
            let id = self.token_to_ids.get(&token).unwrap();
            let score = self.vocab[*id as usize].1;
            // DP update at best[starts_at + tok_bytes.len()]
            // ...
        }
        starts_at += mblen;
    }
    // backtrace into Vec<String>, one allocation per output token
}

Kode tersebut adalah Rust yang mudah dibaca, tetapi banyak pekerjaan terjadi yang tidak terlihat di tingkat sumber. Bagian selanjutnya merinci kemana waktu tersebut dihabiskan.

Sebelum Viterbi berjalan, input melewati normalisasi Unicode (NFKC) dan penandaan batas kata. Pemprofilan menempatkan pra-pemrosesan kurang dari 5% dari total waktu encode dalam skenario kami, jadi kami fokus pada lolosan maju Viterbi untuk sisa postingan ini.

Ada dua cara untuk mempercepat kode CPU: mengeksekusi lebih sedikit instruksi, atau mendapatkan IPC yang lebih tinggi. Cachegrind mengukur yang pertama, perf stat mengukur yang kedua. Setiap pengoptimalan dalam postingan ini mendarat di salah satu atau keduanya.

CPU berhenti (stall) pada empat hal: miss cache (L1d ~4 siklus, miss L3 ke DRAM adalah ratusan), rantai muatan dependen (dependent-load) yang tidak dapat diparalelisasi oleh mesin out-of-order, kesalahan prediksi cabang (~15-20 siklus dibersihkan per tebakan salah), dan panggilan alokator. Implementasi mesin unigram referensi mengenai keempatnya:

Bottleneck	Mekanisme	Dampak terukur
Alokasi per kecocokan	String::from_utf8 pada byte yang cocok ditambah pencarian AHashMap per kecocokan trie; ID token sudah ada di daun, tetapi referensi tidak menyimpannya di sana	7.295 alokasi pada 512 token, 14.542 pada 1k, 299.171 pada 16k
Pengejaran pointer per byte	AHashMap di setiap simpul trie, melakukan hashing pada byte berikutnya dan mendereferensikan dua pointer per langkah; struct Node juga menggabungkan bidang dingin seperti is_leaf, menariknya ke dalam cache pada setiap kunjungan	Tingkat miss L1d tetap rendah (~2,5% pada 1k) karena halaman panas alokator hidup di L1; biaya muncul sebagai latensi muatan dependen
Thrashing L2 pada input panjang	Tabel DP, goresan awalan (prefix scratch), dan daftar token keluaran semuanya dialokasikan baru setiap panggilan	Tingkat miss L2 naik dari 12% pada 128 token menjadi 50% pada 16k karena jejak alokasi kumulatif melebihi L2 2 MB per inti

Referensi bottleneck tokenizer, mekanisme, dan dampak terukur.

Biaya dominan adalah alokasi per kecocokan. Pada 1k token, implementasi referensi memensiunkan (menyelesaikan) sekitar 7M instruksi per encode pada IPC 2,8, sebagian besar di antaranya dalam panggilan alokasi dan konversi string. Miss L2 hanya penting setelah ~1k token, begitu jejak alokasi kumulatif meluap ke cache per inti.

Latensi p50 dan p99 tokenizer referensi berdasarkan ukuran input.

Tingkat cache miss L2 tokenizer referensi berdasarkan ukuran input.

Byte yang dialokasikan per encode oleh tokenizer referensi di berbagai ukuran input.

Alokasi per token bersifat konstan: sekitar 2 KB dan ~18 alokasi per token, terlepas dari ukuran input. Non-linieritas latensi berasal dari L2: byte kumulatif melewati 2 MB sekitar 1k token, tingkat miss naik dari 8% menjadi ~50%, dan kurva p99 melengkung untuk menyesuaikan.

Kami membandingkan tiga tokenizer produksi, semuanya menjalankan algoritma Unigram yang sama terhadap model XLM-RoBERTa yang sama:

Mesin	Bahasa	Trie
Hugging Face	Rust	Trie awalan anak HashMap
SentencePiece	C++	Trie array ganda Darts
Tokenizer IREE	C	Trie array ganda Darts

Implementasi tokenizer, bahasa, dan representasi trie yang digunakan dalam perbandingan.

Kami menautkan SentencePiece dan IREE melalui FFI C/C++ langsung alih-alih pembungkus Rust mereka; pembungkus tersebut menambahkan alokasi per panggilan dan konversi string yang bukan bagian dari biaya perpustakaan mendasar.

Semua mesin dibangun dengan pengoptimalan penuh (O3, penargetan asli, pengoptimalan waktu tautan). Pengukuran berjalan disematkan pada satu inti yang tenang pada Intel Xeon Platinum 8488C. Untuk setiap mesin dan ukuran input, kami mengumpulkan latensi jam dinding (p50 dan p99, 10.000 iterasi setelah 1.000 pemanasan), instruksi yang dipensiunkan melalui Valgrind cachegrind, tingkat miss IPC dan cache dari penghitung perangkat keras perf stat, dan alokasi heap yang dihitung oleh pembungkus alokator global di sekitar jendela yang diukur.

Pada 514 token (+2 di atas 512 adalah injeksi BOS/EOS):

Implementasi	Latensi p50	Instruksi	IPC	Alokasi
Hugging Face	349 µs	3,60M	2,89	7.295
SentencePiece	128 µs	1,83M	3,39	1.559
IREE	112 µs	2,28M	3,06	1

Latensi tokenizer, jumlah instruksi, IPC, dan alokasi pada 514 token.

SP dan IREE mendarat pada sekitar sepertiga dari latensi referensi. Mereka memensiunkan sekitar setengah instruksi, berjalan pada IPC yang lebih tinggi, dan mengalokasikan satu hingga dua tingkat besaran yang lebih sedikit.

SentencePiece dan IREE sama-sama menggunakan trie array ganda yang diperkenalkan oleh Aoe pada tahun 1989 (Aoe, 1989; Karoonboonyanan). Trie dikodekan dalam dua array bilangan bulat datar, base dan check:

cpp

int base[N];   // base[node] = offset for this node's children
int check[N];  // check[child] == node validates the parent-child link

Pencarian anak adalah:

cpp

int next = base[node] + byte;
if (check[next] == node) { /* valid transition; child node = next */ }

Setiap langkah penelusuran trie hanya memerlukan dua pemuatan array, satu penambahan bilangan bulat, dan satu perbandingan, tanpa hashing, tanpa pengejaran pointer, dan tanpa alokasi heap per simpul. Konstruksi menempatkan setiap simpul sedemikian rupa sehingga anak-anaknya jatuh pada slot gratis dalam array validasi, memungkinkan beberapa orang tua berbagi wilayah selama anak-anak mereka berbeda pada byte yang mereka ikuti.

Untuk kosakata 250K XLM-RoBERTa, seluruh trie pas dalam ~9 MB memori kontinu (~780K slot × 12 byte untuk offset, validasi, dan ID token per slot). Kumpulan kerja panas satu encode berada di kisaran 100 KB, pas di L2, dan prefetcher perangkat keras mengunci pola akses reguler.

Sebaliknya, referensi menyimpan peta hash anak per simpul, yang membebani sekitar empat muatan dependen per langkah byte. Lakukan hash pada byte, muat bucket, ikuti pointer ke entri bucket, ikuti pointer lain ke simpul anak di heap, lalu konsultasikan peta hash-nya sendiri untuk byte berikutnya. Objek heap berpencar dan sebagian besar muatan mengalami miss cache.

SP dan IREE sama-sama menyimpan ID token secara langsung di simpul trie. Implementasi trie referensi hanya mengembalikan byte yang cocok, sehingga encoder harus mengalokasikan string baru untuk setiap kecocokan, mencarinya di peta hash samping untuk memulihkan ID token, dan membaca skor dari vektor terpisah. SP mengembalikan ID sebagai nilai tersimpan trie dan membaca skor dari array float datar:

cpp

// unigram_model.cc:567
const size_t num_nodes = trie_->commonPrefixSearch(
    begin, trie_results.data(), trie_results.size(),
    static_cast<int>(end - begin));

for (size_t k = 0; k < num_nodes; ++k) {
    const int   id    = trie_results[k].value;   // already in the trie
    const float score = GetScoreInlined(id);     // flat float[] indexed by id
    Lattice::Node *node = lattice->Insert(begin_pos, length);
    node->id = id;
    node->score = score;
}

IREE menggunakan API kursor stateful alih-alih mengembalikan semua kecocokan dalam satu panggilan, tetapi model biayanya sama: ID token dan skor dapat dijangkau sebagai indeks array datar, tanpa alokasi atau hashing pada penelusuran trie itu sendiri. IREE hanya mengalokasikan satu buffer keluaran per encode; SP juga mengalokasikan simpul kisi per kecocokan selama DP, totalnya sekitar 1.559 alokasi pada 514 token.

Sebelum mengubah trie, kami mengisolasi biaya algoritma dari biaya implementasi: seberapa cepat referensi berjalan dengan pekerjaan yang tidak perlu dihapus?

Baseline mempertahankan trie anak peta-hash referensi tetapi membuat dua perubahan. Struct goresan (scratch) milik pemanggil memegang tabel DP, byte yang telah diproses sebelumnya, dan ID token keluaran, sehingga jalur panas tidak melakukan alokasi setelah pemanasan. ID token dan skor disimpan langsung di simpul trie, menghilangkan konversi string per kecocokan dan pencarian peta hash samping.

Perulangan dalam:

rust

for pos in 0..n {
    if scratch.prep[pos] & 0xC0 == 0x80 { continue; }
    let s0 = scratch.best_score[pos];
    if s0 == f32::NEG_INFINITY { continue; }

    let mut node = 0u32;
    for end in pos..n {
        let byte = scratch.prep[end];
        match self.nodes[node as usize].children.get(&byte) {
            Some(&child) => {
                node = child;
                let n = &self.nodes[node as usize];
                if n.is_terminal {
                    let total = s0 + n.score;
                    if total > scratch.best_score[end + 1] {
                        scratch.best_score[end + 1] = total;
                        scratch.best_start[end + 1] = pos as u32;
                        scratch.best_id[end + 1] = n.token_id;
                    }
                }
            }
            None => break,
        }
    }
}

Ini adalah algoritma yang sama, dengan bentuk trie yang sama dan pola akses yang sama, hanya tanpa alokasi dan tanpa pencarian berlebihan. Hasil pada 514 token:

Mesin	p50	Instruksi	IPC	Alokasi
Hugging Face	326 µs	3,66M	2,86	7.295
SentencePiece	127 µs	1,81M	3,55	1.559
IREE	111 µs	1,58M	3,26	1
Baseline	156 µs	1,53M	2,62	0

Baseline tanpa alokasi dibandingkan dengan implementasi tokenizer yang sudah ada pada 514 token.

Menghilangkan materialisasi string per kecocokan dan pencarian peta hash sekunder memangkas instruksi 2,4× dibandingkan referensi. IPC turun dengannya (2,86 → 2,62) karena pengejaran pointer peta hash, yang sebelumnya tersembunyi di balik pekerjaan alokator, sekarang menjadi biaya per byte yang dominan.

Latensi p50 dan p99 tokenizer referensi dan baseline tanpa alokasi berdasarkan ukuran input.

Tingkat cache miss L2 tokenizer referensi dan baseline tanpa alokasi berdasarkan ukuran input.

Baseline memotong latensi p50 sebesar 2-3× dibandingkan referensi pada setiap ukuran, dan tingkat miss L2 tetap mendekati 2-3% melalui 2k token berbanding 8-48% milik referensi. Biaya yang tersisa adalah pengejaran pointer HashMap, yang dibahas di bagian selanjutnya.

Trie peta-hash adalah pengejaran pointer. SP dan IREE memecahkan ini dengan trie array ganda (lihat bagian sebelumnya), dan kami meminjam struktur data yang sama. Perbedaannya adalah SP dan IREE adalah pustaka tujuan umum yang mendukung input streaming, offset keluaran, dan beberapa mode penyandian; fleksibilitas tersebut membebani mereka dengan pembukuan ekstra di sekitar trie (kisi di SP, pipa delapan tahap di IREE). Kami tidak membutuhkan semua itu, jadi kami menyematkan trie secara langsung ke dalam perulangan Viterbi dan membuang sisanya.

rust

fn child(&self, node: u32, byte: u8) -> Option<u32> {
    let base = self.base[node as usize];
    let next = base + byte as i32;
    if self.check[next as usize] == node as i32 {
        Some(next as u32)
    } else {
        None
    }
}

Langkah byte memerlukan biaya dua pembacaan array, penambahan bilangan bulat, dan perbandingan. Seluruh trie adalah sekitar 9 MB, tetapi encode tunggal apa pun hanya menelusuri ~100 KB darinya, sehingga data panas tetap berada di L2.

Mesin	p50	p99	Instruksi	% miss L2	% miss L3
Hugging Face	327 µs	3.340 µs	3,66M	8,17%	14,66%
SentencePiece	127 µs	1.140 µs	1,82M	4,74%	4,07%
IREE	111 µs	132 µs	1,61M	5,82%	3,87%
Baseline	155 µs	1.170 µs	1,53M	2,59%	16,66%
+ Darts	68 µs	80 µs	1,10M	6,45%	11,42%

Latensi tokenizer, instruksi, dan tingkat cache miss setelah mengadopsi double-array trie.

Jam dinding turun 2,3× dari baseline dan 4,8× dari referensi. Instruksi turun 28% lagi dari baseline. Memotong kisi dan pipa memungkinkan kita memensiunkan 1,10M instruksi per encode berbanding 1,82M milik SP dan 1,61M milik IREE pada bentuk trie yang sama; selisihnya adalah pembukuan yang mereka simpan untuk API tujuan umum yang tidak kita perlukan.

Trie Darts dari Pengoptimalan 1 memerlukan dua muatan dependen per langkah byte. Pertama offset base induk, lalu entri check pada slot anak kandidat untuk mengonfirmasi bahwa induk memilikinya. Entri check hanya memvalidasi kepemilikan. Pertanyaan yang sama dapat dijawab oleh bitmap per simpul yang mencatat byte mana yang memiliki anak. Berdasarkan konstruksi trie array ganda, bit untuk byte b dalam bitmap induk diatur persis ketika slot kandidat untuk byte tersebut dimiliki oleh induk. Bitmap dan array check membawa informasi yang sama, sehingga kita dapat menghapus array check dari struktur waktu proses sepenuhnya.

Pencarian bitmap dikompilasi menjadi satu pengujian bit tunggal terhadap satu kata 64-bit, yang berjalan dalam waktu sekitar satu siklus. Instruksi POPCNT terkait, yang menghitung semua bit yang disetel dalam register, adalah apa yang digunakan desain trie terindeks bitmap lainnya untuk menghitung offset anak dari bitmap secara langsung. Kita tidak membutuhkannya karena konstruksi Darts sudah menyimpan offset tersebut di bidang base simpul.

rust

#[repr(C, align(64))]
struct NodeHot {
    bitmap:   [u64; 4],     // 32 B  — "which bytes have children"
    base:     i32,          //  4 B  — child slot offset
    token_id: i32,          //  4 B  — vocab id (-1 if not terminal)
    score:    f64,          //  8 B  — Viterbi log-prob
    _pad:     [u8; 16],     // 16 B  — pad to one cache line
}

// Lookup: one cache-line load, one bit test, one add.
fn child(&self, parent: u32, byte: u8) -> Option<u32> {
    let h = &self.node_hot[parent as usize];
    if !h.bitmap.test(byte) { return None; }
    Some(h.base.wrapping_add(byte as i32) as u32)
}

Sambil lalu, kita mengemas empat bidang per simpul (bitmap, base, ID token, dan skor) ke dalam satu lini cache 64-byte. Satu kunjungan simpul sekarang menarik semuanya: skor dan ID token yang kita perlukan di simpul terminal, ditambah bitmap dan base untuk langkah berikutnya. Array check hanya digunakan selama konstruksi dan dihapus dari tata letak waktu proses. Pengindeksan jalur panas tidak dicentang (unchecked) karena konstruksi trie dan struktur perulangan sudah menjamin batasnya. Pertukarannya adalah Ruang: pada 64 byte per simpul × ~780K slot, trie tumbuh dari ~9 MB menjadi ~50 MB.

Hasil pada 514 token:

Mesin	p50	p99	Instruksi	Akses L2	% miss L2	% miss L3
Hugging Face	327 µs	3.340 µs	3,66M	15,0K	8,17%	14,66%
SentencePiece	127 µs	1.140 µs	1,82M	7,5K	4,74%	4,07%
IREE	111 µs	132 µs	1,61M	4,7K	5,82%	3,87%
Baseline	155 µs	1.170 µs	1,53M	6,1K	2,59%	16,66%
+ Darts	68 µs	80 µs	1,10M	4,6K	6,45%	11,42%
+ Bitmap dan Pengemasan Sebaris	65 µs	77 µs	1.06M	1,8K	20,53%	15,01%

Hasil tokenizer pada 514 token setelah menambahkan bitmap dan packing inline.

Jam dinding secara sistematis turun 4,5% lagi pada 514 token dan tumbuh dengan panjang input, mencapai 6-7% pada 4k dan 16k. Menghapus array check mengubah langkah trie per byte dari dua muatan lini cache menjadi satu, yaitu akses L2 2,5× lebih sedikit per encode (1,8K berbanding 4,6K milik Darts biasa). Tingkat miss melonjak dari 6% menjadi 20%, tetapi sebagian besar adalah penyebutnya: dengan akses yang kurang dari separuhnya, miss yang kita miliki mengambil porsi yang lebih besar.

Data trie adalah sekitar 50 MB (780.000 simpul dengan masing-masing 64 byte). Pada proses Linux default, memori tersebut didukung oleh halaman 4 KB, sehingga trie penuh mencakup sekitar 12.000 halaman virtual yang berbeda, jauh melampaui apa yang dapat ditampung oleh Translation Lookaside Buffer data tingkat pertama CPU (Sapphire Rapids memiliki 96 entri). Setiap langkah Viterbi menyentuh simpul yang berbeda, dan selama encode 512 token kita menghabiskan sekitar 9.000 siklus dalam penelusuran tabel halaman, sekitar 3% dari anggaran per-encode.

Perbaikannya adalah mendukung trie dengan halaman besar 2 MB alih-alih halaman 4 KB. 50 MB yang sama sekarang mencakup 25 halaman, pas di Translation Lookaside Buffer sepenuhnya, dan direktori tabel halaman itu sendiri berhenti bersaing dengan trie untuk cache L2.

Linux memiliki dua cara untuk mendukung memori dengan halaman 2 MB. Cara oportunistik adalah halaman besar transparan (THP): program Anda meminta kernel untuk meningkatkan wilayah memori dari halaman 4 KB ke 2 MB, dan utas kernel latar belakang mencoba melakukannya ketika memiliki waktu dan memori fisik kontinu yang tersedia. Alternatif lainnya adalah mengalokasikan trie secara langsung dari kumpulan halaman besar yang telah direservasi sebelumnya yang disisihkan kernel saat booting:

rust

let raw = unsafe {
    libc::mmap(
        std::ptr::null_mut(),
        alloc_len,
        libc::PROT_READ | libc::PROT_WRITE,
        libc::MAP_PRIVATE | libc::MAP_ANONYMOUS | libc::MAP_HUGETLB,
        -1,
        0,
    )
};

Kumpulan tersebut harus ada di host (vm.nr_hugepages disetel saat booting). Pada instance produksi kami, 10.561 halaman besar direservasi; trie mengonsumsi 24 di antaranya. Setelah mmap, /proc/<pid>/smaps mengonfirmasi wilayah tersebut: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

Keuntungannya adalah jam dinding 3–12% di berbagai ukuran input, konsisten dan proporsional dengan panjang kumpulan kerja:

Token	Tanpa halaman besar	Dengan halaman besar	Δ
130	15,7 µs	15,2 µs	−3,6%
514	65,4 µs	63,1 µs	−3,4%
1.026	129,5 µs	125,3 µs	−3,3%
4.098	773 µs	679 µs	−12,0%
16.386	3.808 µs	3.554 µs	−6,8%

Latensi tokenizer dengan dan tanpa huge pages di berbagai ukuran input.

Keuntungan terbesar adalah pada 4k token, di mana kumpulan kerja cukup besar sehingga lalu lintas tabel halaman secara aktif bersaing dengan data trie untuk bandwidth L2. Di luar 4k, keuntungan menyusut karena miss L3 mendominasi dan penelusuran tabel halaman menjadi porsi waktu total yang lebih kecil.

Menggabungkan ketiga pengoptimalan, berikut adalah mesin akhir yang diukur terhadap setiap tokenizer RoBERTa lain yang kami uji. Bersamaan dengan biner C++ SentencePiece asli dan C IREE, kami juga menguji tolok ukur crate pembungkus Rust siap pakai (off-the-shelf) yang akan digunakan oleh pengguna produksi, sentencepiece dan iree-tokenizer. Crate sentencepiece mengukur latensi 1.6-1.9× lebih tinggi daripada biner C++ asli pada setiap ukuran input, dengan overhead berasal dari pembungkus yang mengalokasikan daftar pecahan token baru, masing-masing memegang salinan teks pecahannya sendiri, pada setiap encode. Crate iree-tokenizer mengukur ukuran buffer internalnya ke setiap input, yang menghindari alokasi konstan per-encode yang dibayar oleh biner IREE asli terlepas dari ukuran input, dan itu paling penting pada input pendek di mana alokasi akan mendominasi pekerjaan tokenisasi sebenarnya. Pada panjang input produksi, biaya konstan teramortisasi dan overhead per-panggilan pembungkus sendiri dari penyalinan token kembali ke Rust mendorong latensinya di atas biner asli.

Latensi p50 dan p99 per encode di berbagai implementasi tokenizer dan ukuran input.

Mesin akhir menjalankan Viterbi yang sama atas kosakata 250.000 token yang sama, tidak mengalokasikan apa pun pada jalur panas, dan menghasilkan keluaran yang sama persis dengan token terhadap referensi. Setiap langkah byte sekarang menjadi satu muatan lini cache 64-byte, satu pengujian bitmap, dan satu penambahan bilangan bulat, turun dari penyelidikan HashMap, panggilan alokator, dan beberapa cabang kasus khusus dalam implementasi baseline. Instruksi per encode turun dari 3,66M menjadi 1,04M, penurunan 3,5×. Jam dinding cocok dengan rasio tersebut pada input pendek dan melebar lebih jauh pada input panjang, di mana alokasi per token referensi mulai meluap ke L2 dan L3.

Dalam praktiknya, pekerjaan ini mengurangi utilisasi CPU pada lapisan pra-pemrosesan tumpukan inferensi kami sebesar 5-6× dan memangkas latensi reranker sebesar puluhan milidetik.

Sebagian besar pengurangan latensi berasal dari perubahan ringan yang menghilangkan pekerjaan terbuang: menghapus alokasi per-encode, mengganti trie anak-HashMap dengan array ganda, dan melucuti overhead API generik. Penggunaan bitmap per simpul yang ada sebagai pemeriksaan validitas dan mendukung trie dengan halaman besar 2 MB secara bersamaan menyumbang 10-20% di atas peralihan yang lebih besar ke trie array ganda, tergantung pada ukuran input.

Crate pembungkus Rust siap pakai di sekitar SentencePiece dan IREE mengilustrasikan poin yang sama secara terbalik. Di atas tokenizer C dan C++ asli, batas FFI dan alokasi per-panggilan yang diperkenalkan oleh pembungkus terlihat dalam angka latensi. Kode sumber Rust untuk encoder Viterbi akhir tersedia di github.com/perplexityai/pplx-garden.

Tokenizer Hugging Face — https://github.com/huggingface/tokenizers

SentencePiece — https://github.com/google/sentencepiece

Tokenizer IREE — https://github.com/iree-org/iree

Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. https://arxiv.org/abs/1804.10959

Viterbi, A. J. (1967). Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory. https://en.wikipedia.org/wiki/Viterbi_algorithm

Aoe, J. (1989). An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software Engineering. https://ieeexplore.ieee.org/document/31365/

Karoonboonyanan, T. An Implementation of Double-Array Trie. https://linux.thai.net/~thep/datrie/datrie.html

POPCNT (x86) — https://www.felixcloutier.com/x86/popcnt

Halaman besar (Huge pages) — https://docs.kernel.org/admin-guide/mm/hugetlbpage.html

BibTeX

@online{perplexity2026ImprovingUnigramTokenizerCpuPerformance,
  author = {{Perplexity} and Vladimir Zaytsev and Bex Brooker and Daisy Lee and Roshan Shankar},
  title = {{Improving unigram tokenizer CPU performance}},
  date = {2026-05-20},
  url = {https://www.perplexity.ai/hub/blog/improving-unigram-tokenizer-cpu-performance}
}

Motivasi

Algoritma Viterbi

Implementasi Referensi

Catatan tentang Pra-pemrosesan

Tempat Implementasi Referensi Menghabiskan Waktunya

Cara Kami Mengukur

Mengapa SentencePiece dan IREE Lebih Cepat: Trie Array Ganda

Dasar (Baseline): Porting Zero-Allocation dari Referensi

Pengoptimalan 1: Trie Array Ganda Tanpa Abstraksi Ekstra

Optimisasi 2: Bitmap dan pengepakan inline

Optimisasi 3: Huge pages untuk trie

Perbandingan akhir

Penutup

Referensi

Sitasi