改善 Unigram 分詞器的 CPU 效能

我們以專注於提升效能為目標，從零開始重新實作了 Unigram 分詞器（Tokenizer）。在生產環境的輸入長度下，新編碼器將 p50 延遲降低了約 5 倍（相較於 Hugging Face tokenizers crate）、約 2 倍（相較於 SentencePiece (C++)），以及約 1.5 倍（相較於 IREE 的分詞器 (C)），且在穩定狀態下實現了零堆疊記憶體分配。在生產環境中，這將我們推論堆疊（Inference stack）的 CPU 使用率降低了 5-6 倍，並將重排序器（Reranker）的延遲縮短了兩位數毫秒。

大型語言模型（LLM）的推論成本通常被歸類為 GPU 的工作：KV 快取、注意力核心、專家路由。然而，相當大一部分的生產流量是在規模小得多的小型模型上運行的，其規模比前沿轉換器（Frontier transformers）小兩到三個數量級。嵌入模型、分類器和重排序器仍在 GPU 上運行，但其前向傳遞（Forward pass）時間短到足以讓周圍的一切開始變得重要。

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

這項工作針對 XLM-RoBERTa，這是一種使用 SentencePiece 訓練的 250K Token 的 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 中發布的，它將分割問題框架化為「最可能路徑」問題：每個詞彙 Token 都有一個學習到的對數機率（Log-probability），編碼器會選擇 Token 分數總和最高的路徑進行分割。此問題透過維特比演算法（1967）解決，以位元組位置作為圖層，詞彙 Token 作為跨越連續位元組範圍的邊。遞迴是在位元組位置上進行的一維動態規劃（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

外部迴圈與輸入長度成線性關係，在每個位置受限於最長的詞彙 Token（XLM-RoBERTa 為 48 個 UTF-8 位元組）。內部 Trie 走訪（Trie walk）是熱點路徑（Hot path）：在 16k Token 的輸入上，它在每次編碼中執行數十萬次轉換並退休數千萬條指令。

Hugging Face 的 tokenizers v0.22 直接實作了該遞迴，在每個 Trie 節點使用雜湊對應（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）和斷詞標記（Word-boundary marking）。分析顯示，在我們的場景中，預處理佔總編碼時間不到 5%，因此我們在本文的其餘部分專注於維特比前向傳遞。

提升 CPU 程式碼速度有兩種方法：執行更少的指令，或獲得更高的每時脈週期指令數（IPC）。Cachegrind 測量前者，perf stat 測量後者。本文中的每一項最佳化都落在其中之一。

CPU 因四件事而停頓：快取未命中（L1d 約 4 個週期，L3 未命中到 DRAM 則需要數百個週期）、失序執行引擎無法平行化的依賴載入鏈、分支預測錯誤（每個錯誤預測導致約 15-20 個週期被刷新），以及分配器呼叫。參考 Unigram 引擎實作觸發了所有這四點：

瓶頸	機制	測量影響
每次比對的記憶體分配	針對比對的位元組執行 String::from_utf8，外加每次 Trie 比對執行一次 AHashMap 查找；Token ID 已存在於葉節點中，但參考實作未將其儲存在該處	512 個 Token 時為 7,295 次分配，1k 時為 14,542 次，16k 時為 299,171 次
每個位元組的指標追蹤	每個 Trie 節點有一個 AHashMap，雜湊下一個位元組並在每一步取值兩個指標；Node 結構還將冷欄位（如 is_leaf）綑綁在一起，導致每次存取時都會將它們拉入快取	L1d 未命中率保持在低點（1k 時約 2.5%），因為分配器的熱頁面位於 L1 中；成本表現為依賴載入延遲
長輸入時的 L2 損耗	DP 表、前綴暫存區和輸出 Token 列表均在每次呼叫時重新分配	L2 未命中率從 128 Token 時的 12% 上升到 16k 時的 50%，因為累計分配量超過了每核心 2 MB 的 L2 快取

參考分詞器瓶頸、機制與量測影響。

主要成本在於每次比對的記憶體分配。在 1k 個 Token 時，參考實作在 IPC 為 2.8 的情況下，每次編碼大約退休（完成）700 萬條指令，其中大部分用於分配器呼叫和字串轉換。僅在超過約 1k 個 Token 時，L2 未命中才變得重要，屆時累計分配足跡會溢出每核心快取。

每個 Token 的分配是固定的：無論輸入大小，每個 Token 約 2 KB 和約 18 次分配。延遲的非線性來自於 L2：累計位元組在 1k Token 左右超過 2 MB，未命中率從 8% 上升到約 50%，p99 曲線隨之彎曲以適應此變化。

我們比較了三種生產環境分詞器，它們都執行相同的 Unigram 演算法，針對相同的 XLM-RoBERTa 模型：

引擎	語言	Trie
Hugging Face	Rust	HashMap-children 字首 Trie
SentencePiece	C++	Darts 雙陣列 Trie
IREE 分詞器	C	Darts 雙陣列 Trie

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

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

所有引擎均在 Intel Xeon Platinum 8488C 上以完全最佳化（O3、原生目標、連結時最佳化）進行建構。測量時鎖定一個空閒核心。對於每個引擎和輸入大小，我們收集牆鐘時間延遲（p50 和 p99，經過 1,000 次預熱後進行 10,000 次迭代）、透過 Valgrind cachegrind 退休的指令，以及來自 perf stat 硬體計數器的 IPC 和快取未命中率，並由測量視窗周圍的全域分配器包裝器計算堆疊分配。

在 514 個 Token 時（超過 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 時的分詞器延遲、指令數、IPC 與配置量。

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

SentencePiece 和 IREE 都使用 Aoe 於 1989 年引入的雙陣列 Trie（Aoe, 1989; Karoonboonyanan）。Trie 被編碼為兩個扁平整數陣列：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 */ }

每次 Trie 走訪只需兩次陣列載入、一次整數加法和一次比較，沒有雜湊、沒有指標追蹤，也沒有每個節點的堆疊分配。建構過程安置每個節點，使其子節點落在驗證陣列的空閒槽位中，允許多個父節點共享區域，只要它們的子節點在跟隨的位元組上不同即可。

對於 XLM-RoBERTa 的 250K 詞彙，整個 Trie 適合在約 9 MB 的連續記憶體中（約 780K 槽位 × 12 位元組，用於每個槽位的偏移量、驗證和 Token ID）。單次編碼的熱工作集約為 100 KB，舒適地落入 L2 中，硬體預取器鎖定規則的存取模式。

相比之下，參考實作在每個節點維護一個子節點雜湊對應表，每個位元組步驟花費約四次依賴載入。雜湊位元組、載入桶、跟隨指標到桶條目、跟隨另一個指標到堆疊上的子節點，然後諮詢它自己的雜湊對應表獲取下一個位元組。堆疊物件散佈且大多數載入未命中快取。

SP 和 IREE 都將 Token ID 直接儲存在 Trie 節點中。參考實作的 Trie 僅傳回比對到的位元組，因此編碼器必須為每個比對配置一個新字串，在側邊雜湊對應表中查找以恢復 Token ID，並從單獨的向量讀取分數。SP 將 ID 作為 Trie 儲存的值傳回，並從扁平浮點陣列中讀取分數：

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，而不是在單次呼叫中傳回所有比對，但成本模型是相同的：Token ID 和分數可作為扁平陣列索引存取，Trie 走訪本身沒有分配或雜湊。IREE 每次編碼僅配置一個輸出緩衝區；SP 在 DP 期間會額外配置每個比對的格點節點（Lattice node），在 514 個 Token 下總共配置約 1,559 次。

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

基準保留了參考實作的雜湊對應子節點 Trie，但做了兩項更改。一個由呼叫者擁有的暫存結構持有 DP 表、預處理位元組和輸出 Token ID，因此在預熱後，熱路徑不會再產生任何分配。Token ID 和分數直接儲存在 Trie 節點中，消除了每次比對的字串轉換和側邊雜湊對應表查找。

內部迴圈：

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

這是相同的演算法，具有相同的 Trie 形狀和相同的存取模式，只是沒有分配和冗餘查找。514 個 Token 的結果：

引擎	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 時，零配置基準與現有分詞器實作的比較。

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

在每個大小上，基準測試將 p50 延遲比參考實作降低了 2-3 倍，並且其 L2 未命中率在 2k Token 前保持在 2-3% 左右，而參考實作則為 8-48%。剩下的成本是 HashMap 指標追蹤，下一節將解決此問題。

雜湊對應 Trie 是一種指標追蹤。SP 和 IREE 使用雙陣列 Trie（見上一節）解決此問題，我們借用了相同的資料結構。區別在於 SP 和 IREE 是支援串流輸入、輸出偏移量和多種編碼模式的通用函式庫；這種靈活性使它們需要在 Trie 周圍進行額外的 bookkeeping（SP 中的格點，IREE 中的八級管線）。我們不需要這些，因此我們直接在維特比迴圈中嵌入 Trie 並捨棄其餘部分。

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

位元組步驟只需兩次陣列讀取、一次整數加法和一次比較。整個 Trie 約為 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 後的分詞器延遲、指令數與快取未命中率。

牆鐘時間比基準下降了 2.3 倍，比參考實作下降了 4.8 倍。指令數比基準再下降了 28%。砍掉格點和管線讓我們能夠在相同的 Trie 形狀下，以每次編碼 1.10M 的指令數超越 SP 的 1.82M 和 IREE 的 1.61M；差距在於它們為了我們不需要的通用 API 而保留的額外簿記。

最佳化 1 中的 Darts Trie 需要每個位元組步驟進行兩次依賴載入。首先是父節點的基準偏移量，然後是候選子節點槽位處的檢查條目，以確認父節點擁有它。檢查條目僅驗證所有權。相同的問題可以由每個節點的點陣圖（Bitmap）回答，該點陣圖記錄了哪些位元組有子節點。透過雙陣列 Trie 的建構，父節點點陣圖中位元組 b 的位元位設定完全取決於該位元組的候選槽位是否由父節點擁有。點陣圖和檢查陣列攜帶相同的資訊，因此我們可以完全從執行階段結構中刪除檢查陣列。

點陣圖查找編譯為針對一個 64 位元字組的單一位元測試，大約在一個週期內運行。相關的 POPCNT 指令（計算暫存器中所有已設定位元的數量）是其他點陣圖索引 Trie 設計用來直接從點陣圖計算子節點偏移量的方法。我們不需要它，因為 Darts 的建構已經將該偏移量儲存在節點的基準欄位中。

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

在處理這些問題的同時，我們將四個每個節點的欄位（點陣圖、基準、Token ID 和分數）打包成一個 64 位元組的快取列。單次節點存取現在會提取所有內容：我們在終端節點需要的分數和 Token ID，以及用於下一步的點陣圖和基準。檢查陣列僅在建構期間使用，並從執行階段佈局中刪除。熱路徑索引未經檢查，因為 Trie 建構和迴圈結構已經保證了邊界。其代價是空間（空間）：在每個節點 64 位元組 × 約 780K 槽位下，Trie 從約 9 MB 增長到約 50 MB。

514 個 Token 的結果：

引擎	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%
+ Bitmap and Inline Packing	65 µs	77 µs	1.06M	1.8K	20.53%	15.01%

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

在 514 個 Token 下，牆鐘時間系統性地再下降了 4.5%，且隨輸入長度增長，在 4k 和 16k 時達到 6-7%。刪除檢查陣列使每個位元組 Trie 步驟從兩次快取列載入變為一次，這使得每次編碼的 L2 存取次數減少了 2.5 倍（1.8K 對比普通 Darts 的 4.6K）。未命中率從 6% 跳升至 20%，但大部分原因是分母變小：存取次數減少了一半以上，導致我們發生的未命中佔比變大。

Trie 資料約為 50 MB（780,000 個節點，每個 64 位元組）。在預設的 Linux 程序中，該記憶體由 4 KB 分頁支援，因此完整的 Trie 跨越約 12,000 個不同的虛擬分頁，遠超過 CPU 第一級資料轉換後備緩衝區（Translation Lookaside Buffer, TLB）的容量（Sapphire Rapids 有 96 個條目）。每個維特比步驟觸發不同的節點，在 512 個 Token 的編碼過程中，我們在分頁表走訪中消耗了約 9,000 個週期，約佔每次編碼預算的 3%。

解決方案是用 2 MB 巨型分頁而不是 4 KB 分頁來支援 Trie。同樣的 50 MB 現在跨越 25 個分頁，完全適合 TLB，且分頁表目錄本身停止與 Trie 爭奪 L2 快取。

Linux 有兩種方式用 2 MB 分頁支援記憶體。機會主義式的是透明巨型分頁（THP）：你的程式要求核心將記憶體區域從 4 KB 升級為 2 MB 分頁，背景核心討論串（Thread）會在有時間和連續實體記憶體可用時嘗試執行此動作。另一種選擇是直接從核心在啟動時預留的巨型分頁池中分配 Trie：

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 個巨型分頁；Trie 消耗了其中的 24 個。在 mmap 之後，/proc/<pid>/smaps 確認了該區域：KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB。

牆鐘時間獲得了 3–12% 的增益，跨越各種輸入大小，且與工作集長度一致且成正比：

Token 數	無巨型分頁	有巨型分頁	Δ
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 的分詞器延遲。

最大的勝利是在 4k Token 時，此時工作集足夠大，以至於分頁表流量正在與 Trie 資料競爭 L2 頻寬。超過 4k 時增益縮小，因為 L3 未命中佔據主導地位，分頁表走訪佔總時間的比例變小。

綜合這三項最佳化，這是我們針對測試的每個 RoBERTa 分詞器進行測量的最終引擎結果。除了原生的 C++ SentencePiece 和 C IREE 二進位檔之外，我們還基準測試了生產使用者會使用的現成 Rust 包裝器 crates：sentencepiece 和 iree-tokenizer。sentencepiece crate 在每個輸入大小下比原生 C++ 二進位檔測量出高出 1.6-1.9 倍的延遲，額外開銷來自於包裝器在每次編碼時分配新的 Token 片段列表，每個列表都持有自己片段文字的副本。iree-tokenizer crate 將其內部緩衝區調整為每個輸入大小，這避免了原生 IREE 二進位檔無論輸入大小如何都要支付的恆定每次編碼分配，這在短輸入時尤為重要，因為分配本會主導實際的 Tokenization 工作。在生產環境的輸入長度下，恆定成本被攤銷，而包裝器因將 Token 複製回 Rust 產生的每次呼叫開銷使其延遲超過了原生二進位檔。

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

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

延遲降低的主要原因來自於移除無謂工作的輕量級變更：丟棄每次編碼的分配、以雙陣列取代雜湊對應子節點 Trie，並剝離通用 API 的開銷。使用現有的每個節點點陣圖作為有效性檢查，以及用 2 MB 巨型分頁支援 Trie，這些綜合起來在雙陣列 Trie 的更大轉變之上貢獻了 10-20% 的改進，具體取決於輸入大小。

SentencePiece 和 IREE 周圍的現成 Rust 包裝器 crates 反向說明了同樣的觀點。在原生 C 和 C++ 分詞器之上，包裝器引入的 FFI 邊界和每次呼叫的分配在延遲數據中顯而易見。最終維特比編碼器的 Rust 原始碼可在 github.com/perplexityai/pplx-garden 取得。

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

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

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

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

動機

維特比演算法（Viterbi Algorithm）

參考實作

關於預處理的說明

參考實作的時間消耗

我們的測量方式

為什麼 SentencePiece 和 IREE 更快：雙陣列 Trie

基準：零分配參考實作版本

最佳化 1：無額外抽象的雙陣列 Trie

優化 2：位圖與內聯打包

優化 3：Trie 的巨型頁面

最終比較

總結

參考資料

引用