#:g1: リストの破壊的反転でループアンローリング

Posted 2021-07-19 03:09:10 GMT

bit 1982年6月号の有澤誠先生の記事「トーイプログラム・ライブラリから (13) 線形リストの反転」で、リストの破壊的反転関数にループアンローリングを適用し一時変数への代入の回数を減らす手法が紹介されていたので、どんなものか試してみました。

ちなみにどうやらこちらの記事は、文中で紹介されている論文のネタをそのまま紹介している様子で論文は現在PDFで入手可能です。

ループアンローリングで代入を減らす

先に代入を減らしたものから紹介してみますが、こんな風になっています

(defun rev/ (list)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (declare (type list list))
  (let ((q list)
        (p nil)
        (r nil))
    (declare (type list p q r))
    (loop
     (macrolet ((relink (a b c)
                  `(progn
                     (when (null ,b)
                       (return ,a))
                     (setq ,c (cdr ,b))
                     (setf (cdr ,b) ,a))))
       (relink p q r)
       (relink q r p)
       (relink r p q)))))

そして、アンローリングしないものは下記のようになりますが、ループ内の三つの変数に固定した役割を与えるために変数名の付け替えを行なっているのを、無駄なのでやめた結果が上記のアンローリングした格好になっています。

(defun rev (list)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (declare (type list list))
  (let ((q list)
        (p nil)
        (r nil))
    (declare (type list p q r))
    (loop
     (macrolet ((relink (a b c)
                  `(progn
                     (when (null ,b)
                       (return ,a))
                     (setq ,c (cdr ,b))
                     (setf (cdr ,b) ,a))))
       (relink p q r)
       (setq p q)
       (setq q r)))))

アンローリングの効果はあるのか

LispWorksとSBCLで計測してみました。
参考にnreconcとも比較してみています。(nreverseだとリスト以外のsequenceにも対応しているため)

(defparameter *big-list* 
  (loop :repeat 10000 :collect (random 100)))

(let ((u *big-list*)) (time (dotimes (n 100000 (car u)) (setq u (rev u)))))

(let ((u *big-list*)) (time (dotimes (n 100000 (car u)) (setq u (rev/ u)))))

(let ((u *big-list*)) (time (dotimes (n 100000 (car u)) (setq u (nreconc u nil)))))

LispWorks

rev:
User time    =        2.930
System time  =        0.010
Elapsed time =        2.933
Allocation   = 138559752 bytes
0 Page faults
Calls to %EVAL    1800037

rev/: User time = 2.600 System time = 0.000 Elapsed time = 2.591 Allocation = 138568168 bytes 0 Page faults Calls to %EVAL 1800037

nreconc: User time = 5.110 System time = 0.000 Elapsed time = 5.099 Allocation = 138573152 bytes 0 Page faults Calls to %EVAL 1900037

SBCL

rev:
Evaluation took:
  1.530 seconds of real time
  1.530000 seconds of total run time (1.530000 user, 0.000000 system)
  100.00% CPU
  5,048,088,615 processor cycles
  0 bytes consed

rev/: Evaluation took: 1.230 seconds of real time 1.230000 seconds of total run time (1.230000 user, 0.000000 system) 100.00% CPU 4,071,225,671 processor cycles 0 bytes consed

nreconc: Evaluation took: 1.750 seconds of real time 1.740000 seconds of total run time (1.740000 user, 0.000000 system) 99.43% CPU 5,736,956,404 processor cycles 0 bytes consed

今回の例では、アンローリングしたものは、LispWorksで一割強、SBCLで二割強速くはなっているようですが、リストの大きさによっては殆ど速度が変わらないこともあるようです。微妙に速いかも、という程度でしょうか。

まとめ

最近のコンパイラだとこれくらいの最適化はされそうですが、とりあえずのところCommon Lispではまだ無理のようです。


HTML generated by 3bmd in LispWorks 7.0.0

comments powered by Disqus