2011年11月24日木曜日

コンパイラマクロとインライン展開とその問題

最近、Allegro Common Lisp の Enterprise 版が手に入り、最適化熱を再燃させています。その手始めとして、Computer Language Benchmarks Game の Lisp プログラムを高速化しようとしましたが、正直に言って、これらのプログラムは Lisp らしからぬ書きぶりで(いやむしろ Lisp らしいと言ったらいいのか)、高速化しようにもなかなか手が付けられない状態です。どういうことかと言うと、例えば fannkuch-refux には次のようなマクロがあります。

(defmacro setlambda(n)
  (declare (type fixnum n))
  (let ((copy (gensym))
        (perm (gensym)))
  `(lambda (,perm ,copy)
     (declare (optimize (speed 3) (safety 0) (space 0) (debug 0))
      (type (simple-array sb (,n)) ,copy ,perm))
     ,@(loop for i of-type fixnum from 0 below n collect
         `(setf (aref ,copy ,i) (aref ,perm ,i))))))

このマクロは、プログラムの開始時に与えられた n でもって、 (eval `(setlambda ,n)) することで、 n に特化したループしない配列コピー関数を作るためのもので、良く言えば Lisp らしいと言えます。ただ、僕の哲学から言えば(納期に追われ、有無を言わさず高速化する必要がある場合を除いて)、これはむしろ Lisp のバッドノウハウと言いたくなります。なぜなら、Lisp には、コードの可読性を落とさずに、そのような目的を達成する手段があると信じているからです。今回は、件のマクロでやっている、手動 loop unrolling をもっと美しく達成する方法について考えます。なお、議論を明確にするため dotimes に対する最適化にフォーカスします。

まずナイーブな方法として、次のような専用のマクロを作る方法が考えられます。

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter *loop-unrolling-threshold* 32))

(defmacro dotimes/unrolling ((var count &optional result) &body body)
  (if (and (integerp count)
           (< count *loop-unrolling-threshold*))
      `(block nil
         ,@(loop for i from 0 below count
                 collect `(let ((,var ,i)) ,@body))
         ,result)
      `(dotimes (,var ,count ,result) ,@body)))

このマクロは与えられた count が整数で一定の閾値未満なら loop unrolling を行います。例えば、

(dotimes/unrolling (i 10) (print i))

このコードは次のようなコードに macroexpand されます。

(BLOCK NIL
  (LET ((I 0))
    (PRINT I))
  (LET ((I 1))
    (PRINT I))
  (LET ((I 2))
    (PRINT I))
  (LET ((I 3))
    (PRINT I))
  (LET ((I 4))
    (PRINT I))
  (LET ((I 5))
    (PRINT I))
  (LET ((I 6))
    (PRINT I))
  (LET ((I 7))
    (PRINT I))
  (LET ((I 8))
    (PRINT I))
  (LET ((I 9))
    (PRINT I))
  NIL)

実際のところ、製品レベルで使うようなものでは、このようなマクロが現実的ですが、せっかく Lisp なのだからもう少し面白いことがしたいですね。そこで、もう一つの方法としてコンパイラマクロを使う方法を考えてみます。

コンパイラマクロを使えば、関数やマクロの挙動を部分的に最適化することが可能です。そのため、上のようにわざわざ dotimes/unrolling など作らなくとも dotimes コンパイラマクロを定義すれば良いのです。

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter *loop-unrolling-threshold* 32))

(define-compiler-macro dotimes (&whole form (var count &optional result) &body body)
  (if (and (integerp count)
           (< count *loop-unrolling-threshold*))
      `(block nil
         ,@(loop for i from 0 below count
                 collect `(let ((,var ,i)) ,@body))
         ,result)
      form))

これで、通常通りコードを書けば最適化してくれます。

;; loop unrolling されるはず
(dotimes (i 10) (print i))

なお、上のコンパイラマクロを定義するとき、ACL や SBCL では package violation エラーが発生します。 cl パッケージのマクロの挙動を変更するわけですから、危険極まりないですし、当然の処置です。遊ぶときだけ適当に unlock しましょう。

それでは、コンパイラマクロ付きの dotimes を使って最初のマクロを関数に書きなおしてみましょう。

(declaim (inline copy))
(defun copy (dest src n)
  (dotimes (i n)
    (setf (aref dest i) (aref src i))))

例のマクロは、配列をコピーする関数を作るマクロなので、少し一般化しています。また、簡単のため宣言は省いています。私としては、

(let* ((n 10)
       (dest (make-array n))
       (src (make-array n)))
  (copy dest src n))

のようなコードにおいて、 copy の呼び出しがインライン展開され、そのとき n=10 というのが分かっているので、同時に dotimes のコンパイラマクロが展開され、loop unrolling が起こることを期待していたわけですが、よくよく考えれば、これは起こり得ないだろうと予想されます。

インライン展開の厳密な挙動は CLHS に述べられていないため、ここからは処理系依存の話になりますが、一般的に考えて、コンパイラマクロは"マクロ"である以上、そのマクロ展開時に渡される引数(項)はまさにそこにあるべきで、上の例で言えば、インライン展開された dotimes のコンパイラマクロは、10 という定数を取るわけではなく、まさにそこにある n を引数として取るのが常識的と言えるでしょう。

そのため、開発者の意図と、コンパイラマクロ+インライン展開の仕様との間には、ある種のギャップがあると言えます。仕様としての有効な解決手段は、私は思いつきませんが、例えばレキシカル環境にその変数が静的に取り得る定数を格納しておき、 CLtL2 の variable-information で取り出せるようにするのはどうかと考えています。疑似コードで示せば次のようになります。

(eval-when (:compile-toplevel)
  (defun static-constant-value (obj env)
    (cond ((constantp obj) obj)
          ((symbolp obj)
           (nth-value 3 (variable-information obj env))))))

(define-compiler-macro dotimes (&whole form &environment env (var count &optional result) &body body)
  (aif (static-constant-value count env)
       `(block nil
          ,@(loop for i from 0 below it
                  collect `(let ((,var ,i)) ,@body))
          ,result)
       form))

上の例では variable-information を使いましたが、処理系依存の関数を用意しても良い気がします。そこで SBCL 限定で、そのような関数、あるいは同じような目的を達成する手段がないか探してみたところ、 wanted: compiler macro expansion in later compilation stages (e.g. after inlining) という要望を見つけました。この人の要望というのは、まさに私の要望と同じで、静的に決定する正規表現の文字列に関して cl-ppcre:scan のコンパイラマクロを動作させたいというものです。この要望を客観的に見たとき、やはりこのような要望は自然であるし、インライン展開するのであれば、当然満たしておきたい要件でもあります。

SBCL のコアデベロッパである Nikodemus Siivola は、この要望に対して肯定的な態度をとっており、実際にこの問題を解決するためのパッチも提供しています。ただ、現時点では SBCL の HEAD にはそれに該当するコードが見つかりません。コメントを見るに、 Nikodemus はこのパッチに若干の苦悩を抱えており、なかなかマージに至れないという状況なのだと予想されます。 Nikodemus のパッチは、コンパイラマクロに渡されるシンボルを、可能であれば定数に置き換えるというもので、先に述べたようなコンパイラマクロが"マクロ"でなくなる点で苦悩しているようです。この方法は、コンパイラマクロに定数展開のコードを書かなくても良い点でメリットがありますが、やはりコンパイラマクロのなんぞやが問われる点で、デメリットのほうが大きいと私は考えます(おそらく Nikodemus も同じ)。やはり、コンパイラマクロ内部で、定数展開するための、専用の関数なりを用意するのが一番だと思いますが、そういう関数は今のところ見つかってないですし、 Nikodemus 自身もそのような発想はないようです、もしかしたら、そういった関数をそもそも定義できないのかもしれませんが、まだ SBCL のソースを眺めている段階で何とも言えません。

以上、コンパイラマクロ+インライン展開でも期待された最適化が行われない可能性が高いという話でした。ぐだぐだな上、特にオチはなし、終わり。

0 件のコメント:

コメントを投稿