"Стоит только начать" - я писал бэкенд-сервис на Rust, и мне понадобилась валидация международных телефонных номеров. Как и любой Rust-разработчик, я пошёл на crates.io и скачал самую популярную библиотеку для этой задачи.
А затем я открыл их issues на GitHub.
То, что я увидел, было настоящим кладбищем старых, незакрытых багов. «В некоторых случаях национальная часть номера обрезается» (Open). «Номера, начинающиеся с той же последовательности, что и префикс страны, парсятся некорректно» (Open). «Международные номера с префиксом 00 не парсятся» (Open).
Портирование огромной C++ библиотеки libphonenumber от Google - сложная задача, и стоит отдать авторам должное - я уважаю их за то, что они за неё взялись. Но я не мог сдать клиентский проект с такими багами. Поэтому ( ну и потому что мне захотелось ) я решил сделать нечто немного безумное: написать собственный, bug-to-bug совместимый порт сишного libphonenumber, спроектированный с нуля для обеспечения максимальной производительности.
В этой статье я расскажу, как, делая библиотеку «глупее» в плане регулярных выражений, я заставил её работать быстрее.
Фаза 1: Первый прототип
Первой проблемой стала банальная навигация по кодовой базе Google. Читать чужой C++ не так-то просто, когда это не твой основной язык. Я не хотел вслепую копировать файлы по 5000 строк, поэтому начал разбивать логику на более мелкие модули.
Первой стратегической ошибкой стало то, как я обошелся с регулярными выражениями. Библиотека Google использует RE2 и сильно полагается на проверки точных границ совпадений, такие как FullMatch и FindAndConsume. Я почему-то полагал, что смогу просто заменить их стандартными вызовами крейта regex, проверяя условия вроде match.start == 0 && end == strlen.
Затем дело дошло до метаданных. Валидация телефонных номеров опирается на гигантский набор правил для каждой страны на планете. Сначала я думал, что смогу написать Rust-структуры для этих данных вручную. Я ошибался. Скрипт генерации метаданных в C++ выдает сырой бинарный массив protobuf. Чтобы прочитать его, мне пришлось использовать protobuf-gen (хотя сейчас я планирую миграцию на prost или что-то более подходящее).
Ещё одним ранним препятствием стала нормализация строк. Библиотеке нужно конвертировать любой Unicode-символ категории "Decimal Number" (Nd) в стандартную ASCII-цифру, а я в свою очередь не хотел тащить ради этого огромную библиотеку ICU. Решением стало написание отдельного легковесного крейта: dec_from_char. В свои ранние дни это был просто гигантский match, сгенерированный макросом на основе UnicodeProps.txt. Поскольку символов категории Nd не так уж много, это позволило сохранить маленький размер бинарника при приемлемой производительности.
У меня на руках был рабочий прототип. Базовый набор тестов проходил успешно. И я взял долгий перерыв от проекта.
Фаза 2: Тревожный звоночек
Пока я отдыхал от кодовой базы, один неравнодушный контрибьютор открыл PR. Он напрямую перенёс RegexBasedMatcher из C++ в Rust, включая глобальный RegexCache для обработки точного anchored поиска, который использовала библиотека Google. Это было абсолютно точное воспроизведение upstream-логики.
Но когда я у себя запустил бенчмарки, я немного осел:
Formatting Comparison/rlibphonenumber: format(National) time:[3.5683 ms 3.5991 ms 3.6337 ms] change:[+22240% +22556% +22875%] (p = 0.00 < 0.05) Performance has regressed.
Производительность упала более чем на 22 000%. Форматирование одного номера внезапно стало занимать миллисекунды. Я вежливо отклонил PR с мыслью, мол Точная совместимость с внутренностями C++ не стоит того, чтобы уничтожать перфоманс. В тот момент я не особо понимал, что этот PR был ярким доказательством, указывающим на существование гораздо более крупной баги в моём собственном коде.
Фаза 3: Возвращение и дифференциальный фаззинг
Спустя несколько месяцев я вернулся к библиотеке с желанием опубликовать мажорный релиз, но перед публикацией версии v1.0 мне нужны были абсолютные доказательства того, что моя библиотека ведёт себя идентично гугловской. Написать краевые случаи (edge cases) вручную было нереально, поэтому я обратился к дифференциальному фаззингу. Я слинковал оригинальную C++ библиотеку через cxx и скормил обеим реализациям миллионы случайных строк, чтобы сравнить их вывод.
Фаззер упал почти мгновенно. Строка вроде CD(+48X666666644 помечалась моим Rust-кодом как невалидная, а сишным - как валидная, тут до меня дошло: контрибьютор из PR не просто так переводил C++ слово в слово. Мои проверки границ start == 0 && end == strlen были сломаны для сложных краевых случаев. Из-за внутренней структуры паттернов регулярок, мои простые проверки границ не пропускали валидные строки. Мне нужна была точность заякоренных регулярных выражений из C++. Но я категорически отказывался мириться с потерей 22 000% производительности из-за RegexCache, аллоцирующего и компилирующего строки в рантайме.
Фаза 4: Быстрые регулярки (переносим работу в build-time)
Как «заякорить» тысячи регулярных выражений без выделения строк в памяти во время выполнения и без блокировки глобального кэша? Перенести эту работу на этап сборки. Я изменил свой Java-скрипт сборки (который парсит XML с метаданными), чтобы он заранее оборачивал паттерны в ^(?:...)$. Однако инициализация трех разных вариаций регулярного выражения при запуске раздула бы потребление памяти. Вместо этого я создал структуру RegexTriplets:
#[derive(Debug, Clone)] pub struct RegexTriplets { pub pattern_base: Option<String>, pub original: OnceLock<Result<Option<Regex>, crate::regexp::Error>>, pub anchor_start: OnceLock<Result<Option<Regex>, crate::regexp::Error>>, pub anchor_full: OnceLock<Result<Option<Regex>, crate::regexp::Error>>, }
Она весит всего 84 байта. Мы храним сырую строку через pattern_base (так как внутренней логике иногда нужно брать из неё срезы) и лениво инициализируем реальные объекты Regex только если запрашивается конкретная вариация для точного совпадения. Благодаря срезам строк в Rust ([..]), которые практически ничего не стоят в плане производительности, я достиг точности C++ реализации с минимальным оверхедом в рантайме.
Фаза 5: WASM, regex-lite и кастомные префиксные деревья (Trie)
Одной из моих целей была поддержка WebAssembly. Я хотел сделать живое превью на сайте "как у гугол", не оплачивая хостинг для Rust-бэкенда. Но мои первые WASM-сборки весили мегабайты. Главным виновником был крейт regex - компиляция конечных автоматов (DFA) в WASM занимает массу места. Я перешел на regex-lite, что позволило сбросить размер бинарника до прекрасных ~500 КБ. Но была одна загвоздка: regex-lite не поддерживает Unicode-категории вроде \p{L} (Буквы) или \p{N} (Цифры). Отказаться от полной поддержки Unicode для международной библиотеки телефонных номеров не особо хотелось. Чтобы исправить это, я полностью переписал свой крейт dec_from_char в новый генератор кода. Вместо гигантского match, мой build.rs теперь предварительно вычисляет поисковую таблицу (вроде Trie) для нужных свойств Unicode. Используя фиксированные размеры чанков, он генерирует массивы, которые обеспечивают поиск за O(1) для любого символа вплоть до 0x10FFFF.
impl Category { #[inline(always)] pub fn from_char(c: char) -> ::std::option::Option<Self> { let cp = c as u32; if cp > MAX_CODEPOINT { return None; } let index_idx = (cp >> SHIFT) as usize; // SAFETY: Arrays are generated to cover up to 0x10FFFF unsafe { let block_idx = *CATEGORY_INDICES.get_unchecked(index_idx) as usize; let offset = (cp & MASK) as usize; let final_pos = (block_idx << SHIFT) + offset; *CATEGORY_BLOCKS.get_unchecked(final_pos) } } }
Это позволило мне полностью выпилить регулярные выражения из критических горячих путей (hot-paths). Удаление нежелательных символов в конце строки превратилось из медленного совпадения по регулярке в цикле:
// Старый, медленный способ через регулярные выражения pub(crate) fn trim_unwanted_end_chars<'a>(&self, phone_number: &'a str) -> &'a str { // ... цикл с regex.full_match() ... }
В единственный, нативный вызов метода итератора Rust, использующий сгенерированные таблицы:
// Новый, мгновенный способ pub(crate) fn trim_unwanted_end_chars<'a>(&self, phone_number: &'a str) -> &'a str { phone_number.trim_end_matches(|c| { c != '#' && uniprops_without_nl::uniprops::Category::from_char(c).is_some() }) }
Фаза 6: Форматирование без аллокаций (Zero-Allocation)
К этому моменту парсинг стал ощутимо быстрее, но форматирование всё ещё требовало выделения памяти в куче при добавлении ведущих нулей к национальным номерам. Чтобы добиться истинного форматирования без аллокаций, я написал кастомный форматтер целых чисел в строки под названием zeroes_itoa, склонировав и модифицировав популярный крейт itoa.
pub fn format(&mut self, mut n: u64, leading_zero_count: usize) -> Cow<'_, str> { let mut curr = self.bytes.len(); let buf_ptr = self.bytes.as_mut_ptr() as *mut u8; let lut_ptr = DEC_DIGITS_LUT.as_ptr(); // ... логика конвертации let final_len = self.bytes.len() - curr; let bytes = unsafe { slice::from_raw_parts(buf_ptr.add(curr), final_len) }; unsafe { str::from_utf8_unchecked(bytes).into() } }
Если требуемый паддинг не превышает 64-байтовый буфер на стеке (что для телефонного номера практически невозможно), этот код возвращает Cow::Borrowed(&str), полностью избегая обращения к системному аллокатору.
Итоги и результаты
Благодаря дифференциальному фаззингу, компиляции регулярок на этапе сборки, кастомным Unicode Trie и форматированию чисел на стеке, rlibphonenumber теперь абсолютно стабилен, bug-for-bug совместим с гугловским оригиналом и невероятно быстр.
Вот финальное сравнение производительности с upstream-реализацией от Google на C++:
Операция | C++ ( | Rust ( | Ускорение |
|---|---|---|---|
Парсинг | 2279 ns | 506 ns | ~ 4.5x |
Форматирование (E.164) | 63 ns | 36 ns | ~ 1.7x |
Форматирование (International) | 2028 ns | 447 ns | ~ 4.5x |
Форматирование (National) | 2484 ns | 578 ns | ~ 4.3x |
Мы пробили планку в ~500 наносекунд для полного парсинга, и чуть больше 30 наносекунд для форматирования в стандарт E.164.
Если вы работаете с высоконагруженными backend-сервисами и вам нужна валидация номеров, исходники лежат на GitHub:vloldik/rlibphonenumber.
