arrays - `replace` 与普通 `loop` 在 SBCL 中复制大型数组

Question

问题描述

假设您想要在 SBCL 中复制大型专用数组。当然，您希望它速度快、内存效率高，并且语法良好。

执行此操作的两种方法是:

(defparameter *arr1* (make-array 100000 :element-type 'double-float
                                        :initial-element 1d0))
(defparameter *arr2* (make-array 100000 :element-type 'double-float
                                        :initial-element 0d0))

;; First method
(replace arr2 arr1 :start1 20000 :end1 90000)
;; Second method
(loop for i from 20000 below 90000 do
  (setf (aref arr2 i) (aref arr1 i)))

乍一看，replace 似乎更好，因为它的语法紧凑，但基准测试结果阻止我一直使用它。

比较replace与loop的性能

我怀疑这高度依赖于平台和编译器。我在 AMD Ryzen 第一代 CPU 上的 Linux x86_64 5.1.3_1 上使用了 SBCL 1.5.2。

为了进行比较，让我们编写一些测试:

(defun spec-replace (arr1 arr2)
  (declare (type (simple-array double-float) arr1 arr2)
                 (optimize (speed 3)))
  (replace arr2 arr1 :start1 20000 :end1 90000))

(defun spec-loop (arr1 arr2)
  (declare (type (simple-array double-float) arr1 arr2)
                 (optimize (speed 3)))
  (loop for i from 20000 below 90000 do
    (setf (aref arr2 i) (aref arr1 i))))

(declaim (inline spec-loop spec-replace))

(let ((arr1 (make-array 100000 :element-type 'double-float
                               :initial-element 1d0))
      (arr2 (make-array 100000 :element-type 'double-float
                               :initial-element 0d0)))
  (time (spec-replace arr1 arr2))
  (time (spec-loop arr1 arr2)))

您有以下选择:

• 切换每个功能的(速度 3)。
• 切换每个函数的内联声明。

结果似乎是这样的:

• spec-loop 和 spec-replace 在优化或未优化但均未内联时与 CPU 周期数相关。
当两个函数都内联时，
• spec-loop 具有巨大的优势。速度介于 x3 或 x4 之间。
• 完全优化的 spec-loop 的 disassemble 输出比 spec-replace 短很多。

问题

1. 由于这两种方法相当简单，并且在概念上执行相同的操作，为什么 SBCL 不能将它们优化为完全相同的编译指令？除了尚未在 SBCL 中实现之外，还有其他原因吗？
2. 使用 replace 语法编写扩展为 loop 方法的宏有用吗？
3. 我猜测循环优化是以更高的内存使用为代价的，因为默认优化和(速度3)之间存在差异。在大量使用这种操作的大型项目中，我是否会遇到 yield 递减点？

当然，这一切的答案是:根据具体情况进行测试。但是有人可以分享一些关于此类问题的智慧吗？

Answer 1

询问 REPLACE 的来源会导致不同的可能来源(Emacs + Slime、M-.(元点)):

..../sbcl/src/code/seq.lisp
  (DEFUN REPLACE)
..../sbcl/src/compiler/seqtran.lisp
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY CHARACTER (*)) SIMPLE-BASE-STRING &REST T) "optimize")
  (:DEFTRANSFORM REPLACE (SIMPLE-BASE-STRING (SIMPLE-ARRAY CHARACTER (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE (SIMPLE-VECTOR SIMPLE-VECTOR &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (COMPLEX DOUBLE-FLOAT) (*)) (SIMPLE-ARRAY (COMPLEX DOUBLE-FLOAT) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (COMPLEX SINGLE-FLOAT) (*)) (SIMPLE-ARRAY (COMPLEX SINGLE-FLOAT) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (SIGNED-BYTE 64) (*)) (SIMPLE-ARRAY (SIGNED-BYTE 64) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY FIXNUM (*)) (SIMPLE-ARRAY FIXNUM (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (SIGNED-BYTE 32) (*)) (SIMPLE-ARRAY (SIGNED-BYTE 32) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (SIGNED-BYTE 16) (*)) (SIMPLE-ARRAY (SIGNED-BYTE 16) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (SIGNED-BYTE 8) (*)) (SIMPLE-ARRAY (SIGNED-BYTE 8) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 64) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 64) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 63) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 63) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 62) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 62) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 32) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 32) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 31) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 31) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 16) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 16) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 15) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 15) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 8) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 8) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 7) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 7) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 4) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 4) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY (UNSIGNED-BYTE 2) (*)) (SIMPLE-ARRAY (UNSIGNED-BYTE 2) (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE (SIMPLE-BIT-VECTOR SIMPLE-BIT-VECTOR &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY DOUBLE-FLOAT (*)) (SIMPLE-ARRAY DOUBLE-FLOAT (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY SINGLE-FLOAT (*)) (SIMPLE-ARRAY SINGLE-FLOAT (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE ((SIMPLE-ARRAY CHARACTER (*)) (SIMPLE-ARRAY CHARACTER (*)) &REST T) "optimize")
  (:DEFTRANSFORM REPLACE (SIMPLE-BASE-STRING SIMPLE-BASE-STRING &REST T) "optimize")
..../sbcl/src/compiler/knownfun.lisp
  (:DEFOPTIMIZER REPLACE SB-C:DERIVE-TYPE)
..../sbcl/src/compiler/fndb.lisp
  (DECLAIM REPLACE SB-C:DEFKNOWN)

我们感兴趣的是 SIMPLE-ARRAY 或 DOUBLE-FLOAT 的优化器。遵循交叉引用会导致 sbcl/src/compiler/seqtran.lisp 中出现一些可疑的行，调用宏 (define-replace-transforms) (位于第 999 行)最终依赖于同一文件中的 !make-replace-transform。

该函数前面有一个关于如何实现循环的大注释。

代码分支到不同的实现，但是函数中直接可见的一个实现可能对测试有用，作为另一个基准，基于函数的注释；内容如下:

    (do ((i start1 (1+ i))
         (j start2 (1+ j))
         (end (+ start1 replace-len)))
        ((>= i end))
      (declare (optimize (insert-array-bounds-checks 0)))
      (setf (aref seq1 i) (aref seq2 j)))

例如，执行 do 循环的结果如下:

(deftype double-array () '(simple-array double-float (*)))

(declaim (type double-array *arr1* *arr2*))

(defparameter *arr1*
  (make-array 100000 :element-type 'double-float
                     :initial-element 1d0))

(defparameter *arr2*
  (make-array 100000 :element-type 'double-float
                     :initial-element 0d0))

(defun spec-from-source (&aux (arr1 *arr1*) (arr2 *arr2*))
  (declare (type double-array arr1 arr2)
           (optimize (speed 3) (debug 0) (safety 0)))
  (let ((start1 20000) (start2 0) (replace-len #.(- 90000 20000)))
    (do ((i start1 (1+ i))
         (j start2 (1+ j))
         (end (+ start1 replace-len)))
        ((>= i end))
      (declare (optimize (sb-c::insert-array-bounds-checks 0)))
      (setf (aref arr1 i) (aref arr2 j)))))

测试如下:

替换

(time
 (dotimes (i 2000)
   (spec-replace)))

Evaluation took:
  0.201 seconds of real time
  0.200000 seconds of total run time (0.200000 user, 0.000000 system)
  99.50% CPU
  481,862,984 processor cycles
  0 bytes consed

循环

(time
 (dotimes (i 2000)
   (spec-loop)))

Evaluation took:
  0.130 seconds of real time
  0.132000 seconds of total run time (0.132000 user, 0.000000 system)
  101.54% CPU
  312,538,278 processor cycles
  0 bytes consed

正如阅读源代码所预期的那样

(time
 (dotimes (i 2000)
   (spec-from-source)))

Evaluation took:
  0.097 seconds of real time
  0.096000 seconds of total run time (0.096000 user, 0.000000 system)
  98.97% CPU
  231,766,644 processor cycles
  0 bytes consed

根据性能的不同，我看起来不像您编写的代码那样扩展为上面的代码。 SPEC-REPLACE 的反汇编显示

; C2B:       E828AAB6FD       CALL #x2036D658                 ; #<FDEFN SB-KERNEL:UB64-BASH-COPY>

它调用一个所谓的bash-copy函数，这是!make-replace-transform中COND中的第一个情况。经过一点调查，!define-byte-bashers 和 frob-bash-transform 成为值得研究的有趣函数。看起来像 unary-bash-name 引用的函数正在做大量工作来寻找如何为不同情况编写专门的代码。

1. 我不熟悉该代码，但至少源代码是可用的；然而，它需要更多的时间来理解它是如何工作的，以及编译器在优化时如何选择一个路径或另一个路径。

2. 这可能是向 SBCL 开发人员询问的好问题(sbcl-help 邮件列表)。

3. 请注意，如果您需要大量优化这种情况，DO 方法是这里最快的方法。看起来“byte-basher”系列函数可能更加专业，但我对此不确定。如果您了解更多相关信息，请考虑添加答案。