Оптимизируем кодирование 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%