#:g1: Allegro CLのfixed-indexスロットアクセスを真似してみる

Posted 2019-10-14 19:51:18 GMT

先日、RedditでAllegro CLのstandard-objectのスロットのアクセスを高速化するオプションについての投稿があり、記事を読んでみたのですが、

第一感としては、何故standard-instance-accessを使わないのだろうか、というところでした。

それとは別にfixed-indexを新機能として紹介していますが、どうも以前にみたことあるなと思ったので、古いAllegro CL 4.3(1996)を確認してみましたが、やはり存在しました。 (パッケージは、closexclで移動した模様)
昔からの隠し機能が公になった、というところなのかもしれません。

;;; Allegro CL 4.3
(defclass foo ()
  ((a :initarg :a clos::fixed-index 2 :accessor foo-a)
   (b :initarg :b clos::fixed-index 3 :accessor foo-b)
   (c :initarg :c :accessor foo-c)))

(defvar *foo-inst* (make-instance 'foo :a 1 :b 2 :c 3))

(defvar *vec* (clos::std-instance-slots *foo-inst*))

USER(13): *vec* #(3 CLOS::..SLOT-UNBOUND.. 1 2) ...

fixed-index系 と standard-instance-access 系は何が違うのか

fixed-index指定は、オブジェクトのスロットの値を保持しているベクタの位置を直に指定するもので、それに加えて、指定されたfixed-indexの最大値とスロットの総数で大きい方をバックエンドのベクタのサイズにするようです。
指定されていない空き地は#<unbound-marker>のようなもので埋まります。

Allegro CLでもAMOPのstandard-instance-accessslot-definition-locationはサポートしており、fixed-indexの値とも連動しています。
fixed-indexが簡単に実装できないか、standard-instance-access & slot-definition-location 系の処理系を眺めてみましたが、大抵はスロット数のサイズのベクタを隙間なく並べ、先頭から番号を振るようです。

fixed-indexを真似してみる

スロットの値を保持するベクタの確保の方法が難という感じですが、とりあえずLispWorks等で真似できるか試してみます。

(ql:quickload :closer-mop))

(defpackage "4fef36ee-23f6-5dff-beb9-070053d5dbbb" (:use :c2cl))

(in-package "4fef36ee-23f6-5dff-beb9-070053d5dbbb")

;; utils (eval-when (:compile-toplevel :load-toplevel :execute) (setf (fdefinition 'a) #'make-instance) (defun fintern (package control-string &rest args) (with-standard-io-syntax (intern (apply #'format nil control-string args) (or package *package*)))) (defmacro <defclass> (name supers slots &rest class-options) `(defconstant ,(fintern (symbol-package name) "<~A>" name) (defclass ,name ,supers ,slots ,@class-options))))

(<defclass> fixed-index-slot-class (standard-class) ())

(defmethod validate-superclass ((c fixed-index-slot-class) (s standard-class)) T)

(<defclass> fixed-index-slot-definition (standard-slot-definition) ((fixed-index :initform nil :initarg fixed-index :accessor slot-definition-fixed-index)))

(<defclass> fixed-index-direct-slot-definition (fixed-index-slot-definition standard-direct-slot-definition) ())

(defmethod direct-slot-definition-class ((c fixed-index-slot-class) &rest initargs) (declare (ignore initargs)) <fixed-index-direct-slot-definition>)

(defmethod compute-effective-slot-definition ((class fixed-index-slot-class) name direct-slot-definitions) (declare (ignore name)) (let ((effective-slotd (call-next-method))) (dolist (slotd direct-slot-definitions) (when (typep slotd <fixed-index-slot-definition>) (setf (slot-definition-location effective-slotd) (slot-definition-fixed-index slotd)) (return))) effective-slotd))

(defmethod compute-slots ((class fixed-index-slot-class)) (let* ((slots (call-next-method))) (loop :for idx :from 0 :repeat (length slots) :do (let* ((s (find idx slots :key #'slot-definition-location))) (unless s (let ((s (find-if (lambda (x) (null (slot-definition-location x))) slots))) (when s (setf (slot-definition-location s) idx)))))) (sort (copy-list slots) #'< :key #'slot-definition-location)))

ちなみに、 effective-slot-definition-class周りを定義していませんが、スロットの順番を指定するだけなので、effective-slotfixed-indexの値を持たせていません。
(アロケーション〜初期化周りを実装するにあたって必要になりそうではあります。)

再現しようとした結果: 飛び飛びに値を保持するベクタをバックエンドにする方法が分からない

上記では、fixed-indexでスロット群の並び順を指定することはできたのですが、LispWorksではアロケーションされたベクタをAllegro CLのfixed-indexの要件を満すように読み書きする方法が分からず仕舞でした。
SBCLはソースが読めるので、そのうち確認してみたいところ。

とりあえず、Allegro CLのfixed-index記事の御題目としては高速化が目的のようなので、速度を計測してみます。

(<defclass> foo ()
  ((a :initarg :a fixed-index 1 :accessor foo-a)
   (b :initarg :b fixed-index 2 :accessor foo-b)
   (c :initarg :c :accessor foo-c))
  (:metaclass fixed-index-slot-class))

;; test
(defparameter *foo-inst* (a <foo> :a 1 :b 2 :c 3))

(declaim (inline std-instance-slots)) (defun std-instance-slots (inst) #+allegro (excl::std-instance-slots inst) #+sbcl (sb-pcl::std-instance-slots inst) #+lispworks (clos::standard-instance-static-slots inst))

(declaim (simple-vector std-instance-slots)) (defparameter *vec* (std-instance-slots *foo-inst*))

(locally (declare (optimize (safety 1) (space 1) (speed 3) (debug 0) (compilation-speed 0))) (defun p1 () (dotimes (i 10000000) (signum (foo-a *foo-inst*)))) (defun p2 () (dotimes (i 10000000) (signum (slot-value *foo-inst* 'a)))) (defun p3 () (dotimes (i 10000000) (signum (svref *vec* 1)))) (defun p4 () (dotimes (i 10000000) (signum (svref (std-instance-slots *foo-inst*) 1)))) (defun p5 () (dotimes (i 10000000) (signum (standard-instance-access *foo-inst* 1)))) )

(progn (time (p1)) (time (p2)) (time (p3)) (time (p4)) (time (p5)) )

LispWorksの場合

LispWorksではバックエンドのベクタをアクセスする方法がstandard-instance-accessなので、Allegro CLの記事のようにバックエンドをベクタを直接取り出してアクセスしたのとほぼ同一な結果になります。
standard-instance-accessがアクセサの60倍強となりAllegro CLの記事の御題目と似たものとなりました。

Timing the evaluation of (p1)

User time = 1.870 System time = 0.000 Elapsed time = 1.868 Allocation = 10816 bytes 0 Page faults ; (top-level-form 15) Timing the evaluation of (p2)

User time = 1.630 System time = 0.000 Elapsed time = 1.619 Allocation = 17584 bytes 0 Page faults ; (top-level-form 15) Timing the evaluation of (p3)

User time = 0.030 System time = 0.000 Elapsed time = 0.033 Allocation = 13184 bytes 0 Page faults ; (top-level-form 15) Timing the evaluation of (p4)

User time = 0.040 System time = 0.000 Elapsed time = 0.035 Allocation = 0 bytes 0 Page faults ; (top-level-form 15) Timing the evaluation of (p5)

User time = 0.040 System time = 0.000 Elapsed time = 0.039 Allocation = 0 bytes 0 Page faults

SBCLの場合

SBCLでは、アクセサもslot-valuestandard-instance-accessでのアクセスと同等まで最適化されるので、どれも速いという結果になりました。
良く考えればこれが理想では?

Evaluation took: (p1)
  0.050 seconds of real time
  0.050000 seconds of total run time (0.050000 user, 0.000000 system)
  100.00% CPU
  163,816,326 processor cycles
  0 bytes consed

Evaluation took: (p2) 0.044 seconds of real time 0.050000 seconds of total run time (0.050000 user, 0.000000 system) 113.64% CPU 145,140,144 processor cycles 0 bytes consed

Evaluation took: (p3) 0.020 seconds of real time 0.020000 seconds of total run time (0.020000 user, 0.000000 system) 100.00% CPU 68,159,274 processor cycles 1,712 bytes consed

Evaluation took: (p4) 0.022 seconds of real time 0.020000 seconds of total run time (0.020000 user, 0.000000 system) 90.91% CPU 71,779,470 processor cycles 0 bytes consed

Evaluation took: (p5) 0.021 seconds of real time 0.020000 seconds of total run time (0.020000 user, 0.000000 system) 95.24% CPU 69,904,809 processor cycles 0 bytes consed

まとめ

Allegro CLのfixed-index機能は面白いとは思うのですが、高速化ということに限っては、SBCLのように何も指定しなくても、 standard-instance-access を使ったのと同等の所まで最適化してくれる方が望ましいでしょう。
fixed-indexでは、特定の位置に特定のデータを配置したものをクラスを跨いで同一のアクセス方法で処理できたりしそうなので、もっと他の使い方があるのでは……、などと思ったり……。


HTML generated by 3bmd in LispWorks 7.0.0

comments powered by Disqus