改进 Unigram 分词器 CPU 性能

我们从零开始重新实现了 Unigram 分词器，作为一项专注性能优化的项目。在生产环境的输入长度下，新编码器相较于 Hugging Face tokenizers crate，将 p50 延迟降低了约 5 倍；相较于 SentencePiece (C++) 降低了约 2 倍；相较于 IREE 的分词器 (C) 降低了约 1.5 倍，且实现了零稳态堆内存分配。在生产环境中，这使我们推理堆栈的 CPU 利用率降低了 5-6 倍，并将重排序器的延迟减少了两位数的毫秒级时间。

LLM 推理成本通常被归结为 GPU 工作：KV 缓存、注意力算子、专家路由。但生产环境中很大一部分流量运行在规模小得多的模型上，其规模比前沿 Transformer 模型小两到三个数量级。嵌入模型、分类器和重排序器仍在 GPU 上运行，但其前向传播过程足够短，以至于其周围的一切都开始变得至关重要。

最明显的例子是每秒处理数百个候选文档进行评分的重排序器。对于小型模型，GPU 计算通常在个位数的毫秒内完成，但每个输入在处理前仍必须先通过 CPU 侧的分词过程，将文本转换为词汇 ID。当批处理规模较大时，这可能占据总请求延迟的很大一部分。

这项工作针对的是 XLM-RoBERTa，这是一个采用 SentencePiece 训练的 250K 词汇量的 Unigram 模型。经过微调的 RoBERTa 系列编码器是排名、检索和相似度任务的常见选择。我们报告的是单线程下的每编码延迟；在生产环境中，我们使用 rayon 在各核心间进行并行处理。

在整篇文章中，我们将 Hugging Face 的 tokenizers crate 作为我们基准测试的参考对象，因为这是大多数团队默认选用的 Rust 分词器。我们也将 SentencePiece (C++) 和 IREE (C) 作为另外两个主要的生产环境实现包含在内进行比较。

Unigram 分词最初由 Kudo 在 2018 年提出（子词正则化：通过多个子词候选改进神经网络翻译模型）并由 SentencePiece 发布，它将分词问题建模为一个概率最大路径问题：每个词汇 token 都有一个学习到的对数概率，编码器选择分词后 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 树遍历是热点路径：在 16k token 的输入上，它执行数十万次转换，且每次编码都会退役数千万条指令。

Hugging Face 的 tokenizers v0.22 直接实现了该递推过程，在每个 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
}

内部循环（简化版）——每次前缀搜索匹配都会分配一个新的字符串，然后对哈希映射进行探测：

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) 和词边界标记。性能分析显示，在我们的场景中，预处理耗时不到总编码时间的 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 缓存。

参考 tokenizer 的瓶颈、机制和实测影响。

主要成本是每次匹配的分配。在 1k token 时，参考实现每次编码退休（完成）约 7M 条指令，IPC 为 2.8，其中大部分在分配器调用和字符串转换中。只有在 token 数量超过 1k 后，当累计分配足迹超过每核缓存时，L2 未命中问题才会凸显。

每 token 的分配是恒定的：无论输入大小如何，每个 token 大约有 2 KB 和约 18 次分配。延迟的非线性源于 L2：累计字节在 1k token 左右超过 2 MB，未命中率从 8% 上升至约 50%，p99 曲线也随之弯曲。

我们比较了三个生产级分词器，它们都在相同的 XLM-RoBERTa 模型上运行相同的 Unigram 算法：

引擎	语言	Trie
Hugging Face	Rust	HashMap 子节点前缀 Trie
SentencePiece	C++	Darts 双数组 Trie
IREE 分词器	C	Darts 双数组 Trie

比较中使用的 tokenizer 实现、语言和 trie 表示。

我们通过直接的 C/C++ FFI 而非其 Rust 封装来链接 SentencePiece 和 IREE；封装会增加额外的调用分配和字符串转换，这些并非底层库成本的一部分。

所有引擎均在全面优化（O3，原生目标，链接时优化）下构建。测量是在 Intel Xeon Platinum 8488C 上固定在一个安静的核心上运行的。对于每个引擎和输入规模，我们收集挂钟延迟（预热 1,000 次迭代后进行 10,000 次迭代的 p50 和 p99）、通过 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 下的 tokenizer 延迟、指令数、IPC 和分配情况。

SP 和 IREE 的延迟大约是参考实现的三分之一。它们的指令退役数量减少了一半，运行 IPC 更高，分配次数减少了一到两个数量级。

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 期间额外为每个匹配项分配一个晶格节点，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

与现有 tokenizer 实现相比的零分配基线，在 514 个 token 下的表现。

消除每次匹配的字符串具体化和二次哈希映射查找，使得指令数相比参考实现减少了 2.4 倍。IPC 随之下降 (2.86 → 2.62)，因为之前隐藏在分配器工作背后的哈希映射指针追踪现在成为了每字节的主导成本。

参考 tokenizer 和零分配基线 tokenizer 按输入大小划分的 p50 和 p99 延迟。

参考 tokenizer 和零分配基线 tokenizer 按输入大小划分的 L2 缓存未命中率。

在所有规模上，基准版本将 p50 延迟比参考实现降低了 2-3 倍，且其 L2 未命中率在 2k token 前一直保持在 2-3% 左右，而参考实现则为 8-48%。剩余的成本是 HashMap 指针追踪，下一节将解决该问题。

哈希映射 Trie 是一个指针追踪过程。SP 和 IREE 通过双数组 Trie 解决了这个问题（见上一节），我们借用了相同的数据结构。不同之处在于 SP 和 IREE 是通用库，支持流式输入、输出偏移量和多种编码模式；这种灵活性导致它们在 Trie 周围增加了额外的簿记工作（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 后的 tokenizer 延迟、指令数和缓存未命中率。

挂钟时间比基准下降了 2.3 倍，比参考实现下降了 4.8 倍。指令数比基准进一步下降了 28%。去掉晶格和管道让我们能够在相同的 Trie 形状下，实现每编码 1.10M 条指令，而 SP 为 1.82M，IREE 为 1.61M；差距在于它们为了通用 API 所维持的簿记工作。

来自优化 1 的 Darts Trie 每字节步进需要两次依赖加载。首先是父节点的 base 偏移量，然后是候选子节点槽位的 check 条目，以确认父节点拥有它。Check 条目仅验证所有权。同一个问题可以通过记录哪些字节具有子节点的每节点位图来回答。根据双数组 Trie 的构建，父节点位图中字节 b 的位被设置，恰好当该字节的候选槽位由父节点拥有时。位图和 check 数组携带相同的信息，因此我们可以从运行时结构中彻底删掉 check 数组。

位图查找被编译为对一个 64 位字的一次位测试，运行大约需要一个周期。相关的 POPCNT 指令（用于统计寄存器中所有被设置的位）是其他位图索引 Trie 设计用来直接从位图中计算子节点偏移量的方法。我们不需要它，因为 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、token ID 和分数）打包进一个 64 字节的缓存行。单次节点访问现在拉入了所有内容：我们在终端节点需要的分数和 token ID，以及下一步需要的位图和 base。Check 数组仅在构建期间使用，已从运行时布局中移除。热路径索引未经检查，因为 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%
+ 位图和内联打包	65 µs	77 µs	1.06M	1.8K	20.53%	15.01%

添加 bitmap 和内联打包后，514 个 token 下的 tokenizer 结果。

挂钟时间在 514 token 时系统性地又下降了 4.5%，并随着输入长度增长，在 4k 和 16k 时达到 6-7%。丢弃 check 数组将每字节 Trie 步进从两次缓存行加载变为一次，即每次编码的 L2 访问次数减少了 2.5 倍（1.8K 对比普通 Darts 的 4.6K）。未命中率从 6% 跳升至 20%，但这大部分是因为分母：访问次数减少了不到一半，我们确实发生的未命中占据了更大的份额。

Trie 数据约为 50 MB（780,000 个节点，每个 64 字节）。在默认的 Linux 进程中，该内存由 4 KB 页面支持，因此完整 Trie 跨越约 12,000 个不同的虚拟页面，远超 CPU 一级数据转换后备缓冲区 (TLB) 的容量（Sapphire Rapids 有 96 个条目）。每个维特比步进都会触碰不同的节点，在 512 token 的编码过程中，我们在页表遍历中消耗了约 9,000 个周期，约占每编码预算的 3%。

解决方法是用 2 MB 的巨型页面而不是 4 KB 的页面来支持 Trie。相同的 50 MB 现在跨越 25 个页面，完全适配于转换后备缓冲区，且页表目录本身不再与 Trie 争夺 L2 缓存。

Linux 有两种用 2 MB 页面支持内存的方法。机会主义的方法是透明巨型页面 (THP)：您的程序请求内核将内存区域从 4 KB 升级到 2 MB 页面，背景内核线程在有空闲时间和连续物理内存时尝试执行此操作。另一种选择是直接从内核在启动时留出的预留巨型页面池中分配 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%

在不同输入大小下，使用和不使用大页时的 tokenizer 延迟。

最大的收益是在 4k token 时，此时工作集足够大，以至于页表流量在与 Trie 数据争夺 L2 带宽。超过 4k 后，收益缩减，因为 L3 未命中占主导地位，页表遍历占总时间的份额变小。

结合这三个优化，以下是最终引擎与我们测试的每一个其他 RoBERTa 分词器的对比。除了原生的 C++ SentencePiece 和 C IREE 二进制文件外，我们还对生产用户通常会使用的现成 Rust 封装 crate（sentencepiece 和 iree-tokenizer）进行了基准测试。sentencepiece crate 在所有输入长度上显示的延迟比原生 C++ 二进制文件高 1.6-1.9 倍，开销来自于封装器在每次编码时分配一个新的 token 片段列表，且每个片段都持有片段文本的副本。iree-tokenizer crate 将其内部缓冲区调整为每个输入的大小，这避免了原生 IREE 二进制文件无论输入大小如何都要支付的恒定每编码分配成本，这在短输入时尤其重要，因为否则分配会主导实际的分词工作。在生产输入长度下，恒定成本被摊销，而封装器通过将 token 复制回 Rust 产生的每调用开销使其延迟推高至原生二进制文件之上。

跨 tokenizer 实现和输入大小的每次 encode p50 和 p99 延迟。

最终引擎在相同的 250,000 token 词汇量上运行相同的维特比算法，在热路径上零分配，并产生与参考实现完全相同的输出。每个字节步进现在是一个 64 字节缓存行加载、一次位图测试和一次整数加法，相比基准实现中的 HashMap 探测、分配器调用和几个特殊情况分支有了极大改进。每次编码指令数从 3.66M 下降到 1.04M，减少了 3.5 倍。挂钟时间在短输入时匹配该比例，并在长输入时进一步拉大，因为参考实现的每 token 分配开始溢出 L2 和 L3。

在实践中，这项工作将我们推理堆栈预处理层的 CPU 利用率降低了 5-6 倍，并将重排序器的延迟减少了两位数的毫秒数。

延迟降低的主要部分来自于消除浪费工作的轻量级更改：丢弃每编码分配、将 HashMap 子节点 Trie 替换为双数组，以及剥离通用 API 开销。使用现有的每节点位图作为有效性检查，并将 Trie 支持改为 2 MB 巨型页面，在转换为双数组 Trie 的更大转换基础上，根据输入大小额外贡献了 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). 子词正则化：通过多个子词候选改进神经网络翻译模型。 https://arxiv.org/abs/1804.10959

Viterbi, A. J. (1967). 卷积码的误差界限和渐近最优解码算法。 IEEE Transactions on Information Theory. https://en.wikipedia.org/wiki/Viterbi_algorithm

Aoe, J. (1989). 使用双数组结构的高效数字搜索算法。 IEEE Transactions on Software Engineering. https://ieeexplore.ieee.org/document/31365/

Karoonboonyanan, T. 双数组 Trie 的一种实现。 https://linux.thai.net/~thep/datrie/datrie.html

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

巨型页面 — 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) 算法

参考实现

关于预处理的说明

参考实现的时间消耗点

测量方法

为何 SentencePiece 和 IREE 更快：双数组 Trie

基准：参考实现的零分配移植版本

优化 1：没有额外抽象的双数组 Trie

优化 2：位图与内联打包

优化 3：字典树的大页面

最终对比

总结

参考文献

引用