内部構造
Crystalがあなたのコードをどのように扱うか、つまりメモリ内で型をどのように表現し、実行時にどのようにメソッドルックアップを行い、どのようにメソッドディスパッチを行うかについて説明しましょう。プログラミング言語を使用する際には、コードを最も効率的な方法で構成し、コードがどのように変換されるかを正確に理解するために、これを知っておくと常に役立ちます。
メモリ内での型の表現方法
型の表現について説明するために、CおよびLLVM IRコードを使用しますので、リファレンスを確認してください。
Crystalには、組み込み型、ユーザー定義型、およびユニオンがあります。
組み込み型
これらは、Nil、Bool、Char、およびさまざまな数値型（Int32、Float64など）、Symbol、Pointer、Tuple、StaticArray、Enum、Proc、およびClassです。
Boolがどのように表現されるかを見てみましょう。このために、この小さなプログラムを書いてみましょう。
# test.cr
x = true
生成されたLLVMを見るには、次のコマンドを使用できます。
crystal build test.cr --emit llvm-ir --prelude=empty
--emit llvm-irフラグは、コンパイラに結果のLLVM IRコードをtest.llファイルにダンプするように指示します。--prelude=emptyは、コンパイラにデフォルトのpreludeファイルを使用しないように指示します。これは、たとえば、GCを初期化します。
このようにして、私たちが書いたコードだけを含む、非常にシンプルでクリーンなLLVM IRコードファイルを取得できます。
; ModuleID = 'main_module'
%String = type { i32, i32, i32, i8 }
@symbol_table = global [0 x %String*] zeroinitializer
define i1 @__crystal_main(i32 %argc, i8** %argv) {
alloca:
%x = alloca i1
br label %entry
entry: ; preds = %alloca
store i1 true, i1* %x
ret i1 true
}
declare i32 @printf(i8*, ...)
define i32 @main(i32 %argc, i8** %argv) {
entry:
%0 = call i1 @__crystal_main(i32 %argc, i8** %argv)
ret i32 0
}
要点は__crystal_mainにあります。コンパイラがx用のi1をスタックに割り当て、そこにtrueを格納していることがわかります。つまり、コンパイラはBoolを単一のビットとして表します。これは非常に効率的です。
整数でも同じことをしてみましょう。
x = 1
今回はxに対して、次を取得します。
%x = alloca i32
LLVMでは、i32は32ビットで表現される整数です。これもまた非常に効率的であり、Int32の表現として期待されるものです。
つまり、Crystalはオブジェクト指向であり、Int32はオブジェクトのように動作しますが（メソッドがあります）、その内部表現は可能な限り効率的です。
シンボル
次にSymbolを見てみましょう。
x = :one
y = :two
今回は完全なLLVM IRコードを見てみましょう。
; ModuleID = 'main_module'
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-darwin14.1.0"
%String = type { i32, i32, i32, i8 }
@one = private constant { i32, i32, i32, [4 x i8] } { i32 1, i32 3, i32 3, [4 x i8] c"one\00" }
@two = private constant { i32, i32, i32, [4 x i8] } { i32 1, i32 3, i32 3, [4 x i8] c"two\00" }
@symbol_table = global [2 x %String*] [%String* bitcast ({ i32, i32, i32, [4 x i8] }* @one to %String*), %String* bitcast ({ i32, i32, i32, [4 x i8] }* @two to %String*)]
define internal i32 @__crystal_main(i32 %argc, i8** %argv) {
alloca:
%x = alloca i32
%y = alloca i32
br label %entry
entry: ; preds = %alloca
store i32 0, i32* %x
store i32 1, i32* %y
ret i32 1
}
declare i32 @printf(i8*, ...)
define i32 @main(i32 %argc, i8** %argv) {
entry:
%0 = call i32 @__crystal_main(i32 %argc, i8** %argv)
ret i32 0
}
ここで重要なことが3つあります。まず、Symbolがi32、つまり4バイトで表現されていることがわかります。次に、xに値0が割り当てられ、yに値1が割り当てられていることがわかります。3つ目に、上部にいくつかの定数、hello、bye、およびsymbol_tableが見られます。
基本的に、CrystalのSymbolは、一意の番号に割り当てられた名前にすぎません。Symbolは動的に作成することはできず（String#to_symはありません）、作成する唯一の方法はそのリテラル値を使用することであるため、コンパイラはプログラム全体で使用されるすべてのシンボルを知ることができます。コンパイラはそれらにゼロから始まる番号を割り当て、また、それらの番号を文字列にマッピングするテーブルを作成して、Symbol#to_sを非常に効率的な方法で実装できるようにします。これにより、シンボルは、マジックナンバーを使用するようなものですが、代わりに名前を使用するため、小さな定数のグループに使用するのに非常に魅力的になります。
ポインタ
ポインタは、メモリ位置への型付きポインタを表すジェネリック型です。例えば
x = Pointer(Int32).malloc(1_u64)
x.value = 1
x.value #=> 1
生成されたLLVM IRコードを見ると、たくさんのコードが表示されます。まず、xは次のように表されます。
%x = alloca i32*
繰り返しますが、これはあるべき姿であり、int32へのポインタにすぎません。次に、malloc（通常のpreludeを使用してGCからメモリを要求します）とmemsetを呼び出してメモリをクリアし、次にそのメモリアドレスに1を割り当てる命令が表示されます。これはこのブログ記事の主題にとってそれほど重要ではないため、スキップしますが、生成されたコードがCで生成されるコードと非常に似ていることを知っておくことが重要です。
タプル
タプルは、固定サイズで変更不可能な値のシーケンスであり、各位置の型はコンパイル時にわかっています。
x = {1, true}
上記のLLVM IRコードの一部は次のとおりです。
%"{Int32, Bool}" = type { i32, i1 }
...
%x = alloca %"{Int32, Bool}"
ご覧のとおり、タプルは、値を順番にパックするだけのLLVM構造体として表現されています。タプルのこの表現により、たとえば、Int32を次のようにバイトに分解できます。
x = 1234
ptr = pointerof(x) as {UInt8, UInt8, UInt8, UInt8}*
puts ptr.value #=> {21, 205, 91, 7}
StaticArray
StaticArrayは、同じ型の値の固定サイズで変更可能なシーケンスであり、スタックに割り当てられ、値によって渡されます。preludeにはそれらを作成する安全な方法が含まれていますが、ここでは最小限のpreludeを使用しているため、それらを作成する安全でない方法（ガベージを含むデータに初期化されます）は次のとおりです。
x = uninitialized Int32[8]
そのLLVM表現
%x = alloca [8 x i32]
この型は、IOバッファーなどで主に使用され、それほど使用されていないため、これ以上説明しません。他のすべての操作にはArrayが推奨される型です。
Enum
ここに列挙型があります。
enum Color
Red
Green
Blue
end
x = Color::Green
列挙型は、ある意味では、シンボルに似ています。つまり、コードでマジックナンバーの代わりに名前を使用できるように、名前に関連付けられた数値です。予想どおり、列挙型はi32、つまり4バイトで表されます。ただし、宣言で別の指定がない限りは。
enum Color : UInt8
Red
Green
Blue
end
列挙型の良いところは、それらを出力すると、値ではなく名前が表示されることです。
puts Color::Green #=> Green
これは、シンボルとは異なる方法で、コンパイル時のリフレクションとマクロを使用して行われます。しかし、基本的に、列挙型のto_sメソッドは、必要な場合にのみ生成されます。しかし、列挙型はメモリと速度の面で効率的であり、快適に使用でき、デバッグにも役立つ（たとえば、それらを出力すると数値ではなく名前が表示される）のは良いことです。
Proc
Procは、オプションのクロージャデータ情報を持つ関数ポインタです。例えば
f = ->(x : Int32) { x + 1 }
これは、Int32を受け取り、Int32を返す関数ポインタです。ローカル変数をキャプチャしないため、クロージャではありません。しかし、コンパイラはそれでもこのように表します。
%"->" = type { i8*, i8* }
つまり、ポインタのペアです。1つは実際の関数へのポインタを含み、もう1つはクロージャされたデータへのポインタを含みます。
上記のLLVM IRコードは次のとおりです。
; ModuleID = 'main_module'
%String = type { i32, i32, i32, i8 }
%"->" = type { i8*, i8* }
@symbol_table = global [0 x %String*] zeroinitializer
define %"->" @__crystal_main(i32 %argc, i8** %argv) {
alloca:
%f = alloca %"->"
%0 = alloca %"->"
br label %entry
entry: ; preds = %alloca
%1 = getelementptr inbounds %"->"* %0, i32 0, i32 0
store i8* bitcast (i32 (i32)* @"~fun_literal_1" to i8*), i8** %1
%2 = getelementptr inbounds %"->"* %0, i32 0, i32 1
store i8* null, i8** %2
%3 = load %"->"* %0
store %"->" %3, %"->"* %f
ret %"->" %3
}
declare i32 @printf(i8*, ...)
define i32 @main(i32 %argc, i8** %argv) {
entry:
%0 = call %"->" @__crystal_main(i32 %argc, i8** %argv)
ret i32 0
}
define internal i32 @"~fun_literal_1"(i32 %x) {
entry:
%0 = add i32 %x, 1
ret i32 %0
}
上記の例よりも少し理解しにくいですが、基本的には、最初の位置に~fun_literal_1へのポインタを割り当て、2番目の位置にnullを割り当てます。Procがローカル変数をキャプチャする場合
a = 1
f = ->(x : Int32) { x + a }
LLVM IRコードが変更されます。
; ModuleID = 'main_module'
%String = type { i32, i32, i32, i8 }
%"->" = type { i8*, i8* }
%closure = type { i32 }
@symbol_table = global [0 x %String*] zeroinitializer
define %"->" @__crystal_main(i32 %argc, i8** %argv) {
alloca:
%f = alloca %"->"
%0 = alloca %"->"
br label %entry
entry: ; preds = %alloca
%malloccall = tail call i8* @malloc(i32 ptrtoint (i32* getelementptr (i32* null, i32 1) to i32))
%1 = bitcast i8* %malloccall to %closure*
%a = getelementptr inbounds %closure* %1, i32 0, i32 0
store i32 1, i32* %a
%2 = bitcast %closure* %1 to i8*
%3 = getelementptr inbounds %"->"* %0, i32 0, i32 0
store i8* bitcast (i32 (i8*, i32)* @"~fun_literal_1" to i8*), i8** %3
%4 = getelementptr inbounds %"->"* %0, i32 0, i32 1
store i8* %2, i8** %4
%5 = load %"->"* %0
store %"->" %5, %"->"* %f
ret %"->" %5
}
declare i32 @printf(i8*, ...)
declare noalias i8* @malloc(i32)
define i32 @main(i32 %argc, i8** %argv) {
entry:
%0 = call %"->" @__crystal_main(i32 %argc, i8** %argv)
ret i32 0
}
define internal i32 @"~fun_literal_1"(i8*, i32 %x) {
entry:
%1 = bitcast i8* %0 to %closure*
%a = getelementptr inbounds %closure* %1, i32 0, i32 0
%2 = bitcast i8* %0 to %closure*
%3 = load i32* %a
%4 = add i32 %x, %3
ret i32 %4
}
これはさらに理解しにくいですが、基本的には、変数aの値を含むメモリが要求され、Procがそれを受け取り、使用します。この場合、メモリはmallocで要求されますが、通常のpreludeでは、メモリはGCによって割り当てられ、不要になったときに解放されます。
クラス
クラスもオブジェクトです。
x = Int32
驚くべきことではありませんが、クラスはInt32として表されます。
%x = alloca i32
...
store i32 45, i32* %x
クラスは実行時に作成できず、コンパイラはすべてのクラスを認識しているため、型IDを割り当てて、それらを識別できます。
ユーザー定義型
ユーザーは、クラスと構造体を定義できます。違いは、クラスをnewにするとヒープに割り当てられ、そのデータへのポインタが変数とメソッド間で渡されるのに対し、構造体をnewにするとそのメモリがスタックに割り当てられ、構造体全体の値が変数とメソッド間で渡され、コピーされることです。
試してみましょう。
class Point
def initialize(@x, @y)
end
end
x = Point.new(1, 2)
LLVM IRコードには次が含まれます。
%Point = type { i32, i32, i32 }
...
%x = alloca %Point*
むむ…ちょっと待って！Point型はインスタンス変数として、@xと@yの2つを持ち、どちらもInt32型です。では、なぜそこに別のi32があるのでしょうか？実は、Crystalはクラスに関連付けられた型IDを格納するためにInt32を追加しているのです。これは今のところあまり意味をなさないかもしれませんが、共用体(union)の表現方法について議論するときには、より意味がわかるでしょう。
構造体(struct)についても見てみましょう。
struct Point
def initialize(@x, @y)
end
end
x = Point.new(1, 2)
LLVM IRコードには次が含まれます。
%Point = type { i32, i32 }
...
%x = alloca %Point
この場合、構造体は型IDのための追加のInt32フィールドを含んでいません。
ここからが面白いところです。共用体です！
共用体
Crystalは任意の型の共用体をサポートしています。例えば、Int32型またはBool型のどちらかの値を持つ変数を持つことができます。
if 1 == 2
x = 3
else
x = false
end
if文の終わりでは、変数xは3またはfalseのいずれかになり、Int32型またはBool型になります。Crystalでの共用体の表現は、パイプを使って Int32 | Bool のように書きます。LLVM IRコードでは、次のようになります。
%"(Int32 | Bool)" = type { i32, [1 x i64] }
...
%x = alloca %"(Int32 | Bool)"
この特定の共用体の表現は、2つのフィールドを含むLLVM構造体であることがわかります。最初のフィールドは値の型IDを含みます。2番目のフィールドは値そのもので、その共用体で最大の型と同じ大きさのビット配列です（アラインメントの関係で、64ビットアーキテクチャではサイズが64ビット境界まで拡張されます）。C言語では、次のようになります。
struct Int32OrBool {
int type_id;
union {
int int_value;
bool bool_value;
};
}
最初のフィールド、型IDは、xに対してメソッドを呼び出すときにコンパイラによって使用されます。
これで、共用体の表現方法についての話は終わり、となりそうです。しかし、非常に一般的な共用体がいくつかあります。それはnil許容型です。
以前にNilについて話しませんでしたが、Nilは単一の値しか含むことができず、値を表現するためにvoidを使用できないため、i1として表現されます。
x = nil # %x = alloca i1
では、nilとクラスの共用体を作成してみましょう。
if 1 == 2
x = nil
else
x = Point.new(1, 2)
end
LLVM IRコードを確認すると、xに対して次のようになります。
%x = alloca %Point*
したがって、Point | Nilの共用体（Pointはクラス）は、Pointクラスと同じように表現されます。xがNilなのかPointなのかをどうやって判別するのでしょうか？簡単です。ヌルポインタはNilを意味し、非ヌルポインタはPointを意味します。
実際、クラスやnilのみを含むすべての共用体は、常に単一のポインタとして表現されます。ヌルポインタの場合はNilです。それ以外の場合は、共用体に多数のクラスが含まれている場合、値の最初のメンバーであるInt32で型を知ることができます。覚えてますか？これらの共用体がすべてポインタとして表現されることで、ポインタはレジスタに収まり、メモリ使用量が非常に少ないため、コードがはるかに効率的になります。
ただし、Nilと構造体の共用体は、常にInt32 | Boolの場合のように、タグ付き共用体として表現されます。しかし、これらの共用体ははるかに一般的ではありません。
型がどのように表現され、実行時に共用体に含まれる型をどのように知ることができるかを理解したので、次はメソッドディスパッチについて説明します。
メソッドディスパッチ
Crystalはオブジェクト指向言語ですが、メソッドの検索とディスパッチは他のオブジェクト指向言語とは大きく異なります。例えば、仮想テーブルや型に関するメタデータは（前に説明した型IDフィールドを除いて）保存されません。プログラムが動作するために必要なランタイムデータを最小限に抑え、実行速度を最大化しようとしています。場合によっては、結果のバイナリサイズを犠牲にすることもあります（これもそれほど大きくはなりませんが）。例として、次のクラス階層を考えてみましょう。
module Moo
def foo
1
end
end
class Foo
def foo
2
end
end
class Bar < Foo
include Moo
end
class Baz < Bar
end
Baz.new.foo #=> 1
うわあ、大きなクラス階層に、含まれるモジュール、そしてfooの2つの定義があります。コードを見て、この場合どのfooメソッドが呼び出されるかを知ることができますか？
…
それはMoo#fooですよね？はい、確かにそうです。実は、コンパイラもこれを知っており、生成されたコードを見ると次のようになります。
; Create a Bar
%0 = call %Baz* @"*Baz::new:Baz"()
; Invoke Moo#foo: no method lookup
%1 = call i32 @"*Baz@Moo#foo<Baz>:Int32"(%Baz* %0)
...
define internal i32 @"*Baz@Moo#foo<Baz>:Int32"(%Baz* %self) {
entry:
ret i32 1
}
Barのインスタンスを作成して、そのインスタンスでfooを呼び出した場合はどうなるでしょうか？
Bar.new.foo
Baz.new.foo
するとLLVM IRコードには次のものが含まれます。
%0 = call %Bar* @"*Bar::new:Bar"()
%1 = call i32 @"*Bar@Moo#foo<Bar>:Int32"(%Bar* %0)
%2 = call %Baz* @"*Baz::new:Baz"()
%3 = call i32 @"*Baz@Moo#foo<Baz>:Int32"(%Baz* %2)
...
define internal i32 @"*Bar@Moo#foo<Bar>:Int32"(%Bar* %self) {
entry:
ret i32 1
}
define internal i32 @"*Baz@Moo#foo<Baz>:Int32"(%Baz* %self) {
entry:
ret i32 1
}
おっと、そこにfooの重複した定義があるのではないですか？ええ、そうです。コンパイラがfooの定義を各クラスにコピーしたと考えることができます。そのため、実際には同じメソッドのコピーがたくさんあります。しかし、これはあまり重要ではありません。ほとんどのメソッドは大きくなく、メソッド呼び出しの速度がはるかに重要です。さらに、小さなメソッドは最適化されたビルドでインライン化され、重複した関数を検出してマージするためのLLVM変換パスもあります。
もちろん、Moo#fooがインスタンスメソッドを呼び出したり、インスタンス変数を使用したりする場合は、状況が少し変わります。この場合、「重複した」メソッドは実際には異なります。これも、各メソッド定義を最終的にそれを含む各型にコピーしたかのように、です。これにより、メソッド呼び出しが可能な限り効率的になりますが、実行可能ファイルサイズが（場合によっては）大きくなる可能性があります。しかし、エンドユーザーは通常、実行可能ファイルサイズよりも速度を重視します。
上記はすべて、コンパイラがBar.newの正確な型を知っているために可能です。コンパイラがこれを知らない場合はどうなるでしょうか？同じ階層にない型を持つ単純な共用体から始めましょう。
class Foo
def foo
1
end
end
class Bar
def foo
1
end
end
if 1 == 2
obj = Foo.new
else
obj = Bar.new
end
obj.foo
今回は、コンパイラは次のようなコードを生成します。objでfooを呼び出す前に、objがどの型であるかを確認します。これは、オブジェクトを表すポインタの最初のフィールド（型ID）をロードすることで知ることができます。そして、これに基づいて、1つのメソッドまたは別のメソッドを呼び出します。この決定は、1回のメモリロードと1回の比較で行われます。非常に効率的です。より大きな共用体の場合でも、1回のメモリロードまたは共用体の型IDフィールドを読み取るだけで、多くの比較が行われます。しかし…ルックアップテーブルの方が速くならないでしょうか？
実は、LLVMは非常に賢く、多くの比較を検出すると、ルックアップテーブルを構築してくれることがあります。これがよりうまく機能するためには、ルックアップテーブル内の数値が互いに近い必要があります（1と1000000の値に対するルックアップテーブルを想像してください。多くのスペースを必要とするため、LLVMはその場合に比較を行うことを決定します）。幸いなことに、LLVMがこれを達成するのに役立つ方法で型IDを割り当てています。
大きな共用体と言う場合、その共用体には同じ階層のクラスが含まれている可能性が高くなります。通常、すべての型が特定のルールに従い、同様のメソッドセットに応答するようにするためにクラス階層を構築します。クラス階層なしでこれを行うこともできますが、クラス階層はコードを構造化するための非常に一般的な方法です。
このクラス階層を考えてみましょう。
class Foo; end
class Bar < Foo; end
class Baz < Bar; end
class Qux < Bar; end
これらの型のみを考慮すると、コンパイラは型IDをポストオーダー方式で割り当てます。最初にBazに1が割り当てられ、次にQuxに2が割り当てられ、次にBarに3が割り当てられ、最後にFooに4が割り当てられます。また、コンパイラは、型自身のサブタイプを含む、型の型IDの範囲を追跡します。そのため、Barには1〜3の範囲も割り当てられ、Fooには1〜4の範囲が割り当てられます。
次に、これを考えてみましょう。
class Foo
def foo
1
end
end
class Bar < Foo
def foo
2
end
end
class Baz < Bar; end
class Qux < Bar; end
obj = # ... a union of the above types
obj.foo
まず、コンパイラはobjの型をFoo+として型付けします。つまり、Fooまたはそのサブクラスの1つである可能性があります（詳細については、こちらを参照してください）。この場合、2つの異なるメソッドインスタンス化のみが存在します。Foo+用とBar+用です。BazとQuxはそのメソッドを再定義していないためです。どちらを呼び出す必要があるかを知るために、型IDをロードします。次に、「型IDがBar、Baz、またはQuxのものである場合は、Bar#fooを呼び出し、それ以外の場合はFoo#fooを呼び出す」と言う代わりに、型IDがBarに以前に割り当てられた範囲（1〜3）内にあるかどうかを確認するだけで済みます。これはわずか2回の比較です。
この範囲チェックは、is_a?でも機能します。obj.is_a?(Foo)を実行し、場合によってはobjがInt32型、またはFoo、またはそのサブクラスの1つである場合、最大2回の比較でこれを解決できます。
最後に、Crystalの興味深い側面の1つは、メソッドディスパッチが複数の型に基づいて発生する可能性があることです。
def foo(x : Int32, y : Char)
end
def foo(x : Char, y : Int32)
end
def foo(x, y)
end
foo 1, 'a'
また、すべての引数の型がコンパイル時に不明な場合でも、これは機能します。しかし…このブログ記事は少し長くて複雑になってきています。コードを可能な限り効率的にするために適用するマイクロ最適化は他にもたくさんあります。したがって、Crystalを最大限に活用することを恐れないでください :-)