Rust to the rescue (of Ruby)
Fabiano B.
2469

Using another language may solve your problem but it also could introduce new ones: the team must learn how to code in a new language, the codebase may get more complex, the new environment may add complexity to the technology stack, and the list goes on.

I know that, as already mentioned, the fibonacci example is just that: an example used for illustration purposes. Probably the real life problems are much harder than that but as it was used for the demonstration I’d like to also use it to point that the problem was not with ruby or any language in particular. The problem is in the algorithm, that is very naive and __inefficient__. It is inefficient in ruby, it is inefficient in rust and probably will be inefficient in the majority of languages.

Why is this fibonacci implementation inefficient? Because it computes the same thing over and over and over again. Consider calculate the value of fibonacci (5). In this small sample, the fibonacci value for 3, 2, 1 and 0 are __unnecessarily__ calculated respectively 2, 3, 5 and 3 times.

What happens when we calculate the fibonacci series value of 42?

In the hash bellow, the key are the fibonacci sequence number and the value is the number of times it was calculated to determine the fibonacci of 42 using the example implementation:

{
42=>1,
41=>1,
40=>2,
39=>3,
38=>5,
37=>8,
36=>13,
35=>21,
34=>34,
33=>55,
32=>89,
31=>144,
30=>233,
29=>377,
28=>610,
27=>987,
26=>1597,
25=>2584,
24=>4181,
23=>6765,
22=>10946,
21=>17711,
20=>28657,
19=>46368,
18=>75025,
17=>121393,
16=>196418,
15=>317811,
14=>514229,
13=>832040,
12=>1346269,
11=>2178309,
10=>3524578,
9=>5702887,
8=>9227465,
7=>14930352,
6=>24157817,
5=>39088169,
4=>63245986,
3=>102334155,
2=>165580141,
1=>267914296,
0=>165580141
}

Pay close attention to the data. Fibonacci(5) was called ~ 40 million times just to produce the very same result! Fibonacci(1) was calleb about 270 million times just to produce the very same result!

And this is my point. Instead of just learning new languages and technologies, we, programmers, should also invest effort in learn how to improve our abilities to code algorithms.

I’ve executed the same original algorithm in ruby on my machine and got a worst result than reported (probably due to a worse hardware configuration):

60.257010 seconds

But what if I just apply a simple computing algorithm technique called memoization (https://en.wikipedia.org/wiki/Memoization) to my code? The code turns into:

@cache = [0,1]
def fibo(n) return @cache[n] if @cache[n] @cache[n] = fibo(n-1) + fibo(n-2)
end

So, the price to pay is one additional array and the associated additional state stored in it. Are you curious about which results it produces for the very same Fibonacci(42)? Here it goes:

0.000120 seconds.

Yeap. The very same ruby. Just a small modification to the algorithm gave me a performance improvement of 50,214,175% over the old ruby version and it is still much faster than the rust implementation of the very same old algorithm.

This is not a criticism of Rust or any technology in particular. It is just a spotlight on another dimension of the problem that could cause much more impact than the technology choice.

If you want to run the benchmarks in your environments, just check the gist (https://gist.github.com/rpepato/d7fc590dba0d8931f263).