2015-12-22-01-STL書籍の掲載コードをCL-STLで書いてみよう-25

>> Site top >> weblog >> 月別アーカイブ >> 2015年12月のlog >> 2015-12-22-01-STL書籍の掲載コードをCL-STLで書いてみよう-25

最終更新日付：2015/12/22 18:52:43

≪ 2015-12-21-01-STL書籍の掲載コードをCL-STLで書いてみよう-24

2015-12-24-01-最適化で困っている ≫

STL書籍の掲載コードをCL-STLで書いてみよう-25

2015 年 12 月 22 日

次いこう。「第46項：アルゴリズムのパラメータとして関数の代わりに関数オブジェクトの使用を考えよう」から。もう何度も書いている、ファンクタの性能のお話。

Effective STL のこの項で説明されているのは、要するに「アルゴリズムに渡すならファンクタ。通常そっちの方が速い。」ということだ。理由はインライン展開。例として挙げられているのは以下のようなコード。std::greater を使ったモノと、

std::vector<double> v;
//...
std::sort( v.begin(), v.end(), std::greater<double>() );

もうひとつは関数（ポインタ）を渡す場合だ。こっちはポインタ渡しなので関数本体が（インライン宣言されていても）インライン展開されず、結果として関数オブジェクトを渡した方が速くなる‥‥‥と。

inline bool doubleGreater( double d1, double d2 ) {
    return d1 > d2;
}
//...
std::sort( v.begin(), v.end(), doubleGreater );

当然というかなんというか、CL-STL ではこのへんの事情は大きく異なる。Common Lisp にはテンプレートというものがなく（マクロはあるんだけど）、CL-STL は総称関数とクラスをベースに作成されているからだ。そんなわけで、「CL-STL では関数を渡した方が通常は速い」という残念な話になる。というか、少なくともファンクタの方が速いということにはならない。それを説明するために作成したのが以下のコード。

(let ((v (new stl:vector 1000000)))
  (stl:generate (stl:begin v) (stl:end v)
                (lambda () (random 1000000)))
  (time (stl:sort (stl:begin v) (stl:end v) #'>)))

これは 100万要素のランダムな整数値シーケンスを作成し、それをソートする時間を測るものだ。先の Effective STL の書籍にあわせて降順ソートにしている。一方、以下は同じことを stl:greater で行なうモノだ。

(let ((v (new stl:vector 1000000)))
  (stl:generate (stl:begin v) (stl:end v)
                (lambda () (random 1000000)))
  (time (stl:sort (stl:begin v) (stl:end v) (new stl:greater))))

では、最初に #'> を使ったコードの実行結果を。安直に、『10回動かして一番成績の良かったモノ』を掲載している。

* (let ((v (new stl:vector 1000000)))
    (stl:generate (stl:begin v) (stl:end v)
                  (lambda () (random 1000000)))
    (time (stl:sort (stl:begin v) (stl:end v) #'>)))

; => Evaluation took:
;     1.160 seconds of real time
;     1.154407 seconds of total run time (1.154407 user, 0.000000 system)
;     99.48% CPU
;     2,775,723,210 processor cycles
;     0 bytes consed

一方、stl:greater を使ったコードは以下のような実行結果になった。こちらも『10回動かして一番成績の良かったモノ』を掲載。

* (let ((v (new stl:vector 1000000)))
    (stl:generate (stl:begin v) (stl:end v)
                  (lambda () (random 1000000)))
    (time (stl:sort (stl:begin v) (stl:end v) (new stl:greater))))

; => Evaluation took:
;     1.590 seconds of real time
;     1.591210 seconds of total run time (1.591210 user, 0.000000 system)
;     100.06% CPU
;     3,805,356,700 processor cycles
;     0 bytes consed

こんな感じで、ファンクタを使った方が 1.37 倍遅いことがわかる‥‥‥と、ちょっと待てよ。stl:greater ってデフォルトで #'operator_> を使うんではなかったっけ？　だとすれば、#'> を使うようにすればもちっとマシな勝負になるのではなかろうか？　というわけで以下のようにしてみた。

* (let ((v (new stl:vector 1000000)))
    (stl:generate (stl:begin v) (stl:end v)
                  (lambda () (random 1000000)))
    (time (stl:sort (stl:begin v) (stl:end v) (new stl:greater #'>))))

; => Evaluation took:
;     1.201 seconds of real time
;     1.201207 seconds of total run time (1.201207 user, 0.000000 system)
;     100.00% CPU
;     2,891,532,693 processor cycles
;     0 bytes consed

うーん、ビンゴ。直接関数 #'> を渡した最初の例と比べても 1.04倍遅いだけ。これならなんとか性能面で「ファンクタクラスは使わない方がいい」とまで言われなくてすむかもしれない。とはいえ、ラムダ式を直接書いた方が圧倒的に簡単なので、問題はそこだよね。どうしても値コピーの挙動が必要なファンクタを作成する場合だけ、かな。

というわけで、本日はこれにておしまい。第46項について書きたかったことはこれくらいだ。そして、実に３ヶ月にわたって続けてしまった『Effective STL 掲載コードを CL-STL で書いてみよう』という試みもこれでおしまい。おつかれ自分。

このシリーズのこれまでのエントリ

このページにコメントする

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

2015-12-22-01-STL書籍の掲載コードをCL-STLで書いてみよう-25

STL書籍の掲載コードをCL-STLで書いてみよう-25

このシリーズのこれまでのエントリ

コメント

このページのタグ

project-enigma

メニュー

更新履歴

2017/10/02

2017/09/15

2017/09/14