斐波那契基准测试

2016 年 7 月 15 日

Ary Borenzweig

尝试使用 Crystal 时，编写一些小的基准测试来查看该语言的性能与其他语言相比如何，既令人心动，也很有趣。由于其语法，与 Ruby 进行比较通常是最简单的事情。很多时候，我们甚至可以使用相同的代码。

让我们比较一下斐波那契函数

# 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

让我们比较一下时间。

$ ruby fib.cr
433494437
37.105234
$ crystal fib.cr --release
433494437
00:00:00.9999380

可以看出，Crystal 在性能方面给了我们巨大的提升。太棒了！

但是，以上基准测试存在一个根本问题：我们并没有比较相同的函数，相同的算法。

为了证明这一点，让我们尝试将数字 42 增加到 46，然后再次运行程序。

$ ruby fib.cr
2971215073
260.206918
$ crystal fib.cr --release
-1323752223
00:00:06.8042220

刚刚发生了什么？

事实证明，Crystal 有几种整数类型映射到计算机的整数：Int8 用于用 8 位表示的有符号数字，Int32 用于用 32 位表示的有符号数字，UInt64 用于用 64 位表示的无符号数字，等等。Crystal 中整数文字的默认类型是 Int32，因此其最大值为 (2 ** 31) - 1 == 2147483647。由于 2971215073 大于此值，因此运算会溢出并返回负数结果。

另一方面，Ruby 有两种整数类型：Fixnum 和 Bignum（尽管在 Ruby 2.4 中，它们将被合并到一个名为 Integer 的类中）。Ruby 尝试用 64 位表示“较小”的整数（小于 4611686018427387903），尽量避免分配堆内存，并将在超出此范围的情况下使用堆内存表示整数。在对整数进行运算时，Ruby 将确保在溢出时创建一个 Bignum，以提供正确的结果。

现在我们就可以理解为什么 Ruby 比 Crystal 慢了：它必须对每次运算都进行此溢出检查，从而阻止了一些优化。另一方面，Crystal 可以要求 LLVM 对这段代码进行很好的优化，有时甚至可以让 LLVM 在编译时计算结果。但是，Crystal 可能返回错误的结果，而 Ruby 则确保始终返回正确的结果。

在我看来，Ruby 的理念是，在正确行为和良好的性能之间进行选择时，优先考虑正确行为。我们可以在这个小例子中看到这一点。

$ irb
irb(main):001:0> a = []
=> []
irb(main):002:0> a << a
=> [[...]]

注意，在打印数组时，Ruby 注意到它到达了正在打印的相同数组，因此它打印了 [...] 来表示这一点。程序并没有挂起，而是递归地尝试反复打印同一个数组。为了实现这一点，Ruby 必须记住这个数组正在被打印，可能将其放入一个 Hash 中，并在打印此数组中的对象时执行一个 Hash 查找。

当你检查一个对象，并且该对象对自身有引用时，也会发生同样的事情。

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 ...>>

这些细微之处在 Ruby 中并不立即显现，但一旦你发现了它们，你就会对松本行弘和他的团队产生深深的敬意。

这些选择会对性能产生影响。如果我们希望 Crystal 与 Ruby 一样为 fib 返回正确的结果，我们必须牺牲一些性能。但是，Crystal 这样做的原因是，大数字数学运算以及始终检查溢出会影响程序的每个部分。例如，存在一个 CPU 指令用于将数字加一，而 Crystal 可以利用它。Ruby 可能无法做到这一点，因为它还需要检查溢出。

但是，有一种方法可以在 Crystal 中获得正确的结果，这与其他语言类似：显式地使用大数字。让我们来做一下

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

让我们运行一下

$ crystal fib.cr --release
433494437
00:02:28.8212840

现在我们得到了正确的结果，但是请注意，这比 Ruby 慢了 4~5 倍。为什么？

我不知道答案，但我有一些猜测。也许 Ruby 的 Bignum 实现比我们用于 BigInt 的 LibGMP 库更高效。也许 Ruby 的 GC 比我们当前使用的 GC 更好，它并不精确。也许 Ruby 对这些场景有一些特定的优化。无论如何，我对 Ruby 又产生了一种深深的敬意。

我们能否改进 fib 的性能，使其与 Ruby 的性能相匹配？我们可以尝试一下。一个简单的办法是使用迭代方法，而不是递归方法，以避免创建过多的 BigInt 实例。让我们尝试一下

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

运行它

$ crystal fib.cr --release
433494437
00:00:00.0006460

好多了！而且比 Ruby 快得多。但是，当然，我们在作弊，因为 Ruby 仍然使用旧的、缓慢的算法。因此，为了公平起见，我们必须更新我们的 Ruby 实现。

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

运行它

$ ruby fib.rb
433494437
3.6e-05

在这种情况下，Ruby 仍然比 Crystal 快，这可能是因为在这种情况下没有创建 Bignum。

我们还能做些什么吗？

可以。Crystal 的 BigInt 目前是不可变的，但也许可以将其改为可变的，并在性能对这些操作非常重要，或程序的瓶颈的情况下使用它。让我们重新打开 Crystal 的 BigInt 并进行一些修改。

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

运行它

$ crystal fib.cr --release
433494437
00:00:00.0006910

嗯……变化不大。但是，如果我们尝试使用更大的数字，比如 300_000，这些就是时间

$ ruby fib.rb
# number ommited
1.880515
$ crystal fib.cr --release
# number ommited
00:00:00.7621470

似乎在使用大数字时，并且避免创建多个 BigInt 实例，Crystal 在这种情况下比 Ruby 表现略好。

我们能使 Ruby 更快吗？我不知道。至少 Ruby 的 API 不允许修改 Bignum，因此至少现在还没有办法做到这一点。但是，由于性能已经相当不错了，也许根本不需要改进任何东西。

结论

这篇文章得出了一些结论。

首先，Ruby 太棒了。它努力为您提供正确的结果，并且以合理的性能做到了这一点。太棒了！

其次，要谨慎使用基准测试：确保您正在对相同的算法进行基准测试，并且如果可能，请尝试解释为什么语言、代码、框架等之间可能存在时间（或内存使用）差异。

第三，Crystal 让你可以获得非常高的性能，但它需要你，作为程序员，付出更多的努力。这与 Ruby 的区别。但是，Crystal 试图保持与 Ruby 相同的开发幸福感：它可能会让你在编写 BigInt.new(1) 时感到难过或生气，但当你运行代码并看到它执行得非常快时，这种幸福感会弥补这种负面情绪。