速度

3つとか5つとかそれくらいのデータをまとめて扱いたい時は割とすぐ defstruct してて、他にも list とか vector とか hash-table とか色々やり方はあるんで、それぞれ速度的にどーなのよ?と。xyzzy だとそこまで速度を気にすることはあんまりない(compile しないで使ってたりするくらいだし、ヘビーな計算とかするなら SBCL とか使うだろうし)のだけど、気になったので調べてみた。

速い方からざっくり。データ型で言うと

  • (simple-)vector, list
  • plist, alist, hash-table
  • structure

アクセスする関数で言うと

  • 速い組み込み関数*1
    • second, cadr, svref, elt
    • first とか car とかでもほぼ変わらない
  • 遅い組み込み関数
    • si:*slot-value, si:*index-slot-value, aref, getf, gethash, assoc
  • defstruct が定義したアクセサ(lisp の関数)

とまぁ、概ね予想通りの結果に。思ってた以上に structure が遅くてしょんぼり。defstruct のアクセサは

(defun struct-y (x)
  (si:*index-slot-value x 1))

という定義で、(si:*index-slot-value X 0) を関数で包んだだけでこんなに遅くなる(359->844 [msec])ってのもしょんぼり。

測定方法

JSON 的に書くと

{x: 1, y: 2, z: 3}

というようなデータを色んな型で用意しておいてテキトーな方法で y の値を1,000,000回取り出すのに掛かった時間を計測。コードは一番下に。

データ

Form Time [msec]
(svref vec 1) 141.0
(elt struct-vec 1) 141.0
(second list) 157.0
(cadr list) 156.0
(elt struct-list 1) 156.0
---壁--- ---壁---
(system:*index-slot-value struct 1) 359.0
(system:*slot-value struct :y) 375.0
(aref vec 1) 375.0
(getf plist :y) 375.0
(cdr (assoc :y alist)) 469.0
(gethash :y hash-table) 421.0
(gethash :y hash-table-eq) 391.0
(gethash :y hash-table-eql) 422.0
(gethash :y hash-table-equal) 406.0
---壁--- ---壁---
(struct-vec-y struct-vec) 625.0
(struct-list-y struct-list) 625.0
(struct-y struct) 844.0

コード

;; これを適当なファイルに保存してコンパイルして *scratch* から
#|
(defvar *bench* t)
(load "ファイル名")
|#
;; すると(はてな記法で)結果が出てくる
;; 上のデータは手動で並べ替えてある

(defvar *bench* nil)

(defmacro BENCH-IT (form)
  `(when *bench*
     (format t "~&|~S|~F|~%"
       ',form
       (let ((start (get-internal-real-time)))
         (dotimes (i 1000000)
           ,form)
         (- (get-internal-real-time) start)))))

(format t "~&|*Form|*Time [msec]|~%")

;; plain list
(setq list '(1 2 3))
(BENCH-IT (second list))
(BENCH-IT (cadr list))

;; property list
(setq plist '(:x 1 :y 2 :z 3))
(BENCH-IT (getf plist :y))


;; associative list
(setq alist '((:x . 1) (:y . 2) (:z . 3)))
(BENCH-IT (cdr (assoc :y alist)))


;; hash-table
(setq hash-table (make-hash-table))
(setf (gethash :x hash-table) 1
      (gethash :y hash-table) 2
      (gethash :z hash-table) 3)

(BENCH-IT (gethash :y hash-table))

(setq hash-table-eq (make-hash-table :test 'eq))
(setf (gethash :x hash-table-eq) 1
      (gethash :y hash-table-eq) 2
      (gethash :z hash-table-eq) 3)

(BENCH-IT (gethash :y hash-table-eq))

(setq hash-table-eql (make-hash-table :test 'eql))
(setf (gethash :x hash-table-eql) 1
      (gethash :y hash-table-eql) 2
      (gethash :z hash-table-eql) 3)

(BENCH-IT (gethash :y hash-table-eql))


(setq hash-table-equal (make-hash-table :test 'equal))
(setf (gethash :x hash-table-equal) 1
      (gethash :y hash-table-equal) 2
      (gethash :z hash-table-equal) 3)

(BENCH-IT (gethash :y hash-table-equal))


;; vector
(setq vec #(1 2 3))

(BENCH-IT (aref vec 1))
(BENCH-IT (svref vec 1))

;; structure
(defstruct struct
  x y z)

(setq struct (make-struct :x 1 :y 2 :z 3))
(BENCH-IT (struct-y struct))
(BENCH-IT (si:*slot-value struct :y))
(BENCH-IT (si:*index-slot-value struct 1))


;; struct-vector
(defstruct (struct-vec (:type vector))
  x y z)
(setq struct-vec (make-struct-vec :x 1 :y 2 :z 3))

(BENCH-IT (struct-vec-y struct-vec))
(BENCH-IT (elt struct-vec 1))

;; struct-list
(defstruct (struct-list (:type list))
  x y z)
(setq struct-list (make-struct-list :x 1 :y 2 :z 3))

(BENCH-IT (struct-list-y struct-list))
(BENCH-IT (elt struct-list 1))

*1:second, cadr は組み込みではなくて、コンパイルすると (car (cdr X) ) にインライン展開される