How a Rust upgrade more than tripled the speed of my code
I’d like to share a quick story about the sheer power of LLVM and the benefits of using higher-level languages over assembly.
I work at Parity Technologies, who maintains the Parity Ethereum client. In this client we have a need for performant 256-bit arithmetic, which we have to emulate in software since no modern hardware supports it natively.
For a long time we’ve maintained parallel implementations of arithmetic, one in Rust for stable builds and one in inline assembly (which is automatically used when you compile with the nightly compiler). We do this because we store these 256-bit numbers as arrays of 64-bit numbers and there is no way to multiply two 64-bit numbers to get a more-than-64-bit result in Rust (since Rust’s integer types only go up to u64). This is despite the fact that x86_64 (our main target platform) natively supports 128-bit results of calculations with 64-bit numbers. So, we resort to splitting the 64-bit numbers into two 32-bit numbers (because we can multiply two 32-bit numbers to get a 64-bit result).
impl U256 {
fn full_mul(self, other: Self) -> U512 {
let U256(ref me) = self;
let U256(ref you) = other;
let mut ret = [0u64; U512_SIZE];
for i in 0..U256_SIZE {
let mut carry = 0u64;
// `split` splits a 64-bit number into upper and lower halves
let (b_u, b_l) = split(you[i]);
for j in 0..U256_SIZE {
// This process is so slow that it's faster to check for 0 and skip
// it if possible.
if me[j] != 0 || carry != 0 {
let a = split(me[j]);
// `mul_u32` multiplies a 64-bit number that's been split into
// an `(upper, lower)` pair by a 32-bit number to get a 96-bit
// result. Yes, 96-bit (it returns a `(u32, u64)` pair).
let (c_l, overflow_l) = mul_u32(a, b_l, ret[i + j]);
// Since we have to multiply by a 64-bit number, we have to do
// this twice.
let (c_u, overflow_u) = mul_u32(a, b_u, c_l >> 32);
ret[i + j] = (c_l & 0xffffffff) + (c_u << 32);
// Then we have to do this complex logic to set the result. Gross.
let res = (c_u >> 32) + (overflow_u << 32);
let (res, o1) = res.overflowing_add(overflow_l + carry);
let (res, o2) = res.overflowing_add(ret[i + j + 1]);
ret[i + j + 1] = res;
carry = (o1 | o2) as u64;
}
}
}
U512(ret)
}
}
You don’t even have to understand all of the code to see how non-optimal this is. Inspecting the output of the compiler shows that the generated assembly is extremely suboptimal. It does much more work than necessary essentially just to work around limitations in the Rust language. So we wrote an inline assembly version. The important thing about using inline assembly here is that x86_64 natively supports multiplying two 64-bit values into a 128-bit result. When Rust does a * b when a and b are both u64 the CPU actually multiplies them to create a 128-bit result and then Rust just throws away the upper 64 bits. We want the upper 64 in this case though, and the only way to access it efficiently is by using inline assembly.
As you can imagine, our assembly implementation was much faster:
name u64.bench ns/iter inline_asm.bench ns/iter diff ns/iter diff % speedup
u256_full_mul 243,159 197,396 -45,763 -18.82% x 1.23
u256_mul 268,750 95,843 -172,907 -64.34% x 2.80
u256_mul_small 1,608 789 -819 -50.93% x 2.04
u256_full_mul tests the function above, u256_mul multiplies two 256-bit numbers to get a 256-bit result (in Rust, we just create a 512-bit result and then throw away the top half but in assembly we have a seperate implementation), and u256_mul_small multiplies two small 256-bit numbers. As you can see, the assembly implementation is up to 65% faster. This is way, way better. Unfortunately, it only works on nightly, and even then only on x86_64. The truth is that it was a lot of effort and a number of thrown-away implementations to even get the Rust code to “only” half the speed of the assembly, too. There was simply no good way to give the compiler the information necessary.
All that changed with Rust 1.26. Now we can do a as u128 * b as u128 and the compiler will use x86_64’s native u64-to-u128 multiplication (even though you cast both numbers to u128 it knows that they’re “really” just u64, you just want a u128 result). That means our code now looks like this:
impl U256 {
fn full_mul(self, other: Self) -> U512 {
let U256(ref me) = self;
let U256(ref you) = other;
let mut ret = [0u64; U512_SIZE];
for i in 0..U256_SIZE {
let mut carry = 0u64;
let b = you[i];
for j in 0..U256_SIZE {
let a = me[j];
// This compiles down to just use x86's native 128-bit arithmetic
let (hi, low) = split_u128(a as u128 * b as u128);
let overflow = {
let existing_low = &mut ret[i + j];
let (low, o) = low.overflowing_add(*existing_low);
*existing_low = low;
o
};
carry = {
let existing_hi = &mut ret[i + j + 1];
let hi = hi + overflow as u64;
let (hi, o0) = hi.overflowing_add(carry);
let (hi, o1) = hi.overflowing_add(*existing_hi);
*existing_hi = hi;
(o0 | o1) as u64
}
}
}
U512(ret)
}
}
Although it’s almost certainly not as fast as using the LLVM-native i256 type, the speed is much, much better. Here it is compared to the original Rust implementation:
name u64.bench ns/iter u128.bench ns/iter diff ns/iter diff % speedup
u256_full_mul 243,159 73,416 -169,743 -69.81% x 3.31
u256_mul 268,750 85,797 -182,953 -68.08% x 3.13
u256_mul_small 1,608 558 -1,050 -65.30% x 2.88
Which is great, we now get a speed boost on stable. Since we only compile the binaries for the Parity client on stable the only people who could use the assembly before were those who compiled from source, so this is an improvement for a lot of users. But wait, there’s more! The new compiled code actually manages to beat the assembly implementation by a significant margin, even beating the assembly on the benchmark that multiplies two 256-bit numbers to get a 256-bit result. This is despite the fact that the Rust code still produces a 512-bit result first and then discards the upper half, where the assembly implementation does not:
name inline_asm.bench ns/iter u128.bench ns/iter diff ns/iter diff % speedup
u256_full_mul 197,396 73,416 -123,980 -62.81% x 2.69
u256_mul 95,843 85,797 -10,046 -10.48% x 1.12
u256_mul_small 789 558 -231 -29.28% x 1.41
For the full multiplication that’s an absolutely massive improvement, especially since the original code used highly-optimised assembly incantations from our resident cycle wizard. Here’s where the faint of heart might want to step out for a moment, because I’m about to dive into the generated assembly.
Here’s the hand-written assembly. I’ve presented it without comment because I want to comment the assembly that is actually emitted by the compiler (since, as you’ll see, the asm! macro hides more than you’d expect):
impl U256 {
/// Multiplies two 256-bit integers to produce full 512-bit integer
/// No overflow possible
pub fn full_mul(self, other: U256) -> U512 {
let self_t: &[u64; 4] = &self.0;
let other_t: &[u64; 4] = &other.0;
let mut result: [u64; 8] = unsafe { ::core::mem::uninitialized() };
unsafe {
asm!("
mov $8, %rax
mulq $12
mov %rax, $0
mov %rdx, $1
mov $8, %rax
mulq $13
add %rax, $1
adc $$0, %rdx
mov %rdx, $2
mov $8, %rax
mulq $14
add %rax, $2
adc $$0, %rdx
mov %rdx, $3
mov $8, %rax
mulq $15
add %rax, $3
adc $$0, %rdx
mov %rdx, $4
mov $9, %rax
mulq $12
add %rax, $1
adc %rdx, $2
adc $$0, $3
adc $$0, $4
xor $5, $5
adc $$0, $5
xor $6, $6
adc $$0, $6
xor $7, $7
adc $$0, $7
mov $9, %rax
mulq $13
add %rax, $2
adc %rdx, $3
adc $$0, $4
adc $$0, $5
adc $$0, $6
adc $$0, $7
mov $9, %rax
mulq $14
add %rax, $3
adc %rdx, $4
adc $$0, $5
adc $$0, $6
adc $$0, $7
mov $9, %rax
mulq $15
add %rax, $4
adc %rdx, $5
adc $$0, $6
adc $$0, $7
mov $10, %rax
mulq $12
add %rax, $2
adc %rdx, $3
adc $$0, $4
adc $$0, $5
adc $$0, $6
adc $$0, $7
mov $10, %rax
mulq $13
add %rax, $3
adc %rdx, $4
adc $$0, $5
adc $$0, $6
adc $$0, $7
mov $10, %rax
mulq $14
add %rax, $4
adc %rdx, $5
adc $$0, $6
adc $$0, $7
mov $10, %rax
mulq $15
add %rax, $5
adc %rdx, $6
adc $$0, $7
mov $11, %rax
mulq $12
add %rax, $3
adc %rdx, $4
adc $$0, $5
adc $$0, $6
adc $$0, $7
mov $11, %rax
mulq $13
add %rax, $4
adc %rdx, $5
adc $$0, $6
adc $$0, $7
mov $11, %rax
mulq $14
add %rax, $5
adc %rdx, $6
adc $$0, $7
mov $11, %rax
mulq $15
add %rax, $6
adc %rdx, $7
"
: /* $0 */ "={r8}"(result[0]), /* $1 */ "={r9}"(result[1]), /* $2 */ "={r10}"(result[2]),
/* $3 */ "={r11}"(result[3]), /* $4 */ "={r12}"(result[4]), /* $5 */ "={r13}"(result[5]),
/* $6 */ "={r14}"(result[6]), /* $7 */ "={r15}"(result[7])
: /* $8 */ "m"(self_t[0]), /* $9 */ "m"(self_t[1]), /* $10 */ "m"(self_t[2]),
/* $11 */ "m"(self_t[3]), /* $12 */ "m"(other_t[0]), /* $13 */ "m"(other_t[1]),
/* $14 */ "m"(other_t[2]), /* $15 */ "m"(other_t[3])
: "rax", "rdx"
:
);
}
U512(result)
}
}
And here’s what that generates. I’ve heavily commented it so you can understand what’s going on even if you’ve never touched assembly in your life, but you will need to know basic low-level details like the difference between memory and registers. If you want to get a primer on the structure of a CPU, the Wikipedia article on structure and implementation of CPUs is a good place to start:
bigint::U256::full_mul:
;; Function prelude - this is generated by Rust
pushq %r15
pushq %r14
pushq %r13
pushq %r12
subq $0x40, %rsp
;; Load the input arrays into registers...
movq 0x68(%rsp), %rax
movq 0x70(%rsp), %rcx
movq 0x78(%rsp), %rdx
movq 0x80(%rsp), %rsi
movq 0x88(%rsp), %r8
movq 0x90(%rsp), %r9
movq 0x98(%rsp), %r10
movq 0xa0(%rsp), %r11
;; ...and then immediately back into memory
;; This is done by the Rust compiler. There is a way to avoid
;; this happening but I'll get to that later
;; These four are the first input array
movq %rax, 0x38(%rsp)
movq %rcx, 0x30(%rsp)
movq %rdx, 0x28(%rsp)
movq %rsi, 0x20(%rsp)
;; These four are the output array, which is initialised to be
;; the same as the second input array.
movq %r8, 0x18(%rsp)
movq %r9, 0x10(%rsp)
movq %r10, 0x8(%rsp)
movq %r11, (%rsp)
;; This is the main loop, you'll see the same code repeated many
;; times since it's been unrolled so I won't go over it every time.
;; This takes the form of a loop that looks like:
;;
;; for i in 0..U256_SIZE {
;; for j in 0..U256_SIZE {
;; /* Loop body */
;; }
;; }
;; Load the `0`th element of the input array into the "%rax"
;; register so we can operate on it. The first element is actually
;; already in `%rax` at this point but it gets loaded again anyway.
;; This is because the `asm!` macro is hiding a lot of details, which
;; I'll get to later.
movq 0x38(%rsp), %rax
;; Multiply it with the `0`th element of the output array This operates
;; on memory rather than a register, and so is significantly slower than
;; if the same operation had been done on a register. Again, I'll get to
;; that soon.
mulq 0x18(%rsp)
;; `mulq` multiplies two 64-bit numbers and stores the low and high
;; 64 bits of the result in `%rax` and `%rdx`, respectively. We move
;; the low bits into `%r8` (the lowest 64 bits of the 512-bit result)
;; and the high bits into `%r9` (the second-lowest 64 bits of the
;; result).
movq %rax, %r8
movq %rdx, %r9
;; We do the same for `i = 0, j = 1`
movq 0x38(%rsp), %rax
mulq 0x10(%rsp)
;; Whereas above we moved the values into the output registers, this time
;; we have to add the results to the output.
addq %rax, %r9
;; Here we add 0 because the CPU will use the "carry bit" (whether or not
;; the previous addition overflowed) as an additional input. This is
;; essentially the same as adding 1 to `rdx` if the previous addition
;; overflowed.
adcq $0x0, %rdx
;; Then we move the upper 64 bits of the multiplication (plus the carry bit
;; from the addition) into the third-lowest 64 bits of the output.
movq %rdx, %r10
;; Then we continue for `j = 2` and `j = 3`
movq 0x38(%rsp), %rax
mulq 0x8(%rsp)
addq %rax, %r10
adcq $0x0, %rdx
movq %rdx, %r11
movq 0x38(%rsp), %rax
mulq (%rsp)
addq %rax, %r11
adcq $0x0, %rdx
movq %rdx, %r12
;; Then we do the same for `i = 1`, `i = 2` and `i = 3`
movq 0x30(%rsp), %rax
mulq 0x18(%rsp)
addq %rax, %r9
adcq %rdx, %r10
adcq $0x0, %r11
adcq $0x0, %r12
;; This `xor` just ensures that `%r13` is zeroed. Again, this is
;; non-optimal (we don't need to zero these registers at all) but
;; I'll get to that.
xorq %r13, %r13
adcq $0x0, %r13
xorq %r14, %r14
adcq $0x0, %r14
xorq %r15, %r15
adcq $0x0, %r15
movq 0x30(%rsp), %rax
mulq 0x10(%rsp)
addq %rax, %r10
adcq %rdx, %r11
adcq $0x0, %r12
adcq $0x0, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x30(%rsp), %rax
mulq 0x8(%rsp)
addq %rax, %r11
adcq %rdx, %r12
adcq $0x0, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x30(%rsp), %rax
mulq (%rsp)
addq %rax, %r12
adcq %rdx, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x28(%rsp), %rax
mulq 0x18(%rsp)
addq %rax, %r10
adcq %rdx, %r11
adcq $0x0, %r12
adcq $0x0, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x28(%rsp), %rax
mulq 0x10(%rsp)
addq %rax, %r11
adcq %rdx, %r12
adcq $0x0, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x28(%rsp), %rax
mulq 0x8(%rsp)
addq %rax, %r12
adcq %rdx, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x28(%rsp), %rax
mulq (%rsp)
addq %rax, %r13
adcq %rdx, %r14
adcq $0x0, %r15
movq 0x20(%rsp), %rax
mulq 0x18(%rsp)
addq %rax, %r11
adcq %rdx, %r12
adcq $0x0, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x20(%rsp), %rax
mulq 0x10(%rsp)
addq %rax, %r12
adcq %rdx, %r13
adcq $0x0, %r14
adcq $0x0, %r15
movq 0x20(%rsp), %rax
mulq 0x8(%rsp)
addq %rax, %r13
adcq %rdx, %r14
adcq $0x0, %r15
movq 0x20(%rsp), %rax
mulq (%rsp)
addq %rax, %r14
adcq %rdx, %r15
;; Finally, we move everything out of registers so we can
;; return it on the stack
movq %r8, (%rdi)
movq %r9, 0x8(%rdi)
movq %r10, 0x10(%rdi)
movq %r11, 0x18(%rdi)
movq %r12, 0x20(%rdi)
movq %r13, 0x28(%rdi)
movq %r14, 0x30(%rdi)
movq %r15, 0x38(%rdi)
movq %rdi, %rax
addq $0x40, %rsp
popq %r12
popq %r13
popq %r14
popq %r15
retq
So as you can see from my comments, there are a lot of inefficiencies in this code. We multiply on variables from memory instead of from registers, we do superfluous stores and loads, also the CPU has to do many stores and loads before even getting to the “real” code (the multiply-add loop), which is important because although the CPU can do loads and stores in parallel with calculations, the way that this code is written requires it to wait for everything to be loaded before it starts doing calculations. This is because the asm macro hides a lot of details. Essentially you’re telling the compiler to put the input data wherever it likes, and then to substitute wherever it put the data into your assembly code with string manipulation. The compiler stores everything into registers, but then we instruct it to put the input arrays in memory (with the "m" before the input parameters) so it loads it back into memory again. There are ways that you could write this code to remove the inefficiencies in it, but it is clearly very difficult for even a seasoned professional to write the correct code here. This code is bug-prone - if you hadn’t zeroed the output registers with the series of xor instructions then the code would fail sometimes but not always, with seemingly-random values that depended on the calling function’s internal state. It could probably be sped up by replacing "m" with "r" here (I hadn’t tested that because I only realised that this is a problem while investigating why the old assembly was so much slower in the course of writing this article), but that’s not clear from reading the source code of the program and only someone with quite in-depth knowledge of LLVM’s assembly syntax would realise that when looking at the code.
By comparison, the Rust code that uses u128 is about as say-what-you-mean as you can get. Even if your goal was not optimisation you would probably write something similar to it as the simplest solution to the problem, but the code that LLVM produces is very high-quality. You can see already that it’s not too different to our hand-written code, but it addresses some of the issues (commented below) while also including a couple more optimisations that I wouldn’t have even thought of. I couldn’t find any significant optimisations that it missed.
Here’s the generated assembly:
bigint::U256::full_mul:
;; Function prelude
pushq %rbp
movq %rsp, %rbp
pushq %r15
pushq %r14
pushq %r13
pushq %r12
pushq %rbx
subq $0x48, %rsp
movq 0x10(%rbp), %r11
movq 0x18(%rbp), %rsi
movq %rsi, -0x38(%rbp)
;; I originally thought that this was a missed optimisation,
;; but it actually has to do this (instead of doing
;; `movq 0x30(%rbp), %rax`) because the `%rax` register gets
;; clobbered by the `mulq` below. This means it can multiply
;; the first element of the first array by each of the
;; elements of th without having to reload it from memory
;; like the hand-written assembly does.
movq 0x30(%rbp), %rcx
movq %rcx, %rax
;; LLVM multiplies from a register instead of from memory
mulq %r11
;; LLVM moves `%rdx` (the upper bits) into a register, since
;; we need to operate on it further. It moves `%rax` (the
;; lower bits) directly into memory because we don't need
;; to do any further work on it. This is better than moving
;; in and out of memory like we do in the previous code.
movq %rdx, %r9
movq %rax, -0x70(%rbp)
movq %rcx, %rax
mulq %rsi
movq %rax, %rbx
movq %rdx, %r8
movq 0x20(%rbp), %rsi
movq %rcx, %rax
mulq %rsi
;; LLVM uses `%r13` as an intermediate because it needs this
;; value in `%r13` later to operate on it anyway.
movq %rsi, %r13
movq %r13, -0x40(%rbp)
;; Again, we have to operate on both the low and high bits
;; so LLVM moves them both into registers.
movq %rax, %r10
movq %rdx, %r14
movq 0x28(%rbp), %rdx
movq %rdx, -0x48(%rbp)
movq %rcx, %rax
mulq %rdx
movq %rax, %r12
movq %rdx, -0x58(%rbp)
movq 0x38(%rbp), %r15
movq %r15, %rax
mulq %r11
addq %r9, %rbx
adcq %r8, %r10
;; These two instructions store the flags into the `%rcx`
;; register.
pushfq
popq %rcx
addq %rax, %rbx
movq %rbx, -0x68(%rbp)
adcq %rdx, %r10
;; This stores the flags from the previous calculation into
;; `%r8`.
pushfq
popq %r8
;; LLVM takes the flags back out of `%rcx` and then does an
;; add including the carry flag. This is smart. It means we
;; don't need to do the weird-looking addition of zero since
;; we combine the addition of the carry flag and the addition
;; of the number's components together into one instruction.
;;
;; It's possible that the way LLVM does it is faster on modern
;; processors, but storing this in `%rcx` is unnecessary,
;; because the flags would be at the top of the stack anyway
;; (i.e. you could remove the `popq %rcx` above and this
;; `pushq %rcx` and it would act the same). If it is slower
;; then the difference will be negligible.
pushq %rcx
popfq
adcq %r14, %r12
pushfq
popq %rax
movq %rax, -0x50(%rbp)
movq %r15, %rax
movq -0x38(%rbp), %rsi
mulq %rsi
movq %rdx, %rbx
movq %rax, %r9
addq %r10, %r9
adcq $0x0, %rbx
pushq %r8
popfq
adcq $0x0, %rbx
;; `setb` is used instead of explicitly zeroing registers and
;; then adding the carry bit. `setb` just sets the byte at the
;; given address to 1 if the carry flag is set (since this is
;; basically a `mov` it's faster than zeroing and then adding)
setb -0x29(%rbp)
addq %r12, %rbx
setb %r10b
movq %r15, %rax
mulq %r13
movq %rax, %r12
movq %rdx, %r8
movq 0x40(%rbp), %r14
movq %r14, %rax
mulq %r11
movq %rdx, %r13
movq %rax, %rcx
movq %r14, %rax
mulq %rsi
movq %rdx, %rsi
addq %r9, %rcx
movq %rcx, -0x60(%rbp)
;; This is essentially a hack to add `%r12` and `%rbx` and store
;; the output in `%rcx`. It's one instruction instead of the two
;; that would be otherwise required. `leaq` is the take-address-of
;; instruction, so this line is essentially the same as if you did
;; `&((void*)first)[second]` instead of `first + second` in C. In
;; assembly, though, there are no hacks. Every dirty trick is fair
;; game.
leaq (%r12,%rbx), %rcx
;; The rest of the code doesn't have any new tricks, just the same
;; ones repeated.
adcq %rcx, %r13
pushfq
popq %rcx
addq %rax, %r13
adcq $0x0, %rsi
pushq %rcx
popfq
adcq $0x0, %rsi
setb -0x2a(%rbp)
orb -0x29(%rbp), %r10b
addq %r12, %rbx
movzbl %r10b, %ebx
adcq %r8, %rbx
setb %al
movq -0x50(%rbp), %rcx
pushq %rcx
popfq
adcq -0x58(%rbp), %rbx
setb %r8b
orb %al, %r8b
movq %r15, %rax
mulq -0x48(%rbp)
movq %rdx, %r12
movq %rax, %rcx
addq %rbx, %rcx
movzbl %r8b, %eax
adcq %rax, %r12
addq %rsi, %rcx
setb %r10b
movq %r14, %rax
mulq -0x40(%rbp)
movq %rax, %r8
movq %rdx, %rsi
movq 0x48(%rbp), %r15
movq %r15, %rax
mulq %r11
movq %rdx, %r9
movq %rax, %r11
movq %r15, %rax
mulq -0x38(%rbp)
movq %rdx, %rbx
addq %r13, %r11
leaq (%r8,%rcx), %rdx
adcq %rdx, %r9
pushfq
popq %rdx
addq %rax, %r9
adcq $0x0, %rbx
pushq %rdx
popfq
adcq $0x0, %rbx
setb %r13b
orb -0x2a(%rbp), %r10b
addq %r8, %rcx
movzbl %r10b, %ecx
adcq %rsi, %rcx
setb %al
addq %r12, %rcx
setb %r8b
orb %al, %r8b
movq %r14, %rax
movq -0x48(%rbp), %r14
mulq %r14
movq %rdx, %r10
movq %rax, %rsi
addq %rcx, %rsi
movzbl %r8b, %eax
adcq %rax, %r10
addq %rbx, %rsi
setb %cl
orb %r13b, %cl
movq %r15, %rax
mulq -0x40(%rbp)
movq %rdx, %rbx
movq %rax, %r8
addq %rsi, %r8
movzbl %cl, %eax
adcq %rax, %rbx
setb %al
addq %r10, %rbx
setb %cl
orb %al, %cl
movq %r15, %rax
mulq %r14
addq %rbx, %rax
movzbl %cl, %ecx
adcq %rcx, %rdx
movq -0x70(%rbp), %rcx
movq %rcx, (%rdi)
movq -0x68(%rbp), %rcx
movq %rcx, 0x8(%rdi)
movq -0x60(%rbp), %rcx
movq %rcx, 0x10(%rdi)
movq %r11, 0x18(%rdi)
movq %r9, 0x20(%rdi)
movq %r8, 0x28(%rdi)
movq %rax, 0x30(%rdi)
movq %rdx, 0x38(%rdi)
movq %rdi, %rax
addq $0x48, %rsp
popq %rbx
popq %r12
popq %r13
popq %r14
popq %r15
popq %rbp
retq
Although there are a few more instructions in the LLVM-generated version, the slowest type of instruction (loads and stores) are minimised, it (for the most part) avoids redundant work and it applies many cheeky optimisations on top. The end result is that the code runs significantly faster.
This is not the first time that a carefully-written Rust implementation has outperformed our assembly code - some months ago I rewrote the Rust implementations of addition and subtraction, making them outperform the assembly implementation by 20% and 15%, respectively. Those didn’t require 128-bit arithmetic to beat the assembly (to get the full power of the hardware in Rust you only need u64::checked_add/checked_sub), although who knows - maybe in a future PR we’ll use 128-bit arithmetic and see the speed improve further still.
You can see the code from this PR here and the code from the addition/subtraction PR here. I should note that although the latter PR shows multiplication already outperforming the assembly implementation, this was actually due to a benchmark that mostly multiplied numbers with 0. Whoops. If there’s something we can learn from that, it’s that there can be no informed optimisation without representative benchmarks.
My point is not that we should take what we’ve learnt from the LLVM-generated code and write a new version of our hand-rolled assembly. The point is that optimising compilers are really good. There are very smart people working on them and computers are really good at this kind of optimisation problem (in the mathematic sense) in a way that humans find quite difficult. It’s the job of language designers to give us the tools we need to inform the optimiser as best we can as to what our true intent is, and larger integer sizes are another step towards that. Rust has done a great job of allowing programmers to write programs that are easily understandable by humans and compilers alike, and it’s just that power that has largely driven its success.