Unigram Tokenizer CPU Performansını İyileştirme

Odaklanmış bir performans projesi olarak Unigram tokenizer'ımızı sıfırdan yeniden uyguladık. Üretim ortamı girdi uzunluklarında yeni kodlayıcı; Hugging Face tokenizers crate'ine kıyasla p50 gecikmesini kabaca 5 kat, SentencePiece'e (C++) kıyasla ~2 kat ve IREE'nin tokenizer'ına (C) kıyasla ~1.5 kat azaltırken sıfır kararlı durum yığın (heap) tahsisatı sağlar. Üretim ortamında bu, çıkarım (inference) yığınımızdaki CPU kullanımını 5-6 kat azalttı ve yeniden sıralayıcı (reranker) gecikmesinden çift haneli milisaniyeler kırptı.

LLM çıkarım maliyeti genellikle GPU çalışması olarak çerçevelenir: KV önbellekleri, dikkat (attention) çekirdekleri, uzman yönlendirme (expert routing). Ancak üretim trafiğinin anlamlı bir kısmı, sınır (frontier) transformer'larından iki ila üç kat daha küçük olan çok daha küçük modellerde çalışır. Gömme (embedding) modelleri, sınıflandırıcılar ve yeniden sıralayıcılar hala GPU'larda çalışır, ancak ileri geçiş (forward pass) etrafındaki her şeyin önem kazanacağı kadar kısadır.

En net örnek, istek başına yüzlerce aday belgeyi puanlayan bir yeniden sıralayıcıdır. Küçük bir modelde GPU hesaplaması tipik olarak tek haneli milisaniyelerde biter, ancak yine de her girdinin önce CPU tarafındaki tokenization işleminden geçmesi ve metnin kelime dağarcığı kimliklerine (vocabulary ID) dönüştürülmesi gerekir. Toplu iş (batch) büyük olduğunda, bu durum toplam istek gecikmesinin anlamlı bir kısmını oluşturabilir.

Bu çalışma, SentencePiece ile eğitilmiş 250K token'lık bir Unigram kelime dağarcığına sahip olan XLM-RoBERTa'yı hedeflemektedir. İnce ayarlanmış (fine-tuned) RoBERTa ailesi kodlayıcılar; sıralama, erişim ve benzerlik görevleri için yaygın bir tercihtir. Boyunca tek iş parçacıklı (single-threaded) kodlama başına gecikme değerlerini bildiriyoruz; üretim ortamında rayon kullanarak çekirdekler arasında paralelleştirme yapıyoruz.

Bu yaz boyunca, çoğunlukla ekiplerin başvurduğu varsayılan Rust tokenizer'ı olduğu için Hugging Face'in tokenizers crate'ini kıyaslama yaptığımız referans olarak ele alıyoruz. SentencePiece (C++) ve IREE (C), diğer iki büyük üretim uygulaması olarak karşılaştırma amacıyla dahil edilmiştir.

Kudo tarafından 2018'de (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) tanıtılan ve SentencePiece içinde sunulan Unigram tokenization, segmentasyonu en olası yol (most-probable-path) sorunu olarak çerçeveler: her kelime dağarcığı token'ının öğrenilmiş bir log-olasılığı vardır ve kodlayıcı, token puanlarının toplamı en yüksek değeri veren segmentasyonu seçer. Sorun; bayt konumlarının grafik katmanları ve bitişik bir bayt aralığını kapsayan kelime dağarcığı token'larının kenarlar olduğu Viterbi algoritması (1967) ile çözülür. Yineleme, bayt konumları üzerinden tek boyutlu bir DP'dir (dinamik programlama):

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

Dış döngü girdi uzunluğuna göre doğrusaldır (linear), her konumda en uzun kelime dağarcığı token'ı (XLM-RoBERTa için 48 UTF-8 bayt) ile sınırlıdır. İç trie dolaşımı sıcak yoldur (hot path): 16k token'lık bir girdide, kodlama başına yüz binlerce geçiş çalıştırır ve on milyonlarca talimatı (instruction) sonlandırır.

Hugging Face tokenizers v0.22, ters arama (reverse lookup) için bir hash haritası (hash-map) ve her trie düğümünde hash-map çocukları ile yinelemeyi doğrudan uygular:

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
}

Ve iç döngü (basitleştirilmiş) – her önek arama eşleşmesi yeni bir dize (string) tahsis eder ve ardından hash haritasını yoklar (probe):

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
}

Kod okunabilir Rust dilindedir, ancak kaynak düzeyinde görünmeyen birçok iş gerçekleşir. Sonraki bölümde zamanın nereye harcandığı incelenmektedir.

Viterbi çalışmadan önce girdi, Unicode normalizasyonundan (NFKC) ve kelime sınırı işaretlemesinden geçer. Profil oluşturma (profiling), senaryolarımızda ön işlemenin toplam kodlama süresinin %5'inden azını oluşturduğunu göstermektedir, bu nedenle yazının geri kalanında Viterbi ileri geçişine odaklanıyoruz.

CPU kodunu hızlandırmanın iki yolu vardır: daha az talimat yürütmek veya daha yüksek IPC elde etmek. Cachegrind birincisini, perf stat ikincisini ölçer. Bu yazidaki her optimizasyon bunlardan birine dayanmaktadır.

CPU'lar dört konuda duraksar (stall): önbellek ıskalamaları (L1d ~4 çevrim, L3-miss-to-DRAM yüzlerce), sıra dışı (out-of-order) motorun paralelleştiremediği bağımlı yük zincirleri, dal tahmin hataları (yanlış tahmin başına ~15-20 çevrim temizlenir) ve tahsis edici (allocator) çağrıları. Referans unigram motoru uygulaması dördüne de takılır:

Darboğaz	Mekanizma	Ölçülen etki
Eşleşme başına tahsisat	Eşleşen baytlar üzerinde String::from_utf8 ve trie eşleşmesi başına bir AHashMap araması; token kimliği zaten yaprakta (leaf) bulunur ancak referans bunu orada saklamaz	512 token'da 7.295 tahsisat, 1k'da 14.542, 16k'da 299.171
Bayt başına işaretçi takibi (pointer chase)	Her trie düğümünde bir AHashMap, sonraki baytın hash'ini hesaplar ve adım başına iki işaretçinin referansını çözer; ayrıca Node yapısı is_leaf gibi soğuk alanları da bir araya getirerek her ziyaret edildiğinde önbelleğe çeker	Tahsis edici sıcak sayfaları L1'de yaşadığı için L1d ıskalama oranı düşük kalır (1k'da ~%2.5); maliyet bağımlı yük gecikmesi olarak ortaya çıkar
Uzun girdilerde L2 thrashing (çırpınma)	DP tablosu, önek karalama alanı (prefix scratch) ve çıktı token listesinin tümü her çağrıda yeniden tahsis edilir	Kümülatif tahsis ayak izi çekirdek başı 2 MB L2'yi aştıkça L2 ıskalama oranı 128 token'da %12'den 16k'da %50'ye yükselir

Referans tokenizer darboğazları, mekanizmaları ve ölçülen etkileri.

Baskın maliyet, eşleşme başına yapılan tahsisattır. 1k token'da referans uygulama, 2.8 IPC ile kodlama başına kabaca 7M talimatı sonlandırır (tamamlar), bunların çoğunu tahsis edici çağrılarında ve dize dönüşümlerinde yapar. L2 ıskalamaları yalnızca kümülatif tahsis ayak izi çekirdek başı önbelleği aştıktan sonra, yani ~1k token'dan sonra önemlidir.

Giriş boyutuna göre referans tokenizer p50 ve p99 gecikmesi.

Giriş boyutuna göre referans tokenizer L2 önbellek kaçırma oranı.

Giriş boyutları boyunca referans tokenizer tarafından encode başına ayrılan bayt sayısı.

Token başına tahsisat sabittir: girdi boyutundan bağımsız olarak token başına yaklaşık 2 KB ve ~18 tahsisat. Gecikme doğrusalsızlığı L2'den kaynaklanır: kümülatif baytlar 1k token civarında 2 MB'ı geçer, ıskalama oranı %8'den ~%50'ye tırmanır ve p99 eğrisi buna uyacak şekilde bükülür.

Tümü aynı Unigram algoritmasını aynı XLM-RoBERTa modeli üzerinde çalıştıran üç üretim tokenizer'ını karşılaştırıyoruz:

Motor	Dil	Trie
Hugging Face	Rust	HashMap çocuklu önek trie'si (prefix trie)
SentencePiece	C++	Darts çift dizili trie (double-array trie)
IREE tokenizer	C	Darts çift dizili trie (double-array trie)

Karşılaştırmada kullanılan tokenizer uygulamaları, diller ve trie gösterimleri.

SentencePiece ve IREE'yi Rust sarmalayıcıları (wrapper) yerine doğrudan C/C++ FFI aracılığıyla bağlıyoruz; sarmalayıcılar, alttaki kütüphanenin maliyetinin bir parçası olmayan çağrı başına tahsisatlar ve dize dönüşümleri ekler.

Tüm motorlar tam optimizasyonlarla derlenmiştir (O3, yerel hedefleme, bağlantı zamanı optimizasyonu). Ölçümler, bir Intel Xeon Platinum 8488C üzerinde sakin bir çekirdeğe sabitlenmiş (pinned) olarak çalıştırılır. Her motor ve girdi boyutu için duvar saati gecikmesini (p50 ve p99, 1.000 ısınma iterasyonundan sonra 10.000 iterasyon), Valgrind cachegrind ile sonlandırılan talimatları, perf stat donanım sayaçlarından IPC ve önbellek ıskalama oranlarını ve ölçülen pencere etrafındaki genel bir tahsis edici sarmalayıcısı tarafından sayılan yığın tahsisatlarını topluyoruz.

514 token'da (512'ye eklenen +2, BOS/EOS enjeksiyonudur):

Uygulama	p50 gecikme	Talimatlar	IPC	Tahsisatlar
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

514 belirteçte tokenizer gecikmesi, komut sayısı, IPC ve ayırmalar.

SP ve IREE, referansın gecikmesinin kabaca üçte birine ulaşır. Yaklaşık yarı oranında daha az talimat sonlandırır, daha yüksek IPC ile çalışır ve bir ila iki kat daha az bellek tahsis ederler.

SentencePiece ve IREE, Aoe tarafından 1989'da tanıtılan çift dizili trie yapısını kullanır (Aoe, 1989; Karoonboonyanan). Trie, base ve check olmak üzere iki düz tamsayı dizisinde kodlanır:

cpp

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

Alt düğüm (child) arama işlemi şöyledir:

cpp

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

Trie geçişinin her adımı yalnızca iki dizi okuması, bir tamsayı toplama ve bir karşılaştırma gerektirir; hash hesaplama, işaretçi takibi ve düğüm başına yığın tahsisatı yoktur. Yapı, her düğümü çocukları doğrulama dizisindeki boş slotlara denk gelecek şekilde yerleştirir ve çocukları takip ettikleri bayt açısından farklı olduğu sürece birden fazla ebeveynin bölgeleri paylaşmasına izin verir.

XLM-RoBERTa'nın 250K'lık kelime dağarcığı için tüm trie yaklaşık 9 MB'lık bitişik belleğe sığar (slot başına offset, doğrulama ve token kimliği için ~780K slot × 12 bayt). Tek bir kodlamanın sıcak çalışma kümesi (hot working set) 100 KB mertebesindedir, L2'ye rahatça sığar ve donanım önbellek önyükleyicisi (prefetcher) düzenli erişim düzenine kilitlenir.

Buna karşılık referans, düğüm başına bir çocuk hash haritası tutar ve bu da bayt adımı başına yaklaşık dört bağımlı yüke mal olur. Baytın hash'ini hesapla, kovayı (bucket) yükle, kova girdisine giden bir işaretçiyi takip et, yığın üzerindeki çocuk düğüme giden başka bir işaretçiyi takip et, ardından sonraki bayt için kendi hash haritasına danış. Yığın nesneleri dağılır ve yüklerin çoğu önbelleği ıskalar.

SP ve IREE'nin her ikisi de token kimliğini doğrudan trie düğümünde saklar. Referans trie uygulaması yalnızca eşleşen baytları döndürür, bu nedenle kodlayıcı her eşleşme için yeni bir dize tahsis etmek, token kimliğini kurtarmak için yan bir hash haritasında aramak ve puanı ayrı bir vektörden okumak zorundadır. SP, kimliği trienin saklanan değeri olarak döndürür ve puanı düz bir kayan noktalı sayı (float) dizisinden okur:

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, tüm eşleşmeleri tek bir çağrıda döndürmek yerine durum bilgisi olan bir imleç (cursor) API'si kullanır, ancak maliyet modeli aynıdır: token kimliklerine ve puanlara düz dizi indisleri olarak erişilebilir, trie dolaşımının kendisinde tahsisat veya hash hesaplama yoktur. IREE kodlama başına yalnızca bir çıktı tamponu tahsis eder; SP ek olarak DP sırasında eşleşme başına bir kafes (lattice) düğümü tahsis ederek 514 token'da kabaca 1.559 tahsisat gerçekleştirir.

Trie'yi değiştirmeden önce, algoritma maliyetini uygulama maliyetinden izole ediyoruz: referans, gereksiz işler kaldırıldığında ne kadar hızlı çalışır?

Temel çizgi, referansın hash-map çocuklu trie yapısını korur ancak iki değişiklik yapar. Çağıran tarafa ait bir karalama yapısı (scratch struct) DP tablosunu, ön işlenmiş baytları ve çıktı token kimliklerini tutar, böylece sıcak yol ısınmadan sonra hiç tahsisat yapmaz. Token kimliği ve puanı doğrudan trie düğümünde saklanır, böylece eşleşme başına dize dönüşümü ve ikincil hash haritası araması ortadan kalkar.

İç döngü:

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,
        }
    }
}

Bu, aynı trie şekline ve aynı erişim düzenine sahip, yalnızca hiçbir tahsisat ve gereksiz arama içermeyen aynı algoritmadır. 514 token'daki sonuçlar:

Motor	p50	Talimatlar	IPC	Tahsisatlar
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
Temel Çizgi (Baseline)	156 µs	1.53M	2.62	0

Mevcut tokenizer uygulamalarıyla karşılaştırılan sıfır ayırmalı temel ölçüt, 514 belirteçte.

Eşleşme başına dize materialization (oluşturma) işlemini ve ikincil hash haritası aramasını kaldırmak, referansa kıyasla talimatları 2.4 kat azaltır. Bunlarla birlikte IPC düşer (2.86 → 2.62), çünkü daha önce tahsis edici işinin arkasında gizlenen hash haritası işaretçi takibi artık bayt başına baskın maliyet haline gelmiştir.

Giriş boyutuna göre referans ve sıfır ayırmalı temel tokenizer p50 ve p99 gecikmesi.

Giriş boyutuna göre referans ve sıfır ayırmalı temel tokenizer L2 önbellek kaçırma oranı.

Temel çizgi, her boyutta referansa kıyasla p50 gecikmesini 2-3 kat azaltır ve L2 ıskalama oranı referansın %8-48'lik oranına karşılık 2k token boyunca %2-3 civarında kalır. Kalan maliyet, sonraki bölümün ele aldığı HashMap işaretçi takip işlemidir.

Hash haritası trie'si bir işaretçi takibidir. SP ve IREE bunu çift dizili trie ile çözer (önceki bölüme bakın) ve biz de aynı veri yapısını ödünç alıyoruz. Aradaki fark, SP ve IREE'nin akış girdilerini (streaming input), çıktı offset'lerini ve birden fazla kodlama modunu destekleyen genel amaçlı kütüphaneler olmasıdır; bu esneklik onlara trie etrafında ek muhasebe maliyeti getirir (SP'de bir kafes, IREE'de sekiz aşamalı bir boru hattı). Bunların hiçbirine ihtiyacımız yok, bu yüzden trie'yi doğrudan Viterbi döngüsünün içine yerleştirip (inline) geri kalanını atıyoruz.

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
    }
}

Bayt adımı iki dizi okumasına, bir tamsayı toplamaya ve bir karşılaştırmaya mal olur. Tüm trie yaklaşık 9 MB'tır, ancak herhangi bir tek kodlama bunun yalnızca ~100 KB'lık kısmını dolaşır, bu nedenle sıcak veri L2'de kalır.

Motor	p50	p99	Talimatlar	L2 ıskalama%	L3 ıskalama%
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
Temel Çizgi (Baseline)	155 µs	1.170 µs	1.53M	%2.59	%16.66
+ Darts	68 µs	80 µs	1.10M	%6.45	%11.42

Çift dizili trie benimsendikten sonra tokenizer gecikmesi, komutlar ve önbellek kaçırma oranları.

Duvar saati gecikmesi temel çizgiye göre 2.3 kat, referansa göre 4.8 kat düşer. Talimatlar temel çizgiye göre %28 daha azalır. Kafes ve boru hattının kesilmesi, aynı trie şekli üzerinde kodlama başına SP'nin 1.82M ve IREE'nin 1.61M değerine karşılık 1.10M talimat sonlandırmamızı sağlar; aradaki fark, ihtiyacımız olmayan genel amaçlı API'ler için tuttukları muhasebe işlemleridir.

Optimizasyon 1'deki Darts trie'si bayt adımı başına iki bağımlı yük gerektirir. Önce ebeveynin base offset'i, ardından ebeveynin ona sahip olduğunu doğrulamak için aday çocuk slotundaki check girdisi. Check girdisi yalnızca sahipliği doğrular. Aynı soru, hangi baytların çocuklara sahip olduğunu kaydeden düğüm başına bir bitişlem (bitmap) ile yanıtlanabilir. Çift dizili trie yapısı gereği, ebeveynin bitmap'indeki b baytı için bit, tam olarak o bayt için aday slot ebeveyn tarafından sahiplenildiğinde ayarlanır. Bitişlem ve check dizisi aynı bilgiyi taşır, bu nedenle check dizisini çalışma zamanı yapısından tamamen çıkarabiliriz.

Bitişlem araması, tek bir çevrimde çalışan 64 bitlik bir kelimeye karşı tek bir bit testine derlenir. Bir yazmaçtaki (register) tüm ayarlanmış bitleri sayan ilgili POPCNT talimatı, diğer bitişlem indeksli trie tasarımlarının bir çocuk offset'ini doğrudan bitmap'ten hesaplamak için kullandığı şeydir. Buna ihtiyacımız yok çünkü Darts yapısı zaten bu offset'i düğümün base alanında saklıyor.

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)
}

Hazır buradayken, düğüm başına dört alanı (bitmap, base, token kimliği ve puan) 64 baytlık tek bir önbellek hattına (cache line) paketliyoruz. Tek bir düğüm ziyareti artık her şeyi içeri çekiyor: terminal düğümlerde ihtiyaç duyduğumuz puan ve token kimliği, ayrıca sonraki adım için bitmap ve base. Check dizisi yalnızca oluşturma sırasında kullanılır ve çalışma zamanı düzeninden çıkarılır. Sıcak yol indeksleme denetlenmez (unchecked) çünkü trie oluşturma ve döngü yapısı sınırları zaten garanti eder. Takas (trade-off) Alan'dır: düğüm başına 64 bayt × ~780K slot ile trie ~9 MB'tan ~50 MB'a büyür.

514 token'daki sonuçlar:

Motor	p50	p99	Talimatlar	L2 erişimleri	L2 ıskalama%	L3 ıskalama%
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
Temel Çizgi (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
+ Bitişlem ve Satır İçi Paketleme	65 µs	77 µs	1.06M	1.8K	%20.53	%15.01

Bitmap ve satır içi paketleme eklendikten sonra 514 belirteçte tokenizer sonuçları.

Duvar saati 514 token'da sistematik olarak %4.5 daha düşer ve girdi uzunluğuyla birlikte büyüyerek 4k ve 16k'da %6-7'ye ulaşır. Check dizisinin kaldırılması, bayt başına trie adımını iki önbellek hattı yükünden birine düşürür; bu, kodlama başına düz Darts'ın 4.6K değerine kıyasla 2.5 kat daha az L2 erişimi demektir (1.8K). Iskalama oranı %6'dan %20'ye sıçrar, ancak bunun büyük kısmı paydadan kaynaklanır: çok daha az erişimle, yaptığımız ıskalamalar toplam payın daha büyük bir kısmını alır.

Trie verisi yaklaşık 50 MB'tır (her biri 64 baytlık 780.000 düğüm). Varsayılan bir Linux sürecinde bu bellek 4 KB'lık sayfalarla desteklenir, bu nedenle tam trie yaklaşık 12.000 ayrı sanal sayfaya yayılır; bu, CPU'nun ilk seviye veri Translation Lookaside Buffer'ının tutabileceğinden çok ötedir (Sapphire Rapids 96 girdiye sahiptir). Her Viterbi adımı farklı bir düğüme dokunur ve 512 token'lık bir kodlama boyunca sayfa tablosu yürüyüşlerinde kabaca 9.000 çevrim harcarız; bu, kodlama başına bütçenin yaklaşık %3'üdür.

Çözüm, trie'yi 4 KB'lık sayfalar yerine 2 MB'lık dev sayfalarla desteklemektir. Aynı 50 MB artık 25 sayfaya yayılır, tamamen Translation Lookaside Buffer'a sığar ve sayfa tablosu dizinlerinin kendileri L2 önbelleği için trie ile rekabet etmeyi bırakır.

Linux'un belleği 2 MB'lık sayfalarla desteklemek için iki yolu vardır. Fırsatçı olanı şeffaf dev sayfalardır (THP: transparent huge pages): programınız çekirdekten bir bellek bölgesini 4 KB'tan 2 MB'lık sayfalara yükseltmesini ister ve bir arka plan çekirdek konu (thread) zamanı ve uygun fiziksel belleği olduğunda bunu yapmaya çalışır. Diğer alternatif ise trie'yi, çekirdeğin önyüklemede ayırdığı önceden rezerve edilmiş bir dev sayfa havuzundan doğrudan tahsis etmektir:

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,
    )
};

Havuzun konakta mevcut olması gerekir (önyüklemede ayarlanan vm.nr_hugepages). Üretim örneklerimizde 10.561 dev sayfa rezerve edilmiştir; trie bunların 24'ünü tüketir. mmap sonrasında /proc/<pid>/smaps bölgeyi doğrular: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

Kazanç, çalışma kümesi uzunluğuyla tutarlı ve orantılı olarak girdi boyutları arasında %3–12 duvar saati kazancıdır:

Token'lar	Dev sayfalar olmadan	Dev sayfalarla	Δ
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

Giriş boyutlarına göre büyük sayfalarla ve büyük sayfalar olmadan tokenizer gecikmesi.

En büyük kazanç 4k token'dadır; bu noktada çalışma kümesi, sayfa tablosu trafiğinin L2 bant genişliği için trie verileriyle aktif olarak rekabet edeceği kadar büyüktür. 4k'nın ötesinde kazanç küçülür çünkü L3 ıskalamaları baskın hale gelir ve sayfa tablosu yürüyüşleri toplam sürenin daha küçük bir payı olur.

Üç optimizasyonu bir araya getirerek, test ettiğimiz diğer tüm RoBERTa tokenizer'larına karşı ölçülen nihai motor buradadır. Yerel C++ SentencePiece ve C IREE ikililerinin yanı sıra, bir üretim kullanıcısının başvuracağı hazır (off-the-shelf) Rust sarmalayıcı crate'leri olan sentencepiece ve iree-tokenizer'ı da kıyasladık. Sentencepiece crate'i, her kodlama için kendi parça metni kopyasını tutan yeni bir token parçası listesi tahsis eden sarmalayıcının ek yükünden kaynaklanan şekilde, her girdi boyutunda yerel C++ ikilisinden 1.6-1.9 kat daha yüksek gecikme ölçer. IREE-tokenizer crate'i, yerel IREE ikilisinin girdi boyutundan bağımsız olarak ödediği sabit bir kodlama başı tahsisatından kaçınmak için dahili tamponunu her girdiye göre boyutlandırır; bu durum, tahsisatın aksi takdirde gerçek tokenization işine baskın geleceği kısa girdilerde en çok önem kazanır. Üretim girdi uzunluklarında sabit maliyet amorte edilir ve sarmalayıcının token'ları tekrar Rust'a kopyalamasından kaynaklanan çağrı başı ek yükü, gecikmesini yerel ikilinin üzerine çıkarır.

Tokenizer uygulamaları ve giriş boyutları genelinde encode başına p50 ve p99 gecikmesi.

Nihai motor, aynı 250.000 token'lık kelime dağarcığı üzerinde aynı Viterbi'yi çalıştırır, sıcak yolda hiçbir şey tahsis etmez ve referansa göre token açısından tam eşleşen çıktı üretir. Her bayt adımı artık temel uygulamadaki bir HashMap yoklaması, bir tahsis edici çağrısı ve birkaç özel durum dalından farklı olarak tek bir 64 baytlık önbellek hattı yükü, bir bitmap testi ve bir tamsayı toplamasıdır. Kodlama başına talimatlar 3.66M'dan 1.04M'a düştü, bu 3.5 katlık bir düşüştür. Duvar saati, kısa girdilerde bu oranla eşleşir ve referansın token başı tahsisatlarının L2 ve L3'ü taşdığı uzun girdilerde daha da genişler.

Pratikte bu çalışma, çıkarım yığınımızın ön işleme katmanındaki CPU kullanımını 5-6 kat azalttı ve yeniden sıralayıcı gecikmesinden çift haneli milisaniyeler kırptı.

Gecikme azalmasının büyük kısmı, boşa harcanan işi ortadan kaldıran hafif değişikliklerden geldi: kodlama başı tahsisatların bırakılması, HashMap çocuklu trie'nin çift dizili trie ile değiştirilmesi ve genel API ek yükünün soyulması. Girdi boyutuna bağlı olarak, düğüm başına mevcut bitmap'in geçerlilik kontrolü olarak kullanılması ve trie'nin 2 MB dev sayfalarla desteklenmesi, çift dizili trie'ye yapılan daha büyük geçişin üzerine ek olarak %10-20 tasarruf sağladı.

SentencePiece ve IREE etrafındaki hazır Rust sarmalayıcı crate'leri aynı noktayı tersten göstermektedir. Yerel C ve C++ tokenizer'larının üzerinde, sarmalayıcıların tanıttığı FFI sınırı ve çağrı başı tahsisatlar gecikme rakamlarında görülmektedir. Nihai Viterbi kodlayıcısı için Rust kaynağı github.com/perplexityai/pplx-garden adresinde mevcuttur.

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

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

IREE tokenizer — 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

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}
}

Motivasyon

Viterbi Algoritması

Referans Uygulama

Ön İşleme Üzerine Bir Not

Referans Uygulamanın Zamanını Harcadığı Yer

Nasıl Ölçtük

SentencePiece ve IREE Neden Daha Hızlı: Çift Dizili Trie (Double-Array Trie)

Temel Çizgi (Baseline): Referansın Sıfır Tahsisatlı Bir Uyarlaması

Optimizasyon 1: Ek Soyutlamalar Olmadan Çift Dizili Trie

Optimizasyon 2: Bitmap ve satır içi paketleme

Optimizasyon 3: Trie için devasa sayfalar

Son karşılaştırma

Kapanış Düşünceleri

Kaynaklar

Alıntı