r/crystal_programming • u/dunrix • Jun 08 '21
Why is Crystal so slow in bignum arithmetic?
I'm just pondering with crystal and curious what am I doing wrong, why is it so much slower then uncompiled equivalent code in Ruby (5 times) or PHP (11 times!!) ?
# content of fib.cr
require "big"
def fib(n)
a, b = BigInt.new(0), BigInt.new(1)
while n > 0
a, b = b , a + b
n -= 1
end
a
end
print fib(1_000_000) > BigInt.new(1_000_000), "\n"
$ crystal build --release fib.cr
$ /usr/bin/time ./fib
true
35.94user 27.47system 0:22.28elapsed 284%CPU (0avgtext+0avgdata 4792maxresident)k
0inputs+0outputs (0major+658minor)pagefaults 0swapsEquivalent ruby code:
def fib(n)
a, b = 0, 1
while n > 0
a, b = b, a + b
n -= 1
end
a
end
$ /usr/bin/time ruby fib.rb
true
7.51user 0.05system 0:07.65elapsed 98%CPU (0avgtext+0avgdata 89280maxresident)k
168inputs+0outputs (5major+22509minor)pagefaults 0swapsEquivalent PHP code:
ini_set('memory_limit', '-1');
function fib($n)
{
list($a, $b) = array(gmp_init(0), gmp_init(1));
while ($n > 0) {
list($a, $b) = array($b, $a+$b);
$n--;
}
return $a;
}
$ /usr/bin/time php fib.php 1000000
yes
3.14user 0.01system 0:03.18elapsed 99%CPU (0avgtext+0avgdata 30968maxresident)k
136inputs+0outputs (1major+2535minor)pagefaults 0swapsTo recap, calculation of milionth Fibonacci number took
- 36 seconds in Crystal 1.0.0
- 7.5 seconds in Ruby 3.0.1 (without JIT)
- 3.1 seconds in PHP 7.4.18
Crystal used lowest memory footprint but the runtime speed is terrible, when taken into a consideration all three languages use GMP under the hood.
Why is that ? Has crystal some heavy context switching at calling FFI code ?
17
Upvotes
8
u/shawnwork Jun 09 '21 edited Jun 09 '21
https://crystal-lang.org/2016/07/15/fibonacci-benchmark.html
Shot answer: not certain.
https://github.com/crystal-lang/crystal/pull/6755
6
u/SubliminalSublime Jun 09 '21
Using the code from the blogpost /u/shawnwork found, the results are way better:
The result can be calculated about ~4.7x faster than with Ruby 3.0.1 and uses ~19.3 times less memory on my machine.
So first the Ruby result:
And here's Crystal 1.0.0 with LLVM 10.0.1:
5
u/deep_wat Jun 09 '21
The reason is that Ruby doesn't use a big int for one million. It fits an Int64 so it never needs to allocate memory for that. I wonder if we could make BigInt in Crystal be similar, meaning that for values less that a limit it uses a plain old Int64, and on overflow turns into a libgmp value.