arrays - 数组 "view"可能在不同类型的数组上吗？

Question

假设，您想要为字节数组创建 16 位、32 位、64 位“ View ”，其行为就像它们本身是类型化数组一样。

想到的第一个解决方案不起作用(正如规范所指出的):

(defvar *r* (make-array 64 :element-type '(unsigned-byte 8)
                           :initial-contents
                            (loop for i below 64 collecting i)))

(defvar *r16* (make-array 32 :element-type '(unsigned-byte 16)
                             :displaced-to *r*))

; Evaluation aborted on #<SIMPLE-ERROR "Array element type of
; :DISPLACED-TO array does not match specified element type
; {10053520F3}>.

但如果它能工作那就太好了，因为它将允许在字节或单词方面进行非常有效的查找。

因此，这个问题是在询问性能相同但可行的替代想法。

如果它们能满足我的需要，我愿意接受与 ffi 相关的“黑客”。 CLOS 解决方案对我来说可能不够“快”。

Answer 1

这里有两种方法(第二种更好)。

第一种方法将数组存储为字节并重新创建更大的数量。这显然不是一个理想的方法(原因见下文)。这个例子

• 知道您想用 8 位字节来表示 64 位字；
• 将使字节访问速度更快，而字访问速度稍慢；
• 根本没有优化。

在现实生活中，如果您希望速度更快，您可能需要连接字和字节大小，以便声明可以工作。显然，您可以而且应该编写将为您生成适当代码的宏，因此，如果您改变主意，则无需寻找每个假设。

它的作用是将 64 位字的数组存储为 8 位字节的二维数组。这使得索引算术稍微容易一些，并且可能不会使访问变慢(或者如果有声明则不会变慢)。但您可能只想试验一维数组并自己进行索引算术。然后有 8 位字节和 64 位字的访问器:编写中间的访问器会很容易。

这需要快速的是至少声明，并且展开两个循环将有助于我期望(同样，如果此代码是由宏编写的，那就很容易了):

(defun 64-bit-word-array-length (a)
  (array-dimension a 0))

(defun byte-ref (a n b)
  (aref a n b))

(defun (setf byte-ref) (v a n b)
  (setf (aref a n b) v))

(defun 64-bit-word-ref (a n)
  ;; Unroll this loop in real life, add types
  (let ((v 0))
    (dotimes (c 8 v)
      (setf (ldb (byte 8 (* c 8)) v)
            (aref a n c)))))

(defun (setf 64-bit-word-ref) (v a n)
  (dotimes (c 8 v)
    (setf (aref a n c)
          (ldb (byte 8 (* c 8)) v))))

(defun make-64-bit-word-array (n &key (initial-element 0 initial-element-p))
  (let ((a (make-array (list n bytes/word)
                       :element-type '(unsigned-byte 8))))
    (when initial-element-p
      (dotimes (i n)
        (setf (64-bit-word-ref a i) initial-element)))
    a))

现在:

> (make-64-bit-word-array 2 :initial-element 999)
#2A((231 3 0 0 0 0 0 0) (231 3 0 0 0 0 0 0))

> (64-bit-word-ref (make-64-bit-word-array 2 :initial-element 999) 1)
999

第一种方法的缺点是每次读取/存储时需要进行多个(最多 4 个)数组引用，这是一个坏主意，即使这些数组引用在内存中彼此接近。

因此，第二种方法将内容存储为 64 位字，然后屏蔽并将内容从字中移出。这是一种更好的方法，因为它每次函数调用不超过一个数组引用，而数组引用会花费时间。这个例子:

• 再次知道您正在谈论 64 位数量等等；
• 有一些基本的类型声明(但我根本没有检查性能)
• 具有用于 8 位、16 位和 32 位访问的示例函数。

(deftype array-index () 
  `(integer 0 (,array-dimension-limit)))

(deftype 64-bit-word-array ()
  '(array (unsigned-byte 64) (*)))

(defun make-64-bit-word-array (n &key (initial-element 0 initial-element-p))
  (declare (type array-index n)
           (type (unsigned-byte 64) initial-element))
  (if initial-element-p
      (make-array n :element-type '(unsigned-byte 64)
                  :initial-element initial-element)
    (make-array n :element-type '(unsigned-byte 64))))

(defun 64-bit-word-array-byte-length (a)
  (declare (type 64-bit-word-array a))
  (* (array-dimension a 0) 8))

(defun 64-bit-word-array-byte-ref (a n)
  (declare (type 64-bit-word-array a)
           (type array-index n))
  (multiple-value-bind (b o) (floor n 8)
    (ldb (byte 8 (* o 8)) (aref a b))))

(defun (setf 64-bit-word-array-byte-ref) (v a n)
  (declare (type (unsigned-byte 8) v)
           (type array-index n)
           (type 64-bit-word-array a))
  (multiple-value-bind (b o) (floor n 8)
    (setf (ldb (byte 8 (* o 8)) (aref a b)) v)))

(defun 64-bit-word-array-16-bit-word-ref (a n)
  (declare (type 64-bit-word-array a)
           (type array-index n))
  (multiple-value-bind (b o) (floor n 4)
    (ldb (byte 16 (* o 16)) (aref a b))))

(defun (setf 64-bit-word-array-16-bit-word-ref) (v a n)
  (declare (type (unsigned-byte 16) v)
           (type array-index n)
           (type 64-bit-word-array a))
  (multiple-value-bind (b o) (floor n 4)
    (setf (ldb (byte 16 (* o 16)) (aref a b)) v)))


(defun 64-bit-word-array-32-bit-word-ref (a n)
  (declare (type 64-bit-word-array a)
           (type array-index n))
  (multiple-value-bind (b o) (floor n 2)
    (ldb (byte 32 (* o 32)) (aref a b))))

(defun (setf 64-bit-word-array-32-bit-word-ref) (v a n)
  (declare (type (unsigned-byte 32) v)
           (type array-index n)
           (type 64-bit-word-array a))
  (multiple-value-bind (b o) (floor n 2)
    (setf (ldb (byte 32 (* o 32)) (aref a b)) v)))

我认为从第二个版本派生的东西应该在 epsilon 内尽可能快:数组访问是昂贵的，而对立即整数的掩码和移位操作应该非常便宜。