2015-12-24-01-最適化で困っている
>> Site top >> weblog >> 月別アーカイブ >> 2015年12月のlog >> 2015-12-24-01-最適化で困っている
最終更新日付：2015/12/24 08:11:31
最適化で困っている
2015 年 12 月 24 日
数日前から、CL-STL をコンパイルした時に大量に出るコンパイラノートをなんとかしようと頑張っている。大抵、「宣言が足りないから最適化できない」という類のモノなので、それは確認しながら宣言を追加する。しかし、簡単に解決できない問題にでくわしてしまった。今回はそんな話を少し。
説明のために、CL-STL の for-each アルゴリズムのうち、const-vector-pointer に最適化した実装を抜き出して関数にしてみた。以下がそれだ。
;; test1.lisp
(locally (declare (optimize speed))
;; itr1 : const-vector-pointer
;; itr2 : const-vector-pointer
;; func : functor or cl:function
(defun my-for-each (itr1 itr2 func)
(let ((fnc (clone func)))
(let ((idx1 (opr::vec-ptr-index itr1))
(idx2 (opr::vec-ptr-index itr2))
(buffer (opr::vec-ptr-buffer itr1))
(uf (stl:functor-function fnc)))
(declare (type fixnum idx1 idx2))
(declare (type cl:vector buffer))
(declare (type cl:function uf))
(stl:for (nil (< idx1 idx2) (incf idx1))
(funcall uf (aref buffer idx1)))) ;; HERE!!
fnc)))
ポイントは、反復子が内包しているインデックスと配列を抜き出してきて、内部では配列の要素をループするということ。これで反復子経由での操作のオーバーヘッドをバイパスできる。当然、配列の要素を参照する部分をどれだけ速くできるかがキモになる。
で、この関数を収めたファイルをコンパイルすると、以下のようなノートが表示される。あ、Windows 環境で SBCL 使ってます。
* (compile-file "R:/work/test1.lisp") ; compiling file "R:/Work/test1.lisp" (written 22 DEC 2015 08:51:00 AM): ; compiling (DEFUN MY-FOR-EACH ...) ; file: R:/Work/test1.lisp ; in: DEFUN MY-FOR-EACH ; (AREF BUFFER IDX1) ; ==> ; (SB-KERNEL:HAIRY-DATA-VECTOR-REF/CHECK-BOUNDS ARRAY SB-INT:INDEX) ; ; note: unable to ; optimize ; because: ; Upgraded element type of array is not known at compile time. ; ; compilation unit finished ; printed 1 note ; R:/work/test1.fasl written ; compilation finished in 0:00:00.016 #P"R:/Work/test1.fasl" NIL NIL
これは、反復子から取り出した配列である buffer を cl:vector と宣言していることが原因のようだ。コンパイラは汎用的な aref を最適化しようとしたが、buffer が関数の外からやってくるものであり、宣言も cl:vector としているため、「配列要素の型がコンパイル時点ではわからない（から最適化したいけどできない）」と伝えているわけだ。
ここで、確認のために以下のようなコードを用意してみた。
;; test2.lisp
(locally (declare (optimize speed))
(defun foo-test (func)
(let ((buffer (vector 0 1 2 3 4 5 6 7 8 9)))
(idx1 0)
(idx2 10)
(fnc (clone func)))
(let ((uf (stl:functor-function fnc)))
(declare (type fixnum idx1 idx2))
(declare (type cl:vector buffer))
(declare (type cl:function uf))
(stl:for (nil (< idx1 idx2) (incf idx1))
(funcall uf (aref buffer idx1)))) ;; HERE!!
fnc)))
コンパイル結果は以下の通り‥‥‥ノートは出力されない。
* (compile-file "R:/work/test2.lisp") ; compiling file "R:/Work/test2.lisp" (written 22 DEC 2015 08:55:09 AM): ; compiling (DEFUN FOO-TEST ...) ; R:/work/test2.fasl written ; compilation finished in 0:00:00.016 #P"R:/Work/test2.fasl" NIL NIL
おそらくなのだけれど、この foo-test の場合は関数内部で buffer が作成されているため、コンパイラはこれが simple-vector であると断定でき、cl:function との宣言を無視して（おそらくは）svref の呼び出しに変更したのだろう。
最初の for-each の話に戻ろう。そういうことなら、反復子から取り出した配列を cl:vector でなく simple-vector と宣言すればいい話なのでは？ もちろんその通りだ。だが、そうするわけにはいかない理由がある。その理由というのは、この反復子が simple-vector だけをサポートするわけではないことだ。
この、const-vector-pointer は、基本的に cl:vector の要素を反復するように作られている。当初は simple-vector しか想定していなかったのだけれど、string が simple-vector でないため、対象を cl:vector にまで広げたという経緯がある。これによって、以下のようなことが可能になる。要するに、character の配列である文字列の要素を指す反復子を作成して stl:sort にかけているわけだ。
(let ((str (copy-seq "abracadabra")))
(with-operators
(stl:sort &str[0] &str[11] #'char<))
str)
;=> "aaaaabbcdrr"
そういうわけなので、const-vector-pointer は（というかそこから派生した vector-pointer も）cl:vector を相手にすることになる。その意味では、const-vector-pointer のためのアルゴリズム実装は aref を使うしかなく、それ以上の最適化は望めない、というのが本来であればスジだ。それでもこれを何とかしたい理由は２つある。
- 汎用ライブラリなので、できる限り速くしたい。
- コンパイラノートが鬱陶しい。
1 については、アルゴリズムに const-vector-pointer を渡す局面の大半がsimple-vector である（と想定される）ことを考えるとやっぱりなんとかしたいと思うところだ。しかし、ここからさらに反復子クラスを派生させることは避けたい。最適化のために各種のアルゴリズムで特定化をしまくったため、アルゴリズムのモジュールはすでに２万行近い規模にまで膨れ上がっている。もう勘弁‥‥‥というのが正直なところなのだ。
ではどうするか。次に考えるのは、関数（メソッド）の中で分岐することだ。取り出した配列が simple-vector かどうかを判別して svref を使うかどうかを分岐させる、というのをやってみた。
(locally (declare (optimize speed))
;; itr1 : const-vector-pointer
;; itr2 : const-vector-pointer
;; func : functor or cl:function
(defun my-for-each (itr1 itr2 func)
(let ((fnc (clone func)))
(let ((idx1 (opr::vec-ptr-index itr1))
(idx2 (opr::vec-ptr-index itr2))
(buffer (opr::vec-ptr-buffer itr1))
(uf (stl:functor-function fnc)))
(declare (type fixnum idx1 idx2))
(declare (type cl:function uf))
(if (typep buffer 'simple-vector)
;; when buffer is simple-vector
(locally (declare (type simple-vector buffer))
(stl:for (nil (< idx1 idx2) (incf idx1))
(funcall uf (svref buffer idx1))))
;; when buffer is NOT simple-vector
(locally (declare (optimize safety))
(stl:for (nil (< idx1 idx2) (incf idx1))
(funcall uf (aref buffer idx1))))))
fnc)))
buffer が simple-vector かどうかを判定し、そうであれば局所的にこれを宣言。これで simple-vector ならばちゃんと svref が使用されるようになる。だが、残念なことにコンパイラノートは消えないのだ。表示されるコンパイラノートは、判定の結果 simple-vector でなかった場合の aref の使用について出力される。そっちでは局所的に (declare (optimize safety)) と記述しているのだが‥‥‥これでは関数定義全体を包んでいる外側の (declare (optimize speed)) は無効化できないのだろうか？ ちなみに、一番外側の locally 宣言を取り除くとコンパイラノートは表示されなくなるようだ。
上のやり方でコンパイラノートを抑止できたとしても不満は残る。これだとループ変数の扱いを最適化できないからだ。要するに、黙って aref を aref として使って欲しいだけなのだ。最適化全体を諦めるくらいなら、コンパイラノートが出続ける方がまだマシだ。
もうひとつ、 (if (typep buffer 'simple-vector) ...) で分岐させる方法で最適化を制御でき、さらに鬱陶しいコンパイラノートを抑止できたとしても、algorithm と numeric であわせて２万行近いソースコードをさらに膨らませる気力と時間があるか、という問題がある。はてさて。
コメント
このページのタグ
Page tag : STLとその移植
Page tag : Common Lisp
Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.
