В процессе работы над своим приложением для заметок, когда я дошел до сохранения данных в базу данных я стал использовать для идентификации записей 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%