Melhoria do Desempenho de CPU do Tokenizador Unigram

Reimplementamos o nosso tokenizador Unigram do zero como um projeto focado em desempenho. Com comprimentos de entrada de produção, o novo codificador reduz a latência p50 em aproximadamente 5× em comparação com o crate tokenizers do Hugging Face, ~2× em comparação com o SentencePiece (C++) e ~1.5× em comparação com o tokenizador do IREE (C), sem alocações de heap em estado estacionário. Na produção, isso reduziu a utilização da CPU na nossa pilha de inferência em 5-6× e eliminou dezenas de milissegundos da latência do reranqueador.

O custo de inferência de LLMs é geralmente enquadrado como trabalho de GPU: caches KV, kernels de atenção, roteamento de especialistas. Mas uma parcela significativa do tráfego de produção é executada em modelos muito menores, duas a três ordens de magnitude menores do que os transformadores de fronteira. Modelos de incorporação, classificadores e reranqueadores ainda são executados em GPUs, mas a passagem direta (forward pass) é curta o suficiente para que tudo ao redor comece a importar.

O caso mais claro é um reranqueador pontuando centenas de documentos candidatos por solicitação. Com um modelo pequeno, o processamento da GPU normalmente termina em milissegundos de dígito único, mas cada entrada ainda precisa passar primeiro pela tokenização no lado da CPU, transformando texto em IDs de vocabulário. Quando o lote é grande, isso pode representar uma fração significativa da latência total da solicitação.

Este trabalho visa o XLM-RoBERTa, um vocabulário Unigram de 250 mil tokens treinado com o SentencePiece. Codificadores da família RoBERTa ajustados (fine-tuned) são uma escolha comum para tarefas de ranqueamento, recuperação e similaridade. Relatamos a latência por codificação de thread único em todo o texto; na produção, paralelizamos entre núcleos usando o rayon.

Ao longo desta postagem, tratamos o tokenizers crate da Hugging Face como a referência com a qual fazemos benchmarks, uma vez que é o tokenizador padrão em Rust que a maioria das equipes procura. O SentencePiece (C++) e o IREE (C) são incluídos para comparação como as outras duas principais implementações de produção.

A tokenização Unigram, introduzida por Kudo em 2018 (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) e distribuída no SentencePiece, enquadra a segmentação como um problema de caminho mais provável: cada token do vocabulário tem uma log-probabilidade aprendida, e o codificador escolhe a segmentação cujas pontuações de token somam o valor mais alto. O problema é resolvido com o algoritmo de Viterbi (1967), com posições de bytes como camadas de grafo e tokens de vocabulário como arestas que abrangem um intervalo de bytes contíguo. A recorrência é uma DP unidimensional sobre as posições de bytes:

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

O loop externo é linear no comprimento da entrada, limitado em cada posição pelo token de vocabulário mais longo (48 bytes UTF-8 para o XLM-RoBERTa). A caminhada interna na árvore trie é o caminho crítico: em uma entrada de 16 mil tokens, ela executa centenas de milhares de transições e encerra dezenas de milhões de instruções por codificação.

O tokenizers v0.22 da Hugging Face implementa a recorrência diretamente, com um mapa hash para a busca reversa e filhos de mapa hash em cada nó da 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
}

E o loop interno (simplificado) — cada correspondência de busca de prefixo aloca uma string nova e, em seguida, sonda o mapa 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
}

O código está em um Rust legível, mas muito trabalho acontece de forma invisível no nível do código-fonte. A seção seguinte detalha para onde vai o tempo.

Antes de Viterbi ser executado, a entrada passa por normalização Unicode (NFKC) e marcação de limite de palavra. A criação de perfil (profiling) coloca o pré-processamento em menos de 5% do tempo total de codificação nos nossos cenários, por isso focamos na passagem direta de Viterbi para o resto da postagem.

Há duas maneiras de acelerar o código da CPU: executar menos instruções ou obter maior IPC. O Cachegrind mede a primeira, o perf stat mede a segunda. Cada otimização nesta postagem aterrissa em uma ou outra.

As CPUs travam em quatro coisas: falhas de cache (L1d ~4 ciclos, uma falha de L3 para a DRAM são centenas), correntes de carregamento dependentes que o motor de execução fora de ordem não consegue paralelizar, previsões incorretas de desvio (~15-20 ciclos descartados por palpite errado) e chamadas de alocador. A implementação do motor unigram de referência atinge todas as quatro:

Gargalo	Mecanismo	Impacto medido
Alocação por correspondência	String::from_utf8 nos bytes correspondidos mais uma consulta no AHashMap por correspondência na trie; o ID do token já está na folha, mas a referência não o armazena lá	7.295 alocações a 512 tokens, 14.542 a 1k, 299.171 a 16k
Busca de ponteiro por byte	Um AHashMap em cada nó da trie, fazendo hash do próximo byte e desreferenciando dois ponteiros por etapa; a struct Node também agrupa campos frios como is_leaf, puxando-os para o cache a cada visita	A taxa de falha em L1d permanece baixa (~2,5% a 1k) porque as páginas quentes do alocador residem em L1; o custo aparece como latência de carga dependente
Esgotamento (thrashing) de L2 em entradas longas	A tabela DP, o rascunho de prefixo e a lista de tokens de saída são todos recém-alocados a cada chamada	A taxa de falha em L2 sobe de 12% a 128 tokens para 50% a 16k conforme a pegada de alocação cumulativa excede os 2 MB de L2 por núcleo

Referência dos gargalos do tokenizador, mecanismos e impactos medidos.

O custo dominante é a alocação por correspondência. A 1 mil tokens, a implementação de referência encerra (completa) aproximadamente 7M de instruções por codificação a um IPC de 2,8, a maioria em chamadas de alocador e conversões de string. As falhas de L2 só importam após ~1 mil tokens, assim que a pegada de alocação cumulativa transborda o cache por núcleo.

Latência p50 e p99 do tokenizador de referência por tamanho de entrada.

Taxa de falta de cache L2 do tokenizador de referência por tamanho de entrada.

Bytes alocados por codificação pelo tokenizador de referência em diferentes tamanhos de entrada.

A alocação por token é constante: cerca de 2 KB e ~18 alocações por token, independentemente do tamanho da entrada. A não linearidade da latência vem do L2: os bytes cumulativos ultrapassam 2 MB por volta de 1 mil tokens, a taxa de falha sobe de 8% para ~50%, e a curva p99 se curva para corresponder.

Comparamos três tokenizadores de produção, todos executando o mesmo algoritmo Unigram contra o mesmo modelo XLM-RoBERTa:

Motor	Idioma	Trie
Hugging Face	Rust	Trie de prefixo com filhos em HashMap
SentencePiece	C++	Trie de array duplo Darts
Tokenizador IREE	C	Trie de array duplo Darts

Implementações de tokenizador, linguagens e representações trie usadas na comparação.

Vinculamos o SentencePiece e o IREE através de FFI direta em C/C++ em vez de seus wrappers em Rust; os wrappers adicionam alocações por chamada e conversões de string que não fazem parte do custo da biblioteca subjacente.

Todos os motores são construídos com otimizações completas (O3, direcionamento nativo, otimização em tempo de link). As medições são executadas fixadas a um único núcleo ocioso em um Intel Xeon Platinum 8488C. Para cada motor e tamanho de entrada, coletamos a latência de relógio de parede (p50 e p99, 10.000 iterações após 1.000 de aquecimento), instruções encerradas via Valgrind cachegrind, taxas de IPC e falhas de cache de contadores de hardware do perf stat, e alocações de heap contadas por um wrapper de alocador global em torno da janela medida.

A 514 tokens (os +2 acima de 512 são a injeção BOS/EOS):

Implementação	Latência p50	Instruções	IPC	Alocações
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

Latência do tokenizador, contagem de instruções, IPC e alocações em 514 tokens.

O SP e o IREE ficam em aproximadamente um terço da latência da referência. Eles encerram cerca de metade das instruções, executam com um IPC mais alto e alocam de uma a duas ordens de grandeza a menos.

O SentencePiece e o IREE usam a trie de array duplo introduzida por Aoe em 1989 (Aoe, 1989; Karoonboonyanan). A trie é codificada em dois arrays de inteiros planos, base e check:

cpp

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

Uma busca de filho é:

cpp

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

Cada etapa da travessia da trie precisa de apenas duas leituras de array, uma adição de inteiro e uma comparação, sem hashing, sem busca de ponteiro e sem alocação de heap por nó. A construção posiciona cada nó de forma que seus filhos caiam em slots livres no array de validação, permitindo que vários pais compartilhem regiões desde que seus filhos difiram no byte que seguem.

Para o vocabulário de 250K do XLM-RoBERTa, toda a trie cabe em ~9 MB de memória contígua (~780 mil slots × 12 bytes para o deslocamento, validação e ID de token por slot). O conjunto de trabalho ativo de uma única codificação é da ordem de 100 KB, confortavelmente em L2, e o pré-buscador de hardware trava no padrão de acesso regular.

A referência, por sua vez, mantém um mapa hash de filhos por nó, custando aproximadamente quatro cargas dependentes por etapa de byte. Faz hash do byte, carrega o bucket, segue um ponteiro para a entrada do bucket, segue outro ponteiro para o nó filho no heap e, em seguida, consulta seu próprio mapa hash para o próximo byte. Os objetos no heap se dispersam e a maioria das cargas perde o cache.

O SP e o IREE armazenam o ID do token diretamente no nó da trie. A implementação da trie de referência retorna apenas os bytes correspondidos, portanto, o codificador tem de alocar uma string nova para cada correspondência, procurá-la em um mapa hash lateral para recuperar o ID do token e ler a pontuação de um vetor separado. O SP retorna o ID como o valor armazenado da trie e lê a pontuação de um array de ponto flutuante plano:

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

O IREE usa uma API de cursor com estado em vez de retornar todas as correspondências em uma única chamada, mas o modelo de custo é o mesmo: os IDs de tokens e as pontuações são acessíveis como índices de array plano, sem alocação ou hashing na caminhada da trie em si. O IREE aloca apenas um buffer de saída por codificação; o SP adicionalmente aloca um nó de rede (lattice node) por correspondência durante a DP, totalizando aproximadamente 1.559 alocações a 514 tokens.

Antes de alterar a trie, isolamos o custo do algoritmo do custo de implementação: quão rápido a referência é executada com o trabalho desnecessário removido?

A linha de base mantém a trie de filhos de mapa hash da referência, mas faz duas alterações. Uma estrutura de rascunho de propriedade do chamador contém a tabela DP, os bytes pré-processados e os IDs de tokens de saída, de modo que o caminho crítico não faz alocações após o aquecimento. O ID do token e a pontuação são armazenados diretamente no nó da trie, removendo a conversão de string por correspondência e a consulta ao mapa hash lateral.

Loop interno:

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

Este é o mesmo algoritmo, com a mesma forma de trie e o mesmo padrão de acesso, apenas sem alocações e sem consultas redundantes. Resultados a 514 tokens:

Motor	p50	Instruções	IPC	Alocações
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
Linha de base	156 µs	1,53M	2,62	0

A linha de base sem alocação comparada com implementações de tokenizador existentes em 514 tokens.

A remoção da materialização de strings por correspondência e da consulta ao mapa hash secundário reduz as instruções em 2,4× em comparação com a referência. O IPC cai com elas (2,86 → 2,62) porque a busca de ponteiro no mapa hash, anteriormente oculta pelo trabalho do alocador, é agora o custo dominante por byte.

Latência p50 e p99 do tokenizador de referência e da linha de base sem alocação por tamanho de entrada.

Taxa de falta de cache L2 do tokenizador de referência e da linha de base sem alocação por tamanho de entrada.

A linha de base reduz a latência p50 em 2-3× em comparação com a referência em cada tamanho, e sua taxa de falha de L2 permanece próxima de 2-3% até 2k tokens versus os 8-48% da referência. O custo restante é a busca de ponteiro no HashMap, que a seção seguinte aborda.

A trie de mapa hash é uma busca de ponteiro. O SP e o IREE resolvem isso com uma trie de array duplo (veja a seção anterior), e nós adotamos a mesma estrutura de dados. A diferença é que o SP e o IREE são bibliotecas de uso geral que suportam entrada de streaming, deslocamentos de saída e vários modos de codificação; essa flexibilidade custa a eles contabilidade extra em torno da trie (uma rede no SP, um pipeline de oito estágios no IREE). Não precisamos de nada disso, então colocamos a trie diretamente no loop de Viterbi e descartamos o resto.

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

Uma etapa de byte custa duas leituras de array, uma adição de inteiro e uma comparação. A trie inteira tem cerca de 9 MB, mas qualquer codificação única percorre apenas ~100 KB dela, de modo que os dados ativos permanecem em L2.

Motor	p50	p99	Instruções	Falha L2 %	Falha 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%
Linha de base	155 µs	1.170 µs	1,53M	2,59%	16,66%
+ Darts	68 µs	80 µs	1,10M	6,45%	11,42%

Latência do tokenizador, instruções e taxas de falta de cache após adotar a trie de matriz dupla.

O relógio de parede cai 2,3× em relação à linha de base e 4,8× em relação à referência. As instruções caem outros 28% em relação à linha de base. Cortar a rede e o pipeline nos permite encerrar 1,10M de instruções por codificação contra 1,82M do SP e 1,61M do IREE na mesma forma de trie; a lacuna é a contabilidade que eles mantêm para APIs de uso geral de que não precisamos.

A trie Darts da Otimização 1 precisa de duas cargas dependentes por etapa de byte. Primeiro o deslocamento base do pai, depois a entrada check no slot do filho candidato para confirmar que o pai é dono dele. A entrada check apenas valida a propriedade. A mesma pergunta pode ser respondida por um bitmap por nó que registra quais bytes têm filhos. Por construção da trie de array duplo, o bit para o byte b no bitmap do pai é definido exatamente quando o slot candidato para esse byte é de propriedade do pai. O bitmap e o array check carregam a mesma informação, de modo que podemos descartar o array check da estrutura de tempo de execução inteiramente.

A busca no bitmap é compilada para um único teste de bit em uma palavra de 64 bits, que é executada em cerca de um ciclo. A instrução POPCNT relacionada, que conta todos os bits definidos em um registrador, é o que outros designs de trie indexados por bitmap usam para calcular um deslocamento de filho diretamente a partir do bitmap. Nós não precisamos dela porque a construção Darts já armazena esse deslocamento no campo base do nó.

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

Já que estamos nisso, empacotamos os quatro campos por nó (bitmap, base, ID de token e pontuação) em uma única linha de cache de 64 bytes. Uma única visita ao nó agora traz tudo: a pontuação e o ID do token de que precisamos nos nós terminais, mais o bitmap e a base para a próxima etapa. O array check é usado apenas durante a construção e é descartado do layout de tempo de execução. A indexação do caminho crítico não é verificada porque a construção da trie e a estrutura do loop já garantem os limites. A desvantagem é o Espaço: a 64 bytes por nó × ~780 mil slots, a trie cresce de ~9 MB para ~50 MB.

Resultados a 514 tokens:

Motor	p50	p99	Instruções	Acessos L2	Falha L2 %	Falha 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%
Linha de base	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 e Empacotamento Inline	65 µs	77 µs	1,06M	1,8K	20,53%	15,01%

Resultados do tokenizador em 514 tokens após adicionar bitmap e compactação inline.

O relógio de parede cai sistematicamente outros 4,5% a 514 tokens e cresce com o comprimento da entrada, alcançando 6-7% a 4k e 16k. Descartar o array check transforma a etapa da trie por byte de duas cargas de linha de cache em uma, o que resulta em acessos a L2 2,5× menores por codificação (1,8K versus os 4,6K do Darts simples). A taxa de falha pula de 6% para 20%, mas a maior parte disso é o denominador: com menos da metade dos acessos, as falhas que temos assumem uma proporção maior.

Os dados da trie têm cerca de 50 MB (780.000 nós a 64 bytes cada). Em um processo Linux padrão, essa memória é suportada por páginas de 4 KB, de modo que a trie completa abrange cerca de 12 mil páginas virtuais distintas, muito além do que o Translation Lookaside Buffer de dados de primeiro nível da CPU pode reter (o Sapphire Rapids tem 96 entradas). Cada etapa de Viterbi toca em um nó diferente e, ao longo de uma codificação de 512 tokens, gastamos cerca de 9 mil ciclos em caminhadas na tabela de páginas, cerca de 3% do orçamento por codificação.

A correção é suportar a trie com páginas grandes (huge pages) de 2 MB em vez de páginas de 4 KB. Os mesmos 50 MB agora abrangem 25 páginas, cabem inteiramente no Translation Lookaside Buffer, e os diretórios da tabela de páginas param de competir com a trie pelo cache L2.

O Linux tem duas maneiras de suportar memória com páginas de 2 MB. A oportunista são as páginas grandes transparentes (THP): o seu programa pede ao kernel para atualizar uma região de memória de páginas de 4 KB para 2 MB, e um tópico (thread) em segundo plano do kernel tenta fazer isso quando tem tempo e memória física contígua disponível. A outra alternativa é alocar a trie diretamente de um pool de páginas grandes pré-reservado que o kernel reserva na inicialização:

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

O pool precisa existir no host (vm.nr_hugepages definido na inicialização). Nas nossas instâncias de produção, 10.561 páginas grandes são reservadas; a trie consome 24 delas. Após o mmap, /proc/<pid>/smaps confirma a região: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB.

O ganho é de 3–12% no relógio de parede em todos os tamanhos de entrada, consistente e proporcional ao comprimento do conjunto de trabalho:

Tokens	Sem páginas grandes	Com páginas grandes	Δ
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%

Latência do tokenizador com e sem páginas grandes em diferentes tamanhos de entrada.

O maior ganho é a 4k tokens, onde o conjunto de trabalho é grande o suficiente para que o tráfego da tabela de páginas estivesse competindo ativamente com os dados da trie pela largura de banda de L2. Além de 4k, o ganho diminui porque as falhas de L3 dominam e as caminhadas na tabela de páginas tornam-se uma parcela menor do tempo total.

Juntando as três otimizações, aqui está o motor final medido contra todos os outros tokenizadores RoBERTa que testamos. Além dos binários nativos de C++ SentencePiece e C IREE, também fizemos o benchmark dos crates de wrapper em Rust prontos para uso que um usuário de produção procuraria, sentencepiece e iree-tokenizer. O crate sentencepiece mede uma latência de 1,6-1,9× maior do que o binário nativo de C++ em cada tamanho de entrada, com a sobrecarga vindo do wrapper alocando uma nova lista de pedaços de token, cada um contendo sua própria cópia do texto do pedaço, em cada codificação. O crate iree-tokenizer dimensiona seu buffer interno para cada entrada, o que evita uma alocação constante por codificação que o binário nativo do IREE paga independentemente do tamanho da entrada, e isso importa mais em entradas curtas onde a alocação dominaria o trabalho real de tokenização. Em comprimentos de entrada de produção, o custo constante se amortece e a sobrecarga própria por chamada do wrapper de copiar os tokens de volta para o Rust empurra sua latência acima da do binário nativo.

Latência p50 e p99 por codificação entre implementações de tokenizador e tamanhos de entrada.

O motor final executa o mesmo Viterbi sobre o mesmo vocabulário de 250.000 tokens, não aloca nada no caminho crítico e produz saída com tokens exatos em comparação com a referência. Cada etapa de byte agora é uma única carga de linha de cache de 64 bytes, um teste de bitmap e uma adição de inteiro, uma redução em relação à sonda de HashMap, a uma chamada de alocador e a vários desvios de caso especial na implementação de base. As instruções por codificação caíram de 3,66M para 1,04M, uma queda de 3,5×. O relógio de parede corresponde a essa proporção em entradas curtas e se amplia ainda mais em entradas longas, onde as alocações por token da referência começam a transbordar L2 e L3.

Na prática, este trabalho reduziu a utilização da CPU na camada de pré-processamento da nossa pilha de inferência em 5-6× e eliminou dezenas de milissegundos da latência do reranqueador.

A maior parte da redução de latência veio de alterações leves que removeram o trabalho desperdiçado: descartar alocações por codificação, substituir a trie de filhos de HashMap por um array duplo e remover a sobrecarga de API genérica. Usar o bitmap existente por nó como a verificação de validade e apoiar a trie com páginas grandes de 2 MB combinados responderam por 10-20% além da mudança maior para uma trie de array duplo, dependendo do tamanho da entrada.

Os crates de wrapper em Rust prontos para uso em torno do SentencePiece e do IREE ilustram o mesmo ponto ao contrário. Além dos tokenizadores nativos de C e C++, o limite de FFI e as alocações por chamada que os wrappers introduzem são visíveis nos números de latência. O código-fonte em Rust para o codificador Viterbi final está disponível em github.com/perplexityai/pplx-garden.

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

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

Tokenizador 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

Páginas grandes (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}
}

Motivação

O Algoritmo de Viterbi

Implementação de Referência

Uma Nota sobre Pré-processamento

Onde a Implementação de Referência Gasta o Seu Tempo

Como Medimos

Por que o SentencePiece e o IREE são Mais Rápidos: A Trie de Array Duplo

Linha de Base: Uma Porta Sem Alocação da Referência

Otimização 1: Trie de Array Duplo Sem Abstrações Extras

Otimização 2: Bitmap e empacotamento em linha

Otimização 3: Páginas enormes para o trie

Comparação Final

Considerações Finais

Referências

Citação