യൂണിഗ്രാം ടോക്കണൈസർ CPU പ്രകടനം മെച്ചപ്പെടുത്തുന്നു

പ്രകടന മെച്ചപ്പെടുത്തൽ ലക്ഷ്യമിട്ട് ഞങ്ങൾ ഞങ്ങളുടെ യൂണിഗ്രാം ടോക്കണൈസർ ആദ്യത്തുനിന്ന് പുനർനിർമ്മിച്ചു. പ്രൊഡക്ഷൻ ഇൻപുട്ട് നീളത്തിൽ, പുതിയ എൻകോഡർ Hugging Face ടോക്കണൈസേഴ്സ് ക്രേറ്റുമായി താരതമ്യം ചെയ്യുമ്പോൾ p50 ലേറ്റൻസി ഏകദേശം 5 മടങ്ങ് കുറയ്ക്കുന്നു, SentencePiece-മായി (C++) താരതമ്യം ചെയ്യുമ്പോൾ ~2 മടങ്ങ്, IREE-യുടെ ടോക്കണൈസറുമായി (C) താരതമ്യം ചെയ്യുമ്പോൾ ~1.5 മടങ്ങ് കുറയ്ക്കുന്നു, കൂടാതെ സ്റ്റെഡി-സ്റ്റേറ്റ് ഹീപ്പ് അലോക്കേഷനുകൾ ഒന്നുമില്ലതാനും. പ്രൊഡക്ഷനിൽ ഇത് ഞങ്ങളുടെ ഇൻഫറൻസ് സ്റ്റാക്കിലെ CPU ഉപയോഗം 5-6 മടങ്ങ് കുറയ്ക്കുകയും റീറാംകർ ലേറ്റൻസിയിൽനിന്ന് രണ്ടക്ക മില്ലിസെക്കൻഡുകൾ വെട്ടിക്കുറയ്ക്കുകയും ചെയ്തു.

എൽ.എൽ.എം. (LLM) ഇൻഫറൻസ് ചെലവ് സാധാരണയായി ജി.പിയു. (GPU) ജോലിയായാണ് കണക്കാക്കുന്നത്: KV കാഷുകൾ, അറ്റൻഷൻ കർണലുകൾ, എക്സ്പെർട്ട് റൂട്ടിംഗ്. എന്നാൽ പ്രൊഡക്ഷൻ ട്രാഫിക്കിന്റെ ഒരു പ്രധാന ഭാഗം വളരെ ചെറിയ മോഡലുകളിലാണ് പ്രവർത്തിക്കുന്നത്, ഫ്രോണ്ടിയർ ട്രാൻസ്‌ഫോർമറുകളെക്കാൾ രണ്ടോ മൂന്നോ ഓർഡർ മാഗ്നിറ്റ്യൂഡ് ചെറിയവ. എംബെഡിംഗ് മോഡലുകൾ, ക്ലാസിഫയറുകൾ, റീറാംകറുകൾ എന്നിവ ഇപ്പോഴും ജി.പിയു-വിലാണ് പ്രവർത്തിക്കുന്നത്, എന്നാൽ ഫോർവേഡ് പാസ് വളരെ ചെറുതായതിനാൽ അതിനു ചുറ്റുമുള്ളതെല്ലാം പ്രധാനമായിത്തീരുന്നു.

ഒരു അഭ്യർത്ഥനയ്ക്ക് കീഴിൽ നൂറുകണക്കിന് കാൻഡിഡേറ്റ് ഡോക്യുമെന്റുകൾ സ്കോർ ചെയ്യുന്ന ഒരു റീറാംകറാണ് ഏറ്റവും വ്യക്തമായ ഉദാഹരണം. ഒരു ചെറിയ മോഡൽ ഉപയോഗിക്കുമ്പോൾ, ജി.പിയു കമ്പ്യൂട്ട് സാധാരണയായി ഒറ്റക്കക്കം മില്ലിസെക്കൻഡുകളിൽ പൂർത്തിയാകും, എന്നാൽ ഓരോ ഇൻപുട്ടും ആദ്യം സി.പി.യു.-വശത്തെ ടോക്കണൈസേഷനിലൂടെ കടന്നുപോകേണ്ടതുണ്ട്, ഇത് വാചകത്തെ വൊക്കാബുലറി ഐ.ഡി.-കളാക്കി മാറ്റുന്നു. ബാച്ച് വലുതായിരിക്കുമ്പോൾ, ഇത് മൊത്തത്തിലുള്ള അഭ്യർത്ഥന ലേറ്റൻസിയുടെ ഒരു പ്രധാന ഭാഗത്തിന് കാരണമായേക്കാം.

ഈ പ്രവർത്തനം SentencePiece ഉപയോഗിച്ച് പരിശീലിപ്പിച്ച 250K-ടോക്കൺ യൂണിഗ്രാം വൊക്കാബുലറിയുള്ള XLM-RoBERTa-യെ ലക്ഷ്യമിടുന്നു. റാങ്കിംഗ്, റിട്രീവൽ, സിമിലാരിറ്റി ടാസ്കുകൾക്ക് ഫൈൻ-ട്യൂൺ ചെയ്ത RoBERTa-ഫാമിലി എൻകോഡറുകൾ ഒരു സാധാരണ തിരഞ്ഞെടുപ്പാണ്. ഞങ്ങൾ ഉടനീളം സിംഗിൾ-ത്രെഡഡ് പെർ-എൻകോഡ് ലേറ്റൻസി റിപ്പോർട്ട് ചെയ്യുന്നു; പ്രൊഡക്ഷനിൽ ഞങ്ങൾ rayon ഉപയോഗിച്ച് കോറുകളിലുടനീളം പാരലലൈസ് ചെയ്യുന്നു.

ഈ പോസ്റ്റിലുടനീളം ഞങ്ങൾ Hugging Face-ന്റെ ടോക്കണൈസേഴ്സ് ക്രേറ്റിനെയാണ് ബെഞ്ച്മാർക്ക് ചെയ്യുന്നതിനുള്ള റഫറൻസായി കണക്കാക്കുന്നത്, കാരണം മിക്ക ടീമുകളും ഉപയോഗിക്കുന്ന ഡിഫോൾട്ട് റസ്റ്റ് (Rust) ടോക്കണൈസർ ഇതാണ്. മറ്റ് രണ്ട് പ്രധാന പ്രൊഡക്ഷൻ ഇംപ്ലിമെന്റേഷനുകൾ എന്ന നിലയിൽ താരതമ്യത്തിനായി SentencePiece (C++), IREE (C) എന്നിവയും ഉൾപ്പെടുത്തിയിട്ടുണ്ട്.

2018-ൽ കുഡോ അവതരിപ്പിച്ച (സബ്‌വേർഡ് റെഗുലറൈസേഷൻ: ഒന്നിലധികം സബ്‌വേർഡ് കാൻഡിഡേറ്റുകൾ ഉപയോഗിച്ച് ന്യൂറൽ നെറ്റ്‌വർക്ക് ട്രാൻസ്‌ലേഷൻ മോഡലുകൾ മെച്ചപ്പെടുത്തുന്നു) SentencePiece-ൽ ഉൾപ്പെടുത്തിയിട്ടുള്ളതുമായ യൂണിഗ്രാം ടോക്കണൈസേഷൻ, സെഗ്മെന്റേഷനെ ഏറ്റവും സാധ്യമായ പാത പ്രശ്നമായി കണക്കാക്കുന്നു: ഓരോ വൊക്കാബുലറി ടോക്കണും പഠിച്ച ലോഗ്-പ്രൊബബിലിറ്റിയുള്ളതാണ്, കൂടാതെ എൻകോഡർ ടോക്കൺ സ്കോറുകൾ ഉയർന്ന മൂല്യത്തിലേക്ക് തുകയാകുന്ന സെഗ്മെന്റേഷൻ തിരഞ്ഞെടുക്കുന്നു. ഗ്രാഫ് ലെയറുകളായി ബൈറ്റ് പൊസിഷനുകളും തുടർച്ചയായ ബൈറ്റ് റേഞ്ച് വ്യാപിക്കുന്ന എഡ്ജുകളായി വൊക്കാബുലറി ടോക്കണുകളും ഉപയോഗിച്ച് വിറ്റെർബി അൽഗോരിതം (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 ബൈറ്റുകൾ). ഇന്നർ ട്രൈ വോക്ക് ആണ് ഹോട്ട് പാത്ത്: 16k-ടോക്കൺ ഇൻപുട്ടിൽ, ഇത് ലക്ഷക്കണക്കിന് ട്രാൻസിഷനുകൾ പ്രവർത്തിപ്പിക്കുകയും ഓരോ എൻകോഡിലും കോടിക്കണക്കിന് ഇൻസ്ട്രക്ഷനുകൾ റിട്ടയർ ചെയ്യുകയും ചെയ്യുന്നു.

Hugging Face-ന്റെ ടോക്കണൈസേഴ്സ് 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കൾ നാലു കാര്യങ്ങളിൽ സ്റ്റാൾ ചെയ്യുന്നു: cache misses (L1d ഏകദേശം 4 cycles, L3 miss മുതൽ DRAM വരെ നൂറുകളാണ്), out-of-order engine സമാന്തരമാക്കാനാകാത്ത dependent-load chains, branch mispredicts (ഓരോ തെറ്റായ അനുമാനത്തിനും ഏകദേശം 15-20 cycles flush ചെയ്യും), allocator calls. reference unigram engine implementation ഇവ നാലിനെയും ബാധിക്കുന്നു:

ബോട്ട്ലെനെക്ക്	മെക്കാനിസം	അളന്ന സ്വാധീനം
ഓരോ പൊരുത്തത്തിനുമുള്ള അലോക്കേഷൻ	പൊരുത്തപ്പെട്ട ബൈറ്റുകളിൽ String::from_utf8 കൂടാതെ ഓരോ ട്രൈ പൊരുത്തത്തിനും ഒരു AHashMap ലുക്ക്അപ്പ്; ടോക്കൺ ഐ.ഡി. ഇതിനകം ലീഫിലുണ്ട്, എന്നാൽ റഫറൻസ് അത് അവിടെ സൂക്ഷിക്കുന്നില്ല	512 ടോക്കണുകളിൽ 7,295 അലോക്കേഷനുകൾ, 1k-ൽ 14,542, 16k-ൽ 299,171
ബൈറ്റ് പ്രിത്യേകമുള്ള pointer chase	ഓരോ ട്രൈ നോഡിലും ഒരു AHashMap, അടുത്ത ബൈറ്റ് ഹാഷ് ചെയ്യുകയും ഓരോ ഘട്ടത്തിലും രണ്ട് പോയിന്ററുകൾ ഡിറെഫറൻസ് ചെയ്യുകയും ചെയ്യുന്നു; Node സ്ട്രക്ചർ is_leaf പോലുള്ള കോൾഡ് ഫീൽഡുകളെയും ഒരുമിച്ച് ചേർക്കുന്നു, ഇത് ഓരോ സന്ദർശനത്തിലും കാഷിലേക്ക് വലിച്ചെടുക്കുന്നു	അലോക്കേറ്റർ ഹോട്ട് പേജുകൾ L1-ൽ ഉള്ളതുകൊണ്ട് L1d മിസ് റേറ്റ് കുറവായി തുടരുന്നു (~1k-ൽ 2.5%); ഈ ചെലവ് ഡിപെൻഡന്റ്-ലോഡ് ലേറ്റൻസിയായി കാണപ്പെടുന്നു
നീണ്ട ഇൻപുട്ടുകളിൽ L2 താളംതെറ്റൽ (thrashing)	DP ടേബിൾ, പ്രീഫിക്സ് സ്ക്രാച്ച്, ഔട്ട്പുട്ട് ടോക്കൺ ലിസ്റ്റ് എന്നിവയെല്ലാം ഓരോ കോളിലും പുതിയതായി അലോക്കേറ്റ് ചെയ്യപ്പെടുന്നു	ക്യുമുലേറ്റീവ് അലോക്കേഷൻ ഫൂട്ട്പ്രിന്റ് പെർ-കോർ 2 MB L2 കവിയുമ്പോൾ L2 മിസ് റേറ്റ് 128 ടോക്കണുകളിൽ 12%-ൽ നിന്ന് 16k-ൽ 50% ആയി ഉയരുന്നു

റഫറൻസ് ടോക്കനൈസറിലെ ബോട്ടിൽനെക്കുകൾ, സംവിധാനങ്ങൾ, അളന്ന പ്രഭാവങ്ങൾ.

പ്രധാന ചെലവ് ഓരോ പൊരുത്തത്തിനുമുള്ള അലോക്കേഷനാണ്. 1k ടോക്കണുകളിൽ, റഫറൻസ് ഇംപ്ലിമെന്റേഷൻ 2.8 IPC-യിൽ ഓരോ എൻകോഡിലും ഏകദേശം 7M ഇൻസ്ട്രക്ഷനുകൾ പൂർത്തിയാക്കുന്നു, അവയിൽ ഭൂരിഭാഗവും അലോക്കേറ്റർ കോളുകളിലും സ്ട്രിംഗ് കൺവെർഷനുകളിലും ആണ്. ക്യുമുലേറ്റീവ് അലോക്കേഷൻ ഫൂട്ട്പ്രിന്റ് പെർ-കോർ കാഷിനെ കവിയുമ്പോൾ, ~1k ടോക്കണുകൾക്ക് അപ്പുറം മാത്രമേ L2 മിസുകൾ പ്രധാനമാകുകയുള്ളൂ.

ഇൻപുട്ട് വലുപ്പം അനുസരിച്ച് റഫറൻസ് ടോക്കനൈസറിന്റെ p50, p99 ലേറ്റൻസി.

ഇൻപുട്ട് വലുപ്പം അനുസരിച്ച് റഫറൻസ് ടോക്കനൈസറിന്റെ L2 കാഷ് മിസ് നിരക്ക്.

ഇൻപുട്ട് വലുപ്പങ്ങളിലുടനീളം റഫറൻസ് ടോക്കനൈസർ ഓരോ encode-നും അനുവദിച്ച ബൈറ്റുകൾ.

പെർ-ടോക്കൺ അലോക്കേഷൻ സ്ഥിരമാണ്: ഇൻപുട്ട് വലുധിയെ unabhängig ആയി, ഏകദേശം 2 KB ഉം ഓരോ ടോക്കണിലും ~18 അലോക്കേഷനുകളും. ലേറ്റൻസി നോൺ-ലീനിയാരിറ്റി വരുന്നത് L2-ൽ നിന്നാണ്: ക്യുമുലേറ്റീവ് ബൈറ്റുകൾ 1k ടോക്കണുകൾക്ക് ചുറ്റും 2 MB കവിയുന്നു, മിസ് റേറ്റ് 8%-ൽ നിന്ന് ~50% ആയി ഉയരുന്നു, കൂടാതെ p99 കർവ് അതിനനുസരിച്ച് വളയുന്നു.

അതേ XLM-RoBERTa മോഡലിനെതിരെ അതേ യൂണിഗ്രാം അൽഗോരിതം പ്രവർത്തിപ്പിക്കുന്ന മൂന്ന് പ്രൊഡക്ഷൻ ടോക്കണൈസറുകൾ ഞങ്ങൾ താരതമ്യം ചെയ്യുന്നു:

എഞ്ചിൻ	ഭാഷ	ട്രൈ
Hugging Face	റസ്റ്റ്	HashMap-ചിൽഡ്രൻ പ്രീഫിക്സ് ട്രൈ
SentencePiece	C++	Darts ഡബിൾ-അറേ ട്രൈ
IREE ടോക്കണൈസർ	C	Darts ഡബിൾ-അറേ ട്രൈ

താരതമ്യത്തിൽ ഉപയോഗിച്ച ടോക്കനൈസർ നടപ്പാക്കലുകൾ, ഭാഷകൾ, ട്രൈ പ്രതിനിധാനങ്ങൾ.

അടിസ്ഥാന ലൈബ്രറിയുടെ ചെലവിന്റെ ഭാഗമല്ലാത്ത പെർ-കോൾ അലോക്കേഷനുകളും സ്ട്രിംഗ് കൺവെർഷനുകളും റാപ്പറുകൾ ചേർക്കുന്നു എന്നതുകൊണ്ട്, റസ്റ്റ് റാപ്പറുകൾക്ക് പകരം നേരിട്ടുള്ള C/C++ FFI വഴിയാണ് ഞങ്ങൾ SentencePiece-ഉം IREE-യും ലിങ്ക് ചെയ്യുന്നത്.

എല്ലാ എഞ്ചിനുകളും പൂർണ്ണമായ ഒപ്റ്റിമൈസേഷനുകളോടെയാണ് നിർമ്മിച്ചിരിക്കുന്നത് (O3, നേറ്റീവ് ടാർഗെറ്റിംഗ്, ലിങ്ക്-ടൈം ഒപ്റ്റിമൈസേഷൻ). അളവുകൾ ഒരു ഇൻറൽ സിയോൺ പ്ലാറ്റിനം 8488C-യിലെ നിശബ്ദമായ ഒരു കോറിലേക്ക് പിൻ ചെയ്താണ് പ്രവർത്തിപ്പിക്കുന്നത്. ഓരോ എഞ്ചിനും ഇൻപുട്ട് വലുപ്പത്തിനുമായി ഞങ്ങൾ വാൾ-ക്ലോക്ക് ലേറ്റൻസി (p50, p99, 1,000 വാർമപ്പുകൾക്ക് ശേഷം 10,000 ഇറ്ററേഷനുകൾ), വാൽഗ്രിൻഡ് കാഷ്ഗ്രിൻഡ് വഴി റിട്ടയർ ചെയ്ത ഇൻസ്ട്രക്ഷനുകൾ, 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 ടോക്കണുകളിൽ ടോക്കനൈസർ ലേറ്റൻസി, നിർദ്ദേശങ്ങളുടെ എണ്ണം, IPC, അലോക്കേഷനുകൾ.

SP-യും IREE-യും റഫറൻസിന്റെ ലേറ്റൻസിയുടെ മൂന്നിലൊന്നിൽ എത്തുന്നു. അവ പകുതിയോളം ഇൻസ്ട്രക്ഷനുകൾ റിട്ടയർ ചെയ്യുന്നു, ഉയർന്ന IPC-യിൽ പ്രവർത്തിക്കുന്നു, കൂടാതെ ഒന്നോ രണ്ടോ ഓർഡർ മാഗ്നിറ്റ്യൂഡ് കുറവ് അലോക്കേറ്റ് ചെയ്യുന്നു.

1989-ൽ ആവോ (Aoe) അവതരിപ്പിച്ച ഡബിൾ-അറേ ട്രൈ ആണ് SentencePiece-ഉം IREE-യും ഉപയോഗിക്കുന്നത് (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 */ }

ട്രൈ ട്രാവൽ ചെയ്യുന്ന ഓരോ ഘട്ടത്തിനും രണ്ട് അറേ ലോഡുകൾ, ഒരു ഇന്റിജർ കൂട്ടൽ, ഒരു താരതമ്യം എന്നിവ മാത്രം മതിയാകും, ഹാഷിംഗോ പോയിന്റർ ചെയ്സിംഗോ പെർ-നോഡ് ഹീപ്പ് അലോക്കേഷനോ ഇല്ല. വാലിഡേഷൻ അറേയിലെ ഫ്രീ സ്ലോട്ടുകളിൽ അതിന്റെ കുട്ടികൾ (children) വീഴുന്ന രീതിയിലാണ് കൺസ്ട്രക്ഷൻ ഓരോ നോഡും സ്ഥാപിക്കുന്നത്, കുട്ടികൾ പിന്തുടരുന്ന ബൈറ്റിൽ വ്യത്യാസമുള്ളിടത്തോളം കാലം ഒന്നിലധികം പേരന്റുകൾക്ക് പ്രദേശങ്ങൾ പങ്കിടാൻ ഇത് അനുവദിക്കുന്നു.

XLM-RoBERTaയുടെ 250K vocab-നായി, മുഴുവൻ trie ഏകദേശം 9 MB contiguous memoryയിൽ ചേരുന്നു (ഓരോ slot-നും offset, validation, token ID എന്നിവയ്ക്കായി ഏകദേശം 780K slots × 12 bytes). ഒരു single encode-ന്റെ hot working set ഏകദേശം 100 KB മാത്രമാണ്, ഇത് L2യിൽ സുഖമായി പൊരുത്തപ്പെടുന്നു, കൂടാതെ hardware prefetcher regular access pattern-നെ പെട്ടെന്ന് പിടിച്ചെടുക്കുന്നു.

ഇതിന് വിപരീതമായി, റഫറൻസ് ഓരോ നോഡിനും കുട്ടികളുടെ ഒരു ഹാഷ്-മാപ്പ് സൂക്ഷിക്കുന്നു, ഇതിന് ഓരോ ബൈറ്റ് ഘട്ടത്തിനും ഏകദേശം നാല് ഡിപെൻഡന്റ് ലോഡുകൾ ചെലവാകും. ബൈറ്റ് ഹാഷ് ചെയ്യുക, ബക്കറ്റ് ലോഡ് ചെയ്യുക, ബക്കറ്റ് എൻട്രിയിലേക്ക് ഒരു പോയിന്റർ പിന്തുടരുക, ഹീപ്പിലെ ചൈൽഡ് നോഡിലേക്ക് മറ്റൊരു പോയിന്റർ പിന്തുടരുക, തുടർന്ന് അടുത്ത ബൈറ്റിനായി അതിന്റെ സ്വന്തം ഹാഷ്-മാപ്പ് പരിശോധിക്കുക. ഹീപ്പ് ഒബ്ജക്റ്റുകൾ ചിതറിക്കിടക്കുന്നു കൂടാതെ മിക്ക ലോഡുകളും കാഷ് മിസ് ചെയ്യുന്നു.

SP-യും IREE-യും ടോക്കൺ ഐ.ഡി നേരിട്ട് ട്രൈ നോഡിൽ സൂക്ഷിക്കുന്നു. റഫറൻസ് ട്രൈ ഇംപ്ലിമെന്റേഷൻ പൊരുത്തപ്പെട്ട ബൈറ്റുകൾ മാത്രം തിരികെ നൽകുന്നു, അതിനാൽ എൻകോഡർ ഓരോ പൊരുത്തത്തിനും ഒരു പുതിയ സ്ട്രിംഗ് അലോക്കേറ്റ് ചെയ്യണം, ടോക്കൺ ഐ.ഡി വീണ്ടെടുക്കാൻ ഒരു സൈഡ് ഹാഷ്-മാപ്പിൽ അത് നോക്കണം, കൂടാതെ ഒരു പ്രത്യേക വെക്ടറിൽ നിന്ന് സ്കോർ വായിക്കണം. SP ഐ.ഡി ട്രൈ-ൽ സംഭരിച്ച മൂല്യമായി തിരികെ നൽകുകയും ഒരു ഫ്ലാറ്റ് ഫ്ലോട്ട് അറേയിൽ നിന്ന് സ്കോർ വായിക്കുകയും ചെയ്യുന്നു:

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 ഉപയോഗിക്കുന്നു, എന്നാൽ ചെലവ് മാതൃക ഒന്നുതന്നെയാണ്: ട്രൈ വാക്കിൽ തന്നെ അലോക്കേഷനോ ഹാഷിംഗോ ഇല്ലാതെ, ടോക്കൺ ഐ.ഡികളും സ്കോറുകളും ഫ്ലാറ്റ്-അറേ ഇൻഡക്സുകളായി ലഭ്യമാണ്. IREE ഓരോ എൻകോഡിനും ഒരു ഔട്ട്പുട്ട് ബഫർ മാത്രം അലോക്കേറ്റ് ചെയ്യുന്നു; SP അധികമായി DP-ക്കിടയിൽ ഓരോ പൊരുത്തത്തിനും ഒരു ലാറ്റിസ് നോഡ് അലോക്കേറ്റ് ചെയ്യുന്നു, 514 ടോക്കണുകളിൽ ഇത് ആകെ ഏകദേശം 1,559 അലോക്കേഷനുകൾ വരുന്നു.

ട്രൈ മാറ്റുന്നതിന് മുമ്പ്, ഞങ്ങൾ അൽഗോരിതം ചെലവിനെ ഇംപ്ലിമെന്റേഷൻ ചെലവിൽ നിന്ന് വേർതിരിക്കുന്നു: ആവശ്യമില്ലാത്ത ജോലികൾ നീക്കം ചെയ്താൽ റഫറൻസ് എത്ര വേഗത്തിൽ പ്രവർത്തിക്കും?

ബേസ്‌ലൈൻ റഫറൻസിന്റെ ഹാഷ്-മാപ്പ്-ചിൽഡ്രൻ ട്രൈ നിലനിർത്തുന്നു എന്നാൽ രണ്ട് മാറ്റങ്ങൾ വരുത്തുന്നു. കോളർ-ടൈപ്പ് ചെയ്ത ഒരു സ്ക്രാച്ച് സ്ട്രക്ചർ DP ടേബിൾ, പ്രീപ്രോസസ് ചെയ്ത ബൈറ്റുകൾ, ഔട്ട്പുട്ട് ടോക്കൺ ഐ.ഡികൾ എന്നിവ സൂക്ഷിക്കുന്നു, അതിനാൽ വാർമപ്പിന് ശേഷം ഹോട്ട് പാത്ത് അലോക്കേഷനുകൾ ഒന്നും വരുത്തുന്നില്ല. പെർ-മാച്ച് സ്ട്രിംഗ് കൺവെർഷനും സെക്കൻഡറി ഹാഷ്-മാപ്പ് ലുക്ക്അപ്പും നീക്കം ചെയ്തുകൊണ്ട് ടോക്കൺ ഐ.ഡിയും സ്കോറും നേരിട്ട് ട്രൈ നോഡിൽ സൂക്ഷിക്കുന്നു.

ഇന്നർ ലൂപ്പ്:

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 ലേറ്റൻസി.

ഇൻപുട്ട് വലുപ്പം അനുസരിച്ച് റഫറൻസും സീറോ-അലോക്കേഷൻ ബേസ്‌ലൈൻ ടോക്കനൈസറും ഉള്ള L2 കാഷ് മിസ് നിരക്ക്.

ബേസ്‌ലൈൻ എല്ലാ വലുപ്പത്തിലും റഫറൻസുമായി താരതമ്യം ചെയ്യുമ്പോൾ p50 ലേറ്റൻസി 2-3× കുറയ്ക്കുന്നു, കൂടാതെ ഇതിന്റെ L2 മിസ് റേറ്റ് റഫറൻസിന്റെ 8-48%-ന് എതിരായി 2k ടോക്കണുകൾ വരെ 2-3%-ൽ തന്നെ തുടരുന്നു. ബാക്കി ചെലവ് ഹാഷ്‌മാപ്പ് പോയിന്റർ ചെയ്സ് ആണ്, ഇത് അടുത്ത വിഭാഗം അഭിസംബോധന ചെയ്യുന്നു.

ഹാഷ്-മാപ്പ് ട്രൈ ഒരു പോയിന്റർ ചെയ്സ് ആണ്. 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%

ഡബിൾ-അറേ ട്രൈ സ്വീകരിച്ചതിനു ശേഷം ടോക്കനൈസർ ലേറ്റൻസി, നിർദ്ദേശങ്ങൾ, കാഷ് മിസ് നിരക്കുകൾ.

വാൾ-ക്ലോക്ക് ബേസ്‌ലൈനിൽ നിന്ന് 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)
}

അതോടൊപ്പം, ഞങ്ങൾ ഓരോ node-ലുമുള്ള നാലു fields (bitmap, base, token ID, score) ഒരു 64-byte cache line-ൽ പാക്ക് ചെയ്യുന്നു. ഇപ്പോൾ ഒരു single node visit എല്ലാം കൊണ്ടുവരുന്നു: terminal nodes-ൽ വേണ്ട scoreയും token IDയും, അതിനൊപ്പം അടുത്ത ഘട്ടത്തിനുള്ള bitmapയും baseഉം. check array construction സമയത്ത് മാത്രം ഉപയോഗിക്കപ്പെടുന്നു, runtime layout-ൽ നിന്ന് അത് ഒഴിവാക്കപ്പെടുന്നു. Hot-path indexing unchecked ആകുന്നത് trie construction ഉം loop structure ഉം bounds ഇതിനകം ഉറപ്പാക്കുന്നതിനാലാണ്. ഇതിന്റെ trade-off space ആണ്: ഓരോ node-നും 64 bytes × ഏകദേശം 780K slots എന്ന നിരക്കിൽ trie ഏകദേശം 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%

ബിറ്റ്മാപ്പും ഇൻലൈൻ പാക്കിംഗും ചേർത്തതിന് ശേഷമുള്ള 514 ടോക്കണുകളിലെ ടോക്കനൈസർ ഫലങ്ങൾ.

വാൾ-ക്ലോക്ക് 514 ടോക്കണുകളിൽ മറ്റൊരു 4.5% വ്യവസ്ഥാപിതമായി കുറയുകയും ഇൻപുട്ട് നീളത്തിനനുസരിച്ച് വർദ്ധിക്കുകയും ചെയ്യുന്നു, 4k-ലും 16k-ലും 6-7% എത്തുന്നു. check അറേ ഒഴിവാക്കുന്നത് പെർ-ബൈറ്റ് ട്രൈ ഘട്ടത്തെ രണ്ട് കാഷ്-ലൈൻ ലോഡുകളിൽ നിന്ന് ഒന്നാക്കി മാറ്റുന്നു, ഇത് ഓരോ എൻകോഡിനും 2.5× കുറവ് L2 ആക്സസുകൾ നൽകുന്നു (പ്ലെയിൻ Darts-ന്റെ 4.6K-ന് എതിരായി 1.8K). മിസ് റേറ്റ് 6%-ൽ നിന്ന് 20% ആയി ഉയരുന്നു, എന്നാൽ അതിൽ ഭൂരിഭാഗവും ഡിനോമിനേറ്റർ ആണ്: പകുതിയിൽ താഴെ ആക്സസുകൾ ഉള്ളപ്പോൾ, നമുക്ക് ഉണ്ടാകുന്ന മിസുകൾ വലിയൊരു പങ്ക് എടുക്കുന്നു.

ട്രൈ ഡാറ്റ ഏകദേശം 50 MB ആണ് (ഓരോന്നും 64 ബൈറ്റുകൾ വീതമുള്ള 780,000 നോഡുകൾ). ഒരു ഡിഫോൾട്ട് ലിനക്സ് പ്രൊസസ്സിൽ, ആ മെമ്മറി 4 KB പേജുകൾ പിന്തുണയ്ക്കുന്നു, അതിനാൽ മുഴുവൻ ട്രൈയും ഏകദേശം 12,000 വ്യത്യസ്ത വെർച്വൽ പേജുകൾ വ്യാപിക്കുന്നു, CPU-വിന്റെ ഫസ്റ്റ്-ലെവൽ ഡാറ്റ ട്രാൻസ്‌ലേഷൻ ലുക്ക്അസൈഡ് ബഫറിന് ഉൾക്കൊള്ളാൻ കഴിയുന്നതിലും അപ്പുറം (Sapphire Rapids-ന് 96 എൻട്രികളുണ്ട്). ഓരോ വിറ്റെർബി ഘട്ടവും വ്യത്യസ്തമായ ഒരു നോഡിൽ തൊടുന്നു, കൂടാതെ ഒരു 512-ടോക്കൺ എൻകോഡിൽ നമ്മൾ പേജ്-ടേബിൾ വാക്കുകളിൽ ഏകദേശം 9,000 സൈക്കിളുകൾ ചെലവഴിക്കുന്നു, ഇത് പെർ-എൻകോഡ് ബജറ്റിന്റെ ഏകദേശം 3% ആണ്.

4 KB പേജുകൾക്ക് പകരം 2 MB ഹ്യൂജ് പേജുകൾ ഉപയോഗിച്ച് ട്രൈ ബാക്ക് ചെയ്യുക എന്നതാണ് പരിഹാരം. അതേ 50 MB ഇപ്പോൾ 25 പേജുകൾ വ്യാപിക്കുന്നു, ട്രാൻസ്‌ലേഷൻ ലുക്ക്അസൈഡ് ബഫറിൽ പൂർണ്ണമായി ഒതുങ്ങുന്നു, കൂടാതെ പേജ്-ടേബിൾ ഡയറക്ടറികൾ L2 കാഷിനായി ട്രൈയുമായി മത്സരിക്കുന്നത് നിർത്തുകയും ചെയ്യുന്നു.

മെമ്മറിയെ 2 MB പേജുകൾ ഉപയോഗിച്ച് ബാക്ക് ചെയ്യാൻ ലിനക്സിന് രണ്ട് വഴികളുണ്ട്. അതിലൊന്ന് സുതാര്യമായ ഹ്യൂജ് പേജുകൾ (THP) ആണ്: ഒരു മെമ്മറി മേഖല 4 KB-ൽ നിന്ന് 2 MB പേജുകളിലേക്ക് അപ്‌ഗ്രേഡ് ചെയ്യാൻ നിങ്ങളുടെ പ്രോഗ്രാം കേർണലിനോട് ആവശ്യപ്പെടുന്നു, ഒപ്പം അതിന് സമയവും തുടർച്ചയായ ഫിസിക്കൽ മെമ്മറിയും ലഭ്യമാകുമ്പോൾ ഒരു പശ്ചാത്തല കേർണൽ ത്രെഡ് അത് ചെയ്യാൻ ശ്രമിക്കുന്നു. ബൂട്ട് ചെയ്യുമ്പോൾ കേർണൽ മാറ്റിവെക്കുന്ന മുൻകൂട്ടി കരുതിവെച്ച ഹ്യൂജ്-പേജ് പൂളിൽ നിന്ന് ട്രൈ നേരിട്ട് അലോക്കേറ്റ് ചെയ്യുക എന്നതാണ് മറ്റൊരു പകരമുള്ള വഴി:

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%

ഇൻപുട്ട് വലുപ്പങ്ങളിലുടനീളം വലിയ പേജുകളോടെയും ഇല്ലാതെയും ടോക്കനൈസർ ലേറ്റൻസി.

ഏറ്റവും വലിയ വിജയം 4k ടോക്കണുകളിലാണ്, അവിടെ വർക്കിംഗ് സെറ്റ് വളരെ വലുതായതുകൊണ്ട് പേജ്-ടേബിൾ ട്രാഫിക് L2 ബാൻഡ്‌വിഡിത്തിനായി ട്രൈ ഡാറ്റയുമായി സജീവമായി മത്സരിക്കുന്നുണ്ടായിരുന്നു. 4k-ക്ക് അപ്പുറം നേട്ടം കുറയുന്നു കാരണം L3 മിസുകൾ ആധിപത്യം സ്ഥാപിക്കുകയും പേജ്-ടേബിൾ വാക്കുകൾ മൊത്തം സമയത്തിന്റെ ചെറിയൊരു പങ്കായി മാറുകയും ചെയ്യുന്നു.

മൂന്ന് ഒപ്റ്റിമൈസേഷനുകളും ഒരുമിച്ച് കൊണ്ടുവരുമ്പോൾ, ഞങ്ങൾ പരീക്ഷിച്ച മറ്റേതെങ്കിലും RoBERTa ടോക്കണൈസറിനെതിരെ അളന്ന അവസാന എഞ്ചിൻ ഇതാ. നേറ്റീവ് C++ SentencePiece, C IREE ബൈനറികൾക്കൊപ്പം, ഒരു പ്രൊഡക്ഷൻ ഉപയോക്താവ് ഉപയോഗിക്കുന്ന ഓഫ്-ദി-ഷെൽഫ് റസ്റ്റ് റാപ്പർ ക്രേറ്റുകളായ sentencepiece, iree-tokenizer എന്നിവയും ഞങ്ങൾ ബെഞ്ച്മാർക്ക് ചെയ്തു. sentencepiece ക്രേറ്റ് എല്ലാ ഇൻപുട്ട് വലുപ്പത്തിലും നേറ്റീവ് C++ ബൈനറിയേക്കാൾ 1.6-1.9× ഉയർന്ന ലേറ്റൻസി കാണിക്കുന്നു, ഓരോ എൻകോഡിലും ഓരോരുത്തരുടെയും പീസ് ടെക്സ്റ്റിന്റെ സ്വന്തം പകർപ്പ് സൂക്ഷിക്കുന്ന ടോക്കൺ പീസുകളുടെ ഒരു പുതിയ ലിസ്റ്റ് റാപ്പർ അലോക്കേറ്റ് ചെയ്യുന്നതിൽ നിന്നാണ് ഓവർഹെഡ് വരുന്നത്. iree-tokenizer ക്രേറ്റ് അതിന്റെ ആന്തരിക ബഫർ ഓരോ ഇൻപുട്ടിലേക്കും വലുപ്പം മാറ്റുന്നു, ഇത് ഇൻപുട്ട് വലുപ്പം പരിഗണിക്കാതെ നേറ്റീവ് IREE ബൈനറി നൽകുന്ന സ്ഥിരമായ പെർ-എൻകോഡ് അലോക്കേഷൻ ഒഴിവാക്കുന്നു, അലോക്കേഷൻ യഥാർത്ഥ ടോക്കണൈസേഷൻ ജോലികളിൽ ആധിപത്യം പുലർത്തുന്ന ചെറിയ ഇൻപുട്ടുകളിൽ ഇത് വളരെ പ്രധാനമാണ്. പ്രൊഡക്ഷൻ ഇൻപുട്ട് നീളങ്ങളിൽ സ്ഥിരമായ ചെലവ് അമോർടൈസ് ചെയ്യപ്പെടുകയും ടോക്കണുകൾ റസ്റ്റിലേക്ക് തിരികെ പകർത്തുന്നതിൽ നിന്നുള്ള റാപ്പറുടെ സ്വന്തം പെർ-കോൾ ഓവർഹെഡ് അതിന്റെ ലേറ്റൻസിയെ നേറ്റീവ് ബൈനറിയേക്കാൾ മുകളിലേക്ക് ഉയർത്തുകയും ചെയ്യുന്നു.

ടോക്കനൈസർ നടപ്പാക്കലുകളിലും ഇൻപുട്ട് വലുപ്പങ്ങളിലുമുള്ള ഓരോ encode-നും p50, p99 ലേറ്റൻസി.

അവസാന എഞ്ചിൻ അതേ 250,000-ടോക്കൺ വൊക്കാബുലറിക്കെതിരെ അതേ വിറ്റെർബി പ്രവർത്തിപ്പിക്കുന്നു, ഹോട്ട് പാത്തിൽ ഒന്നും അലോക്കേറ്റ് ചെയ്യുന്നില്ല, കൂടാതെ റഫറൻസിനെതിരെ ടോക്കൺ-കൃത്യമായ ഔട്ട്പുട്ട് ഉത്പാദിപ്പിക്കുന്നു. ഓരോ ബൈറ്റ് ഘട്ടവും ഇപ്പോൾ ഒരൊറ്റ 64-ബൈറ്റ് കാഷ്-ലൈൻ ലോഡ്, ഒരു ബിറ്റ്‌മാപ്പ് ടെസ്റ്റ്, ഒരു ഇന്റിജർ കൂട്ടൽ എന്നിവയാണ്, ഇത് ബേസ്‌ലൈൻ ഇംപ്ലിമെന്റേഷനിലെ ഒരു ഹാഷ്‌മാപ്പ് പ്രോബ്, ഒരു അലോക്കേറ്റർ കോൾ, നിരവധി സ്പെഷ്യൽ-കേസ് ബ്രാഞ്ചുകൾ എന്നിവയിൽ നിന്ന് കുറഞ്ഞതാണ്. ഓരോ എൻകോഡിനുമുള്ള ഇൻസ്ട്രക്ഷനുകൾ 3.66M-ൽ നിന്ന് 1.04M ആയി കുറഞ്ഞു, 3.5× കുറവ്. ഹ്രസ്വ ഇൻപുട്ടുകളിൽ വാൾ-ക്ലോക്ക് ആ അനുപാതവുമായി പൊരുത്തപ്പെടുന്നു കൂടാതെ ദീർഘമായ ഇൻപുട്ടുകളിൽ കൂടുതൽ വ്യാപിക്കുന്നു, അവിടെ റഫറൻസിന്റെ പെർ-ടോക്കൺ അലോക്കേഷനുകൾ L2, L3 എന്നിവ കവിയാൻ തുടങ്ങുന്നു.

പ്രയോഗത്തിൽ ഈ പ്രവർത്തനം ഞങ്ങളുടെ ഇൻഫറൻസ് സ്റ്റാക്കിന്റെ പ്രീപ്രോസസിങ് പാളിയിലെ CPU ഉപയോഗം 5-6 മടങ്ങ് കുറയ്ക്കുകയും റീറാംകർ ലേറ്റൻസിയിൽനിന്ന് രണ്ടക്ക മില്ലിസെക്കൻഡുകൾ വെട്ടിക്കുറയ്ക്കുകയും ചെയ്തു.

പാഴായ ജോലി നീക്കം ചെയ്ത ഭാരം കുറഞ്ഞ മാറ്റങ്ങളിൽ നിന്നാണ് ലേറ്റൻസി കുറവിന്റെ ഭൂരിഭാഗവും വന്നത്: പെർ-എൻകോഡ് അലോക്കേഷനുകൾ ഒഴിവാക്കൽ, ഹാഷ്-മാപ്പ്-ചിൽഡ്രൻ ട്രൈയ്ക്ക് പകരം ഡബിൾ-അറേ ഉപയോഗിക്കൽ, ജനറൽ-API ഓവർഹെഡ് നീക്കം ചെയ്യൽ. ഇൻപുട്ട് വലുപ്പത്തെ ആശ്രയിച്ച്, ഡബിൾ-അറേ ട്രൈയിലേക്കുള്ള വലിയ മാറ്റത്തിന് പുറമേ, നിലവിലുള്ള പെർ-നോഡ് ബിറ്റ്‌മാപ്പ് വാലിഡിറ്റി ചെക്ക് ആയി ഉപയോഗിക്കുന്നതും 2 MB ഹ്യൂജ് പേജുകൾ ഉപയോഗിച്ച് ട്രൈ ബാക്ക് ചെയ്യുന്നതും സംയുക്തമായി 10-20% സംഭാവന ചെയ്തു.

SentencePiece-നും IREE-ക്കും ചുറ്റുമുള്ള ഓഫ്-ദി-ഷെൽഫ് റസ്റ്റ് റാപ്പർ ക്രേറ്റുകൾ എതിരായി ഒരേ കാര്യം വ്യക്തമാക്കുന്നു. നേറ്റീവ് C, C++ ടോക്കണൈസറുകൾക്ക് മുകളിൽ, റാപ്പറുകൾ അവതരിപ്പിക്കുന്ന FFI അതിർത്തിയും പെർ-കോൾ അലോക്കേഷനുകളും ലേറ്റൻസി സംഖ്യകളിൽ ദൃശ്യമാണ്. അവസാന വിറ്റെർബി എൻകോഡറിനായുള്ള റസ്റ്റ് സോഴ്സ് github.com/perplexityai/pplx-garden-ൽ ലഭ്യമാണ്.

Hugging Face ടോക്കണൈസറുകൾ — 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}
}

പ്രചോദനം

വിറ്റെർബി അൽഗോരിതം

റഫറൻസ് ഇംപ്ലിമെന്റേഷൻ

പ്രീപ്രോസസിംഗിനെക്കുറിച്ചുള്ള ഒരു കുറിപ്പ്

റഫറൻസ് ഇംപ്ലിമെന്റേഷൻ അതിന്റെ സമയം എവിടെയാണ് ചെലവഴിക്കുന്നത്

ഞങ്ങൾ എങ്ങനെ അളന്നു

SentencePiece-ഉം IREE-യും വേഗതയേറിയതാകാൻ കാരണം: ഡബിൾ-അറേ ട്രൈ

ബേസ്‌ലൈൻ: റഫറൻസിന്റെ ഒരു സീറോ-അലോക്കേഷൻ പോർട്ട്

ഒപ്റ്റിമൈസേഷൻ 1: അധിക അമർക്കലുകൾ (abstractions) ഇല്ലാത്ത ഡബിൾ-അറേ ട്രൈ

ഒപ്റ്റിമൈസേഷൻ 2: ബിറ്റ്‌മാപ്പും ഇൻലൈൻ പാക്കിംഗും

ഒപ്റ്റിമൈസേഷൻ 3: ട്രൈയ്ക്കായുള്ള വലിയ പേജുകൾ

അവസാന താരതമ്യം

അവസാന ചിന്തകൾ

റഫറൻസുകൾ

ഉദ്ധരണി