Оптимизируем кодирование u128 в base62
В процессе работы над своим приложением для заметок, когда я дошел до сохранения данных в базу данных я стал использовать для идентификации записей uuid4 идентификаторы, которые обычно выглядят примерно так, когда представлены в виде строки:
32dca18531a1435480461f99837a5b1d
По некоторым причинам использовать uuid мне не очень нравилось:
это довольно длинная строка из 32 символов, а мне надо будет иногда показывать ее пользователям
6 бит в uuid4 не используются, это константы, расточительно
константные биты в uuid4:
uuid.uuid4().bytes[6] & 0b11110000 # == 64
uuid.uuid4().bytes[8] & 0b11000000 # == 128
Я решил изучить другие варианты. Так определенной популярностью пользуются ulid, ksuid. Но они мне тоже не подошли, в основном из-за того что включают в себя временную метку.
Моим вариантом стали полностью случайные 128-битные идентификаторы, которые я кодирую в base62 строку. Почему base62? Они содержат только буквы и цифры, поэтому их можно выделять двойным кликом (a, например, base64 — нет). Идентификаторы стали короче, теперь это 22-символьные строки, например:
4xT8QKx8f3BwZP06VKSEMy
Но есть проблема! Кодирование в систему счисления, которая не является степенью двойки это довольно медленный процесс, из-за того, что включает операцию деления. Для декодирования (base62 в u128) такой проблемы нет, так как там не будет деления, только умножение и сложение.
Итак, сначала попробуем очевидный вариант кодировщика, написанный на Rust:
const BASE62_N: usize = 62;
const BASE62_DIGITS: &[u8; BASE62_N] =
b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
// сколько понадобится чисел в base62 для хранения u128?
// вычислить это число можно так, python: math.ceil(math.log(2**128, 62))
const U128_BASE62_ENCODED_LEN: usize = 22;
pub fn u128_to_base62_naive(mut n: u128) -> String {
// заполнение происходит от меньших разрядов к старшим, незаполненные старшие разряды останутся нулями
let mut b62_str = vec![b'0'; U128_BASE62_ENCODED_LEN];
let mut i = U128_BASE62_ENCODED_LEN;
while n > 0 {
i -= 1;
let digit_index = (n % BASE62_N as u128) as usize;
b62_str[i] = BASE62_DIGITS[digit_index];
n /= BASE62_N as u128;
}
// переменная гарантированно содержит корректную utf-8 строку, незачем дополнительно ее проверять
unsafe { String::from_utf8_unchecked(b62_str) }
}
По сути это конвертация из десятичной системы счисления в систему счисления с базой 62. Для этого мы делим изначальное число на новое основание, в которое переводим, остаток от деления является следующим разрядом в новой системе счисления, частное от деление снова делим и так далее в цикле.
Посмотрим на скорость алгоритма, результат бенчмарка (i5–4690 3.50GHz): bench_u128_to_base62_naive 1000000: 32.86Mib/s, 2153250.28/s
Грустные цифры, не правда ли? Для сравнения, base64 кодировщик работает со скоростью 309.35Mib/s, hex кодировщик 645.34Mib/s.
Почему так? Так как 62 не является степенью двойки, для конвертации нам приходится на каждом цикле повторно делить все 128-битное число, каждый бит исходного числа влияет на каждый следующий разряд результата. Посмотрим на сгенерированный компилятором Rust ассемблер godbolt, здесь можно увидеть, что для деления используются две функции:
__umodti3
__udivti3
Это функции реализованные в рантайме (llvm) для деления 128-битных чисел (обозначения «u» — unsigned, «ti» — 128 bit). И конечно они будут относительно медленными.
Надо облегчить работу процессору. Как вам известно любое число в базе BASE можно представить в виде: HIGH * BASE**R + LOW, например десятичное 1111222 = 1111 * 10**3 + 222, что это нам дает? Разделим обе части на 10**3 целочисленным делением, получаем 1111 = 1111, для остатка от деления будет 222 = 222, таким образом это представление позволяет нам при преобразовании между базами делить не все число, а только его часть. Как вы уже, наверное, догадались мы будет замещать деление 128-битных чисел, делением 64-битных чисел.
Итак для начала нам надо выбрать степень, в которую будем возводить 62, оптимальным будет R, при котором выполняется условие 62**R <= 2**64 < 62**(R+1), вычислить его можно по формуле:
math.floor(math.log(2**64, 62)) # == 10
Теперь напишем новую реализацию на Rust, выглядит она следующим образом:
const BASE62_N: usize = 62;
const BASE62_DIGITS: &[u8; BASE62_N] =
b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const U128_BASE62_ENCODED_LEN: usize = 22;
const BASE62_POW_10: u128 = (BASE62_N as u128).pow(10);
pub fn u128_to_base62(mut n: u128) -> String {
let mut b62_str = vec![b'0'; U128_BASE62_ENCODED_LEN];
// `nlow` будет формировать нижние 10 разрядов в base62
let mut nlow = (n % BASE62_POW_10) as u64;
let mut i = U128_BASE62_ENCODED_LEN;
// преобразуем число в три шага:
// 0000000000001111111111
// + 0022222222220000000000
// + 3300000000000000000000
// = 3322222222221111111111
for _ in 0..2 {
// здесь тот же алгоритм для преобразования числа в новую базу, но теперь с использованием 64-битного деления
for _ in 0..10 {
i -= 1;
let digit_index = (nlow % BASE62_N as u64) as usize;
b62_str[i] = BASE62_DIGITS[digit_index];
nlow /= BASE62_N as u64;
}
// переходим к следующему блоку разрядов
n /= BASE62_POW_10;
nlow = (n % BASE62_POW_10) as u64;
}
// завершаем преобразовние 2 оставшихся разрядов
for _ in 0..2 {
i -= 1;
let digit_index = (nlow % BASE62_N as u64) as usize;
b62_str[i] = BASE62_DIGITS[digit_index];
nlow /= BASE62_N as u64;
}
unsafe { String::from_utf8_unchecked(b62_str) }
}
Смотрим, что в результирующем ассемблере godbolt, теперь, там для 64-битного деления используется инструкция div.
В итоге было __umodti3 x 22, __udivti3 x 22, стало __umodti3 x 3, __udivti3 x 2, div x 44. Вот что показывает бенчмарк: bench_u128_to_base62 1000000: 112.18Mib/s, 7351959.26/s. Ускорение в 3.5 раза!
Готово.
и да я пробовал заменить деление u64, делением u32, значительного прибавления производительности не было, прирост около 2%
