Source of slight inefficiency compared to GCC in Ackermann program

I came across this question on Stackoverflow and was curious where Rust is in these benchmarks performance - Ackermann very inefficient with Haskell/GHC - Stack Overflow

The Rust version is as below:

fn ack(m: usize, n: usize) -> usize {
  if m == 0 { n+1 }
  else if n == 0 { ack (m-1, 1) }
  else { ack(m-1, ack(m, n-1)) }

fn main() {
  println!("{}", ack(4,1));

On my computer, the C programs runs in 2.3s with gcc -O2 , 1.9s with gcc -O3, and 3.1s with rustc -O. I use gcc 6.2.0 and rust 1.13.0.

What is it that makes this compiled Rust program slightly slower than C?

Take a look at the asm they give, with the and

1 Like

You should also try the C version with clang, to see if this is just LLVM to blame.


Make sure you compare using the same integer widths. The C program in the linked post uses int, which is usually 32 bits on x64, while usize is 64 bits.


Thanks @cuviper. I tried clang -O3, and the performance was very simular to Rust. So this looks like it's LLVM that can be improved.

Then you can write a LLVM enhancement request...

1 Like