Rustc is the official compiler for the Rust programming language. It takes Rust source code as input and produces binary code, either as a library or executable. Rustc is written in Rust itself, and is designed to be fast, efficient, and safe. Having so many responsibilities, it’s no surprise that it has a number of reusable data structures and algorithms under the hood. Today we’re going to take a look at one of them - integer encoding for requested base.
The implementation is clean and easy to understand. At the same time, every time I see reverse call, I start to wonder if it’s really necessary. Let’s see, on each iteration we chop off the last digit of the resulting number and we place it at the `index`th position from left to right. But we already know the size of the buffer, so why don’t we just place this digit into its final position right away?
This way we no longer need the reverse call. We shouldn’t expect huge wins here, since the length of the resulting string is usually fairly small to matter much, but according to
use criterion::{criterion_group, criterion_main, Criterion}; | |
use std::str; | |
pub const MAX_BASE: usize = 64; | |
pub const ALPHANUMERIC_ONLY: usize = 62; | |
pub const CASE_INSENSITIVE: usize = 36; | |
const BASE_64: &[u8; MAX_BASE] = | |
b"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@$"; | |
#[inline] | |
pub fn push_str(mut n: u128, base: usize, output: &mut String) { | |
debug_assert!(base >= 2 && base <= MAX_BASE); | |
let mut s = [0u8; 128]; | |
let mut index = 0; | |
let base = base as u128; | |
loop { | |
s[index] = BASE_64[(n % base) as usize]; | |
index += 1; | |
n /= base; | |
if n == 0 { | |
break; | |
} | |
} | |
s[0..index].reverse(); | |
output.push_str(str::from_utf8(&s[0..index]).unwrap()); | |
} | |
#[inline] | |
pub fn push_str2(mut n: u128, base: usize, output: &mut String) { | |
debug_assert!(base >= 2 && base <= MAX_BASE); | |
let mut s = [0u8; 128]; | |
let mut index = s.len(); | |
let base = base as u128; | |
loop { | |
index -= 1; | |
s[index] = BASE_64[(n % base) as usize]; | |
n /= base; | |
if n == 0 { | |
break; | |
} | |
} | |
output.push_str(str::from_utf8(&s[index..]).unwrap()); | |
} | |
fn bench_push_str(c: &mut Criterion) { | |
let mut group = c.benchmark_group("push_str"); | |
let xs = [0, 1, 35, 36, 37, u64::MAX as u128, u128::MAX]; | |
group.bench_function("old", |b| { | |
b.iter(|| { | |
let mut total = 0; | |
let mut s = String::new(); | |
for base in 2..37 { | |
for n in xs { | |
s.clear(); | |
push_str(n, base, &mut s); | |
total += s.len(); | |
} | |
} | |
total | |
}) | |
}); | |
group.bench_function("new", |b| { | |
b.iter(|| { | |
let mut total = 0; | |
let mut s = String::new(); | |
for base in 2..37 { | |
for n in xs { | |
s.clear(); | |
push_str2(n, base, &mut s); | |
total += s.len(); | |
} | |
} | |
total | |
}) | |
}); | |
group.finish(); | |
} | |
criterion_group!(benches, bench_push_str); | |
criterion_main!(benches); |
this small change even managed to result in a modest win on M1 macbook air:
Running benches/base_n_benchmark.rs (target/release/deps/base_n_benchmark-825fe5895b5c2693)
push_str/old time: [14.180 µs 14.313 µs 14.462 µs]
Performance has improved.
Found 5 outliers among 100 measurements (5.00%)
4 (4.00%) high mild
1 (1.00%) high severe
push_str/new time: [13.741 µs 13.839 µs 13.973 µs]
Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
3 (3.00%) high mild
5 (5.00%) high severe
There is also a chance that at this point you’re using rustc with this change.