高效计算多个结果
Efficiently computing multiple results
上下文
我目前正在优化一个用于科学计算的库。我是 Commom Lisp 的新手。我使用的功能非常小，大约可以执行。在普通笔记本电脑上为 10 纳秒到几百纳秒。性能已经非常接近 C，但我想要我能得到的 speed 的每一点。
我使用 SBCL 及其编译器说明和 (time) 宏进行优化（欢迎任何一般性建议）。我目前正在优化一个单线程计算字符串，该字符串将包含在未来的独立线程中。
问题
为了论证，假设我有一个函数 (foo)，它逐项添加两个包含 3 个变量的列表。优化后，它可能类似于：
(defun foo (a1 a2 a3 b1 b2 b3)
(declare (optimize (speed 3))
(type double-float a1 a2 a3 b1 b2 b3))
(list (+ a1 b1) (+ a2 b2) (+ a3 b3)))
我用 :
计时
(time (dotimes (it 1000000 t) (foo 1.0d0 2.0d0 2.351d0 223.0d0 124.2d0 321d0)))
SBCL 备注
据我所知，编译器抱怨 "casting" 列表中的结果很昂贵。
note: doing float to pointer coercion (cost 13)
我想要什么
SBCL 的抱怨似乎是明智的，所以我正在寻找一种方法来消除那些讨厌的列表，无论如何我必须在以后的某个时候再次剥离它们以便将它们提供给其他计算。我愿意为此降低水平并失去（一些）抽象。用例可能如下所示：
(let ((res1 0d0)
(res2 0d0)
(res3 0d0))
(declare (type double-float res1 res2 res3))
(magic-abstraction-I-want res1 res2 res3 (foo 1d0 1d0 1d0 1d0 1d0 1d0)))
有了这个，我可以以最小或不存在的开销进行字符串计算，只做需要的计算，而不用花时间创建列表或访问它们。
我tried/Think 的尝试
内联
我看到简单函数的巨大性能改进，例如 foo 放置 :
时
(declaim (inline foo))
据我了解，它有点像 "expands" 函数，并在调用的级别内联编写它。是这样吗，它到底做了什么？这实际上是我想要的吗？它是否以某种方式解决了 "casting to lists" 的问题？
（此外，如果您从我写的内容中看出我可能误解了某些内容，请随时提供一般的速度优化建议）
编辑：了解 values
之后
我修改了foo，现在是：
(defun foo (a1 a2 a3 b1 b2 b3)
(declare (optimize (speed 3))
(type double-float a1 a2 a3 b1 b2 b3))
(values (+ a1 b1) (+ a2 b2) (+ a3 b3)))
SBCL 仍然输出三个关于将 return 值强制转换为指针的注释。而且我仍在消耗字节，如 :
所测量
(time (dotimes (it 1000000 t) (foo 1.0d0 2.0d0 2.351d0 223.0d0 124.2d0 321d0)))
但是，使用 inline 的调用要快得多并且不会产生任何问题（正如我猜的那样）：
(declaim (inline foo))
;;;;
(let ((r1 0d0) (r2 0d0) (r3 0d0)
(a1 1d0) (a2 2d0) (a3 3d0)
(b1 4d0) (b2 5d0) (b3 6d0))
(declare (optimize (speed 3))
(type double-float r1 r2 r3 a1 a2 a3 b1 b2 b3))
(time (dotimes (it 1000000 t) (setf (values r1 r2 r3) (foo a1 a2 a3 b1 b2 b3)))))
性能与完全相同：
(let ((r1 0d0) (r2 0d0) (r3 0d0)
(a1 1d0) (a2 2d0) (a3 3d0)
(b1 4d0) (b2 5d0) (b3 6d0))
(declare (optimize (speed 3))
(type double-float r1 r2 r3 a1 a2 a3 b1 b2 b3))
(time (dotimes (it 1000000 t)
(setf r1 (+ a1 b1))
(setf r2 (+ a2 b2))
(setf r3 (+ a3 b3)))))
这正是我想要的。最后一个非常小的事情是 SBCL 仍然抱怨 foo 的优化，但我可以把它压下去。
好的，所以我要做的第一件事就是解释“浮点数到指针强制转换”的含义。
（先决条件：了解机器中的内存、位和 C 内存模型的粗略概念）。
在动态类型的 Lisp 中，值具有类型而不是变量。因此，您需要一些一致的内存表示，可用于传递任何类型的任何值，并且您需要能够为此确定类型。 （请注意，在某些强类型函数语言中，可能仍然需要某种结构化内存表示形式来表示垃圾 collection 以跟随指针，或者需要一种统一的方式来表示一个词中的所有指针，以便多态性起作用）。典型的选择是一个指针，它总是一个字（假设是 8 个字节），然后指向的 object 可能有一个 header，其中包含有关其类型的更多信息。在 C 中它看起来像：
struct LispObj_s {
uint32_t length;
uint16_t gc_data;
uint16_t type_code;
union {
int64_t as_smallint;
float as_float
double as_double;
char as_string;
... /* bignums, arrays, cons, structs, etc */
}
}
typedef LispObj_s * LispObj
这很糟糕，因为许多常用的东西（即整数）会产生巨大的开销：一个词用于指向 object 的指针，一个词用于 header（说“我是一个整数，我有 1 个字长”），还有一个代表数字本身。这是 200% 的开销，意味着整数需要指针取消引用和可能的缓存未命中。所以有一个优化：你使用指针的一些最低有效位来说明类型是什么（这些是免费的，因为一切都是 word-aligned 所以三个最低有效位总是 0）。然后你可以得到如果（比如说）最后一位是 0 那么你有一个 fixnum（一个小数字，算术很快，在这种情况下是 63 位），如果你的最后一位是 101 你有一个指向 cons 单元格的指针，如果它们是 111 那么一个指向双精度数的指针，011 一个浮点数和 001 一个指向其他东西的指针。现在整数、cons 和浮点数更便宜，这很好，但缺点是您现在需要更加小心以确保标签始终正确。问题是我们不能像对待整数那样对待双精度数。像处理整数那样仅将 double 的 2 位砍掉是不可行的，尤其是当您希望与外部程序兼容时。
在编译后的代码中，您希望对 objects（如浮点数）本身进行操作，从而将它们以原始形式保存在寄存器或堆栈中。只有编译后的代码才能访问它们并且知道它们是什么类型。
当您想 return 或传递（例如）一个浮点数作为参数时，接收它的代码不一定知道它会得到什么样的 object 以及发送它的代码当然不知道接收者想要某种类型的数据。因此，您需要将它转换为某种统一形式，该形式还说明它是什么类型，为此您需要为其分配一些内存并将标记指针传递给该内存。当调用一个函数时，你不知道被调用函数将如何处理浮点数，因此你不一定（见后面）将它分配到堆栈上，因为被调用者可能例如把它放在一个全局变量中，稍后该变量将指向垃圾数据或未映射的内存。当你 returning 时，情况更糟，因为你将在你自己的堆栈框架中分配浮点数，而你将要销毁它。分配往往很慢（尽管比例如 C 快得多；主要是因为你正在写入内存而不是缓存）并且读取分配的 objects 往往很慢（因为你需要检查和删除标签和取消引用一个指针，并且经常缓存未命中）这就是为什么 sbcl 在优化器必须分配和装箱 object.
时抱怨的原因
要加快分配速度，可以做的一件事是声明动态范围。这告诉 Lisp 你保证 some object 不会在当前动态作用域结束后指向某个地方，因此它可能被分配到堆栈上。堆栈分配更快，本地缓存更多，释放堆栈分配基本上是免费的，因为不涉及 gc。您可以在传递参数时执行此操作，但在 returning.
时则不行
使用 values 有点像 stack-allocating 一个 returned 列表（如果 sbcl 中的动态范围，函数的 &rest 参数也可以堆栈分配）除了它是可能的因此，这是 return 多个值的更有效方法。不幸的是，由于统一的内存表示，无法从中获得分配浮点数的优势。
回答
然而，如果我们知道我们正在调用的函数，我们可以预先 stack-allocate 其 space 的 return 值，然后让函数将其值放在那里。如果我们这样做，我们也可以通过以下方式避免浮点数到指针的强制转换：sbcl 有一个浮点数数组的优化表示，而不是指向浮点数的指针数组，浮点数直接存储（例如 float* 而不是比 float**):
(defun foo3 (a1 a2 a3 b1 b2 b3 result)
(declare (optimize (speed 3) (safety 0))
(type double-float a1 a2 a3 b1 b2 b3)
(type (simple-array double-float (3)) result))
(setf (aref result 0) (+ a1 b1)
(aref result 1) (+ a2 b2)
(aref result 2) (+ a3 b3))
nil)
然后我们可以在下面调用它曲折的方式：
(let ((foo-result (make-array '(3) :element-type 'double-float :initial-element 0d0)))
(declare (dynamic-extent foo-result))
(foo a1 a2 a3 b1 b2 b3 foo-result)
(let ((c1 (aref foo-result 0)) ...)
...))
这样我们为堆栈上的结果分配 space，然后 foo3 填充它们，然后我们将它们从堆栈中提取出来，大概是放入寄存器中。这应该几乎与 foo3 return 将其结果存入寄存器一样快，并且关键是不需要堆分配（（编辑：我不认为这是真的）如果 sbcl 假设函数获胜'改变它可以调用类型 checking/unboxing 直接进入函数的主体）。
不幸的是，语法令人不快，但在 Lisp 中有一种解决方法：宏。可以实现特殊的宏来定义像 foo3 这样的函数和一个特殊的宏来调用和绑定结果，但这很糟糕，因为你现在已经将世界分成两种类型的函数并且你不能使用高阶foo 的函数，您可能正在执行 macros-generating-macros，这很难调试。相反，想法是这样的：我们使用奇怪的调用约定和调用它并设置为内联的包装函数生成一个快速版本。然后，每当我们调用包装器函数时，我们都可以获得快速调用的优势，并且包装器的所有成本都被编译器移除了。
(defmacro fast-defun (name num-values lambda-list &body body)
(assert (and (integerp num-values) (plusp num-values)))
(let ((fast-name (gensym (symbol-name name)))
(result (gensym "RESULT"))
(vars (loop repeat num-values collect (gensym "V")))
`(progn
(defun ,fastname ,(cons result lambda-list) ;;FIXME: this only works if lambda-list is a list of symbols
(declare (optimize (speed 3) (safety 0))
(type (simple-array double-float (,num-values))))
;; Todo: move declarations here from body
(multiple-value-bind ,vars (progn ,@body)
,@(loop for v in vars
for n from 0
collect `(setf (svref ,result ,n) ,v))
nil))
(declaim (inline ,name))
(defun ,name ,lambda-list
(let ((,result (make-array '(,num-values) :element-type 'double-float :initial-element 0d0)))
(declare (dynamic-extent ,result) (optimize (speed 3)))
(,fast-name ,result ,@lambda-list)
(values ,@(loop for n below num-values collect `(aref ,result n))))))))
此宏不是最通用的形式，但您可以像上面的 (defun foo 一样使用它，但 (fast-defun foo 3.
经过更多的实验，似乎实际上并没有更快。不知何故 consing 仍在发生，我不知道如何在不内联所有内容的情况下避免它。我还尝试将输入设为动态范围数组，但这似乎没有帮助。
仔细查看后，我没能找到一种方法来查看编译管道中的中间结果，这让我很难过，但我在源代码中进行了扫描，我认为，尽管编译器可以（有时) 专注于函数的调用，它不能专注于 returning 浮点值。
上下文
我目前正在优化一个用于科学计算的库。我是 Commom Lisp 的新手。我使用的功能非常小，大约可以执行。在普通笔记本电脑上为 10 纳秒到几百纳秒。性能已经非常接近 C，但我想要我能得到的 speed 的每一点。
我使用 SBCL 及其编译器说明和 (time) 宏进行优化（欢迎任何一般性建议）。我目前正在优化一个单线程计算字符串，该字符串将包含在未来的独立线程中。
问题
为了论证，假设我有一个函数 (foo)，它逐项添加两个包含 3 个变量的列表。优化后，它可能类似于：
(defun foo (a1 a2 a3 b1 b2 b3)
(declare (optimize (speed 3))
(type double-float a1 a2 a3 b1 b2 b3))
(list (+ a1 b1) (+ a2 b2) (+ a3 b3)))
我用 :
计时(time (dotimes (it 1000000 t) (foo 1.0d0 2.0d0 2.351d0 223.0d0 124.2d0 321d0)))
SBCL 备注
据我所知，编译器抱怨 "casting" 列表中的结果很昂贵。
note: doing float to pointer coercion (cost 13)
我想要什么
SBCL 的抱怨似乎是明智的，所以我正在寻找一种方法来消除那些讨厌的列表，无论如何我必须在以后的某个时候再次剥离它们以便将它们提供给其他计算。我愿意为此降低水平并失去（一些）抽象。用例可能如下所示：
(let ((res1 0d0)
(res2 0d0)
(res3 0d0))
(declare (type double-float res1 res2 res3))
(magic-abstraction-I-want res1 res2 res3 (foo 1d0 1d0 1d0 1d0 1d0 1d0)))
有了这个，我可以以最小或不存在的开销进行字符串计算，只做需要的计算，而不用花时间创建列表或访问它们。
我tried/Think 的尝试
内联
我看到简单函数的巨大性能改进，例如 foo 放置 :
(declaim (inline foo))
据我了解，它有点像 "expands" 函数，并在调用的级别内联编写它。是这样吗，它到底做了什么？这实际上是我想要的吗？它是否以某种方式解决了 "casting to lists" 的问题？
（此外，如果您从我写的内容中看出我可能误解了某些内容，请随时提供一般的速度优化建议）
编辑：了解 values
之后
我修改了foo，现在是：
(defun foo (a1 a2 a3 b1 b2 b3)
(declare (optimize (speed 3))
(type double-float a1 a2 a3 b1 b2 b3))
(values (+ a1 b1) (+ a2 b2) (+ a3 b3)))
SBCL 仍然输出三个关于将 return 值强制转换为指针的注释。而且我仍在消耗字节，如 :
所测量(time (dotimes (it 1000000 t) (foo 1.0d0 2.0d0 2.351d0 223.0d0 124.2d0 321d0)))
但是，使用 inline 的调用要快得多并且不会产生任何问题（正如我猜的那样）：
(declaim (inline foo))
;;;;
(let ((r1 0d0) (r2 0d0) (r3 0d0)
(a1 1d0) (a2 2d0) (a3 3d0)
(b1 4d0) (b2 5d0) (b3 6d0))
(declare (optimize (speed 3))
(type double-float r1 r2 r3 a1 a2 a3 b1 b2 b3))
(time (dotimes (it 1000000 t) (setf (values r1 r2 r3) (foo a1 a2 a3 b1 b2 b3)))))
性能与完全相同：
(let ((r1 0d0) (r2 0d0) (r3 0d0)
(a1 1d0) (a2 2d0) (a3 3d0)
(b1 4d0) (b2 5d0) (b3 6d0))
(declare (optimize (speed 3))
(type double-float r1 r2 r3 a1 a2 a3 b1 b2 b3))
(time (dotimes (it 1000000 t)
(setf r1 (+ a1 b1))
(setf r2 (+ a2 b2))
(setf r3 (+ a3 b3)))))
这正是我想要的。最后一个非常小的事情是 SBCL 仍然抱怨 foo 的优化，但我可以把它压下去。
好的，所以我要做的第一件事就是解释“浮点数到指针强制转换”的含义。
（先决条件：了解机器中的内存、位和 C 内存模型的粗略概念）。
在动态类型的 Lisp 中，值具有类型而不是变量。因此，您需要一些一致的内存表示，可用于传递任何类型的任何值，并且您需要能够为此确定类型。 （请注意，在某些强类型函数语言中，可能仍然需要某种结构化内存表示形式来表示垃圾 collection 以跟随指针，或者需要一种统一的方式来表示一个词中的所有指针，以便多态性起作用）。典型的选择是一个指针，它总是一个字（假设是 8 个字节），然后指向的 object 可能有一个 header，其中包含有关其类型的更多信息。在 C 中它看起来像：
struct LispObj_s {
uint32_t length;
uint16_t gc_data;
uint16_t type_code;
union {
int64_t as_smallint;
float as_float
double as_double;
char as_string;
... /* bignums, arrays, cons, structs, etc */
}
}
typedef LispObj_s * LispObj
这很糟糕，因为许多常用的东西（即整数）会产生巨大的开销：一个词用于指向 object 的指针，一个词用于 header（说“我是一个整数，我有 1 个字长”），还有一个代表数字本身。这是 200% 的开销，意味着整数需要指针取消引用和可能的缓存未命中。所以有一个优化：你使用指针的一些最低有效位来说明类型是什么（这些是免费的，因为一切都是 word-aligned 所以三个最低有效位总是 0）。然后你可以得到如果（比如说）最后一位是 0 那么你有一个 fixnum（一个小数字，算术很快，在这种情况下是 63 位），如果你的最后一位是 101 你有一个指向 cons 单元格的指针，如果它们是 111 那么一个指向双精度数的指针，011 一个浮点数和 001 一个指向其他东西的指针。现在整数、cons 和浮点数更便宜，这很好，但缺点是您现在需要更加小心以确保标签始终正确。问题是我们不能像对待整数那样对待双精度数。像处理整数那样仅将 double 的 2 位砍掉是不可行的，尤其是当您希望与外部程序兼容时。
在编译后的代码中，您希望对 objects（如浮点数）本身进行操作，从而将它们以原始形式保存在寄存器或堆栈中。只有编译后的代码才能访问它们并且知道它们是什么类型。
当您想 return 或传递（例如）一个浮点数作为参数时，接收它的代码不一定知道它会得到什么样的 object 以及发送它的代码当然不知道接收者想要某种类型的数据。因此，您需要将它转换为某种统一形式，该形式还说明它是什么类型，为此您需要为其分配一些内存并将标记指针传递给该内存。当调用一个函数时，你不知道被调用函数将如何处理浮点数，因此你不一定（见后面）将它分配到堆栈上，因为被调用者可能例如把它放在一个全局变量中，稍后该变量将指向垃圾数据或未映射的内存。当你 returning 时，情况更糟，因为你将在你自己的堆栈框架中分配浮点数，而你将要销毁它。分配往往很慢（尽管比例如 C 快得多；主要是因为你正在写入内存而不是缓存）并且读取分配的 objects 往往很慢（因为你需要检查和删除标签和取消引用一个指针，并且经常缓存未命中）这就是为什么 sbcl 在优化器必须分配和装箱 object.
时抱怨的原因要加快分配速度，可以做的一件事是声明动态范围。这告诉 Lisp 你保证 some object 不会在当前动态作用域结束后指向某个地方，因此它可能被分配到堆栈上。堆栈分配更快，本地缓存更多，释放堆栈分配基本上是免费的，因为不涉及 gc。您可以在传递参数时执行此操作，但在 returning.
时则不行使用 values 有点像 stack-allocating 一个 returned 列表（如果 sbcl 中的动态范围，函数的 &rest 参数也可以堆栈分配）除了它是可能的因此，这是 return 多个值的更有效方法。不幸的是，由于统一的内存表示，无法从中获得分配浮点数的优势。
回答
然而，如果我们知道我们正在调用的函数，我们可以预先 stack-allocate 其 space 的 return 值，然后让函数将其值放在那里。如果我们这样做，我们也可以通过以下方式避免浮点数到指针的强制转换：sbcl 有一个浮点数数组的优化表示，而不是指向浮点数的指针数组，浮点数直接存储（例如 float* 而不是比 float**):
(defun foo3 (a1 a2 a3 b1 b2 b3 result)
(declare (optimize (speed 3) (safety 0))
(type double-float a1 a2 a3 b1 b2 b3)
(type (simple-array double-float (3)) result))
(setf (aref result 0) (+ a1 b1)
(aref result 1) (+ a2 b2)
(aref result 2) (+ a3 b3))
nil)
然后我们可以在下面调用它曲折的方式：
(let ((foo-result (make-array '(3) :element-type 'double-float :initial-element 0d0)))
(declare (dynamic-extent foo-result))
(foo a1 a2 a3 b1 b2 b3 foo-result)
(let ((c1 (aref foo-result 0)) ...)
...))
这样我们为堆栈上的结果分配 space，然后 foo3 填充它们，然后我们将它们从堆栈中提取出来，大概是放入寄存器中。这应该几乎与 foo3 return 将其结果存入寄存器一样快，并且关键是不需要堆分配（（编辑：我不认为这是真的）如果 sbcl 假设函数获胜'改变它可以调用类型 checking/unboxing 直接进入函数的主体）。
不幸的是，语法令人不快，但在 Lisp 中有一种解决方法：宏。可以实现特殊的宏来定义像 foo3 这样的函数和一个特殊的宏来调用和绑定结果，但这很糟糕，因为你现在已经将世界分成两种类型的函数并且你不能使用高阶foo 的函数，您可能正在执行 macros-generating-macros，这很难调试。相反，想法是这样的：我们使用奇怪的调用约定和调用它并设置为内联的包装函数生成一个快速版本。然后，每当我们调用包装器函数时，我们都可以获得快速调用的优势，并且包装器的所有成本都被编译器移除了。
(defmacro fast-defun (name num-values lambda-list &body body)
(assert (and (integerp num-values) (plusp num-values)))
(let ((fast-name (gensym (symbol-name name)))
(result (gensym "RESULT"))
(vars (loop repeat num-values collect (gensym "V")))
`(progn
(defun ,fastname ,(cons result lambda-list) ;;FIXME: this only works if lambda-list is a list of symbols
(declare (optimize (speed 3) (safety 0))
(type (simple-array double-float (,num-values))))
;; Todo: move declarations here from body
(multiple-value-bind ,vars (progn ,@body)
,@(loop for v in vars
for n from 0
collect `(setf (svref ,result ,n) ,v))
nil))
(declaim (inline ,name))
(defun ,name ,lambda-list
(let ((,result (make-array '(,num-values) :element-type 'double-float :initial-element 0d0)))
(declare (dynamic-extent ,result) (optimize (speed 3)))
(,fast-name ,result ,@lambda-list)
(values ,@(loop for n below num-values collect `(aref ,result n))))))))
此宏不是最通用的形式，但您可以像上面的 (defun foo 一样使用它，但 (fast-defun foo 3.
经过更多的实验，似乎实际上并没有更快。不知何故 consing 仍在发生，我不知道如何在不内联所有内容的情况下避免它。我还尝试将输入设为动态范围数组，但这似乎没有帮助。
仔细查看后，我没能找到一种方法来查看编译管道中的中间结果，这让我很难过，但我在源代码中进行了扫描，我认为，尽管编译器可以（有时) 专注于函数的调用，它不能专注于 returning 浮点值。