Оптимизируем декодирование u128 из base62

В предыдущей статье мы рассмотрели кодирование u128 в base62, теперь реализуем и оптимизируем обратную операцию декодирования u128 из base62, это может понадобиться, например, для более компактного хранения в памяти или в базе данных.

Чтобы понять какие оптимизации можно применить, начнем с простой, очевидной реализации:

const BASE62_N: usize = 62;  pub fn base62_to_u128_naive(base62_str: &str) -> Option<u128> {     let base62_str: [u8; 22] = base62_str.as_bytes().try_into().ok()?;     let mut n: u128 = 0;     for digit in &base62_str {         let number = match digit {             d if (b'0'..=b'9').contains(d) => d - 48,             d if (b'A'..=b'Z').contains(d) => d - 55,             d if (b'a'..=b'z').contains(d) => d - 61,             _ => return None,         };         n = n             .checked_mul(BASE62_N as u128)             .and_then(|n| n.checked_add(number as u128))?;     }     Some(n) } 

Разберем, что здесь происходит, сигнатура функции показывает, что мы принимаем строку и получаем в результате опциональное u128 число, так как в случае некорректных данных в строке мы ее не сможем декодировать:

fn base62_to_u128_naive(base62_str: &str) -> Option<u128> 

Все идентификаторы должны иметь длину 22 символа, подтверждаем это условие:

let base62_str: [u8; 22] = base62_str.as_bytes().try_into().ok()?; 

Далее вычисляем значение числа в цикле из цифр base62-строки:

for digit in &base62_str 

Нам надо конвертировать каждую цифру в десятичную систему, например «B» будет «11» в десятичной системе, выполняем это в match, проверяя каждый из возможных интервалов разрешенных символов:

let number = match digit 

Теперь вычисляем число, умножая на базу 62 и прибавляя следующую цифру. 22-х символьное число в базе 62 вмещает больше чисел, чем 128-битное, поэтому при конвертации необходимо проверять на переполнение:

n = n.checked_mul(BASE62_N as u128).and_then(|n| n.checked_add(number as u128))?; 

Получили результат, возвращаем:

Some(n) 

Посмотрим на результаты бенчмарка, на что способна первая версия функции (CPU i5-4690):

bench_base62_to_u128_naive 1000000: 0.121s 125.75Mib/s, 8240895.48/s 

Неплохо, скорость уже немного больше чем скорость даже оптимизированного кодировщика из первой статьи. Все из-за того, что при декодировании нет дорогих операций деления, но мы можем лучше!

Приступим к оптимизации. Начнем с того, что избавимся от match. Вместо того, чтобы проверять интервалы и вычитать смещение можно создать массив со всеми возможными вариантами, байтовое представление символа из base62-строки будет смещением (индексом), а значение это цифра в десятичной системе:

const BASE62_MAP: [u8; 123] = [     255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,     255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,     255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 255, 255, 255,     255, 255, 255, 255, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,     29, 30, 31, 32, 33, 34, 35, 255, 255, 255, 255, 255, 255, 36, 37, 38, 39, 40, 41, 42, 43, 44,     45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, ]; 

Теперь для конвертации достаточно взять значение по индексу, например BASE62_MAP[b'A'] будет 10.

Следующим шагом разберемся с умножением и сложением в цикле. Эти операции с проверкой переполнения (checked варианты), требуют бо́льшего количества инструкций, чем обычные без проверки. Так как переполнение возможно только на последнем шаге, мы можем вынести его проверку за цикл, конвертируя в цикле только первые 21 символ, а последний после цикла:

for digit in &base62_str[..21] {         // ...         n = n * BASE62_N as u128 + number as u128; } 

Другая проблема здесь в том, что само по себе умножение (так же как и сложение) 128-битных чисел более дорогая операция по сравнению, например, с умножением 64-битных чисел, в чем легко убедиться посмотрев на сгенерированный ассемблер для обеих этих операций. В предыдущей статье мы заменяли деление 128-битных чисел делением 64-битных, здесь же мы сделаем тоже самое для умножения и сложения. Для этого разделим исходное base62-число на несколько блоков по границам разрядов, конвертируем отдельно каждый блок, затем соберем все число из этих частей:

3322222222221111111111 -> 33 2222222222 1111111111                           n3         n2         n1 n = n3 * 62^20 + n2 * 62^10 + n1 

Итак итоговый оптимизированный вариант декодера, который у нас получился выглядит следующим образом:

const BASE62_N: usize = 62; const BASE62_POW_10: u128 = (BASE62_N as u128).pow(10); const BASE62_POW_20: u128 = (BASE62_N as u128).pow(20); const BASE62_MAP: [u8; 123] = [     255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,     255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,     255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 255, 255, 255,     255, 255, 255, 255, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,     29, 30, 31, 32, 33, 34, 35, 255, 255, 255, 255, 255, 255, 36, 37, 38, 39, 40, 41, 42, 43, 44,     45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, ];  pub fn base62_to_u128(base62_str: &str) -> Option<u128> {     let base62_str: [u8; 22] = base62_str.as_bytes().try_into().ok()?;     let mut n_section: u64 = 0;     for digit in &base62_str[12..22] {         let number = *BASE62_MAP.get(*digit as usize).filter(|it| **it <= 61)?;         n_section = n_section * BASE62_N as u64 + number as u64;     }     let mut n = n_section as u128;     n_section = 0;     for digit in &base62_str[2..12] {         let number = *BASE62_MAP.get(*digit as usize).filter(|it| **it <= 61)?;         n_section = n_section * BASE62_N as u64 + number as u64;     }     n += n_section as u128 * BASE62_POW_10;     n_section = 0;     for digit in &base62_str[0..2] {         let number = *BASE62_MAP.get(*digit as usize).filter(|it| **it <= 61)?;         n_section = n_section * BASE62_N as u64 + number as u64;     }     n.checked_add((n_section as u128).checked_mul(BASE62_POW_20)?) } 

Некоторые разъяснения к коду. Здесь мы вычисляем число на основе блоков разрядов (низкие разряды в конце строки):

for digit in &base62_str[12..22] // ... for digit in &base62_str[2..12] // ... for digit in &base62_str[0..2] // .. 

Эта строка преобразует цифру из базы 62 в десятичное число. При этом так как данные могут быть некорректны, добавлена проверка на то, что digit находится в разрешенном интервале:

let number = *BASE62_MAP.get(*digit as usize).filter(|it| **it <= 61)?; 

Убеждаемся, что верхние 2 разряда не вызывают переполнения:

n.checked_add((n_section as u128).checked_mul(BASE62_POW_20)?) 

Проверим бенчмарк, стоило ли это наших усилий?

bench_base62_to_u128 10000000: 0.182s 836.24Mib/s, 54803747.40/s 

Ого впечатляет! Мне даже пришлось увеличить количество итераций в 10 раз, чтобы получать стабильные измерения. В итоге ускорение по сравнению с первоначальным вариантом в 6.65 раз.

Если статья понравилась, можете угостить меня чашкой кофе, кнопка «Задонатить» внизу под статьей, винк-винк.