유니그램 토크나이저 CPU 성능 향상

당사는 성능 향상을 위한 집중 프로젝트의 일환으로 유니그램(Unigram) 토크나이저를 처음부터 다시 구현했습니다. 프로덕션 입력 길이에서 새로운 인코더는 Hugging Face 토크나이저 크레이트(crate) 대비 p50 지연 시간을 약 5배, SentencePiece(C++) 대비 약 2배, IREE 토크나이저(C) 대비 약 1.5배 단축했으며, 정상 상태의 힙 할당은 전혀 발생하지 않았습니다. 프로덕션 환경에서 이 구현은 추론 스택의 CPU 사용률을 5~6배 감소시켰으며, 리랭커(reranker) 지연 시간을 두 자릿수 밀리초만큼 단축했습니다.

LLM 추론 비용은 일반적으로 GPU 작업(KV 캐시, 어텐션 커널, 전문가 라우팅 등)으로 간주됩니다. 그러나 프로덕션 트래픽의 상당 부분은 프런티어 트랜스포머보다 두세 자릿수 더 작은 소규모 모델에서 실행됩니다. 임베딩 모델, 분류기, 리랭커는 여전히 GPU에서 실행되지만, 순방향 패스(forward pass)가 짧아 그 주변의 모든 요소가 중요해지기 시작합니다.

가장 명확한 사례는 요청당 수백 개의 후보 문서를 점수 매기는 리랭커입니다. 소규모 모델의 경우, GPU 연산은 일반적으로 한 자릿수 밀리초 내에 완료되지만, 모든 입력은 여전히 CPU 측 토큰화 과정을 먼저 거쳐 텍스트를 어휘 ID로 변환해야 합니다. 배치 크기가 클 경우, 이는 전체 요청 지연 시간 중 상당 부분을 차지할 수 있습니다.

이 작업은 SentencePiece로 훈련된 250K 토큰 유니그램 어휘인 XLM-RoBERTa를 대상으로 합니다. 미세 조정된 RoBERTa 계열 인코더는 순위 지정, 검색 및 유사도 작업에 흔히 사용됩니다. 본 문서 전반에서 단일 스레드 인코딩당 지연 시간을 보고하며, 프로덕션 환경에서는 rayon을 사용하여 코어 전반에 걸쳐 병렬화합니다.

본 게시물 전반에서 대부분의 팀이 기본적으로 선택하는 Rust 토크나이저인 Hugging Face의 tokenizers crate를 벤치마크 비교 기준으로 삼습니다. SentencePiece(C++)와 IREE(C)는 다른 두 가지 주요 프로덕션 구현체로서 비교 대상으로 포함되었습니다.

2018년 Kudo가 소개하고(Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) SentencePiece에 탑재된 유니그램 토큰화는 세그먼테이션을 가장 확률이 높은 경로 문제로 정의합니다. 각 어휘 토큰은 학습된 로그 확률을 가지며, 인코더는 토큰 점수의 합이 가장 높은 세그먼테이션을 선택합니다. 이 문제는 비테르비 알고리즘(1967)을 통해 해결되며, 바이트 위치를 그래프 계층으로, 어휘 토큰을 연속된 바이트 범위를 걸치는 에지로 사용합니다. 재귀는 바이트 위치에 대한 1차원 동적 계획법(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) 탐색은 핵심 경로(hot path)로, 16k 토큰 입력에서 인코딩당 수십만 개의 전이를 실행하고 수천만 개의 명령어를 처리합니다.

Hugging Face의 tokenizers v0.22는 역조회용 해시 맵과 모든 트라이 노드의 해시 맵 자식을 사용하여 재귀를 직접 구현합니다.

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로 작성되었지만, 소스 수준에서는 보이지 않는 많은 작업이 수행됩니다. 다음 섹션에서는 시간이 어디에 소요되는지 분석합니다.

비테르비가 실행되기 전, 입력은 유니코드 정규화(NFKC) 및 단어 경계 표시를 거칩니다. 프로파일링 결과, 당사의 시나리오에서 전처리는 전체 인코딩 시간의 5% 미만을 차지하므로, 이 글의 나머지 부분에서는 비테르비 순방향 패스에 집중합니다.

CPU 코드를 가속화하는 방법에는 명령어 실행 횟수를 줄이거나 IPC(클록당 명령어 처리 횟수)를 높이는 두 가지가 있습니다. Cachegrind는 첫 번째를 측정하고, perf stat은 두 번째를 측정합니다. 이 글의 모든 최적화는 이 중 하나에 해당합니다.

CPU는 캐시 누락(L1d 약 4사이클, DRAM까지의 L3 누락은 수백 사이클), 비순차적 엔진이 병렬화할 수 없는 의존적 로드 체인, 분기 예측 실패(잘못된 추측당 약 15~20사이클 플러시), 할당기 호출 등 네 가지 요인으로 인해 지연됩니다. 참조 유니그램 엔진 구현은 이 네 가지 문제를 모두 겪습니다.

병목 현상	메커니즘	측정된 영향
일치 항목당 할당	일치하는 바이트에 대한 String::from_utf8과 트라이 일치당 AHashMap 조회; 토큰 ID는 이미 리프에 있지만 참조 구현에서는 거기에 저장하지 않음	512 토큰에서 7,295건, 1k에서 14,542건, 16k에서 299,171건의 할당
바이트당 포인터 체이싱	모든 트라이 노드에 AHashMap을 배치하여 다음 바이트를 해싱하고 단계당 두 개의 포인터를 역참조함; Node 구조체는 is_leaf와 같은 비활성 필드도 함께 묶어 방문할 때마다 캐시로 불러옴	할당기의 핫 페이지가 L1에 존재하므로 L1d 누락률은 낮게 유지됨(1k에서 약 2.5%); 비용은 의존적 로드 지연으로 나타남
긴 입력에 대한 L2 스래싱(thrashing)	DP 테이블, 접두사 스크래치, 출력 토큰 목록이 모두 호출될 때마다 새로 할당됨	누적 할당 공간이 코어당 2MB L2 캐시를 초과함에 따라 L2 누락률이 128 토큰의 12%에서 16k의 50%까지 상승함

토크나이저 병목, 메커니즘, 그리고 측정된 영향에 대해 참고하세요.

가장 큰 비용은 일치 항목당 발생하는 할당입니다. 1k 토큰에서 참조 구현은 인코딩당 약 7M개의 명령어를 IPC 2.8로 처리하며, 대부분은 할당기 호출 및 문자열 변환에 사용됩니다. L2 누락은 누적 할당 공간이 코어당 캐시를 초과하는 약 1k 토큰 이후에만 문제가 됩니다.

토큰당 할당은 입력 크기와 관계없이 약 2KB, 약 18회 할당으로 일정합니다. 지연 시간의 비선형성은 L2에서 발생합니다. 누적 바이트가 1k 토큰 부근에서 2MB를 넘어서면 누락률이 8%에서 약 50%까지 상승하고 p99 곡선이 그에 맞춰 굴절됩니다.

당사는 모두 동일한 XLM-RoBERTa 모델에 대해 동일한 유니그램 알고리즘을 실행하는 세 가지 프로덕션 토크나이저를 비교합니다.

엔진	언어	트라이(Trie)
Hugging Face	Rust	HashMap-children 접두사 트라이
SentencePiece	C++	Darts 이중 배열 트라이
IREE 토크나이저	C	Darts 이중 배열 트라이

비교에 사용된 토크나이저 구현, 언어, 그리고 트라이 표현입니다.

당사는 SentencePiece와 IREE를 Rust 래퍼가 아닌 직접적인 C/C++ FFI를 통해 연결합니다. 래퍼는 근본적인 라이브러리 비용에 포함되지 않는 호출당 할당 및 문자열 변환을 추가하기 때문입니다.

모든 엔진은 완전한 최적화(O3, 네이티브 타겟팅, 링크 타임 최적화)로 빌드되었습니다. 측정은 Intel Xeon Platinum 8488C의 조용한 코어 하나에 고정되어 실행됩니다. 각 엔진 및 입력 크기에 대해 벽시계 지연 시간(p50 및 p99, 1,000회 웜업 후 10,000회 반복), Valgrind cachegrind를 통한 명령어 처리 횟수, perf stat 하드웨어 카운터를 통한 IPC 및 캐시 누락률, 그리고 측정된 윈도우 주변의 전역 할당기 래퍼에 의해 계산된 힙 할당을 수집합니다.

514 토큰(512개에 BOS/EOS 주입으로 +2) 기준:

구현	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 토큰에서의 토크나이저 지연 시간, 명령어 수, IPC, 그리고 할당량입니다.

SP와 IREE는 참조 구현 지연 시간의 약 3분의 1 수준입니다. 이들은 참조 구현보다 명령어 처리 횟수가 절반 정도이며, 더 높은 IPC에서 실행되고, 할당량은 1~2자릿수 적습니다.

SentencePiece와 IREE는 모두 1989년 Aoe가 도입한 이중 배열 트라이를 사용합니다(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 어휘의 경우, 전체 트라이는 약 9MB의 연속 메모리에 들어갑니다(슬롯당 오프셋, 유효성 검사 및 토큰 ID를 위한 약 780K 슬롯 × 12바이트). 단일 인코딩의 핫 워킹 세트는 약 100KB 수준으로 L2 캐시에 쾌적하게 들어가며, 하드웨어 프리페처는 규칙적인 액세스 패턴에 고정됩니다.

반면 참조 구현은 노드당 자식의 해시 맵을 유지하며, 바이트 단계당 약 4개의 의존적 로드 비용이 발생합니다. 바이트를 해싱하고, 버킷을 로드하고, 버킷 항목에 대한 포인터를 따라가고, 힙의 자식 노드에 대한 또 다른 포인터를 따라간 다음, 다음 바이트를 위해 자체 해시 맵을 참조합니다. 힙 객체는 흩어지고 대부분의 로드는 캐시를 누락합니다.

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 중에 일치 항목당 격자 노드를 추가로 할당하여 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 토큰에서의 제로 할당 기준선입니다.

일치 항목별 문자열 구현 및 보조 해시 맵 조회를 제거하여 참조 구현 대비 명령어 수를 2.4배 줄였습니다. IPC는 그와 함께 하락했는데(2.86 → 2.62), 이는 이전에 할당기 작업 뒤에 숨겨져 있던 해시 맵 포인터 체이싱이 이제 바이트당 지배적인 비용이 되었기 때문입니다.

입력 크기별 기준 및 제로 할당 기준선 토크나이저의 p50 및 p99 지연 시간.

베이스라인은 모든 크기에서 참조 구현 대비 p50 지연 시간을 2~3배 단축했으며, L2 누락률은 참조 구현의 8~48%에 비해 2k 토큰까지 2~3% 수준을 유지합니다. 나머지 비용은 HashMap 포인터 체이싱이며, 다음 섹션에서 다룹니다.

해시 맵 트라이는 포인터 체이싱입니다. SP와 IREE는 이중 배열 트라이로 이 문제를 해결하며(이전 섹션 참조), 당사도 동일한 데이터 구조를 빌려옵니다. 차이점은 SP와 IREE는 스트리밍 입력, 출력 오프셋, 다중 인코딩 모드를 지원하는 범용 라이브러리라는 점입니다. 해당 유연성은 트라이 주변의 추가적인 북키핑 비용을 발생시킵니다(SP의 격자, IREE의 8단계 파이프라인). 당사는 그중 아무것도 필요하지 않으므로 비테르비 루프 내에 트라이를 직접 인라인하고 나머지는 버립니다.

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

바이트 단계는 두 번의 배열 읽기, 정수 덧셈, 비교 비용이 듭니다. 전체 트라이는 약 9MB이지만 단일 인코딩은 그중 약 100KB만 순회하므로 핫 데이터는 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%

더블 배열 트라이를 채택한 후의 토크나이저 지연 시간, 명령어 수, 그리고 캐시 미스율입니다.

벽시계 시간은 베이스라인에서 2.3배, 참조 구현에서 4.8배 줄어들었습니다. 명령어는 베이스라인에서 28% 더 줄었습니다. 격자와 파이프라인을 제거함으로써 동일한 트라이 모양에서 SP의 1.82M, IREE의 1.61M 대비 인코딩당 1.10M개의 명령어를 처리할 수 있게 되었습니다. 격차는 범용 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 배열은 구성 중에만 사용되며 런타임 레이아웃에서는 제외됩니다. 핵심 경로 인덱싱은 트라이 구성과 루프 구조가 이미 경계를 보장하므로 검사되지 않습니다. 절충점은 스페이스(space)입니다. 노드당 64바이트 × 약 780K 슬롯에서 트라이는 약 9MB에서 약 50MB로 증가합니다.

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%

비트맵과 인라인 패킹을 추가한 후 514 토큰에서의 토크나이저 결과입니다.

벽시계 시간은 514 토큰에서 4.5% 더 체계적으로 줄어들고 입력 길이에 따라 증가하여 4k 및 16k에서 6~7%에 도달합니다. check 배열을 삭제함으로써 바이트당 트라이 단계를 두 번의 캐시 라인 로드에서 한 번으로 줄였으며, 이는 인코딩당 2.5배 적은 L2 액세스입니다(일반 Darts의 4.6K 대비 1.8K). 누락률은 6%에서 20%로 급증하지만 그 대부분은 분모 때문입니다. 액세스 횟수가 절반 미만으로 줄어들면서 발생하는 누락이 전체에서 더 큰 비중을 차지하게 되기 때문입니다.

트라이 데이터는 약 50MB(노드당 64바이트로 780,000개)입니다. 기본 Linux 프로세스에서 이 메모리는 4KB 페이지로 백업되므로 전체 트라이는 약 12,000개의 고유 가상 페이지에 걸쳐 있으며, 이는 CPU의 1단계 데이터 TLB(Translation Lookaside Buffer)가 담을 수 있는 범위를 훨씬 초과합니다(Sapphire Rapids는 96개 항목). 각 비테르비 단계는 다른 노드를 건드리며, 512 토큰 인코딩 동안 페이지 테이블 탐색에 약 9,000사이클을 소모하는데, 이는 인코딩당 예산의 약 3%입니다.

해결책은 트라이를 4KB 페이지 대신 2MB 대형 페이지로 백업하는 것입니다. 동일한 50MB가 이제 25개의 페이지에 걸쳐 있으며 TLB에 완전히 들어가고, 페이지 테이블 디렉터리 자체가 더 이상 L2 캐시를 놓고 트라이와 경쟁하지 않게 됩니다.

Linux는 메모리를 2MB 페이지로 백업하는 두 가지 방법을 제공합니다. 기회주의적인 방법은 투명 대형 페이지(THP)입니다. 프로그램이 커널에 메모리 영역을 4KB에서 2MB 페이지로 업그레이드하도록 요청하면, 배경 커널 스레드(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%

입력 크기 전반에 걸친 거대 페이지 사용 및 미사용 시의 토크나이저 지연 시간입니다.

가장 큰 성과는 워킹 세트가 충분히 커서 페이지 테이블 트래픽이 L2 대역폭을 놓고 트라이 데이터와 경쟁하던 4k 토큰에서 발생했습니다. 4k 이후에는 L3 누락이 지배적이 되고 페이지 테이블 탐색이 전체 시간에서 차지하는 비중이 줄어들기 때문에 성과가 줄어듭니다.

세 가지 최적화를 결합하여, 당사가 테스트한 다른 모든 RoBERTa 토크나이저와 비교하여 최종 엔진을 측정했습니다. 네이티브 C++ SentencePiece 및 C IREE 바이너리와 함께, 프로덕션 사용자가 사용할 만한 기성 Rust 래퍼 크레이트인 sentencepiece와 iree-tokenizer도 벤치마크했습니다. sentencepiece 크레이트는 모든 입력 크기에서 네이티브 C++ 바이너리 대비 1.6~1.9배 높은 지연 시간을 보였으며, 이는 래퍼가 인코딩할 때마다 각각 자체 복사본을 가진 토큰 조각 리스트를 새로 할당하기 때문에 발생했습니다. iree-tokenizer 크레이트는 내부 버퍼를 각 입력에 맞게 크기 조정하여 네이티브 IREE 바이너리가 입력 크기에 상관없이 지불하는 고정적인 인코딩당 할당을 피하며, 이는 할당이 실제 토큰화 작업을 압도하는 짧은 입력에서 가장 중요합니다. 프로덕션 입력 길이에서는 고정 비용이 상각되며, 토큰을 Rust로 복사하는 래퍼 자체의 호출당 오버헤드가 지연 시간을 네이티브 바이너리보다 높게 밀어 올립니다.

토크나이저 구현 및 입력 크기 전반의 인코드당 p50 및 p99 지연 시간.

최종 엔진은 동일한 250,000개 토큰 어휘에 대해 동일한 비테르비를 실행하고, 핵심 경로에서 아무것도 할당하지 않으며, 참조 구현과 토큰 단위로 정확한 출력을 생성합니다. 각 바이트 단계는 이제 HashMap 프로브, 할당기 호출, 베이스라인 구현의 여러 특수 사례 분기에서 하향된 단일 64바이트 캐시 라인 로드, 하나의 비트맵 테스트, 하나의 정수 덧셈입니다. 인코딩당 명령어는 3.66M에서 1.04M으로 3.5배 감소했습니다. 벽시계 시간은 짧은 입력에서 그 비율과 일치하며 긴 입력에서는 참조 구현의 토큰당 할당이 L2와 L3를 넘치기 시작하여 격차가 더 벌어집니다.

실제로 이 작업은 추론 스택 전처리 레이어의 CPU 사용률을 5~6배 감소시켰으며 리랭커 지연 시간을 두 자릿수 밀리초만큼 단축했습니다.

지연 시간 감소의 대부분은 불필요한 작업을 제거한 가벼운 변경에서 나왔습니다. 인코딩당 할당 제거, HashMap 자식 트라이를 이중 배열로 교체, 일반 API 오버헤드 제거 등이 그것입니다. 유효성 검사로 기존 노드별 비트맵을 사용하고 트라이를 2MB 대형 페이지로 백업하는 것은 입력 크기에 따라 이중 배열 트라이로의 더 큰 전환 외에 10~20%의 추가 성과를 제공했습니다.

SentencePiece와 IREE 주변의 기성 Rust 래퍼 크레이트는 동일한 점을 반대로 보여줍니다. 네이티브 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}
}

동기

비테르비 알고리즘(Viterbi Algorithm)

참조 구현

전처리 관련 참고 사항

참조 구현의 시간 소요 분석

측정 방법

SentencePiece와 IREE가 더 빠른 이유: 이중 배열 트라이

베이스라인: 참조 구현의 무할당 포트

최적화 1: 추가 추상화가 없는 이중 배열 트라이

최적화 2: 비트맵 및 인라인 패킹

최적화 3: 트라이를 위한 대형 페이지

최종 비교

결언

참고 문헌

인용