为什么列表比简单访问的向量更快？

Question

我知道有类似的问题，例如，但即使对于简单的元素访问，列表似乎也比向量更快，这是违反直觉的。这是我的例子：

(let ((x '(0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (nth 9 x) 0))))

(let ((x #(0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (aref x 9) 0))))

在我的机器上，使用 SBCL，第一个块的运行速度几乎是第二个块的两倍。（如果我测试读取访问时间，那么列表和向量的时间几乎相同）。我预计列表会慢 10 倍左右，因为它需要遍历到末尾才能找到第 9 个元素。为什么列表更快？

Answer 1

我无法重现您的观察结果。下面是我测量的内容，以及另外两个使用不同类型数组的测试。首先请注意，我的安装脚本执行以下操作：

(sb-ext:restrict-compiler-policy 'debug 3)
(sb-ext:restrict-compiler-policy 'safety 3)

这可能会对代码编译产生影响。

你的测试

(print :list)
(let ((x (list 0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (nth 9 x) 0))))

(print :simple-vector)
(let ((x (vector 0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (aref x 9) 0))))

轨迹如下：

:LIST 
Evaluation took:
  6.649 seconds of real time
  6.649545 seconds of total run time (6.649545 user, 0.000000 system)
  100.02% CPU
  21,224,869,441 processor cycles
  0 bytes consed


:SIMPLE-VECTOR 
Evaluation took:
  0.717 seconds of real time
  0.716708 seconds of total run time (0.716708 user, 0.000000 system)
  100.00% CPU
  2,287,130,610 processor cycles
  0 bytes consed

关于您的原始问题，使用列表和向量之间的速度因子几乎相差 10 (9.27)。我不知道为什么你的测试显示不同（编辑：显然它与未定义的行为有关，我看到你改变了常量数据并在我的代码中修复了它而不认为它可能是相关的：/）

专用数组

我还尝试尽可能准确地描述数组，方法是在其类型中声明其包含的元素种类 (mod 10) 和数组维度 (10)。 SBCL中实际的数组元素类型是(UNSIGNED-BYTE 4)，这意味着数组很可能被打包：多个数组元素可以存储在一个机器字（32或64位）中。打包适合 space，但当 storing/accessing 个元素时需要 coding/decoding 个步骤。

(print :packed-array)
(let ((x (make-array 10
                     :element-type '(mod 10)
                     :initial-contents '(0 1 2 3 4 5 6 7 8 9))))
  (declare (type (array (mod 10) (10)) x)
           (optimize (speed 3)))
  (time (dotimes (i 1000000000)
          (setf (aref x 9) (the (mod 10) 0)))))

我还有一个版本，其中实际的数组元素类型 (unsigned-byte 32)，应该避免进行转换：

(print :unpacked-array)
(let ((x (make-array 10
                     :element-type '(unsigned-byte 32)
                     :initial-contents '(0 1 2 3 4 5 6 7 8 9))))
  (declare (type (array (unsigned-byte 32) (10)) x)
           (optimize (speed 3)))
  (time (dotimes (i 1000000000)
          (setf (aref x 9) (the (mod 10) 0)))))

其他测试：

:PACKED-ARRAY 
Evaluation took:
  1.168 seconds of real time
  1.167929 seconds of total run time (1.167929 user, 0.000000 system)
  100.00% CPU
  3,727,528,968 processor cycles
  0 bytes consed

在这里您可以看到，在该特定情况下，使用最精确的类型实际上会减慢测试速度。这可能可以用 decoding/encoding 操作的开销来解释 (?)

:UNPACKED-ARRAY 
Evaluation took:
  0.231 seconds of real time
  0.231094 seconds of total run time (0.231094 user, 0.000000 system)
  100.00% CPU
  737,633,062 processor cycles
  0 bytes consed

使用 32 位值的数组，执行时间更短。

如果您调用 disassemble 对两种向量进行测试（只需删除对 time 的调用会增加很多噪音，并可能降低调试级别），最终差异会沸腾循环中使用了哪种类型的寄存器：

简单向量使用 64 位 (RCX)，因为向量必须能够存储 T 类型的对象：

; C0: L2:   B900000000       MOV ECX, 0
; C5:       48894A49         MOV [RDX+73], RCX
; C9:       4883C002         ADD RAX, 2
; CD: L3:   483D00943577     CMP RAX, 2000000000
; D3:       7CEB             JL L2

32位数组测试使用ECX（32位）寄存器。

; 960: L2:   31C9             XOR ECX, ECX
; 962:       894A25           MOV [RDX+37], ECX
; 965:       4883C002         ADD RAX, 2
; 969: L3:   483D00943577     CMP RAX, 2000000000
; 96F:       7CEF             JL L2

另外，偏移量不同，但与类型一致：

- 37 = 4 (bytes) * 9 (index) + 1 (storage for array size?)
- 73 = 8 (bytes) * 9 (index) + 1 (storage for array size?)

Answer 2

奇怪的行为是由于您正在修改常量数据，这可能导致未定义的行为（参见 manual）：

The consequences are undefined if literal objects (including quoted objects) are destructively modified.

如果您更改两个表达式以修改两个非文字数据结构，例如：

(let ((x (list 0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (nth 9 x) 0))))

(let ((x (vector 0 1 2 3 4 5 6 7 8 9)))
  (time (dotimes (i 1000000000) (setf (aref x 9) 0))))

那么结果将完全不同，正如其他答案中所显示的那样。

为什么列表比简单访问的向量更快？

Why are lists faster then vectors for simple access?

sbcl

common-lisp

你的测试

专用数组