単相比較による高速化テクニック、そして、そのあまり知られていない落とし穴

今日は一転、真面目な話です

ある程度 OCaml プログラミング経験がある皆様は、

int, string 等の基本型の比較には多相比較ではなく、単相比較を使うべし。最適化された比較関数が使われ、早くなる

という教をご存知かと思います。正しいです。でも、そこに実は落とし穴が:

実は、型だけ単相にしてもダメで、引数を全適用した形で使用しないと、最適化されない!!

(OCaml 3.11.2 現在。将来は知りませんよ!!)

もしこれをご存知でしたら、もう読んでいただく必要はありません。

第一のポイントは結構知られているようなのですが、実は第二のポイントはあまり知られていない様なのです。ざっと私が普段使っているOCamlオープンソースライブラリを検索してみましたが、最適化された比較関数を使おうとしているが、第二のポイントを知らなかったため、実はされていなかった、というコードを結構見つけてしまいました。

OCaml の多相比較

OCaml の構造比較関数 (=), (<>), (<), (<=), compare は多相型です。つまり、

val (=) : 'a -> 'a -> bool

という型を持っている。二つの引数の型さえ同じなら、なんでも(関数クロージャはだめよん)でも比較できるのです。int の比較にも、string の比較にも、リストの比較にも、なんでも使える。型によって比較アルゴリズムが違うはずなのに一つにまとまっている。

ML ではこんな不思議な関数は ML 内では定義できません。OCaml でも同様です。ですから、この多相比較はプリミティブ呼び出しにコンパイルされます。このプリミティブは、実行時に値に付属している、その値の種類を表すタグを調べ、内部でタグによって特化された比較プリミティブを使いわけます。いわゆる generic な挙動ですね。前者を汎用プリミティブ、後者を特化プリミティブとでも呼びましょうか。こんな感じになっています:

 OCaml   | 汎用プリミティブ | 特化プリミティブ (int用, string用, ...
 (=)     | caml_equal    | (==),             caml_string_equal, ... 
 (<)     | caml_lessthan | (<),              caml_string_lessthan, ... 
 compare | caml_compare  | caml_int_compare, caml_string_compare, ... 
 ...     | caml_*        | caml_タグ名_*

特化プリミティブ(caml_タグ名_*) は int, float, string などの基本データにしか用意されていません。これらは基本型とそれにコンパチな内部表現を持っている型の比較で使用することができます。それに対し、汎用プリミティブはこれらの基本データに加え、ブロック(lisp の consセルみたいなもの)の比較にも使えす。

コンパイル時の汎用と特化プリミティブの使いわけ

基本型に対しては、汎用と特化、両方の比較プリミティブが使えることに注意して下さい。機能としては汎用プリミティブの方が強力ですが、その内部でタグを調べて、特化プリミティブに割り振る分、特化プリミティブを直接使うのに比べスピードは遅くなります。
じゃあ、基本型の比較は常に特化プリミティブへとコンパイルすれば、それでいいじゃないか?と思われるかもしれませんが、、、OCamlは多相言語なので、そうはいかないのです:

let rec merge xs ys =
  match xs, ys with
  | x::xs, y::_  when x < y -> x::merge xs ys
  | x::_,  y::ys when x > y -> y::merge xs ys
  | x::xs, y::ys (* when x = y *) -> x::merge xs ys
  | [],    _  -> ys
  | _,     [] -> xs

この merge 関数は二つのそれぞれ既にソートされたリストを取り、要素の比較を行って、二つのリストの要素を持つ、やはりソートされたリストを返します:

# merge [1;3;5;7;9] [0;2;4;6;8];;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
# merge ["a";"c";"e"] ["b";"d";"f"];;
- : string list = ["a"; "b"; "c"; "d"; "e"; "f"]

この二つの merge では二つの異なる基本型の比較が内部で行われる事に注意して下さい。このため、merge の内の比較を特化プリミティブへとコンパイルする訳にはいきません。何が来るか判らないので、汎用プリミティブにコンパイルします。このように多相関数の内部で、定義時に比較対象の型がわからない場合、比較関数は汎用比較プリミティブを使ってコンパイルされます。*1

コンパイル状況を -dlambda で確認する

さて、では実際に merge での比較が汎用比較になっていることを確認しましょう。ocaml -dlambda を使うと、コンパイル時の中間言語を眺めることができます:

$ ocaml -dlambda
        Objective Caml version 3.11.2

# let rec merge xs ys =
  match xs, ys with
  | x::xs, y::_  when x < y -> x::merge xs ys
  | x::_,  y::ys when x > y -> y::merge xs ys
  | x::xs, y::ys (* when x = y *) -> x::merge xs ys
  | [],    _  -> ys
  | _,     [] -> xs
;;
(letrec
  (merge/66
     (function xs/67 ys/68
       (if xs/67
         (if ys/68
           (let
             (ys/74 (field 1 ys/68)
              y/71 (field 0 ys/68)
              xs/70 (field 1 xs/67)
              x/69 (field 0 xs/67))
             (if (caml_lessthan x/69 y/71)
               (makeblock 0 x/69 (apply merge/66 xs/70 ys/68))
               (if (caml_greaterthan x/69 y/71)
                 (makeblock 0 y/71 (apply merge/66 xs/67 ys/74))
                 (makeblock 0 x/69 (apply merge/66 xs/70 ys/74)))))
           xs/67)
         ys/68)))
  (apply (field 1 (global Toploop!)) "merge" merge/66))
val merge : 'a list -> 'a list -> 'a list = <fun>

括弧が沢山ついているのが中間言語 Lambda です。caml_lessthan と caml_greaterthan という汎用比較が使われているのが判ります。

もうちょっと簡単にしてみましょう:

# fun x y -> compare x y;;
(function x/81 y/82 (caml_compare x/81 y/82))
- : 'a -> 'a -> int = <fun>

多相関数なので、汎用比較です。

型を制限することで比較プリミティブの最適化を行う

以上、比較の型が多相的なため、汎用プリミティブを使ってコンパイルせざるを得ない例を見てきました。では、型が特定された比較はどのようにコンパイルされるのでしょうか。

もちろん、特化プリミティブの用意されていない型の比較には汎用プリミティブが使われます:

# [1;2;3] = [4;5;6];;
(caml_equal [0: 1 [0: 2 [0: 3 0a]]] [0: 4 [0: 5 [0: 6 0a]]])
- : bool = false

しかし、基本型が使われている場合には、汎用を使う義理はありません。こんな時、OCamlコンパイラは特化プリミティブを使ってコンパイルを(ある条件下で)行います:

# "hello" = "world";;
(caml_string_equal "hello" "world")
- : bool = false

caml_equal ではなく、 caml_string_equal が使われていますね!!この特化プリミティブは引数が文字列であることを仮定し、値のタグを調べず、文字列内容の比較をすぐに行います。そのため、汎用プリミティブよりも少し早いのです。「ある条件下で」と書きましたが、これが、この記事の一番上で述べた、第二のポイントです。後で説明します。

この特化プリミティブを使うことによるスピードアップは個々の比較では小さなものですが、比較を大量に行うハッシュテーブルなどのデータ構造の実装では違いが顕著に出てきます。まあ、汎用/特定プリミティブで計算量が根本的に変わる、とかいった事は無いので、最適化のテクニックの一つ、と言えばそれまでですが、重要です。次の次の節で解説するようなファンクタを使った例では特に気をつけてください。

型制限による汎用プリミティブを使った最適化

merge の例に戻りましょう。merge は多相関数でその型は 'a list -> 'a list -> 'a list。比較が多相なため、内部で汎用比較プリミティブが使われます。
この merge の定義を型制限を使って int list のマージ専用に変えると、この汎用プリミティブとしてコンパイルされていたものが特化プリミティブへと変化します!!:

let rec merge (xs : string list) ys =
  match xs, ys with
  | x::xs, y::_  when x < y -> x::merge xs ys
  | x::_,  y::ys when x > y -> y::merge xs ys
  | x::xs, y::ys (* when x = y *) -> x::merge xs ys
  | [],    _  -> ys
  | _,     [] -> xs
;;
(letrec
  (merge/225
     (function xs/226 ys/227
       (if xs/226
         (if ys/227
           (let
             (ys/233 (field 1 ys/227)
              y/230 (field 0 ys/227)
              xs/229 (field 1 xs/226)
              x/228 (field 0 xs/226))
             (if (caml_string_lessthan x/228 y/230)
               (makeblock 0 x/228 (apply merge/225 xs/229 ys/227))
               (if (caml_string_greaterthan x/228 y/230)
                 (makeblock 0 y/230 (apply merge/225 xs/226 ys/233))
                 (makeblock 0 x/228 (apply merge/225 xs/229 ys/233)))))
           xs/226)
         ys/227)))
  (apply (field 1 (global Toploop!)) "merge" merge/225))
val merge : string list -> string list -> string list = <fun>

多相バージョンでは汎用の caml_lessthan, caml_greaterthan だったプリミティブが caml_string_lessthan, caml_string_greaterthan の特化プリミティブに変化しています。
もちろん、この最適化された merge はもはや多相型ではありませんから、汎用性は落ちますが、元々 int list にしか使わなければ構わないわけです。

型制限をつけなくてもコンパイラがこの辺を酌んで自動的に最適化を行ってくれればよいのですが、そのためにはプログラム全体で関数の使われ方の解析を行わなければいけません。これはとっても大変です。

ファンクタを使ったデータ構造定義と特化プリミティブによる最適化

この汎用と特化プリミティブの使いわけで特に注意しなければならないのは、ファンクタを使ってデータ構造を扱うモジュールを作る場合です。(ファンクタはもちろんご存知ですよね?!知らない人は…飛ばして下さい。)

次は整数の集合を扱うモジュールを Set.Make で作成していますが、、、

module Int_set = Set.Make(struct
  type t = int
  let compare x y = compare x y
end)

もちろんこれはダメですよね!!そう、compareが多相のままですから、汎用プリミティブが使われています(-dlambda で確かめてね)。これは、

module Int_set = Set.Make(struct
  type t = int
  let compare x y = compare (x:int) y
end)

とでもして特化プリミティブを使ったバージョンを使いましょう。これでどれだけ性能が違うかは、各自の宿題です。特定分野ではクリティカルなレベルです。

ファンクタを使わない多相ハッシュテーブル Hashtbl.create も注意が必要です。キーが int や string などの基本型の場合は、こいつを使うよりはちょっと面倒ですが、Hashtbl.Make を使った単相テーブルを作った方が早いのです。

OCaml の、型制限による比較最適化の落とし穴

さて、ここまで、型を制限することによって、比較関数の汎用プリミティブへのコンパイルを、より早い特化プリミティブへと変える最適化について、原理とテクニックを解説してきましたが、お判りいただけたでしょうか。判んない場合、もし手を動かしてなかったら動かして下さいね。

さて、上の方で、

基本型が使われている場合には、汎用を使う義理はありません。こんな時、OCamlコンパイラは特化プリミティブを使ってコンパイルを(ある条件下で)行います:

と書きました。「ある条件下」、、、これがトリッキーで、実はよく知られていないのです。

次のコンパイル例を見てください:

$ ocaml -dlambda
# compare 1 2;;
(caml_int_compare 1 2)
- : int = -1
# compare 1;;
(apply (function prim/67 prim/66 (caml_compare prim/67 prim/66)) 1)
- : int -> int = <fun>
# (compare : int -> int -> int);;
(function prim/69 prim/68 (caml_compare prim/69 prim/68))
- : int -> int -> int = <fun>

三つとも、compare の型は int -> int -> int なんですけど、特化プリミティブが使われているのは、初めの一つだけ、、、それ以外は汎用です。
色々調べてみたら判りますが、型が判明していて特化プリミティブを使える場合、コンパイルの最適化が行われるのは、全引数が適用されている場合に限るのです。
えええ、なんで?

理由は特にありません

私と Markus Mottl で考えてみましたが、特にないんすよ。上の例を見ても判る通り、プリミティブの場合は partial application であろうと、まったく引数が無くても eta expansion されてるわけですから、基本型の比較しているならプリミティブを汎用から特化に入れ替えるだけで別に何の問題もないし、、、どうやら全適用されてるときにしか、この特化プリミティブによる最適化を行うコードが動いていないだけ。なんで、バグレポートしときました。(http://caml.inria.fr/mantis/view.php?id=4965)

ということは、こんな型制限は意味がないんです:

module Int_set = Set.Make(struct
  type t = int
  let compare : int -> int -> int = compare
end)

これだと全適用されていませんから、最適化が行われない。遅いままです。-dlambda で確認して下さい。上の例のように、let compare : int -> int -> int = fun x y -> compare x y と書かないと期待した効果は得られません。

この様な意味の無い失敗最適化なんですが、結構有名なライブラリでも行われているようです。理由は単純で、全適用されていようが、されてなかろうが、最適化が行われない理由が見えない => されるに決まっていると思い込む、に他なりません。でも残念ながら、OCaml 3.11.2 現在、実装はそうなってはいないのです。

もちろん、ファクタ以外のシチュエーションでも、

let foo lst = List.fold_left compare 0 lst

こんなコードでも、compare の最適化は当然行われません。

まあ、レポート出しましたから、遠からず直されると思うのですが、皆さんのプログラムでも、全適用されてない型制限された比較があったら勿体ないので、是非一度チェックを!!

なお、

module Int_set = Set.Make(struct
  type t = int
  external compare : int -> int -> int = "caml_int_compare"
end)

だと直接特化プリミティブを使えますが、間違った型を書いていた場合、型チェックできないのでクラッシュします。やめましょう。

まとめ

  • 比較関数は使われる型でコンパイルが変わる。特化プリミティブの方が早い
  • 比較関数で型制限を使うと多相性は失われるが、最適化できる
  • 基本型を使った hashtbl などのファンクタによるデータ構造のせいせいえは特に型制限に注意
  • ここまでは多分これからの OCaml でも重要なテクニック。
  • OCaml 3.11.2 現在、この最適化が行われるのは全適用されている時だけ!!!

*1:このような方法とは別に、コンパイル時には特定できない比較関数プリミティブはディスパッチによって型が判明している外部から渡すという方法もあります。Haskell の type class に通じる方法ですが、型にプリミティブを受け取ることを明示せねばならなくなります: Haskell でいう Comparable a => [a] -> [a] -> [a] 。いや、Comparable って type class があるかどうかは知らんぜよ。