Source of slight inefficiency compared to GCC in Ackermann program


#1

I came across this question on Stackoverflow and was curious where Rust is in these benchmarks http://stackoverflow.com/questions/16115815/ackermann-very-inefficient-with-haskell-ghc

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?


#2

Take a look at the asm they give, with the https://rust.godbolt.org/ and https://gcc.godbolt.org/


#3

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


#4

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.


#5

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.


#6

Then you can write a LLVM enhancement request…