提升 Unigram 標記化工具的 CPU 效能

我們將 Unigram 標記化工具（tokenizer）從頭重新實作，作為一個專注於效能的專案。在生產環境的輸入長度下，新編碼器與 Hugging Face tokenizers crate 相比，將 p50 延遲降低了約 5 倍；與 SentencePiece (C++) 相比降低了約 2 倍；與 IREE 的 tokenizer (C) 相比降低了約 1.5 倍，且完全沒有穩定狀態的堆積（heap）配置。在生產環境中，這使我們推論堆疊中的 CPU 使用率降低了 5 至 6 倍，並將重新排序器（reranker）的延遲縮短了雙位數毫秒。

LLM 推論成本通常被視為 GPU 工作：KV 快取、注意力核心、專家路由。但相當一部分的生產環境流量都在運行小得多的模型，比前沿 Transformer 小兩到三個數量級。嵌入模型、分類器和重新排序器仍然在 GPU 上運行，但前向傳遞（forward pass）足夠短，以至於它周圍的一切都開始變得重要。

最明顯的例子是重新排序器為每個請求評分數百個候選文件。對於小型模型，GPU 運算通常在個位數毫秒內完成，但每個輸入仍然必須先經過 CPU 端的標記化，將文字轉換為詞彙 ID。當批次很大時，這可能會佔總請求延遲的相當大一部分。

這項工作以 XLM-RoBERTa 為目標，這是一個使用 SentencePiece 訓練的 250K 詞彙的 Unigram 詞彙表。微調過的 RoBERTa 系列編碼器是排名、檢索和相似度任務的常見選擇。我們報告了整個過程中的單執行緒每個編碼延遲；在生產環境中，我們使用 rayon 在多核心之間進行平行化。

在整篇文章中，我們將 Hugging Face 的 tokenizers crate 視為我們進行基準測試的參考，因為它是大多數團隊首選的預設 Rust 標記化工具。SentencePiece (C++) 和 IREE (C) 作為另外兩個主要的生產環境實作被納入比較。

Unigram 標記化由 Kudo 於 2018 年引入（Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates）並在 SentencePiece 中發布，它將分割 framing 為一個最大機率路徑問題：每個詞彙標記都有一個學到的對數機率（log-probability），編碼器會選擇其標記分數總和為最高值的分割。這個問題是用維特比演算法（Viterbi algorithm）（1967）來解決的，其中位元組位置作為圖層，詞彙標記作為跨越連續位元組範圍的邊。遞迴是在位元組位置上的一維 DP：

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

外部迴圈在輸入長度上是線性的，在每個位置由最長的詞彙標記（XLM-RoBERTa 為 48 個 UTF-8 位元組）所限制。內部的前綴樹（trie）走訪是熱點路徑：在 16k 標記的輸入上，它執行了數十萬次轉換，並且在每個編碼中退役了數千萬個指令。

Hugging Face 的 tokenizers v0.22 直接實作了遞迴，使用雜湊對應（hash-map）進行反向查找，並在每個前綴樹節點使用雜湊對應子節點：

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
}

而內部迴圈（已簡化）——每個前綴搜尋符合項都會配置一個新的字串，然後探測雜湊對應：

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
}

這段程式碼是可讀的 Rust，但發生了許多在原始碼層級看不到的工作。下一節將詳細分析時間都花在了哪裡。

在維特比執行之前，輸入會經過 Unicode 正規化（NFKC）和單字邊界標記。在我們的情境中，效能分析（profiling）顯示預處理佔總編碼時間不到 5%，因此在本文的剩餘部分中，我們專注於維特比前向傳遞。

加速 CPU 程式碼有兩種方法：執行較少的指令，或獲得更高的 IPC。Cachegrind 測量前者，perf stat 測量後者。本文中的每一項最佳化都落在此兩者之一。

CPU 會在四件事上停滯：快取未命中（L1d 約 4 個週期，L3 未命中至 DRAM 則為數百個）、亂序執行引擎無法平行化的相依載載入鏈（dependent-load chains）、分支預測錯誤（每次錯誤猜測清除約 15-20 個週期），以及配置器（allocator）呼叫。參考的 unigram 引擎實作觸及了這四點：

瓶頸	機制	測得的影響
每次符合的配置	對符合的位元組進行 String::from_utf8，加上每個前綴樹符合項進行一次 AHashMap 查找；標記 ID 已經在葉子中，但參考實作沒有將其儲存在那裡	在 512 個標記時為 7,295 次配置，1k 時為 14,542 次，16k 時為 299,171 次
每個位元組的指標追逐（Pointer chase）	每個前綴樹節點都有一個 AHashMap，對下一個位元組進行雜湊並在每一步取值兩個指標；Node 結構還將冷欄位（如 is_leaf）綑綁在一起，在每次造訪時將其拉入快取	L1d 未命中率保持在低點（1k 時約 2.5%），因為配置器熱頁面存活在 L1 中；成本表現為相依載入延遲
長輸入上的 L2 劇烈擺動（thrashing）	DP 表、前綴暫存（scratch）和輸出標記清單在每次呼叫時都是重新配置的	L2 未命中率從 128 個標記時的 12% 攀升至 16k 時的 50%，因為累積的配置佔用空間超過了每個核心 2 MB 的 L2

參考 tokenizer 的瓶頸、機制與量測影響。

主要的成本是每次符合的配置。在 1k 個標記時，參考實作在 IPC 為 2.8 的情況下，每個編碼大約退役（完成）7M 個指令，其中大部分在配置器呼叫和字串轉換中。L2 未命中只在超過 ~1k 個標記後才重要，一旦累積的配置佔用空間溢位了每個核心的快取。

每個標記的配置是常數：大約 2 KB 且每個標記約 18 次配置，與輸入大小無關。延遲的非線性來自 L2：累積位元組在大約 1k 個標記時跨越 2 MB，未命中率從 8% 攀升至約 50%，並且 p99 曲線彎曲以與之相符。

我們比較了三個生產環境標記化工具，它們都在相同的 XLM-RoBERTa 模型上執行相同的 Unigram 演算法：

引擎	語言	前綴樹（Trie）
Hugging Face	Rust	HashMap-children 前綴樹
SentencePiece	C++	Darts 雙陣列前綴樹
IREE 標記化工具	C	Darts 雙陣列前綴樹

比較中使用的 tokenizer 實作、語言與 trie 表示法。

我們透過直接的 C/C++ FFI 而非其 Rust 包裝函式來連結 SentencePiece 和 IREE；包裝函式增加了每次呼叫的配置和字串轉換，這些並非底層函式庫成本的一部分。

所有引擎都是透過完整最佳化建構的（O3、native 目標鎖定、連結時間最佳化）。測量時固定在 Intel Xeon Platinum 8488C 上的某個安靜核心執行。對於每個引擎和輸入大小，我們收集實時延遲（p50 和 p99，在 1,000 次預熱後的 10,000 次迭代）、透過 Valgrind cachegrind 退役的指令、來自 perf stat 硬體計數器的 IPC 和快取未命中率，以及由測量視窗周圍的全域配置器包裝函式計算的堆積配置。

在 514 個標記時（512 加上 2 個 BOS/EOS 注入）：

實作	p50 延遲	指令	IPC	配置
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 個 token 時的 tokenizer 延遲、指令數、IPC 與配置情況。

SP 和 IREE 的延遲大約是參考實作的三分之一。它們退役了大約一半的指令，以更高的 IPC 運行，並且配置量少了一到兩個數量級。

SentencePiece 和 IREE 都使用了由 Aoe 於 1989 年引入的雙陣列前綴樹（Aoe, 1989；Karoonboonyanan）。前綴樹編碼在兩個扁平的整數陣列中，base 和 check：

cpp

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

子節點查找為：

cpp

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

前綴樹走訪的每個步驟只需要兩次陣列載入、一次整數加法和一次比較，沒有雜湊、沒有指標追逐，也沒有每個節點的堆積配置。建構過程放置每個節點，使其子節點落在驗證陣列上的可用槽位中，只要它們的子節點在跟隨的位元組上不同，就允許有多個父節點共用區域。

對於 XLM-RoBERTa 的 250K 詞彙量，整個前綴樹適合大約 9 MB 的連續記憶體（大約 780K 個槽位 × 每個槽位用於位移、驗證和標記 ID 的 12 個位元組）。單一編碼的熱工作集大約是 100 KB，舒適地放在 L2 中，並且硬體預取器（prefetcher）會鎖定常規的存取模式。

相比之下，參考實作保留了每個節點的子節點雜湊對應，每個位元組步驟花費大約四個相依載入。對位元組進行雜湊、載入儲存桶（bucket）、跟隨指標到儲存桶項目、跟隨另一個指標到堆積上的子節點，然後查閱其自己的雜湊對應以獲取下一個位元組。堆積物件會分散，大多數載入都會發生快取未命中。

SP 和 IREE 都將標記 ID 直接儲存在前綴樹節點中。參考的前綴樹實作只傳回符合的位元組，因此編碼器必須為每個符合項配置一個新的字串，在側邊雜湊對應中查找它以恢復標記 ID，並從獨立的向量中讀取分數。SP 將 ID 傳回為前綴樹儲存的值，並從扁平的浮點數陣列中讀取分數：

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 使用有狀態的游標 API，而不是在單一呼叫中傳回所有符合項，但成本模型是相同的：標記 ID 和分數可作為扁平陣列索引來存取，在前綴樹走訪本身上沒有配置或雜湊。IREE 每個編碼只配置一個輸出緩衝區；SP 在 DP 期間額外為每個符合項配置一個晶格（lattice）節點，在 514 個標記時計畫大約 1,559 次配置。

在更改前綴樹之前，我們將演算法成本與實作成本隔離：移除不必要的工作後，參考實作運行得有多快？

基準保留了參考實作的雜湊對應子節點前綴樹，但做了兩項更改。呼叫者擁有的暫存結構保存了 DP 表、預處理過的位元組和輸出標記 ID，因此熱點路徑在預熱後不會進行任何配置。標記 ID 和分數直接儲存在前綴樹節點中，消除了每次符合的字串轉換和次要雜湊對應查找。

內部迴圈：

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

這是相同的演算法，具有相同的前綴樹形狀和相同的存取模式，只是沒有配置且沒有多餘的查找。在 514 個標記時的結果：

引擎	p50	指令	IPC	配置
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
基準	156 µs	1.53M	2.62	0

在 514 個 token 時，零配置基準與現有 tokenizer 實作的比較。

移除每次符合的字串實體化和次要雜湊對應查找，使得指令數比參考實作減少了 2.4 倍。IPC 隨之下降（2.86 → 2.62），因為先前隱藏在配置器工作背後的雜湊對應指標追逐，現在成了每個位元組的主要成本。

參考與零配置基準 tokenizer 的 p50 與 p99 延遲，按輸入大小劃分。

基準在每個大小下都將 p50 延遲比參考實作降低了 2-3 倍，並且其 L2 未命中率在 2k 個標記內保持在近 2-3%，而參考實作則為 8-48%。剩餘的成本是 HashMap 指標追逐，下一節將解決這個問題。

雜湊對應前綴樹是一個指標追逐。SP 和 IREE 用雙陣列前綴樹解決了這個問題（見前一節），我們借用了相同的資料結構。不同之處在於，SP 和 IREE 是支援串流輸入、輸出位移和多種編碼模式的通用函式庫；這種靈活性使它們在前綴樹周圍產生了額外的記帳開銷（SP 中的晶格、IREE 中的八階段管線）。我們不需要這些，因此我們將前綴樹直接內嵌在維特比迴圈中並捨棄其餘部分。

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

一個位元組步驟花費兩次陣列讀取、一次整數加法和一次比較。整個前綴樹大約 9 MB，但任何單一編碼只會走訪其中的約 100 KB，因此熱資料會停留在 L2 中。

引擎	p50	p99	指令	L2 未命中 %	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%
基準	155 µs	1,170 µs	1.53M	2.59%	16.66%
+ Darts	68 µs	80 µs	1.10M	6.45%	11.42%

採用 double-array trie 後的 tokenizer 延遲、指令數與快取未命中率。

實時延遲比基準下降了 2.3 倍，比參考實作下降了 4.8 倍。指令數比基準進一步下降了 28%。在相同的前綴樹形狀下，捨棄晶格和管線讓我們每個編碼能退役 1.10M 個指令，而 SP 為 1.82M，IREE 為 1.61M；差距在於它們為我們不需要的通用 API 保留的記帳開銷。

最佳化 1 中的 Darts 前綴樹需要每個位元組步驟進行兩次相依載入。首先是父節點的 base 位移，然後是候選子節點槽位處的 check 項目，以確認父節點擁有它。check 項目僅用於驗證所有權。相同問題可以透過記錄哪些位元組具有子節點的每個節點位元圖來回答。透過雙陣列前綴樹的建構，當且僅當該位元組的候選槽位由父節點擁有時，父節點位元圖中位元組 b 的位元才會被設定。位元圖和 check 陣列承載相同的資訊，因此我們可以完全從執行階段結構中捨棄 check 陣列。

位元圖查找會編譯成針對一個 64 位元字的單一位元測試，這在大約一個週期內執行。相關的 POPCNT 指令會計算暫存器中所有設定的位元，是其他以位元圖索引的前綴樹設計用來直接從位元圖計算子節點位移的方法。我們不需要它，因為 Darts 建構已經將該位移儲存在節點的 base 欄位中。

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

順便一提，我們將四個每個節點的欄位（位元圖、base、標記 ID 和分數）封裝到一個 64 位元組的快取行中。現在，單次節點造訪會拉入所有東西：我們在終端節點需要的分數和標記 ID，以及下一步的位元圖和 base。check 陣列僅在建構期間使用，並已從執行階段配置中捨棄。熱點路徑索引是未檢查的（unchecked），因為前綴樹建構和迴圈結構已經保證了邊界。代價是空間：以每個節點 64 位元組 × 約 780K 個槽位計算，前綴樹從約 9 MB 成長到約 50 MB。

在 514 個標記時的結果：

引擎	p50	p99	指令	L2 存取	L2 未命中 %	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%
基準	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%
+ 位元圖與內嵌封裝	65 µs	77 µs	1.06M	1.8K	20.53%	15.01%

加入 bitmap 與 inline packing 後，514 個 token 時的 tokenizer 結果。

實時在 514 個標記時系統性地再下降了 4.5%，並隨著輸入長度增加，在 4k 和 16k 時達到 6-7%。捨棄 check 陣列將每個位元組的前綴樹步驟從兩次快取行載入變成一次，這使得每個編碼的 L2 存取減少了 2.5 倍（1.8K 對比純 Darts 的 4.6K）。未命中率從 6% 躍升至 20%，但其中大部分是分母造成的：由於存取次數不到一半，我們實際發生的未命中佔了更大的比例。

前綴樹資料大約為 50 MB（780,000 個節點，每個 64 位元組）。在預設的 Linux 程序上，該記憶體由 4 KB 頁面支援，因此完整的前綴樹跨越了大約 12,000 個不同的虛擬頁面，遠遠超過了 CPU 的第一級資料轉譯旁看緩衝區（Translation Lookaside Buffer）所能容納的大小（Sapphire Rapids 有 96 個項目）。每個維特比步驟都會觸碰不同的節點，在 512 個標記的編碼中，我們在頁面表走訪中消耗了大約 9,000 個週期，約佔每個編碼預算的 3%。

解決方法是用 2 MB 的大頁面來支援前綴樹，而不是 4 KB 的頁面。相同的 50 MB 現在跨越 25 個頁面，完全可以放入轉譯旁看緩衝區中，並且頁面表目錄本身不再與前綴樹爭奪 L2 快取。

Linux 有兩種方法用 2 MB 頁面支援記憶體。機會主義的方法是透明大頁面（THP）：您的程式要求核心將記憶體區域從 4 KB 升級到 2 MB 頁面，而背景核心執行緒（thread）會在有時間且有連續實體記憶體可用時嘗試這樣做。另一種選擇是直接從核心在開機時預留的大頁面池中配置前綴樹：

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

該池需要在主機上存在（在開機時設定 vm.nr_hugepages）。在我們的生產環境執行個體上，預留了 10,561 個大頁面；前綴樹消耗了其中 24 個。mmap 之後，/proc/<pid>/smaps 確認了該區域：KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB。

效益在所有輸入大小下呈現 3–12% 的實時改善，且與工作集長度一致且成正比：

標記	無大頁面	有大頁面	Δ
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%

採用與未採用 huge pages 時，tokenizer 在不同輸入大小下的延遲。

最大的贏家在 4k 個標記時，此時的工作集夠大，以至於頁面表流量積極地與 L2 頻寬的前綴樹資料競爭。超過 4k 之後，效益會縮小，因為 L3 未命中佔據主導地位，且頁面表走訪佔總時間的比例變小。

將這三項最佳化結合在一起，以下是最終引擎與我們測試過的每個其他 RoBERTa 標記化工具相比的測量結果。除了原生的 C++ SentencePiece 和 C IREE 二進位檔之外，我們還對生產使用者會接觸到的現成 Rust 包裝函式 crate（sentencepiece 和 iree-tokenizer）進行了基準測試。sentencepiece crate 的延遲在每個輸入大小下都比原生 C++ 二進位檔高出 1.6-1.9 倍，其額外負擔來自於包裝函式在每個編碼中配置一個新的標記片段清單，每個片段都持有其自己的片段文字複本。iree-tokenizer crate 將其內部緩衝區的大小調整為每個輸入，這避免了原生 IREE 二進位檔無論輸入大小如何都需要支付的常數每編碼配置，這在配置會支配實際標記化工作的短輸入中尤其重要。在生產環境輸入長度下，常數成本被攤銷，而包裝函式將標記複製回 Rust 所產生的每次呼叫自身額外負擔，使其延遲高於原生二進位檔。

各 tokenizer 實作與不同輸入大小下，每次編碼的 p50 與 p99 延遲。

最終引擎在相同的 250,000 個標記詞彙表上執行相同的維特比，在熱點路徑上不進行任何配置，並產生與參考實作完全相符的標記輸出。每個位元組步驟現在是單個 64 位元組快取行載入、一次位元圖測試和一次整數加法，相較於基準實作中的 HashMap 探測、配置器呼叫和幾個特殊情況分支有所減少。每個編碼的指令數從 3.66M 下降到 1.04M，減少了 3.5 倍。實時在短輸入時符合該比例，並在長輸入時進一步擴大，此時參考實作的每個標記配置開始溢位 L2 和 L3。

實際上，這項工作將我們推論堆疊預處理層中的 CPU 使用率降低了 5 至 6 倍，並將重新排序器的延遲縮短了雙位數毫秒。

延遲降低的大部分來自於消除了浪費工作的輕量級更改：捨棄每編碼配置、用雙陣列取代 HashMap 子節點前綴樹，以及剝離通用 API 的額外負擔。根據輸入大小的不同，使用現有的每個節點位元圖作為有效性檢查，並用 2 MB 大頁面支援前綴樹，這兩者的結合在轉向雙陣列前綴樹的更大轉變之上額外帶來了 10-20% 的效益。

圍繞 SentencePiece 和 IREE 的現成 Rust 包裝函式 crate 反向說明了這一點。在原生 C 和 C++ 標記化工具之上，FFI 邊界和包裝函式引入的每次呼叫配置在延遲數字中是清晰可見的。最終維特比編碼器的 Rust 原始碼可在 github.com/perplexityai/pplx-garden 取得。

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

動機

維特比演算法（The Viterbi Algorithm）

參考實作

關於預處理的注意事項

參考實作將時間花在哪裡

我們如何測量

為什麼 SentencePiece 和 IREE 更快：雙陣列前綴樹

基準：參考的零配置移植

最佳化 1：沒有額外抽象的雙陣列前綴樹

最佳化 2：點陣圖與內嵌打包

最佳化 3：Trie 的大頁面

最終比較

結語

參考資料

引用