Crystal言語作者がRubyを愛する理由（7）秘密のアルゴリズム（翻訳）
Crystalの標準ライブラリがRubyのそれとほぼ同じに見えるのは秘密でも何でもありません。Rubyの標準ライブラリは実によく設計されていて便利なツールがたくさん詰まっているのですから、Crystalも同じようなAPIにしない理由はありませんし、わざわざ名前を一から考え直す理由もありません。
そこで私たちはこの数年、コンパイラで必要なメソッドを追加したり、楽しみのため、完成度を高めるために必要なメソッドを追加するようになりました。
それと並行して、RubyとCrystalのパフォーマンスを常に比較しています。Crystalは静的に型付けおよびコンパイルされ、LLVM最適化を武器としているので、Crystalは常にRubyよりパフォーマンスがよいだろうと考えたのです。しかし実際には必ずしもそうではありませんでした。
私たちは「この部分がRubyで高速になる理由は何だろう？」と考えを巡らせたものです。Rubyのソースコードを見ると、そこには美しくパフォーマンスの高いコードがぎっしり詰まっていることがわかってきました。そうしたコードはユーザーから見えないよう隠蔽されており、気づく人はほとんどいません。
そこで今回は、そうした部分についていくつかお話ししたいと思います。
文字列や配列の乗算
Rubyでは以下のような書き方が可能です。
"hello" * 3 # => "hellohellohello"
これを最もわかりやすく実装するとしたら以下のような感じになるでしょう。
- この文字列の長さは5バイトである
- この長さに3をかけると15バイトの文字列が必要になる
- この5バイトを何度もコピーすることで3回の反復を行う（
memcpyなどで効率を高められるでしょう）
Crystalの最初の実装はこれでした。しかしRubyの方が高速だったのです。
Rubyはどんなふうにやっているのでしょうか。文字列に16をかける場合、以下のようになります。
- この文字列の長さは5バイトである
- この長さに16をかけると80バイトの文字列が必要になる
- 最初に、元の文字列から5バイトをコピーする: これで残り75バイト（なるほど！）
- 次に、さらに5バイトをコピーする: これで残り70バイト（なるほど！）
- ここまでコピーした10バイト（"hellohello"）を次の位置にコピーする: 20バイトがコピーされ、残り60バイト
- ここまでコピーした20バイト（"hellohellohellohello"）も同様に次の位置にコピーする: 40バイトがコピーされ、残り40バイト
- ここまでコピーした40バイトも同様に次の位置にコピーする: 80バイトコピー完了！
この方法でも最終的にコピーされるのは80バイトなので、何も最適化されていないように見えるかもしれません。しかし、40バイトを1回のmemcpyでコピーする方が、5バイトをmemcpyで8回コピーするよりも効率が高くなります。memcpyは実によく最適化されていて、大きなメモリ範囲を非常に高速にコピーできます（内部の仕掛けはわかりませんが）。
この方法は、乗数が2のべき乗の場合に非常に効果的です。それ以外の場合は、別のもっとシンプルなアルゴリズムで残りを埋めればよいのです。
私はアルゴリズムの本をあまりたくさん読んでいませんが、もしかするとこのアルゴリズムは有名なのでしょうか？しかしここでは確かに何かが行われています。Goがこの最適化を導入したのは8年前ですが（7bcbb65）、Rubyでは14年も前に導入済みです（35cb0f8）。GoもRubyも初期の時代は最も単純なアルゴリズムを使っていたので、少なくとも誰もがすぐに気付くような最適化ではなさそうです。
別の例
RubyにあってGoでは見られなかった最適化がもうひとつあります。ただし、ここでRubyがGoより優れているといったことを証明しようというわけではありません。Rubyの標準ライブラリではメソッドひとつひとつに細やかな心配りがなされていること、そして世の中にあるのはそういう言語ばかりではないということを示したいだけです。
以下のようなコードを書いたとしましょう。
"a" * 100
Rubyは、被乗数の文字列がたった1バイトしかないことを目ざとく見つけます。この場合は以下のように最適化されます。
- サイズが100バイトの新規文字列を作成する
- memsetを呼び出して、この100バイトを元の文字列の1バイトで埋める
配列
Rubyに出会うまでの私は、主にJavaやC#でコーディングしていました。これらの言語で何らかのコレクションが必要になった場合、多くの選択肢があります。Javaの場合は以下が使えます。
Rustにも同じようなコレクションがあります。
コレクションの型がたくさんある理由は、あるコレクションは特定のユースケースでパフォーマンスがよくても別のユースケースでは遅くなることがあるからです。これらのコレクションは、ユースケースに応じて使い分ける必要があります。
つまり、コレクションを使うときは、その要素のコレクションが今後どう使われるかを考え抜いておかなければならないということです。使うのは自分かもしれませんし、他の誰かかもしれません。そして「xxはやってよい、しかしyyは効率が悪いのでやってはいけない」といったAPIドキュメントを書く必要が生じることでしょう。
これらのコレクションは、Rubyではどこにあるのでしょうか？
「1つの型がすべてを統べる」
Ruby世界を何度も旅するうちに、私は古代文字で記されたある古文書を発見しました。そのときの私には意味がわからなかったので、とりあえずfoo.rbファイルに内容を書き写してrubyで実行してみると、こんなものが出力されました。
Three Types for the Java-kings under the beans,
Seven for the Rust-lords in their halls of stone,
Nine for Mortal Men doomed to use C++,
One for the Happy Lord on his shiny throne
In the Land of Ruby where Happiness lies.
One Type to rule them all, One Type to find them,
One Type to bring them all, and in the bliss bind them,
In the Land of Ruby where Hapiness lies.
試訳
3つの型はbeansの下なるJavaの王に
7つの型は石の館なるRustの君主に
9つは死すべき定めのC++使いに
1つは輝かしい玉座におわします果報なる主君に
福徳横たわるRubyの地に
1つの型がすべてを統べ、1つの型がすべてを見つけ
1つの型がすべてを幸福のうちにつなぎとめる
福徳横たわるRubyの地に
Rubyでは、Arrayというただ1つの型をコレクションに使います。RubyのArrayは多くのユースケースをカバーするように実装されており、要素のコレクションが欲しいときには何も考えずにArrayを使えば済むようになっています。ユーザーの生活に面倒を持ち込まないことがRubyのすべてです。
まず、RubyのArrayの実装はJavaのArrayListに似ていますが、決してLinkedListには似ていません。理論書で解説されているリンク付きリストは一見よさげですが、要素を挿入するときにあらゆるノードでメモリを確保しなければならず、コストが非常に高くなります、リストをトラバースすると、ノードがメモリ上で分散している場合にローカルキャッシュが効かなくなるのもよくありません。
技術的な詳細にあまり深入りしたくありませんが、RubyのArrayは最初から一定量のメモリをアロケーションする形で実装されています。初期状態のArrayの容量は、たとえば要素10個分のメモリがアロケーションされる場合でも、中身が空の状態から始まります。ある要素を挿入するときは、現在アロケーション済みのメモリ容量を超えない限り、普通に挿入します。メモリ容量を超えた場合はもう少しメモリを要求し（たとえば要素20個分）、コピー前から存在している要素を新しいメモリにコピーし、それから新しい要素をそこに配置します。
RubyのArrayにはpushやpopといったスタック的に使えるメソッドもあるので、上記のような構造でも簡単に利用できます。さらにshiftやunshiftといったメソッドもあるので、キューイングやキュー取り出しにも使えます。通常、配列の冒頭に要素を挿入する場合は、既存の要素をすべて前方（末尾方向）にシフトして場所を空けてから要素を配置する必要があります。Rubyがこのあたりをどう処理しているのかはわかりませんが、そのような処理方法ではないことは間違いありません。どうやらRubyは配列の開始位置を把握しているらしく、shiftを実行すると単にポインタを前方に移動しているようです。実に効率的です。
Rubyの秘密はまだまだある
Rubyの配列で可能な操作は、この他にもブログ記事で紹介しきれないほどたくさんあり、そうした機能のひとつひとつが注意深く丹念に処理を進めています。そのおかげで、配列では必要なときに必要な方法が利用でき、適切かつ高速に動作することが保証されます。
次回は？
先のことはわかりません。今回で最終回かと思われましたが、Rubyの素晴らしさはまだまだ尽きそうにないので、またの機会にお会いしたいと思います。
概要
原著者の許諾を得て翻訳・公開いたします。