なぜ私はRubyが好きか：秘密のアルゴリズム
Crystalの標準ライブラリがRubyにとても似ていることはよく知られていることです。Rubyのライブラリは非常によく設計されたAPIを持っており、使えるものがたくさんあるので、Crystalでも似たようなAPIを持たせるのはどうでしょう？名前や他のものを一から考え直す必要があるのでしょうか？
そういうわけで、数年前からコンパイラに必要なメソッドを追加したり、楽しみだったり完全性を追求するために追加してきました。そうしている間、RubyのパフォーマンスとCrystalを常に比較していました。Crystalは静的に型がつけられコンパイルされ、LLVMの最適化に頼っているため、常に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"）があるので、その10バイトを次の位置にコピー。今、20バイトをコピーした。あと60バイト
- 今、20バイト（"hellohellohellohello"）があるので、それをコピー。今、40バイトをコピーした！あと40バイト
- 次に、40バイトを次の位置にコピー。完了！全部で80バイトをコピーした
全く最適化に見えないかもしれませんね。とにかく最後には80バイトをコピーしますから。しかしながら、単一のmemcpyコールで40バイトをコピーするのは、5バイトをコピーする8回のmemcpyコールよりも効率的です。memcpyはすごくよく最適化されています！どんなトリックを使っているのかはわかりませんが、大量のメモリをすごく速くコピーできます。
もちろん、これは掛け算の数が2の冪乗の場合に素晴らしい働きをします。もしそうでなければ、残りのバイトは単純なアルゴリズムで埋めることができます。
多くのアルゴリズムの本を読んだわけではありませんが、これはよく知られたアルゴリズムかもしれませんね。わかりません。しかし、ここに何かがあります。Rubyではこの最適化が14年前に導入されましたが、Goでは8年前に導入されました。どちらの場合も、最初に使われたアルゴリズムは最も単純なものだったので、少なくともこの最適化がすぐには明らかではないようです。
さらにある！
RubyにはGoにはない別の最適化があります。これはRubyがGoよりも優れていると証明したいわけではなく、ただ単にRubyの標準ライブラリの各メソッドにどれだけの注意が払われているか、そしてこれが全ての言語で行われているわけではないことを示したいだけです。
こんな感じで何かをする場合：
"a" * 100
フルスクリーンモードを終了
Rubyは掛けている文字列が1バイトしか占めていないことに気づきます。その場合には次の最適化を行います：
- 100バイトの新しい文字列を作る
- 元の文字列からの単一バイトでその100バイトを埋めるために
memsetを呼び出す
Rubyに出会う前は主にJavaやC#でコーディングしていました。これらの言語では何らかのコレクションが必要な場合、多くの選択肢があります。Javaを見てみましょう：
これはRustでも同様です：
多くのコレクションタイプがある理由は、それぞれが特定のユースケースで性能が良く、他では悪くなるためです。ユースケースに応じて選ぶべきです。
ですから、要素のコレクションを始める前に、そのコレクションの要素がどのように使われるか、自分や他の人によって考える必要があります！おそらく「これをするけど、これはしないで欲しい、不効率だから」といったドキュメントが必要になるかもしれません。
それでは、Rubyではこれらすべてのコレクションタイプはどこにあるのでしょうか？
すべてを支配する一つのタイプ
Rubylandを何度も訪れた中で、古い字が書かれた古い紙を見つけました。その意味は理解できませんでしたが、foo.rbファイルに内容をコピーしてrubyで実行したら、次のような出力がありました：
Java王たちの豆の下には三つのタイプが、
石の宮殿の中にあるRust領主たちには七つ、
C++を使う運命にある凡人たちには九つ、
輝く玉座にいる幸せな主には一つ
幸福があるRubyの国にて。
すべてを支配する一つのタイプ、それを見つける一つ、
すべてを束ね、歓喜の中にそれらを結びつけるための一つ、
幸福があるRubyの国にて。
Rubyにはこれのためだけの一つのタイプがあります：Array。そして、それは多くのユースケースをカバーする方法で実装されています。要素のコレクションが必要ならば、何を使うか考える必要はありません：答えはArrayを使うことです。ユーザーの生活を単純化するのがRubyのすべてです。
まず、JavaのArrayListのように実装されており、決してLinkedListのようにはなりません。リンクドリストは紙の上では綺麗に見えますが、要素を挿入したい際にはそれぞれのノードに対してメモリを割り当てる必要があるので、とてもコストがかかります。さらにリストを走査するのは素晴らしいとは言えません。なぜならこれらのノードのメモリは散在している可能性があるので、キャッシュを局所的に使うことができません。
あまり技術的になりたくありませんが、Arrayはメモリを割り当てることで実装されています。たとえば初期の容量を10としますが、始めは空です。要素を挿入するたびに、現在のサイズが現在の容量に達していない限り、それを行います。もしそうなら、少し多くのメモリ（たとえば20要素分）を求め、以前のものをこの新しいスペースにコピーし、新しい要素を置きます。
Arrayにはpushやpopのようなメソッドがあり、上記の構造でスタックのように使うことができます。しかし、shiftやunshiftのようなメソッドもあり、キューやデキューとしても使うことができます！通常、要素を配列の最初に挿入するときは、既存の内容を前に移動させてから要素を入れる必要があります。Rubyがここで何をしているのかはわかりませんが、確かにそれはやっていないようです。配列の開始位置がわかるようで、shiftするときはそのポインタを前に移動させるだけなので、非常に効率的です！
Arrayではもっとたくさんの操作ができますし、多すぎてブログ投稿ではカバーしきれませんが、どのように使うにしてもうまくかつ速く動作することが保証されています。
わかりません！この投稿が最後になると思っていましたが、まだRubyについて良いことを言いたいことがたくさんあるので、続きを見てみましょう :-)
こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。
https://dev.to/asterite/why-i-love-ruby-the-secret-algorithms-424d
