Оптимизируем декодирование u128 из base62
В предыдущей статье мы рассмотрели кодирование u128 в base62, теперь реализуем и оптимизируем обратную операцию декодирования u128 из base62, это может понадобиться, например, для более компактного хранения в памяти или в базе данных.
Чтобы понять какие оптимизации можно применить, начнем с простой, очевидной реализации:
const BASE62_N: usize = 62;
pub fn base62_to_u128_naive(base62_str: &str) -> Option {
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
Все идентификаторы должны иметь длину 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 {
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 раз.
если статья понравилась, можете угостить меня чашкой кофе, кнопка «Задонатить» внизу под статьей, винк-винк
