loopマクロのcollect節でintoを使うと非常に遅い

Emacs

loopマクロでcollect節と一緒にintoを使うと演算コストが非常に大きくなるという話。

原因を探るためにintoなしとintoありのloopマクロをmacroexpandで展開してpretty-printしてみます。どちらの演算式も返す値は同じになります。

;; intoなし
(pp (macroexpand-all '(loop for i from 1 to 10000 collect i)))

;; intoあり
(pp (macroexpand-all '(loop for i from 1 to 10000 collect i into x finally return x)))

;; 結果

;; intoなし
(cl-block-wrapper
 (catch '--cl-block-nil--
   (let*
       ((i 1)
        (--cl-var-- nil))
     (while
         (<= i 10000)
       (setq --cl-var--
             (cons i --cl-var--))
       (setq i
             (+ i 1)))
     (nreverse --cl-var--))))

;; intoあり
(cl-block-wrapper
 (catch '--cl-block-nil--
   (let*
       ((i 1)
        (x nil))
     (while
         (<= i 10000)
       (setq x
             (nconc x
                    (list i)))
       (setq i
             (+ i 1)))
     x)))

intoなしの方は、高速なリスト生成手法としてよく知られたpush/nreverseイディオムが使用されています。それに対して、intoありの方は、nconcでリストの末尾に逐一値を追加しているのが分かります(参照されるタイミングが不明なため、常に追加順を保たないといけない)。Lispのリスト構造に詳しい方ならすぐに気付くと思いますが、nconcは結合されるリストの末尾コンスセルを走査するため、結合されるリストが長くなればなるほど演算コストが増加します。そのため、intoありのcollectは指数関数的に演算コストが増加するのです。

実際、以下のようなベンチマークを取ってみるとその違いが歴然としていることが分かります。

(require 'benchmark)
(let ((gc-cons-threshold (* 1024 1024 32)))
  (garbage-collect)
  (message "push: %s" (benchmark-run-compiled 1
                          (funcall (lambda ()
                                     (loop for i from 1 to 10000 collect i)))))
  (garbage-collect)
  (message "nconc: %s" (benchmark-run-compiled 1
                           (funcall (lambda ()
                                      (loop for i from 1 to 10000 collect i into l))))))

結果
push: (0.001274 0 0.0)
nconc: (0.39666999999999997 0 0.0)

push/nreverse版では1msで完了するのに対し、nconc版では396msもかかっています。

この結果をふまえて、intoありcollectは利用しないよう促すつもりでしたが、ふと自作パッケージをgrepしてみると見事にauto-complete.elで利用していました。これがJoel Spolskyの言う「抽象化の漏れ」なのかと、自分を戒めながらヒシヒシと感じたのでした。

参考
  • info cl :: Loop Facility
  • Joel on Software