フィボナッチベンチマーク
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には、コンピューターの整数にマップされるいくつかの整数型があります。8ビットで表される符号付き数値用のInt8、32ビットで表される符号付き数値用のInt32、64ビットで表される符号なし数値用のUInt64などです。Crystalにおける整数リテラルのデフォルト型はInt32であるため、その最大値は(2 ** 31) - 1 == 2147483647です。2971215073はこれよりも大きいため、演算はオーバーフローし、負の結果になります。
一方、RubyにはFixnumとBignumの2つの整数型があります（ただし、Ruby 2.4では単一のIntegerクラスに統合されます）。Rubyは、整数が「小さい」（4611686018427387903未満）場合は64ビットで整数表現を試み、ヒープメモリを割り当てないようにし、それよりも大きい整数にはヒープメモリを使用して表現します。整数間の演算を行う場合、Rubyはオーバーフローが発生した場合にBignumを作成して正しい結果を得るようにします。
これで、Rubyが遅い理由が理解できます。Rubyはすべての演算でこのオーバーフローチェックを行う必要があり、最適化を妨げています。一方、CrystalはLLVMにこのコードを非常にうまく最適化させることができ、場合によってはLLVMがコンパイル時に結果を計算できるようにすることもあります。しかし、Crystalは間違った結果を返す可能性がありますが、Rubyは常に正しい結果を返すようにします。
私の意見では、Rubyの哲学は、正しい動作と良好なパフォーマンスのどちらを選ぶべきかの選択肢がある場合、正しい動作を優先することです。この小さな例でそれを見ることができます。
$ irb irb(main):001:0> a = [] => [] irb(main):002:0> a << a => [[...]]
配列を出力する場合、Rubyは同じ配列に到達したことに気づき、[...]を出力して示します。プログラムはハングせず、同じ配列を繰り返し出力しようとはしませんでした。これを実装するために、Rubyは、この配列が出力されていることを覚えておく必要があり、おそらく何らかのハッシュに格納し、この配列内のオブジェクトを出力する際にハッシュのルックアップを実行します。
オブジェクトを検査し、そのオブジェクトが自分自身への参照を持っている場合にも同じことが起こります。
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ではすぐに目に見えませんが、一度発見すると、Matzとそのチームへの深い敬意を持つようになります。
これらの選択はパフォーマンスに影響を与えます。Rubyのようにfibに正しい結果を得させたい場合、パフォーマンスを犠牲にする必要があります。しかし、Crystalはこの決定を行います。大きな数値の数学を行い、常にオーバーフローをチェックすると、プログラムのすべての部分が影響を受けるためです。たとえば、数値を1つ増やす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に深い敬意を感じています。
Rubyと同等のfibのパフォーマンスを向上させることはできますか？試してみましょう。簡単な方法の1つは、再帰的に行うのではなく、反復的な方法を使用することで、あまりにも多くの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は素晴らしいです。正しい結果を得ようと努力し、妥当なパフォーマンスで実現しています。Chapeau!
次に、ベンチマークには注意が必要です。同じアルゴリズムをベンチマークしていることを確認し、可能であれば、言語、コード、フレームワークなど間で時間（またはメモリ使用量）の差がある可能性のある理由を説明してみてください。
第三に、Crystalを使用すると非常に高いパフォーマンスを得ることができますが、プログラマーであるあなたはより多くの作業を行う必要があります。これはRubyとは異なります。しかし、CrystalはRubyが提供するほぼ同じ開発者の満足度を維持しようとします。BigInt.new(1)を書くのは悲しいまたは腹立たしいと感じるかもしれませんが、これはコードを実行して非常に高速に実行されるのを見ることで得られる幸福によって補われます。