Fibonacci benchmark
When trying out Crystal it’s tempting, and very fun, to write small benchmarks to see how the language’s performance compares to other languages. Because of its syntax, comparing with Ruby is usually the simplest thing to do. Many times we can even use the same code.
Let’s compare the fibonacci function:
# fib.cr
def fib(n)
if n <= 1
1
else
fib(n - 1) + fib(n - 2)
end
end
time = Time.now
puts fib(42)
puts Time.now - time
Let’s compare the times.
$ ruby fib.cr 433494437 37.105234 $ crystal fib.cr --release 433494437 00:00:00.9999380
As can be seen, Crystal is giving us a huge increase in performance. Nice!
However, there’s a fundamental problem in the above benchmark: we aren’t comparing the same function, the same algorithm.
To see that this is true, let’s try increasing the number 42 to 46 and run the programs again:
$ ruby fib.cr 2971215073 260.206918 $ crystal fib.cr --release -1323752223 00:00:06.8042220
What did just happen?
It turns out Crystal has several integer types that map to a computer’s integers:
Int8 for signed numbers represented with 8 bits, Int32 for signed numbers represented
with 32 bits, UInt64 for unsigned numbers represented with 64 bits and so on. The
default type of an integer literal in Crystal is Int32, so its maximum value is
(2 ** 31) - 1 == 2147483647. Because 2971215073 is bigger than this, the operation
overflows and gives a negative result.
Ruby, on the other hand, has two integer types: Fixnum and Bignum (although in Ruby 2.4 they will be unified in a single Integer class). Ruby tries to represent integers with 64 bits if the are “small” (less than 4611686018427387903), trying not to allocate heap memory, and will use heap memory to represent integers larger than that. When doing operations between integers, Ruby will make sure to create a Bignum in case of overflow, to give a correct result.
Now we can understand why Ruby is slower: it has to do this overflow check on every operation, preventing some optimizations. Crystal, on the other hand, can ask LLVM to optimize this code very well, sometimes even letting LLVM compute the result at compile time. However, Crystal might give incorrect results, while Ruby makes sure to always give the correct result.
In my opinion, Ruby’s philosophy is, whenever there’s a choice between correct behavior and good performance, to favor correct behaviour. One can see this in this small example:
$ irb irb(main):001:0> a = [] => [] irb(main):002:0> a << a => [[...]]
Note that when printing an array, Ruby notices that it reached the same array it was printing,
so it printed [...] to show this. The program didn’t hang up, recurisvely trying to print the
same array over and over. To implement this, Ruby has to remember that this Array is being printed,
probably putting it in a Hash of some sort, and when printing an object inside this Array a hash
lookup is performed.
The same happens when you inspect an object, and the object has a reference to itself:
irb(main):001:0> class Foo irb(main):002:1> def initialize irb(main):003:2> @self = self irb(main):004:2> end irb(main):005:1> end => :initialize irb(main):006:0> Foo.new => #<Foo:0x007fc7429bbe30 @self=#<Foo:0x007fc7429bbe30 ...>>
These subtleties aren’t immediately visible in Ruby, but once you discover them they make you have a profound respect for Matz and his team.
These choices have an impact on performance, though. If we’d like Crystal to give the correct
result to fib, like in Ruby, we would have to sacrifice some performance. However, Crystal
makes this decision because doing big numbers math, and checking overflows all the time,
affects every part of a program. For example, there’s a CPU instruction to increment a number
by one, and Crystal can take advantage of it. Ruby probably can’t, because it also needs
to check for overflow.
There is, however, a way to get the correct result in Crystal, and this is similar to other languages: explicitly use big numbers. Let’s do it:
require "big"
def fib(n)
if n <= 1
BigInt.new(1)
else
fib(n - 1) + fib(n - 2)
end
end
time = Time.now
puts fib(BigInt.new(42))
puts Time.now - time
Let’s run it:
$ crystal fib.cr --release 433494437 00:02:28.8212840
Now we get the correct result, but note that this is about 4~5 times slower than Ruby. Why?
I don’t know the answer, but I have some guesses. Maybe Ruby’s Bignum implementation is more efficient than LibGMP, the library we are using for BigInt. Maybe Ruby’s GC is better than the GC we are currently using, which isn’t precise. Maybe Ruby has some specific optimizations for these scenarios. In any case, I feel a profound respect for Ruby, again.
Can we improve the performance of fib to match that of Ruby? We can try. One simple
thing is to use an iterative method, instead of doing it recursively, to avoid
creating too many BigInt instances. Let’s try:
require "big"
def fib(n)
a = BigInt.new(1)
b = BigInt.new(1)
n.times do
a += b
a, b = b, a
end
a
end
time = Time.now
puts fib(42)
puts Time.now - time
Running it:
$ crystal fib.cr --release 433494437 00:00:00.0006460
Much better! And way faster than Ruby. But, of course, we are cheating because Ruby still uses the old, slow algorithm. So to be fair, we must update our Ruby implementation:
def fib(n)
a = 1
b = 1
n.times do
a += b
a, b = b, a
end
a
end
time = Time.now
puts fib(42)
puts Time.now - time
Running it:
$ ruby fib.rb 433494437 3.6e-05
Ruby is still faster than Crystal in this case, maybe because no Bignum was created in this case.
Is there something else we can do?
Yes. Crystal’s BigInt is currently immutable, but maybe it could be changed to be mutable,
and be used like this for scenarios where performance of these operations is super important,
or a bottleneck in the program. Let’s reopen Crystal’s BigInt and make some changes:
require "big"
struct BigInt
def add!(other : BigInt) : BigInt
LibGMP.add(self, self, other)
self
end
end
def fib(n)
a = BigInt.new(1)
b = BigInt.new(1)
n.times do
a.add!(b)
a, b = b, a
end
a
end
time = Time.now
puts fib(42)
puts Time.now - time
Running it:
$ crystal fib.cr --release 433494437 00:00:00.0006910
Hmmm… it didn’t change much. But if we try with a bigger number, say 300_000, these are the times:
$ ruby fib.rb # number ommited 1.880515 $ crystal fib.cr --release # number ommited 00:00:00.7621470
It seems that with big numbers, and avoiding creating multiple BigInt instance, Crystal performs a bit better than Ruby in this case.
Can we make Ruby faster? I don’t know. At least Ruby’s API doesn’t allow mutating a Bignum, so at least now there’s nothing that can be done. But since the performance is already quite good, maybe there’s no need to improve anything in the first place.
Conclusion
There are several conclusions to this blog post.
First, Ruby is just awesome. It strives to give you correct results, and it does so with a reasonable performance. Chapeau!
Second, be careful with benchmarks: make sure you are benchmarking the same algorithm, and, if possible, try to explain why there’s a possible difference in times (or memory usage) between languages, codes, frameworks, etc.
Third, Crystal lets you be very performant, but it requires more work from you, the programmer.
This is a difference from Ruby. However, Crystal tries to keep almost the same developer happiness
that Ruby gives you: it might make you feel sad or angry writing BigInt.new(1), but this is
compensated with the happiness you get when you run your code and see it executes very fast.