#Optimization of u128 to base62 encoding

2 messages · Page 1 of 1 (latest)

pine mist
opaque blaze
#

Nice one! I tried a simple thing to make the loop unroll, but the performance really is all in the div instruction! Good finding. I managed to improve on your code just a tiny bit, getting maybe 5-10% more throughput by replacing your single loop encode into a dual encode step. https://godbolt.org/z/GfeTbYjYP

i -= 2;
let nlow2 = nlow % BASE62_N2;
let nlowhi = nlow2 / (BASE62_N as u64);
let nlowlo = nlow2 % (BASE62_N as u64);
b62_str[i] = BASE62_DIGITS[nlowhi as usize];
b62_str[i + 1] = BASE62_DIGITS[nlowlo as usize];
nlow /= BASE62_N2;

The improvement here comes from removing some dependency chains in the registers which allows the CPU to pipeline the operations more aggresively, even if it's a little bit more work overall

Compiler Explorer - Rust (rustc 1.68.0)

const BASE62_N: usize = 62;
const BASE62_N2: u64 = (BASE62_N as u64).pow(2);
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 b...