#:g1: Emacs Lispのseq-filterの謎

Posted 2022-08-27 18:57:54 GMT

こんなtweetを目にしたので、どうなっているのだろうと思ってソースを確認してみました。

;;; lisp/emacs-lisp/seq.el.gz
(cl-defgeneric seq-filter (pred sequence)
  "Return a list of all the elements for which (PRED element) is non-nil in SEQUENCE."
  (let ((exclude (make-symbol "exclude")))
    (delq exclude (seq-map (lambda (elt)
                             (if (funcall pred elt)
                                 elt
                               exclude))
                           sequence))))

なるほど確かにseq-mapで削除対象をマークで置き換えてからdelqでマークを一括削除しています。

リストを二回走査するのは効率が悪そうですが、実はこの方が速かったりするのでしょうか。

ということでseq-map方式のものと、一回の走査で結果を作成するLispでは正統派なものを定義して速度を計測してみました。
なお、計測に利用したマシンはM1 Macです。

;;; 下準備
(require 'cl-lib)
(require 'benchmark)

(defun make-big-list () (make-list 10000000 0))

まずはseq-filterそのまま。10,000,000個の0のリストなので述語がevenpの場合には何も削除せず、oddpの場合には全部削除することになります。
結果を眺めるに、delqが仕事をするかしないかで若干の速度の違いがあるようです。

(let ((big-list (make-big-list)))
  (benchmark-progn
    (seq-filter #'evenp big-list))
  nil)
;Elapsed time: 0.967336s (0.171383s in 1 GCs)

(let ((big-list (make-big-list)))
  (benchmark-progn
    (seq-filter #'oddp big-list))
  nil)
;Elapsed time: 1.014695s (0.180690s in 1 GCs)

次にseq-mapの中身を抜き出してリスト専用にしたもの。今回の例ではsequenceで受けて特定の型にディスパッチするようなことはしていないので、元とあまり速度に違いはありません。

(defun my-filter-map&delq (fn list)
  (let ((exclude (make-symbol "exclude")))
    (delq exclude (mapcar (lambda (elt)
                            (if (funcall fn elt)
                                elt
                                exclude))
                          list))))

(let ((big-list (make-big-list))) (benchmark-progn (my-filter-map&delq #'evenp big-list)) nil) ;Elapsed time: 0.992169s (0.196337s in 1 GCs) (let ((big-list (make-big-list))) (benchmark-progn (my-filter-map&delq #'oddp big-list)) nil) ;Elapsed time: 1.013334s (0.181091s in 1 GCs)

次にお馴染のcons & reverseでリストを組立てるもの。
map & deleteの逆で、evenpの場合に仕事をしてoddpの場合に何もしませんが、evenpの場合は約5割遅くなり、oddpの場合は約4割速くなりました。

(defun my-filter-cons&nrev (fn list)
  (cl-do ((x list (cdr x))
          (ans '()))
      ((null x)
       (nreverse ans))
    (when (funcall fn (car x))
      (push (car x) ans))))

(let ((big-list (make-big-list))) (benchmark-progn (my-filter-cons&nrev #'evenp big-list)) nil) ;Elapsed time: 1.581908s (0.818741s in 6 GCs) (let ((big-list (make-big-list))) (benchmark-progn (my-filter-cons&nrev #'oddp big-list)) nil) ;Elapsed time: 0.593515s

リストの末尾に要素を繋げていく所謂tconcですが、cons & reverseと大差ないようです。
ちなみにrplacdの返り値がCommon Lispと違ってセルのcdrなところにはまりました。こんなところに違いがあるとは……。

(defun my-filter-tconc (fn list)
  (let* ((ans (list nil))
         (tem ans))
    (cl-do ((x list (cdr x)))
        ((null x)
         (cdr ans))
      (when (funcall fn (car x))
        (setq tem (rplacd tem (list (car x))))))))

(let ((big-list (make-big-list))) (benchmark-progn (my-filter-tconc #'evenp big-list)) nil) ;Elapsed time: 1.415054s (0.751842s in 5 GCs) (let ((big-list (make-big-list))) (benchmark-progn (my-filter-tconc #'oddp big-list)) nil) ;Elapsed time: 0.580962s

まとめ

どうやらelispだと、削除する要素が多い場合は、cons & reverseの方が速いのですが、削除する要素が少なければ遅くなるようです。
map & deleteはどちらのケースでも中間の速度で速くもなく遅くもなく、という結果になりました。
Emacs Lispではこのあたりを考慮してmap & deleteなのかもしれません。

しかし、普段書いているCommon Lispの感覚からするとtconcあたりが最速になる気がするのでCommon Lispでもベンチをとってみました。
結果を概観すると、Common Lispでは、予想どおり、cons & reverseかtconcの方がmap & deleteより常に速いという結果になりましたが、思った程の差はないというところです。
ちなみに処理系組み込みのremove-if-notも計測してみましたが、最適化のお蔭か10倍程度速かったりします。

(defun make-big-list ()
  (make-list 10000000 :initial-element 0))

(defmacro benchmark-progn (&body forms) `(time ,@forms))

(setf (macro-function 'cl-do) (macro-function 'do))

(defun my-filter-map&delq (fn list) (let ((exclude (make-symbol "exclude"))) (delete exclude (mapcar (lambda (elt) (if (funcall fn elt) elt exclude)) list) :test #'eq)))

(let ((big-list (make-big-list))) (benchmark-progn (my-filter-map&delq #'evenp big-list)) nil) #|| Timing the evaluation of (MY-FILTER-MAP&DELQ #'EVENP BIG-LIST)

User time = 0.535 System time = 0.022 Elapsed time = 0.552 Allocation = 160032168 bytes 11402 Page faults GC time = 0.112 ||#

(let ((big-list (make-big-list))) (benchmark-progn (my-filter-map&delq #'oddp big-list)) nil) #|| Timing the evaluation of (MY-FILTER-MAP&DELQ #'ODDP BIG-LIST)

User time = 0.431 System time = 0.001 Elapsed time = 0.431 Allocation = 160007680 bytes 5 Page faults GC time = 0.000 ||#

(defun my-filter-cons&nrev (fn list) (cl-do ((x list (cdr x)) (ans '())) ((null x) (nreverse ans)) (when (funcall fn (car x)) (push (car x) ans))))

(let ((big-list (make-big-list))) (benchmark-progn (my-filter-cons&nrev #'evenp big-list)) nil) #|| Timing the evaluation of (MY-FILTER-CONS&NREV #'EVENP BIG-LIST)

User time = 0.246 System time = 0.004 Elapsed time = 0.250 Allocation = 160007128 bytes 1 Page faults GC time = 0.000 ||#

(let ((big-list (make-big-list))) (benchmark-progn (my-filter-cons&nrev #'oddp big-list)) nil) #|| Timing the evaluation of (MY-FILTER-CONS&NREV #'ODDP BIG-LIST)

User time = 0.029 System time = 0.000 Elapsed time = 0.028 Allocation = 7120 bytes 1 Page faults GC time = 0.000 ||#

(defun my-filter-tconc (fn list) (let* ((ans (list nil)) (tem ans)) (cl-do ((x list (cdr x))) ((null x) (cdr ans)) (when (funcall fn (car x)) (setq tem (cdr (rplacd tem (list (car x)))))))))

(let ((big-list (make-big-list))) (benchmark-progn (my-filter-tconc #'evenp big-list)) nil) #|| Timing the evaluation of (MY-FILTER-TCONC #'EVENP BIG-LIST)

User time = 0.390 System time = 0.006 Elapsed time = 0.395 Allocation = 160007208 bytes 0 Page faults GC time = 0.000 ||#

(let ((big-list (make-big-list))) (benchmark-progn (my-filter-tconc #'oddp big-list)) nil) #|| Timing the evaluation of (MY-FILTER-TCONC #'ODDP BIG-LIST)

User time = 0.029 System time = 0.000 Elapsed time = 0.028 Allocation = 14256 bytes 1 Page faults GC time = 0.000 ||#

(let ((big-list (make-big-list))) (time (remove-if-not #'evenp big-list)) nil) #|| Timing the evaluation of (REMOVE-IF-NOT #'EVENP BIG-LIST)

User time = 0.057 System time = 0.003 Elapsed time = 0.060 Allocation = 160007104 bytes 1 Page faults GC time = 0.000 ||#

(let ((big-list (make-big-list))) (time (remove-if-not #'oddp big-list)) nil) #|| Timing the evaluation of (REMOVE-IF-NOT #'ODDP BIG-LIST)

User time = 0.043 System time = 0.000 Elapsed time = 0.042 Allocation = 7144 bytes 1 Page faults GC time = 0.000 ||#


HTML generated by 3bmd in LispWorks 8.0.1

comments powered by Disqus