2016-12-16-01-initializer_listで失敗

>> Site top >> weblog >> 月別アーカイブ >> 2016年12月のlog >> 2016-12-16-01-initializer_listで失敗

最終更新日付：2016/12/16 01:00:00

≪ 2016-12-15-01-ひとまず大丈夫みたい

2016-12-17-01-最適化とは無関係なintializer_listの変更 ≫

initializer_listで失敗

2016 年 12 月 16 日

まぁ、なんていうか、調子に乗ったのかもしれない。最適化できると思ったが何重にも間違っていた、という話。

C++ の初期化リストをリードマクロで模倣する stl:initializer_list は、以下のように展開される。

#{a b c d e}

=> (LOCALLY (DECLARE (OPTIMIZE SPEED))
     (LET ((#:ARR (MAKE-ARRAY 5)))
       (DECLARE (TYPE VECTOR #:ARR))
       (SETF (AREF #:ARR 0) A)
       (SETF (AREF #:ARR 1) B)
       (SETF (AREF #:ARR 2) C)
       (SETF (AREF #:ARR 3) D)
       (SETF (AREF #:ARR 4) E)
       (MAKE-INSTANCE 'CL-STL:INITIALIZER_LIST :DATA #:ARR)))

正直、無駄な気がしないだろうか？　少なくとも自分はそう思った。わざわざ配列をアロケートするなんて、というわけだ。stl:initializer_list インスタンスにレキシカルクロージャを保有させて、要素にアクセスさせればいいじゃないか。そこで、以下のように展開されるようにしてみようかと考えた。

(LOCALLY (DECLARE (OPTIMIZE SPEED))
 (MAKE-INSTANCE 'CL-STL::INITIALIZER_LIST
                :COUNT 5
                :CLOSURE (LAMBDA (#:IDX)
                           (DECLARE (TYPE INTEGER #:IDX))
                           (ECASE #:IDX
                             (0 A)
                             (1 B)
                             (2 C)
                             (3 D)
                             (4 E)))))

もちろん、クラスの定義は変更する必要がある。しかしこれで初期化リストを作成するのに配列のアロケートは必要なくなるぜ！　と思ったのだが、よく考えると面倒なことに気付く。stl:initializer_list のための反復子を新規に作成してやらなければならなくなってしまうのだ。これまでは内部実装が配列だったから、const-vector-pointer が使えた。しかしそれが使えなくなるというわけだ。

それでもこれで最適化になるなら‥‥‥と反復子を実装。出来上がったところで計測してみる。stl:initializer_list の作成に伴うメモリ使用量はたしかに節約できるようになった。stl:begin や stl:end で反復子を使用する場合のパフォーマンスもまぁそれほど違わない。これならイケるんでないの‥‥‥？　と思ったが、最後に落とし穴が待っていた。

初期化リストの反復子を stl:for_each などのアルゴリズムに渡してみると、数十倍も遅くなっているのだ。そんな非効率な実装にしたかなぁ？　と思ってしばらくコードを眺めているうちに気付いた。配列ポインタに対するアルゴリズムの最適化が効かなくなった分パフォーマンスが落ちたのだ。これは完全に頭から抜け落ちていた。

それでも配列ポインタに対する最適化を度外視すれば同じなんだし、そもそも stl:initializer_list を処理するような（たとえばコンテナの初期化とかの）コードでアルゴリズムなんて使ってないよね‥‥‥？　と思ってコードをさらに確認。すると、逆に stl:initializer_list の実装（つまり内部配列を使っていること）に依存するコードだらけになっていた。つまり、上記のように実装を完全に置き換え（て配列の使用をやめ）る場合、CL-STL ライブラリの内部でも広範囲に影響が出るということだ。そして、内部配列を直接利用していた以上、どう変えても遅くなるだろう‥‥‥。

しかも、だ。初期化リストの要素として副作用のある式（まぁたとえば (incf x) とかね）を書いた場合、アクセスするたびにそれが実行されてしまうことになるだろう。そうなると、gensym で全ての要素を一時変数に格納し、それをクロージャで参照することになる。となると、これは配列と対して変わらない話になってしまうかもしれない（これは計測してないけど）。

すっかり意気消沈して C++ の標準文書の 18 章 9 節、std::initializer_list の項目を読んでいると、こいつの begin/end はいわゆる「反復子」ではなく、テンプレートパラメータとして与えられる要素型の const ポインタを返すと明記されていた‥‥‥。つまり、元々の実装が正しかったのだ。もちろん、そこまで合わせるかどうかというのは「決め」の問題だ。しかし、ここまでの流れで「あえて押しきる」というのはちょっと考えられないな、と思って諦めた次第。

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