Common Lisp SBCL 中函数调用的性能
Performance of function call in Common Lisp SBCL
我是 Common Lisp 的新手，运行 是一个让我觉得很奇怪的性能事物。我在循环中使用 rem 检查数字是否可以被 10 整除。如果我将检查移到一个函数中，它的运行速度会慢 5 倍。什么会导致这种情况？
我是 运行 64 位上的 sbcl 1.4.5 Ubuntu 18.04.
(defun fn (x)
(= 0 (rem x 10))
)
(defun walk-loop-local (n)
(loop for i from 1 to n do
(= 0 (rem i 10))
))
(defun walk-loop-func (n)
(loop for i from 1 to n do
(fn i)
))
(time (walk-loop-local 232792560))
(time (walk-loop-func 232792560))
我希望时间相同（而且会快很多，但这是一个单独的问题）。相反，这是输出，
CL-USER> (load "loops.lisp")
Evaluation took:
0.931 seconds of real time
0.931389 seconds of total run time (0.931389 user, 0.000000 system)
100.00% CPU
2,414,050,454 processor cycles
0 bytes consed
Evaluation took:
4.949 seconds of real time
4.948967 seconds of total run time (4.948967 user, 0.000000 system)
100.00% CPU
12,826,853,706 processor cycles
0 bytes consed
每个函数调用都会增加开销。这就是你正在测量的。
您可以声明函数 fn 是内联的，还可以尝试修改编译器标志以优化运行时执行（与调试信息或安全性相反）。我现在在 phone，但如果需要可以添加超规格 link。
BR，埃里克
Common Lisp 允许动态重新定义函数：如果您在大约期间重新定义 fn。在第二次测试的 5 秒后，运行 循环将切换到调用 fn while 运行 的新定义。此功能对如何编译函数调用以及如何在需要时优化它们有一些限制。
正如 RainerJoswing 在评论中指出的那样，上面是一个 over-simplification，在某些情况下编译器可能会假设函数没有被重新定义（递归函数，同一文件中的函数），参见 3.2.2.3 Semantic Constraints，例如：
A call within a file to a named function that is defined in the same
file refers to that function, unless that function has been declared
notinline. The consequences are unspecified if functions are redefined
individually at run time or multiply defined in the same file.
一个函数混合了错误检查和您希望它执行的计算。在函数调用边界处，您通常有一个检查输入的序言和一个结果可能为 "boxed" 的结尾：如果编译器知道局部变量始终为 single-float，它可以使用原始在函数范围内表示浮点数，但在返回结果时，它应该是有效的 Lisp 类型，这意味着将其强制转换回标记值，例如。
SBCL 编译器会尝试确保代码安全，其中 安全 意味着永远不会调用在 Lisp 规范中具有未定义行为的代码。但是请注意，如果您使用字符串输入调用 fn，代码将检测到类型错误。与 C 不同，Lisp 中的 type-error 在运行时是 well-defined （只要 声明的 类型默认为 T，在运行时包含所有可能的值）。因此，为了安全而编译 Lisp 代码往往会在程序的多个点添加大量错误检查。
优化代码包括删除保证始终为真的检查，消除生成代码中的死分支。
例如，如果单独考虑 fn，您会发现它 必须在每次调用时检查其输入，因为它很可能会使用字符串输入来调用.但是当你直接内联操作时，索引 i 可以被静态确定为一个整数，这允许调用 = 和 rem 而不需要（很多）错误检查。
SBCL 中的优化发生是因为有一个静态分析将变量映射到 Lisp 类型格的元素（and 和 or 基本上是类型的最大下限和最低上限, 类型 T 和类型 nil 在两端）。 SBCL 只报告肯定会发生的错误：如果你调用一个接受 0 到 5 整数的函数，如果你用一个已知总是大于 5 或小于 0 的输入调用它，你就会出错（两组没有交集), 但如果你用 2 到 10 之间的整数调用它，则不会发出警告。这是安全的，因为编译器可以在运行时推迟错误检查，这与运行时没有类型感的其他语言相反（每次尝试警告鉴于 Lisp 的 open-worldness，代码 可能 有错误会导致大量警告。
您可以 (declaim (inline fn)) 在您的文件中，然后性能将与第一个版本相同。一个经验法则是，在函数内部，事物比在全局环境中更静态：局部函数不能重新定义，局部变量可以精确定义它们的类型，等等。你可以更好地控制什么总是为真。
请注意，如果执行很多时间（相对于代码的其余部分），错误检查的开销就是一个问题。如果用 single-float 填充一个大数组并在其上应用数字代码，则使用专门的数组类型（如 (simple-array single-float) 或使用 [=23= 将局部变量声明为浮点数是有意义的]，这样您就不会检查每个值是否实际上是一个浮点数。在其他情况下，开销不够高，无法花费太多时间来减少它。
您正在使用 SBCL 编译器：
(defun walk-loop-local (n)
(loop for i from 1 to n do
(= 0 (rem i 10))))
我认为您的代码在循环迭代中没有执行任何操作。它被优化掉了，因为 = 形式的值没有在任何地方使用并且没有 side-effects.
因此没有开销，因为没有代码。
使用(disassemble #'walk-local-form)查看编译代码
If I move the check into a function, it runs 5x slower. What would cause that?
不是什么都不做，而是在每次迭代中调用函数并执行您的代码。
实际测量调用开销
(defparameter *i* nil)
(defun walk-loop-local (n)
(loop for i from 1 to n do
(setf *i* (= 0 (rem i 10)))))
(defun fn (x)
(setf *i* (= 0 (rem x 10))))
(defun walk-loop-func (n)
(loop for i from 1 to n do
(fn i)))
在上述情况下，代码不会被删除。
CL-USER> (time (walk-loop-local 232792560))
Evaluation took:
5.420 seconds of real time
5.412637 seconds of total run time (5.399134 user, 0.013503 system)
99.87% CPU
6,505,078,020 processor cycles
0 bytes consed
NIL
CL-USER> (time (walk-loop-func 232792560))
Evaluation took:
6.235 seconds of real time
6.228447 seconds of total run time (6.215409 user, 0.013038 system)
99.89% CPU
7,481,974,847 processor cycles
0 bytes consed
可以看到函数调用的开销并没有那么大。
我是 Common Lisp 的新手，运行 是一个让我觉得很奇怪的性能事物。我在循环中使用 rem 检查数字是否可以被 10 整除。如果我将检查移到一个函数中，它的运行速度会慢 5 倍。什么会导致这种情况？
我是 运行 64 位上的 sbcl 1.4.5 Ubuntu 18.04.
(defun fn (x)
(= 0 (rem x 10))
)
(defun walk-loop-local (n)
(loop for i from 1 to n do
(= 0 (rem i 10))
))
(defun walk-loop-func (n)
(loop for i from 1 to n do
(fn i)
))
(time (walk-loop-local 232792560))
(time (walk-loop-func 232792560))
我希望时间相同（而且会快很多，但这是一个单独的问题）。相反，这是输出，
CL-USER> (load "loops.lisp")
Evaluation took:
0.931 seconds of real time
0.931389 seconds of total run time (0.931389 user, 0.000000 system)
100.00% CPU
2,414,050,454 processor cycles
0 bytes consed
Evaluation took:
4.949 seconds of real time
4.948967 seconds of total run time (4.948967 user, 0.000000 system)
100.00% CPU
12,826,853,706 processor cycles
0 bytes consed
每个函数调用都会增加开销。这就是你正在测量的。
您可以声明函数 fn 是内联的，还可以尝试修改编译器标志以优化运行时执行（与调试信息或安全性相反）。我现在在 phone，但如果需要可以添加超规格 link。
BR，埃里克
Common Lisp 允许动态重新定义函数：如果您在大约期间重新定义 fn。在第二次测试的 5 秒后，运行 循环将切换到调用 fn while 运行 的新定义。此功能对如何编译函数调用以及如何在需要时优化它们有一些限制。
正如 RainerJoswing 在评论中指出的那样，上面是一个 over-simplification，在某些情况下编译器可能会假设函数没有被重新定义（递归函数，同一文件中的函数），参见 3.2.2.3 Semantic Constraints，例如：
A call within a file to a named function that is defined in the same file refers to that function, unless that function has been declared notinline. The consequences are unspecified if functions are redefined individually at run time or multiply defined in the same file.
一个函数混合了错误检查和您希望它执行的计算。在函数调用边界处，您通常有一个检查输入的序言和一个结果可能为 "boxed" 的结尾：如果编译器知道局部变量始终为 single-float，它可以使用原始在函数范围内表示浮点数，但在返回结果时，它应该是有效的 Lisp 类型，这意味着将其强制转换回标记值，例如。
SBCL 编译器会尝试确保代码安全，其中 安全 意味着永远不会调用在 Lisp 规范中具有未定义行为的代码。但是请注意，如果您使用字符串输入调用 fn，代码将检测到类型错误。与 C 不同，Lisp 中的 type-error 在运行时是 well-defined （只要 声明的 类型默认为 T，在运行时包含所有可能的值）。因此，为了安全而编译 Lisp 代码往往会在程序的多个点添加大量错误检查。
优化代码包括删除保证始终为真的检查，消除生成代码中的死分支。
例如，如果单独考虑 fn，您会发现它 必须在每次调用时检查其输入，因为它很可能会使用字符串输入来调用.但是当你直接内联操作时，索引 i 可以被静态确定为一个整数，这允许调用 = 和 rem 而不需要（很多）错误检查。
SBCL 中的优化发生是因为有一个静态分析将变量映射到 Lisp 类型格的元素（and 和 or 基本上是类型的最大下限和最低上限, 类型 T 和类型 nil 在两端）。 SBCL 只报告肯定会发生的错误：如果你调用一个接受 0 到 5 整数的函数，如果你用一个已知总是大于 5 或小于 0 的输入调用它，你就会出错（两组没有交集), 但如果你用 2 到 10 之间的整数调用它，则不会发出警告。这是安全的，因为编译器可以在运行时推迟错误检查，这与运行时没有类型感的其他语言相反（每次尝试警告鉴于 Lisp 的 open-worldness，代码 可能 有错误会导致大量警告。
您可以 (declaim (inline fn)) 在您的文件中，然后性能将与第一个版本相同。一个经验法则是，在函数内部，事物比在全局环境中更静态：局部函数不能重新定义，局部变量可以精确定义它们的类型，等等。你可以更好地控制什么总是为真。
请注意，如果执行很多时间（相对于代码的其余部分），错误检查的开销就是一个问题。如果用 single-float 填充一个大数组并在其上应用数字代码，则使用专门的数组类型（如 (simple-array single-float) 或使用 [=23= 将局部变量声明为浮点数是有意义的]，这样您就不会检查每个值是否实际上是一个浮点数。在其他情况下，开销不够高，无法花费太多时间来减少它。
您正在使用 SBCL 编译器：
(defun walk-loop-local (n)
(loop for i from 1 to n do
(= 0 (rem i 10))))
我认为您的代码在循环迭代中没有执行任何操作。它被优化掉了，因为 = 形式的值没有在任何地方使用并且没有 side-effects.
因此没有开销，因为没有代码。
使用(disassemble #'walk-local-form)查看编译代码
If I move the check into a function, it runs 5x slower. What would cause that?
不是什么都不做，而是在每次迭代中调用函数并执行您的代码。
实际测量调用开销
(defparameter *i* nil)
(defun walk-loop-local (n)
(loop for i from 1 to n do
(setf *i* (= 0 (rem i 10)))))
(defun fn (x)
(setf *i* (= 0 (rem x 10))))
(defun walk-loop-func (n)
(loop for i from 1 to n do
(fn i)))
在上述情况下，代码不会被删除。
CL-USER> (time (walk-loop-local 232792560))
Evaluation took:
5.420 seconds of real time
5.412637 seconds of total run time (5.399134 user, 0.013503 system)
99.87% CPU
6,505,078,020 processor cycles
0 bytes consed
NIL
CL-USER> (time (walk-loop-func 232792560))
Evaluation took:
6.235 seconds of real time
6.228447 seconds of total run time (6.215409 user, 0.013038 system)
99.89% CPU
7,481,974,847 processor cycles
0 bytes consed
可以看到函数调用的开销并没有那么大。