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

>> Site top >> weblog >> 月別アーカイブ >> 2015年12月のlog >> 2015-12-24-01-最適化で困っている

最終更新日付：2015/12/24 01:00:00

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

2015-12-29-01-Realforceの大掃除 ≫

最適化で困っている

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 であわせて２万行近いソースコードをさらに膨らませる気力と時間があるか、という問題がある。はてさて。

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