#Why my algorithm 4x faster (it is not, bug in bench) in Zig compared to Rust?

1 messages · Page 1 of 1 (latest)

thin bear
#

I've wrote algorithm for converting u128 into base62, and testing it. It has two versions naive and hand optimized.

naive version have same performance in Zig and Rust:

Rust

bench_u128_to_base62_naive 1000000: 32.86Mib/s, 2153250.28/s

Zig

bench_u128_to_base62_naive 1000000: 34.05Mb/s, 2231504.73/s

But with optimized version something interesting happening (both release builds):

Rust

bench_u128_to_base62 1000000: 111.97Mb/s, 7338325.18/s

Zig

bench_u128_to_base62 1000000: 491.03Mb/s, 32179951.21/s

Zig code is 4x faster compared to Rust, how is it possible? Both using llvm, does Zig using some better defaults or something? How can I investigate, only looking at generated assembler?

neat cairn
#

You probably implemented it with different performance characteristics

#

E.g., maybe you implicitly used a different allocation scheme, memory access pattern, or whatever else

thin bear
#

@neat cairn both implementations are almost same line by line, and don't do any allocations, function signature u128_to_base62(n: u128) [22]u8, I do have memory allocations in benchmark, but removing it makes Rust just a bit faster 130Mb/s
My initial plan was to try Zig's vectors, to try vectorize algorithm, will write here on results when finish, interesting how it will affect performance

neat cairn
#

Would have to see the actual impls to judge

#

There's no concrete answer to this question without seeing the actual code

#

There's probably some gap in understanding or misconception on your part that would cause you to believe two semantically different programs are equivalent

#

There's no magic, just computer subtlety

#

Probably the main advantage zig has here is that it caters to making it easier to write more performant code, because where rust hides complexity through abstraction, zig lays it bare

#

If they really are absolutely equivalent, the only thing that could maybe stand out to me is that maybe zig just happens to optimize u128 code better

thin bear
#

@neat cairn there is almost no u128 math left, it was optimized by hand, it mostly u64 math

#

Here is my code I was testing (with benchmark code):

Rust (run with --release flag)

const BASE62_N: usize = 62;
const BASE62_DIGITS: &[u8; BASE62_N] =
    b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
// digit count for base62 representation of u128, equal to:
//     ceil(16 * log(256) / log(62))
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];
    let mut nlow = (n % BASE62_POW_10) as u64;
    let mut i = U128_BASE62_ENCODED_LEN;
    for _ in 0..2 {
        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;
    }
    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) }
}

pub fn bench_u128_to_base62() {
    let count = 1000000;
    let mut numbers: Vec<u128> = vec![0; count];
    let step = u128::MAX / (count as u128 + 1);
    for (i, n) in numbers.iter_mut().enumerate() {
        *n = i as u128 * step;
    }
    let mut b62_strings = vec![];
    let a = Instant::now();
    for b in numbers {
        b62_strings.push(u128_to_base62(b));
    }
    let t = Instant::now() - a;
    println!(
        "{}, {}",
        b62_strings.first().unwrap(),
        b62_strings.last().unwrap()
    );
    println!(
        "bench_u128_to_base62 {count}: {:.2}Mb/s, {:.2}/s",
        count as f64 * 16.0 / 1024.0 / 1024.0 / t.as_secs_f64(),
        count as f64 / t.as_secs_f64()
    );
    _ = b62_strings;
}
#

Zig (run with -O ReleaseSafe)

const std = @import("std");
const math = std.math;

const BASE62_N: usize = 62;
const BASE62_DIGITS =
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const U128_BASE62_ENCODED_LEN: usize = 22;
const BASE62_POW_10: u128 = math.powi(u128, BASE62_N, 10) catch unreachable;

pub fn u128_to_base62(number_to_encode: u128) [U128_BASE62_ENCODED_LEN]u8 {
    // function arguments in zig is constants
    var n = number_to_encode;
    // no need to init, will be filled
    var b62_str: [U128_BASE62_ENCODED_LEN]u8 = undefined;
    var nlow = @intCast(u64, n % BASE62_POW_10);
    var i = U128_BASE62_ENCODED_LEN;
    for (0..2) |_| {
        for (0..10) |_| {
            i -= 1;
            const digit_index = nlow % BASE62_N;
            b62_str[i] = BASE62_DIGITS[digit_index];
            nlow /= BASE62_N;
        }
        n /= BASE62_POW_10;
        nlow = @intCast(u64, n % BASE62_POW_10);
    }
    for (0..2) |_| {
        i -= 1;
        const digit_index = nlow % BASE62_N;
        b62_str[i] = BASE62_DIGITS[digit_index];
        nlow /= BASE62_N;
    }
    return b62_str;
}
# 
fn bench_u128_to_base62(a: Allocator) !void {
    const count = 1000000;
    const count_f64: f64 = @intToFloat(f64, count);
    const step = std.math.maxInt(u128) / (count + 1);
    var numbers: [count]u128 = undefined;
    for (&numbers, 0..) |*n, i| {
        n.* = @as(u128, i) * step;
    }
    var b62_strings = std.ArrayList([22]u8).init(a);
    defer b62_strings.deinit();
    const start = try std.time.Instant.now();
    for (&numbers) |*n| {
        try b62_strings.append(base62.u128_to_base62(n.*));
    }
    const t: f64 = @intToFloat(f64, (try std.time.Instant.now()).since(start)) / 10e9;
    var s: u128 = 0;
    for (b62_strings.items) |*it| {
        // count sum to prevent compiler optimizations
        s += it[0];
    }
    try stdout.print("first {s}, last {s}, count {d}, s {d}\n", .{ b62_strings.items[0], b62_strings.getLast(), b62_strings.items.len, s });
    try stdout.print("bench_u128_to_base62 {}: {d:.2}Mb/s, {d:.2}/s\n", .{ count, count_f64 * 16.0 / 1024.0 / 1024.0 / t, count_f64 / t });
}
neat cairn
#

Isn't String allocating?

thin bear
#

hm, yes

neat cairn
#

Zig [n]u8 is just a value on the stack, rust's String is basically a heap-allocated vector of bytes verified to be UTF-8

#

You've elided the UTF-8 check, but not the allocation

#

Maybe try returning a [u8; N] in rust as well

#

Then it would be a fair comparison

thin bear
#

ok, let me test

neat cairn
#

But yeah, this is what I mean about zig making complexity lay bare. In rust you wouldn't think twice about using String, which allocates implicitly

#

Whilst in zig, you will, because allocating requires you to pass in an allocator and contemplate the allocation scheme

#

(and also there's no default string type in zig lol)

thin bear
#

@neat cairn a bit faster (+27%) but nowhere close to Zig result:

bench_u128_to_base62_no_alloc 1000000: 142.17Mb/s, 9317312.85/s
neat cairn
#

You also removed the usage of vec!, aye?

thin bear
#

@neat cairn yes, here is Rust full code:

pub fn u128_to_base62_no_alloc(mut n: u128) -> [u8; U128_BASE62_ENCODED_LEN] {
    // zero padded result string
    let mut b62_str = [b'0'; U128_BASE62_ENCODED_LEN];
    let mut nlow = (n % BASE62_POW_10) as u64;
    let mut i = U128_BASE62_ENCODED_LEN;
    for _ in 0..2 {
        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;
    }
    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;
    }
    b62_str
}
neat cairn
#

Maybe it's because zig version has fewer bounds checks, since you're doing b62_str[i] in rust, but capturing with for in zig, eliding the bounds check

#

Just a guess

thin bear
#

I was testing with get_unchecked which skips bounds checks, it gives some boost, but insignificant
was thinking it may be bug in my benchmark code, but can't find so far, both produce same results, looks like everything correct, functions tested too

neat cairn
#

It's probably some small thing like some weird difference in how the IO is being managed, or maybe zig eliding more checks than rust wrt to getLast() vs last().unwrap()

#

Or maybe the allocator you're using in zig is more friendly to the benchmark's allocation scheme than rusts default global allocator is

fallow sphinx
#

Have you tried to profile it?

neat cairn
#

Yeah, that would be the next logical step

thin bear
#

here is what profiler shows, udivti3/umodti3 - is u128 division functions defined in llvm, in both it called same amount of times

bench.png
neat cairn
#

It looks like overall there's less overhead in the zig version in a variety of things, whereas in rust while it's mostly spending time on the udivmod, it's also spending >1% in a bunch of other functions (notice in zig it spends <1% in everything else)

#

Probably the extra bits of overhead come from how the benchmark is done

#

It seems to be doing a bunch of dll lookup?

little steeple
#

Plot twist: Zig is actually 2.5× slower. You screwed up the time unit conversion:

const t: f64 = @intToFloat(f64, (try std.time.Instant.now()).since(start)) / 10e9;

10e9 is not 10⁹ instead it's 10·10⁹ = 10¹⁰

neat cairn
#

Aha, lol

modern cosmos
#

alright new question then: why is zig slower

neat cairn
#

Probably because of using general-purpose allocator

#

It's pretty unoptimized

#

Using std.heap.c_allocator should produce near identical results

#

(since that's also what rust is using I think)

little steeple
neat cairn
#

Not necessarily

thin bear
#

@little steeple wow lol, my bad 😅

neat cairn
#

At any rate, as pointed out, it's from LLVM, so should be identic in both

#

Would be interested also to see the benchmark for zig in ReleaseFast

#

Zig may be eliding fewer safety checks in safe release

fallow sphinx
#

Looks like safety checks are off anyway

#

Interesting stuff, I wonder how Rust managed to be this much faster with same backend

thin bear
#

profiler shows "ir per call" higher for zig

ir.png
fallow sphinx
#

maybe zig uses bigInts to implement u128?

#

I have no idea why those are so different

thin bear
#

Why my algorithm 4x faster in Zig compared to Rust?

#

Why my algorithm 4x faster in Zig compared to Rust?

thin bear
#

Why my algorithm 4x faster (it is not, bug in bench) in Zig compared to Rust?

modern cosmos
#

@thin bear whats the actual speed comparison

#

im on the edge of my seat here. rust v zig comparison???

thin bear
#

@modern cosmos hehe, I'm changing benchmark code, in order to avoid allocations, Zig happens to be slower, as far as I can see because of slow implementations of udivti3/umodti3 functions, will post actual numbers later after benchmark fixes

steel thorn
#

this is a really interesting thread!

#

good to know re: the general purpose allocator slowness. I was benching some code that I ported from javascript, and zig in release fast mode was 3.5X faster. But I'm using the gpa in several places. Would be really interesting to re-bench with the c_allocator

#

I was really surprised that my app which is totally cpu bound was only 3.5X faster vs javascript. Was expecting at least one order of magnitude higher. perhaps the gpa is the reason

quick moon
thin bear
#

Behold! The Numbers!
I removed allocation code from benchmarking part, and after fixing benchmark time conversion, here is results:

Zig
 ❯ zig run src/main.zig -O ReleaseSafe
bench_u128_to_base62_naive 1000000: 3.45Mib/s, 225813.33/s
bench_u128_to_base62 1000000: 57.47Mib/s, 3766656.60/s
 ❯ zig run src/main.zig -O ReleaseFast
bench_u128_to_base62_naive 1000000: 5.18Mib/s, 339277.65/s
bench_u128_to_base62 1000000: 53.72Mib/s, 3520329.95/s


Rust
 ❯ cargo run --release
bench_u128_to_base62_naive 1000000: 35.04Mib/s, 2296614.54/s
bench_u128_to_base62 1000000: 145.12Mib/s, 9510607.44/s

as far as I understand from profiler, Zig is slower because it uses slower implementations of udivti3/umodti3 functions
if you want to have a look at code here it is https://gist.github.com/rsk700/07c1cb0468bda9bd7c6f4584a139aea8

Gist
benchmarking u128 -> base62 encoder

benchmarking u128 -> base62 encoder. GitHub Gist: instantly share code, notes, and snippets.

quick moon
#

Looks like both udivti3 and umodti3 use the same procedure udivmod, which is the common bottleneck

#

The function does look pretty complex tbh

thin bear
quick moon
#

hm the examples it shows are very short, the zig implementation has a lot of branching

thin bear
daring lodge
#

I'll make a tracking issue later for performance improvements.

#

in 12h or so on 22:00 20230612 CET.

verbal nebula