В предыдущей статье мы рассмотрели кодирование 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 раз.

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