A Smarter Algorithm Beats A Faster Language

I've been tinkering with the Rust language a bit lately. I mainly program in Ruby, and I'd like a way to write tight, fast, "close to the metal" code, but I'm scared of segfaults. Rust has neat ideas built in about ownership of resources, which should prevent problems like "you threw away memory I needed" or "I used memory that should have been yours".

So far, I only know a tiny, tiny bit of Rust, but I decided to try a speed experiment. I wrote a simple fibonacci generator in Rust, wrote the same thing in Ruby, and compared speed.

Here's the Rust code:

#!rust
# fib.rs
fn main() {
    let n: i32 = 42;
    let answer = fib(n);
    println!("fib of {} is {}", n, answer);
}

fn fib(n :i32) -> i32 {
    let answer = if n == 1 {
    0
    } else if n == 2 {
        1
    } else {
        fib(n - 1) + fib(n - 2)
    };
    return answer;
}

The main feature of this program is my ignorance. For example, I hardcoded 42 because I don't yet know how to parse command-line arguments. But it runs.

Here's the Ruby version (written in Rust style, with a 'main' function, for easier comparison):

#!ruby
# fib.rb
def main
  n = 42
  puts "fib of #{n} is #{fib(n)}"
end

def fib(n)
  case n
  when 1 then 0
  when 2 then 1
  else fib(n - 1) + fib(n - 2)
  end
end

main

How do they compare for speed? time ruby fib.rb takes 35.81 seconds of user time. time ./target/debug/fib takes 4.16 seconds. (I tested this with Rust 1.0.0-beta and Ruby 2.1)

Wow! Much faster! So, Rust wins, right?

Well, yes and no. Rust is definitely faster than Ruby. But at this moment, I'm still much better at Ruby than I am at Rust. Which means that in Ruby, I'm confident enough to try a slightly fancier algorithm: adding memoization.

Here's my improved Ruby code.

#!ruby
# memoized_fib.rb
def main
  n = 42
  puts "fib of #{n} is #{fib(n)}"
end

def fib(n)
  @cache ||= {}
  @cache.fetch(n) {
    @cache[n] = calc_fib(n)
  }
end

def calc_fib(n)
  case n
  when 1 then 0
  when 2 then 1
  else fib(n - 1) + fib(n - 2)
  end
end

main

This memoized Ruby code runs in... 0.03 seconds. It turns out that most of the work done by this function was repeated, and that caching the answer for a given run of fib cuts out giant chunks of the call graph.

Again, those results for comparison:

Naive Ruby     - 35.81s
Naive Rust     -  4.16s
Memoized Ruby  -  0.03s

The lesson here is that the fastest code is the code that does the least work. The two naive implementations have the same algorithm, so because Rust doesn't have to do stuff like build objects in memory, it has less work to do and finishes faster. But the smart algorithm in Ruby cuts out much more work by skipping most of the recursion.

(In terms of my Big O Notation analogies, the naive Rust has a shallower slope than the naive Ruby, but the memoized Ruby has a linear shape instead of an exponential one.)

I picture the naive Rust code like a race car, and the memoized Ruby code like a crafty turtle. The race car can drive around the course at high speed, but the crafty turtle plods across a footbridge to the finish line, skipping 100 kilometers of track.

A smart algorithm is faster than a fast language.

Now, when I get smart enough to memoize a Rust function...