Blobs in Games: Rust memory optimization

Thursday, February 06, 2020

One of my goals this year is to learn new things that take more than a few weeks to learn. I've been learning Rust. One of the claims I saw is that Rust's borrow mechanics allow it to optimize better than C++ does. I wanted to see this in action so I ran some simple examples through godbolt. Here's some C++ code that reads from array A and writes to array B:

int test(const int* A, int* B, int i) {
    int x = A[i];
    B[i] = x+1;
    int y = A[i];
    return x+y;
}

This C++ code compiles to assembly, with -O2:

movsx   rdx, edx
lea     rcx, [rdi+rdx*4]
mov     eax, DWORD PTR [rcx]
lea     edi, [rax+1]
mov     DWORD PTR [rsi+rdx*4], edi
add     eax, DWORD PTR [rcx]
ret

Note that it is loading DWORD PTR [rcx] twice and loading DWORD PTR [rsi+…] once. That means it's accessing A[i]'s memory twice and B[i] once. It knows that A hasn't changed and it knows i hasn't changed but it doesn't know that A[i] hasn't changed. It's possible that A and B overlap. That means it has to load A[i] twice, even though it's marked const.

Here's the Rust version:

pub fn test(A: &[i32], B: &mut [i32], i: usize) -> i32 {
    let x = A[i];
    B[i] = x+1;
    let y = A[i];
    return x+y;
}

and the output (some parts omitted):

push    rax
mov     eax, DWORD PTR [rdi + 4*r8]
…
lea     ecx, [rax + 1]
mov     DWORD PTR [rdx + 4*r8], ecx
add     eax, eax
pop     rcx
ret

This code has only two DWORD PTR accesses. It knows that A is a shared reference (so there are no other writers), and B is a mutable reference (so there are no other readers). That means it can conclude that A and B can't overlap. Once it's read A[i] from memory it doesn't have to read it again. Cool!

C (but not C++) has the restrict keyword for this. You can tell the C compiler "trust me, these don't overlap", but C doesn't check. Rust checks this at compile time.

So far I'm enjoying learning Rust. It has many of the things I wanted in a language since the mid-1990s. I don't know if I'll actually use it for a real project, but that's not my goal right now. My goal is to learn some new things that challenge my brain, and Rust is doing that for me.

Labels: rust

– Amit – Thursday, February 06, 2020

4 comments:

Gabriel Ferrer wrote at February 06, 2020 5:37 PM: Hi Amit,

I'm glad to see you are learning Rust! I have become a Rust aficionado over the last few years. I have twice taught Operating Systems in Rust, and I just had my first paper accepted where I implemented the underlying algorithm in Rust. I am trying to find as many ways as possible to use it.

With compiler-guaranteed immunity to race conditions and unwanted mutations, so far for me there has been no going back.

Here's a blog post I wrote about the OS class: OS in Rust
Toby Hutton wrote at February 07, 2020 4:14 PM: I'm curious which C++ compiler you used. I've seen a couple of comparisons recently between the ASM generated by Rust vs C++ and they have neglected to mention that Rust is an LLVM language, and so it's LLVM which is generating the machine code from the IR generated by Rust. So it'd be most interesting to compare Rust and Clang which both use the same LLVM backend.
Amit wrote at February 08, 2020 7:55 PM: @Gabriel: cool! I'll check out the blog post.

@Toby: I had used gcc on godbolt.org but clang produces similar code. I think the extra load is required in C++ because B and A might be pointing to the same array, and then the write to B will affect the read from A.
manki pao wrote at January 12, 2023 9:04 AM: I have twice taught Operating Systems in Rust, and I just had my first paper accepted where I implemented the underlying algorithm in Rust. I am trying to find as many ways as possible to use it.