ইউনিগ্রাম টোকেনাইজার সিপিইউ পারফরম্যান্স উন্নত করা

আমরা পারফরম্যান্স বাড়ানোর একটি সুনির্দিষ্ট প্রজেক্ট হিসেবে আমাদের ইউনিগ্রাম টোকেনাইজার স্ক্র্যাচ থেকে পুনরায় তৈরি করেছি।

লেখকগণPerplexity Research

আমরা পারফরম্যান্স বাড়ানোর একটি সুনির্দিষ্ট প্রজেক্ট হিসেবে আমাদের ইউনিগ্রাম টোকেনাইজার স্ক্র্যাচ থেকে পুনরায় তৈরি করেছি। প্রোডাকশন ইনপুটের দৈর্ঘ্যে, নতুন এনকোডার Hugging Face tokenizers ক্রেটের তুলনায় p50 ল্যাটেন্সি প্রায় ৫ গুণ, SentencePiece (C++) এর তুলনায় প্রায় ২ গুণ এবং IREE's tokenizer (C) এর তুলনায় প্রায় ১.৫ গুণ কমিয়ে আনে, যেখানে কোনো স্টেডি-স্টেট হিপ অ্যালোকেশন নেই। প্রোডাকশনে এটি আমাদের ইনফারেন্স স্ট্যাকের CPU ব্যবহার ৫-৬ গুণ কমিয়ে দিয়েছে এবং রিকারারের ল্যাটেন্সি থেকে দুই অঙ্কের মিলিসেকেন্ড কমিয়ে এনেছে।

প্রেরণা

এলএলএম (LLM) ইনফারেন্স খরচ সাধারণত জিপিইউ (GPU) কাজের হিসেবে ধরা হয়: কেভি ক্যাশ, অ্যাটেনশন কার্নেল, এক্সপার্ট রাউটিং। কিন্তু প্রোডাকশন ট্রাফিকের একটি উল্লেখযোগ্য অংশ অনেক ছোট মডেলের উপর চলে, যা ফ্রন্টিয়ার ট্রান্সফরমারের চেয়ে দুই থেকে তিন অর্ডার ছোট। এমবেডিং মডেল, ক্লাসিফায়ার এবং রিকারার এখনও জিপিইউতে চলে, কিন্তু ফরোয়ার্ড পাস এতটাই ছোট যে এর আশেপাশের সবকিছুই গুরুত্বপূর্ণ হয়ে ওঠে।

সবচেয়ে স্পষ্ট উদাহরণ হলো একটি রিকারার যা প্রতি অনুরোধে শত শত প্রার্থী নথি স্কোর করে। একটি ছোট মডেলের সাথে, জিপিইউ কম্পিউট সাধারণত একক-সংখ্যার মিলিসেকেন্ডে শেষ হয়, তবে প্রতিটি ইনপুটকে প্রথমে সিপিইউ-সাইড টোকেনাইজার-এর মাধ্যমে যেতে হয়, যা টেক্সটকে ভোকাবুলারি আইডিতে রূপান্তরিত করে। যখন ব্যাচটি বড় হয়, তখন এটি মোট অনুরোধের ল্যাটেন্সির একটি উল্লেখযোগ্য অংশের জন্য দায়ী হতে পারে।

এই কাজটি XLM-RoBERTa-কে লক্ষ্য করে, যা SentencePiece দিয়ে প্রশিক্ষিত একটি ২৫০কে-টোকেন ইউনিগ্রাম ভোকাবুলারি। ফাইন-টিউন করা RoBERTa-পরিবারের এনকোডারগুলো র‍্যাঙ্কিং, রিট্রিভাল এবং মিল টাস্কের জন্য একটি সাধারণ পছন্দ। আমরা সর্বত্র একক-থ্রেডেড প্রতি-এনকোড ল্যাটেন্সি রিপোর্ট করি; প্রোডাকশনে আমরা rayon ব্যবহার করে কোরের মধ্যে প্যারালাইজ করি।

এই পোস্টে আমরা Hugging Face-এর tokenizers crate-কে সেই রেফারেন্স হিসেবে বিবেচনা করি যার বিরুদ্ধে আমরা বেঞ্চমার্ক করি, কারণ এটি ডিফল্ট রাসট টোকেনাইজার যা বেশিরভাগ টিম ব্যবহার করে। অন্যান্য দুটি প্রধান প্রোডাকশন ইমপ্লিমেন্টেশন হিসেবে তুলনার জন্য SentencePiece (C++) এবং IREE (C) অন্তর্ভুক্ত করা হয়েছে।

ভিটারবি অ্যালগরিদম

ইউনিগ্রাম টোকেনাইজেশন, যা কুডো কর্তৃক ২০১৮ সালে প্রবর্তিত হয়েছিল (Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates) এবং SentencePiece-এ পাঠানো হয়েছিল, সেগমেন্টেশনকে একটি মোস্ট-প্রোবাবল-পাথ সমস্যা হিসেবে রূপ দেয়: প্রতিটি ভোকাবুলারি টোকেনের একটি শেখা লগ-প্রোবাবিলটি থাকে, এবং এনকোডার সেই সেগমেন্টেশন বেছে নেয় যার টোকেন স্কোর যোগ করলে সর্বোচ্চ মান পাওয়া যায়। সমস্যাটি ভিটারবি অ্যালগরিদম (১৯৬৭) দিয়ে সমাধান করা হয়, যেখানে গ্রাফ লেয়ার হিসেবে বাইট পজিশন এবং একটি সংলগ্ন বাইট রেঞ্জ জুড়ে এজ হিসেবে ভোকাবুলারি টোকেন থাকে। রিকারেন্স হলো বাইট পজিশনের উপর একটি ওয়ান-ডাইমেনশনালডিপি (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-এর জন্য ৪৮টি UTF-8 বাইট) দ্বারা সীমাবদ্ধ। ইনার ট্রাই ওয়াক হলো হট পাথ: ১৬কে-টোকেন ইনপুটে, এটি প্রতি এনকোডে লক্ষ লক্ষ ট্রানজিশন চালায় এবং কোটি কোটি নির্দেশ অপারেশন সম্পন্ন করে।

রেফারেন্স ইমপ্লিমেন্টেশন

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) এবং ওয়ার্ড-বাউন্ডারি মার্কিংয়ের মধ্য দিয়ে যায়। প্রোফাইলিং অনুসারে আমাদের দৃশ্যপটগুলোতে মোট এনকোড সময়ের ৫% এরও কম সময় প্রিপ্রসেসিংয়ে ব্যয় হয়, তাই আমরা পোস্টের বাকি অংশের জন্য ভিটারবি ফরোয়ার্ড পাসের উপর ফোকাস করি।

যেখানে রেফারেন্স ইমপ্লিমেন্টেশন তার সময় ব্যয় করে

সিপিইউ কোডের গতি বাড়ানোর দুটি উপায় রয়েছে: কম নির্দেশ execute করা, অথবা উচ্চ IPC পাওয়া। Cachegrind প্রথমটি পরিমাপ করে, perf stat দ্বিতীয়টি পরিমাপ করে। এই পোস্টের প্রতিটি অপ্টিমাইজেশন এর যেকোনো একটির উপর কাজ করে।

সিপিইউ চারটি বিষয়ের কারণে স্লো হয়ে যায়: ক্যাশ মিস (L1d ~৪ সাইকেল, L3-miss-to-DRAM হলো শত শত), ডিপেন্ডেন্ট-লোড চেইন যা আউট-অফ-অর্ডার ইঞ্জিন প্যারালাইজ করতে পারে না, ব্রাঞ্চ মিসপ্রেডিক্ট (~১৫-২০ সাইকেল প্রতি ভুল অনুমানের জন্য ফ্লাশ হয়), এবং অ্যালোকেটর কল। রেফারেন্স ইউনিগ্রাম ইঞ্জিন ইমপ্লিমেন্টেশন এই চারটিকেই হিট করে:

বটলনেক

মেকানিজম

পরিমাপকৃত প্রভাব

প্রতি ম্যাচে অ্যালোকেশন

ম্যাচ করা বাইটের উপর String::from_utf8 এবং প্রতিটি ট্রাই ম্যাচের জন্য একটি AHashMap লুকআপ; টোকেন আইডি ইতিমধ্যে লিফ-এ রয়েছে, কিন্তু রেফারেন্স এটি সেখানে সংরক্ষণ করে না

৫১২ টোকেনে ৭,২৯৫টি অ্যালোকেশন, ১কে-তে ১৪,৫৪২টি, ১৬কে-তে ২৯৯,১৭১টি

প্রতি বাইটে পয়েন্টার চেজ

প্রতিটি ট্রাই নোডে একটি AHashMap, পরবর্তী বাইট হ্যাশ করা এবং প্রতি ধাপে দুটি পয়েন্টার ডিফারেন্সিং করা; Node স্ট্রাক্ট কোল্ড ফিল্ড যেমন is_leaf-কেও বান্ডিল করে, প্রতি ভিজিটে সেগুলোকে ক্যাশে টেনে নিয়ে আসে

L1d মিস রেট কম থাকে (১কে-তে প্রায় ২.৫%) কারণ অ্যালোকেটর হট পেজগুলো L1-এ থাকে; খরচটি ডিপেন্ডেন্ট-লোড ল্যাটেন্সি হিসেবে প্রকাশ পায়

দীর্ঘ ইনপুটে L2 থ্র্যাশিং

DP টেবিল, প্রিফিক্স স্ক্র্যাচ এবং আউটপুট টোকেন তালিকা প্রতিটি কলের জন্য নতুন করে অ্যালোকেট করা হয়

cumulative alloc ফুটপ্রিন্ট প্রতি-কোর ২ MB L2 অতিক্রম করার কারণে L2 মিস রেট ১২৮ টোকেনে ১২% থেকে বেড়ে ১৬কে-তে ৫০% হয়ে যায়

রেফারেন্স টোকেনাইজারের বটলনেক, প্রক্রিয়া, এবং পরিমাপিত প্রভাব।

প্রধান খরচ হলো প্রতি ম্যাচের জন্য অ্যালোকেশন। ১কে টোকেনে, রেফারেন্স ইমপ্লিমেন্টেশন প্রতি এনকোডে প্রায় ৭M নির্দেশ ২.৮ IPC-তে সম্পূর্ণ করে, যার বেশিরভাগই অ্যালোকেটর কল এবং স্ট্রিং রূপান্তর। L2 মিস কেবল ~১কে টোকেনের পরে গুরুত্বপূর্ণ হয়, যখন কিমুলেটিভ অ্যালোকেশন ফুটপ্রিন্ট প্রতি-কোরের ক্যাশ ছাড়িয়ে যায়।

ইনপুট আকার অনুযায়ী রেফারেন্স টোকেনাইজারের p50 এবং p99 ল্যাটেন্সি।
ইনপুট আকার অনুযায়ী রেফারেন্স টোকেনাইজারের L2 ক্যাশ মিস হার।
ইনপুট আকার জুড়ে রেফারেন্স টোকেনাইজার প্রতি এনকোডে বরাদ্দকৃত বাইট।

প্রতি-টোকেন অ্যালোকেশন কনস্ট্যান্ট: ইনপুটের আকার নির্বিশেষে প্রতি টোকেনে প্রায় ২ KB এবং ~১৮টি অ্যালোকেশন। ল্যাটেন্সি অ-রৈখিকতা (non-linearity) আসে L2 থেকে: কিমুলেটিভ বাইট ১কে টোকেনের আশেপাশে ২ MB অতিক্রম করে, মিস রেট ৮% থেকে বেড়ে ~৫০% হয়ে যায়, এবং p99 কার্ভ এর সাথে সামঞ্জস্য রাখতে বেঁকে যায়।

আমরা যেভাবে পরিমাপ করেছি

আমরা তিনটি প্রোডাকশন টোকেনাইজার তুলনা করি, সবগুলোই একই XLM-RoBERTa মডেলের বিরুদ্ধে একই ইউনিগ্রাম অ্যালগরিদম চালাচ্ছে:

ইঞ্জিন

ভাষা

ট্রাই (Trie)

Hugging Face

রাসট (Rust)

HashMap-children prefix trie

SentencePiece

C++

Darts double-array trie

IREE টোকেনাইজার

C

Darts double-array trie

তুলনায় ব্যবহৃত টোকেনাইজার ইমপ্লিমেন্টেশন, ভাষা, এবং ট্রাই উপস্থাপনাগুলি।

আমরা রাসট র‍্যাপারের পরিবর্তে সরাসরি C/C++ FFI এর মাধ্যমে SentencePiece এবং IREE লিঙ্ক করি; র‍্যাপারগুলো প্রতি-কল অ্যালোকেশন এবং স্ট্রিং রূপান্তর যোগ করে যা আন্ডারলাইং লাইব্রেরির খরচের অংশ নয়।

সমস্ত ইঞ্জিন পূর্ণ অপ্টিমাইজেশন (O3, নেটিভ টার্গেটিং, লিংক-টাইম অপ্টিমাইজেশন) দিয়ে তৈরি করা হয়। পরিমাপগুলো Intel Xeon Platinum 8488C-এর একটি শান্ত কোরে পিন করে চালানো হয়। প্রতিটি ইঞ্জিন এবং ইনপুট আকারের জন্য আমরা ওয়াল-ক্লক ল্যাটেন্সি (p50 এবং p99, ১,০০০ ওয়ার্মআপের পর ১০,০০০ ইটারেশন), Valgrind cachegrind এর মাধ্যমে নির্দেশসমূহ, perf stat হার্ডওয়্যার কাউন্টার থেকে IPC এবং ক্যাশ মিস রেট, এবং পরিমাপকৃত উইন্ডোজের চারপাশে একটি গ্লোবাল অ্যালোকেটর র‍্যাপার দ্বারা গণনা করা হিপ অ্যালোকেশন সংগ্রহ করি।

৫১৪ টোকেনে (৫১২ এর উপর +২ হলো BOS/EOS ইনজেকশন):

ইমপ্লিমেন্টেশন

p50 ল্যাটেন্সি

নির্দেশসমূহ (Instructions)

IPC

অ্যালোকেশন

Hugging Face

৩৪৯ µs

৩.৬০M

২.৮৯

৭,২৯৫

SentencePiece

১২৮ µs

১.৮৩M

৩.৩৯

১,৫১৯

IREE

১১২ µs

২.২৮M

৩.০৬

১

৫১৪ টোকেনে টোকেনাইজারের ল্যাটেন্সি, নির্দেশনা সংখ্যা, IPC, এবং অ্যালোকেশন।

SP এবং IREE রেফারেন্সের ল্যাটেন্সির প্রায় এক তৃতীয়াংশে অবস্থান করে। তারা প্রায় অর্ধেক নির্দেশ সম্পন্ন করে, উচ্চ IPC-তে চলে, এবং এক থেকে দুই অর্ডার কম অ্যালোকেট করে।

কেন SentencePiece এবং IREE দ্রুততর: ডাবল-অ্যারে ট্রাই

SentencePiece এবং IREE উভয়ই ১৯৮৯ সালে 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-এর ২৫০কে ভোকাবের জন্য, সম্পূর্ণ ট্রাই ~৯ MB কন্টিন্যুস মেমরিতে ফিট করে (~৭৮০কে স্লট × প্রতি স্লটে অফসেট, ভ্যালিডেশন এবং টোকেন আইডির জন্য ১২ বাইট)। একটি একক এনকোডের হট ওয়ার্কিং সেট প্রায় ১০০ KB এর অর্ডারে, আরামে L2-তে থাকে, এবং হার্ডওয়্যার প্রিফেচার নিয়মিত অ্যাক্সেস প্যাটার্নে লক হয়ে যায়।

এর বিপরীতে, রেফারেন্স প্রতিটি নোডের চিলড্রেনের একটি হ্যাশ-ম্যাপ রাখে, যার খরচ প্রতি বাইট ধাপে প্রায় চারটি ডিপেন্ডেন্ট লোড। বাইট হ্যাশ করুন, বাকেট লোড করুন, বাকেট এন্ট্রির একটি পয়েন্টার অনুসরণ করুন, হিপে চাইল্ড নোডের আরেকটি পয়েন্টার অনুসরণ করুন, তারপর পরবর্তী বাইটের জন্য এর নিজস্ব হ্যাশ-ম্যাপ কনসাল্ট করুন। হিপ অবজেক্টগুলো বিক্ষিপ্ত থাকে এবং বেশিরভাগ লোড ক্যাশ মিস করে।

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 চলাকালীন প্রতি ম্যাচে একটি ল্যাটিস নোড অ্যালোকেট করে, যা ৫১৪ টোকেনে মোট প্রায় ১,৫৫৮ অ্যালোকেশন হয়।

বেসলাইন: রেফারেন্সের একটি জিরো-অ্যালোকেশন পোর্ট

ট্রাই পরিবর্তন করার আগে, আমরা ইমপ্লিমেন্টেশন খরচ থেকে অ্যালগরিদম খরচ আলাদা করি: অপ্রয়োজনীয় কাজ বাদ দিলে রেফারেন্সটি কত দ্রুত চলে?

বেসলাইনটি রেফারেন্সের হ্যাশ-ম্যাপ-চিলড্রেন ট্রাই রাখে কিন্তু দুটি পরিবর্তন করে। একটি কলার-মালিকানাধীন স্ক্র্যাচ স্ট্রাক্ট 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, } } }

এটি একই অ্যালগরিদম, একই ট্রাই আকৃতি এবং একই অ্যাক্সেস প্যাটার্ন সহ, কেবল কোনো অ্যালোকেশন এবং কোনো অতিরিক্ত লুকআপ ছাড়াই। ৫১৪ টোকেনে ফলাফল:

ইঞ্জিন

p50

নির্দেশসমূহ (Instructions)

IPC

অ্যালোকেশন

Hugging Face

৩২৬ µs

৩.৬৬M

২.৮৬

৭,২৯৫

SentencePiece

১২৭ µs

১.৮১M

৩.৫৫

১,৫১৯

IREE

১১১ µs

১.৫৮M

৩.২৬

১

বেসলাইন

১৫৬ µs

১.৫৩M

২.৬২

০

৫১৪ টোকেনে বিদ্যমান টোকেনাইজার ইমপ্লিমেন্টেশনগুলির তুলনায় জিরো-অ্যালোকেশন বেসলাইন।

প্রতি-ম্যাচ স্ট্রিং মেটেরিয়ালাইজেশন এবং সেকেন্ডারি হ্যাশ-ম্যাপ লুকআপ অপসারণ করা রেফারেন্সের তুলনায় নির্দেশ ২.৪ গুণ কমিয়ে দেয়। এর সাথে IPC কমে যায় (২.৮৬ → ২.৬২) কারণ হ্যাশ-ম্যাপ পয়েন্টার চেজ, যা আগে অ্যালোকেটর কাজের আড়ালে ঢাকা ছিল, এখন প্রতি বাইটের প্রধান খরচ হয়ে দাঁড়ায়।

ইনপুট আকার অনুযায়ী রেফারেন্স এবং জিরো-অ্যালোকেশন বেসলাইন টোকেনাইজারের p50 এবং p99 ল্যাটেন্সি।
ইনপুট আকার অনুযায়ী রেফারেন্স এবং জিরো-অ্যালোকেশন বেসলাইন টোকেনাইজারের L2 ক্যাশ মিস হার।

বেসলাইনটি প্রতিটি আকারে রেফারেন্সের তুলনায় p50 ল্যাটেন্সি ২-৩ গুণ কমিয়ে দেয়, এবং এর L2 মিস রেট রেফারেন্সের ৮-48% এর বিপরীতে ২কে টোকেন পর্যন্ত ২-3% এর কাছাকাছি থাকে। বাকি খরচ হলো HashMap পয়েন্টার চেজ, যা পরবর্তী বিভাগে সমাধান করা হয়েছে।

অপ্টিমাইজেশন ১: অতিরিক্ত অ্যাবস্ট্রাকশন ছাড়াই ডাবল-অ্যারে ট্রাই

হ্যাশ-ম্যাপ ট্রাই একটি পয়েন্টার চেজ। 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 } }

একটি বাইট ধাপের খরচ দুটি অ্যারে রিড, একটি ইন্টিজার যোগ এবং একটি তুলনা। সম্পূর্ণ ট্রাই প্রায় ৯ MB, কিন্তু যেকোনো একক এনকোডে এর কেবল ~১০০ KB ওয়াক করে, তাই হট ডেটা L2-তে থাকে।

ইঞ্জিন

p50

p99

নির্দেশসমূহ (Instructions)

L2 মিস%

L3 মিস%

Hugging Face

৩২৭ µs

৩,৩৪০ µs

৩.৬৬M

৮.১৭%

১৪.৬৬%

SentencePiece

১২৭ µs

১,১৪০ µs

১.৮২M

৪.৭৪%

৪.০৭%

IREE

১১১ µs

১৩২ µs

১.৬১M

৫.৮২%

৩.৮৭%

বেসলাইন

১৫৫ µs

১,১৭০ µs

১.৫৩M

২.৫৯%

১৬.৬৬%

+ Darts

৬৮ µs

৮০ µs

১.১০M

৬.৪৫%

১১.৪২%

ডাবল-অ্যারে ট্রাই গ্রহণের পর টোকেনাইজারের ল্যাটেন্সি, নির্দেশনা, এবং ক্যাশ মিস হার।

ওয়াল-ক্লক বেসলাইন থেকে ২.৩ গুণ এবং রেফারেন্স থেকে ৪.৮ গুণ কমে যায়। নির্দেশসমূহ বেসলাইন থেকে আরও ২৮% কমে যায়। ল্যাটিস এবং পাইপলাইন বাদ দেওয়ার ফলে আমরা একই ট্রাই আকৃতিতে SP-এর ১.৮২M এবং IREE-এর ১.৬১M-এর বিপরীতে প্রতি এনকোডে ১.১০M নির্দেশ সম্পূর্ণ করতে পারি; ব্যবধানটি হলো সেই বুককিপিং যা তারা জেনারেল-পারপাস API-এর জন্য রাখে যা আমাদের প্রয়োজন নেই।

অপ্টিমাইজেশান ২: বিটম্যাপ এবং ইনলাইন প্যাকিং

অপ্টিমাইজেশন ১ থেকে Darts ট্রাইয়ের জন্য প্রতি বাইট ধাপে দুটি ডিপেন্ডেন্ট লোড প্রয়োজন। প্রথমে প্যারেন্টের বেস অফসেট, তারপর প্যারেন্টের মালিকানা নিশ্চিত করতে ক্যান্ডিডেট চাইল্ড স্লটে চেক এন্ট্রি। চেক এন্ট্রি কেবল মালিকানা যাচাই করে। একই প্রশ্নের উত্তর একটি প্রতি-নোড বিটম্যাপ দিয়ে দেওয়া যেতে পারে যা রেকর্ড করে কোন বাইটগুলোর চিলড্রেন রয়েছে। ডাবল-অ্যারে ট্রাইয়ের কনস্ট্রাকশন অনুসারে, প্যারেন্টের বিটম্যাপে বাইট b-এর জন্য বিট তখনই সেট হয় যখন সেই বাইটের জন্য ক্যান্ডিডেট স্লটের মালিক প্যারেন্ট হয়। বিটম্যাপ এবং চেক অ্যারে একই তথ্য বহন করে, তাই আমরা রানটাইম স্ট্রাকচার থেকে চেক অ্যারে সম্পূর্ণভাবে বাদ দিতে পারি।

বিটম্যাপ লুকআপ একটি একক ৬৪-বিট শব্দের বিপরীতে একটি একক বিট টেস্টে কম্পাইল হয়, যা প্রায় এক সাইকেলে চলে। সংশ্লিষ্ট POPCNT নির্দেশ, যা একটি রেজিস্টারে সমস্ত সেট বিট গণনা করে, তা অন্যান্য বিটম্যাপ-ইনডেক্সড ট্রাই ডিজাইন বিটম্যাপ থেকে সরাসরি চাইল্ড অফসেট গণনা করতে ব্যবহার করে। আমাদের এটির প্রয়োজন নেই কারণ 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) }

এর পাশাপাশি, আমরা প্রতি-নোডের চারটি ক্ষেত্র (বিটম্যাপ, বেস, টোকেন আইডি এবং স্কোর) একটি ৬৪-বাইটের ক্যাশ লাইনে প্যাক করি। একটি একক নোড ভিজিট এখন সবকিছু টেনে নিয়ে আসে: টার্মিনাল নোডে আমাদের যে স্কোর এবং টোকেন আইডি প্রয়োজন, সাথে পরবর্তী ধাপের জন্য বিটম্যাপ এবং বেস। চেক অ্যারে কেবল কনস্ট্রাকশনের সময় ব্যবহৃত হয় এবং রানটাইম লেআউট থেকে বাদ দেওয়া হয়। হট-পথ ইনডেক্সিং আনচেক করা হয় কারণ ট্রাই কনস্ট্রাকশন এবং লুপ স্ট্রাকচার ইতিমধ্যে সীমানা নিশ্চিত করে। ট্রেড-অফ হলো স্পেস: প্রতি নোডে ৬৪ বাইট × ~৭৮০কে স্লট হওয়ায় ট্রাই ~৯ MB থেকে বেড়ে ~৫০ MB হয়ে যায়।

৫১৪ টোকেনে ফলাফল:

ইঞ্জিন

p50

p99

নির্দেশসমূহ (Instructions)

L2 অ্যাক্সেস

L2 মিস%

L3 মিস%

Hugging Face

৩২৭ µs

৩,৩৪০ µs

৩.৬৬M

১৫.০K

৮.১৭%

১৪.৬৬%

SentencePiece

১২৭ µs

১,১৪০ µs

১.৮২M

৭.৫K

৪.৭৪%

৪.০৭%

IREE

১১১ µs

১৩২ µs

১.৬১M

৪.৭K

৫.৮২%

৩.৮৭%

বেসলাইন

১৫৫ µs

১,১৭০ µs

১.৫৩M

৬.১K

২.৫৯%

১৬.৬৬%

+ Darts

৬৮ µs

৮০ µs

১.১০M

৪.৬K

৬.৪৫%

১১.৪২%

+ Bitmap and Inline Packing

৬৫ µs

৭৭ µs

১.০৬M

১.৮K

২০.৫৩%

১৫.০১%

বিটম্যাপ এবং ইনলাইন প্যাকিং যোগ করার পর ৫১৪ টোকেনে টোকেনাইজারের ফলাফল।

ওয়াল-ক্লক ৫১৪ টোকেনে সিস্টেমেটিকভাবে আরও ৪.৫% কমে যায় এবং ইনপুটের দৈর্ঘ্যের সাথে বৃদ্ধি পায়, ৪কে এবং ১৬কে তে ৬-৭% এ পৌঁছায়। চেক অ্যারে বাদ দিলে প্রতি-বাইট ট্রাই ধাপ দুটি ক্যাশ-লাইন লোড থেকে একটিতে পরিণত হয়, যা প্রতি এনকোডে ২.৫ গুণ কম L2 অ্যাক্সেস (প্লেন Darts-এর ৪.৬K এর বিপরীতে ১.৮K)। মিস রেট ৬% থেকে বেড়ে ২০% এ পৌঁছায়, কিন্তু এর বেশিরভাগই হলো ডিনোমিনেটর: অর্ধেকেরও কম অ্যাক্সেসের সাথে, আমাদের যে মিসগুলো হয় তা একটি বড় অংশ নেয়।

অপ্টিমাইজেশান ৩: ট্রাইয়ের জন্য হিউজ পেজ

ট্রাই ডেটা হলো প্রায় ৫০ MB (প্রতিটি ৬৪ বাইটে ৭,৮০,০০০ নোড)। একটি ডিফল্ট লিনাক্স প্রসেসে, সেই মেমরি ৪ KB পেজ দ্বারা সমর্থিত, তাই সম্পূর্ণ ট্রাই প্রায় ১২,০০০ স্বতন্ত্র ভার্চুয়াল পেজ জুড়ে থাকে, যা সিপিইউ-এর ফার্স্ট-লেভেল ডাটা ট্রান্সলেশন লুকাসাইড বাফার ধারণ করতে পারে তার চেয়ে অনেক বেশি (Sapphire Rapids-এ ৯৬টি এন্ট্রি রয়েছে)। প্রতিটি ভিটারবি ধাপ একটি ভিন্ন নোড স্পর্শ করে, এবং একটি ৫১২-টোকেন এনকোডের উপর আমরা পেজ-টেবিল ওয়াক-এ প্রায় ৯,০০০ সাইকেল খরচ করি, যা প্রতি-এনকোড বাজেটের প্রায় ৩%।

এর সমাধান হলো ৪ KB পেজের পরিবর্তে ২ MB হিউজ পেজ দিয়ে ট্রাই ব্যাক করা। একই ৫০ MB এখন ২৫টি পেজ জুড়ে থাকে, ট্রান্সলেশন লুকাসাইড বাফারে সম্পূর্ণভাবে ফিট করে, এবং পেজ-টেবিল ডিরেক্টরিগুলো নিজেই L2 ক্যাশের জন্য ট্রাইয়ের সাথে প্রতিযোগিতা করা বন্ধ করে দেয়।

২ MB পেজ দিয়ে মেমরি ব্যাক করার লিনাক্সের দুটি উপায় রয়েছে। সুবিধাবাদী উপায়টি হলো ট্রান্সপারেন্ট হিউজ পেজ (THP): আপনার প্রোগ্রাম কার্নেলকে ৪ KB থেকে ২ 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 সেট করা)। আমাদের প্রোডাকশন ইনস্ট্যান্সে, ১০,৫৬১টি হিউজ পেজ রিজার্ভ করা আছে; ট্রাই তার মধ্যে ২৪টি ব্যবহার করে। mmap এর পরে, /proc/<pid>/smaps অঞ্চলটি নিশ্চিত করে: KernelPageSize: 2048 kB, Private_Hugetlb: 49152 kB।

লাভ হলো ইনপুট আকারের উপর ৩–১২% ওয়াল-ক্লক, যা ওয়ার্কিং-সেট দৈর্ঘ্যের সাথে সামঞ্জস্যপূর্ণ এবং সমানুপাতিক:

টোকেন

হিউজ পেজ ছাড়া

হিউজ পেজ সহ

Δ

১৩০

১৫.৭ µs

১৫.২ µs

−৩.৬%

৫১৪

৬৫.৪ µs

৬৩.১ µs

−৩.৪%

১,০২৬

১২৯.৫ µs

১২৫.৩ µs

−৩.৩%

৪,০৯৮

৭৭৩ µs

৬৭৯ µs

−১২.০%

১৬,৩৮৬

৩,৮০৮ µs

৩,৫৫৪ µs

−৬.৮%

বিভিন্ন ইনপুট আকারে বিশাল পেজসহ এবং ছাড়া টোকেনাইজারের ল্যাটেন্সি।

সবচেয়ে বড় লাভ হলো ৪কে টোকেনে, যেখানে ওয়ার্কিং সেট এতটাই বড় যে পেজ-টেবিল ট্রাফিক L2 ব্যান্ডউইথর জন্য ট্রাই ডেটার সাথে সক্রিয়ভাবে প্রতিযোগিতা করছিল। ৪কে এর বাইরে লাভ কমে যায় কারণ L3 মিস আধ বিস্তার করে এবং পেজ-টেবিল ওয়াক মোট সময়ের একটি ছোট অংশ হয়ে দাঁড়ায়।

চূড়ান্ত তুলনা

তিনটি অপ্টিমাইজেশন একত্রিত করে, আমরা পরীক্ষা করা অন্যান্য প্রতিটি RoBERTa টোকেনাইজারের বিপরীতে পরিমাপ করা চূড়ান্ত ইঞ্জিন এখানে রয়েছে। নেটিভ C++ SentencePiece এবং C IREE বাইনারির পাশাপাশি, আমরা অফ-দ্য-শেল্ফ রাসট র‍্যাপার ক্রেটগুলোও বেঞ্চমার্ক করেছি যা একজন প্রোডাকশন ব্যবহারকারী ব্যবহার করবে, যেমন sentencepiece এবং iree-tokenizer। sentencepiece ক্রেট প্রতিটি ইনপুট আকারে নেটিভ C++ বাইনারির তুলনায় ১.৬-১.9 গুণ উচ্চ ল্যাটেন্সি পরিমাপ করে, যে ওভারহেড র‍্যাপার থেকে আসে তা হলো প্রতিটি এনকোডে টোকেন পিসের একটি নতুন তালিকা অ্যালোকেট করা, যার প্রতিটির নিজস্ব পিস টেক্সটের কপি থাকে। iree-tokenizer ক্রেট প্রতিটি ইনপুটে এর অভ্যন্তরীণ বাফার সাইজ করে, যা একটি ধ্রুবক প্রতি-এনকোড অ্যালোকেশন এড়ায় যা নেটিভ IREE বাইনারি ইনপুট আকার নির্বিশেষে প্রদান করে, এবং এটি ছোট ইনপুটে সবচেয়ে বেশি গুরুত্বপূর্ণ যেখানে অ্যালোকেশন অন্যথায় আসল টোকেনাইজেশন কাজকে ছাড়িয়ে যেত। প্রোডাকশন ইনপুটের দৈর্ঘ্যে ধ্রুবক খরচ অ্যামোর্টাইজ হয় এবং রাসটে টোকেনগুলো অনুলিপি করার কারণে র‍্যাপারের নিজস্ব প্রতি-কল ওভারহেড এর ল্যাটেন্সিকে নেটিভ বাইনারির উপরে ঠেলে দেয়।

টোকেনাইজার ইমপ্লিমেন্টেশন এবং ইনপুট আকার জুড়ে প্রতি-এনকোড p50 এবং p99 ল্যাটেন্সি।

চূড়ান্ত ইঞ্জিনটি একই ২৫০,০০০-টোকেন ভোকাবুলারির উপর একই ভিটারবি চালায়, হট পথে কিছুই অ্যালোকেট করে না, এবং রেফারেন্সের বিপরীতে টোকেন-সঠিক আউটপুট তৈরি করে। প্রতিটি বাইট ধাপ এখন একটি একক ৬৪-বাইটের ক্যাশ-লাইন লোড, একটি বিটম্যাপ টেস্ট এবং একটি ইন্টিজার যোগ, যা বেসলাইন ইমপ্লিমেন্টেশনের একটি HashMap প্রোব, একটি অ্যালোকেটর কল এবং বেশ কয়েকটি বিশেষ-কেস ব্রাঞ্চ থেকে নিচে নেমে এসেছে। প্রতি এনকোডে নির্দেশসমূহ ৩.৬৬M থেকে কমে ১.০৪M হয়েছে, যা ৩.৫ গুণ হ্রাস। ওয়াল-ক্লক ছোট ইনপুটে সেই অনুপাতের সাথে মেলে এবং দীর্ঘ ইনপুটে আরও প্রসারিত হয়, যেখানে রেফারেন্সের প্রতি-টোকেন অ্যালোকেশন L2 এবং L3 ছাড়িয়ে যেতে শুরু করে।

শেষ ভাবনা

বাস্তবে এই কাজটি আমাদের ইনফারেন্স স্ট্যাকের প্রিপ্রসেসিং স্তরে CPU ব্যবহার ৫-৬ গুণ কমিয়ে দিয়েছে এবং রিকারারের ল্যাটেন্সি থেকে দুই অঙ্কের মিলিসেকেন্ড কমিয়ে এনেছে।

ল্যাটেন্সি হ্রাসের বেশিরভাগ অংশ এসেছে হালকা ওজনের পরিবর্তন থেকে যা অপচয়কৃত কাজ দূর করেছে: প্রতি-এনকোড অ্যালোকেশন বাদ দেওয়া, HashMap-চিলড্রেন ট্রাইকে ডাবল-অ্যারে দিয়ে প্রতিস্থাপন করা, এবং জেনেরিক-API ওভারহেড স্ট্রিপ করা। বৈধতা পরীক্ষা হিসেবে বিদ্যমান প্রতি-নোড বিটম্যাপ ব্যবহার করা এবং ২ MB হিউজ পেজ দিয়ে ট্রাই ব্যাক করা একত্রিত হয়ে ইনপুট আকারের উপর নির্ভর করে ডাবল-অ্যারে ট্রাইয়ে বড় স্যুইচের উপরে ১০-২০% অবদান রেখেছে।

SentencePiece এবং IREE এর চারপাশে অফ-দ্য-শেল্ফ রাসট র‍্যাপার ক্রেটগুলো বিপরীতভাবে একই বিন্দু চিত্রিত করে। নেটিভ C এবং C++ টোকেনাইজারের উপরে, FFI বাউন্ডারি এবং প্রতি-কল অ্যালোকেশন যা র‍্যাপারগুলো নিয়ে আসে তা ল্যাটেন্সি সংখ্যায় দৃশ্যমান। চূড়ান্ত ভিটারবি এনকোডারের রাসট সোর্স 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}
}