时间戳

首页 > 解决方案 > Common Lisp SBCL 中函数调用的性能

common-lisp - Common Lisp SBCL 中函数调用的性能

问题描述

我是 Common Lisp 的新手，遇到了一个让我觉得很奇怪的性能问题。我正在循环使用 rem 检查一个数字是否可以被 10 整除。如果我将检查移到一个函数中，它的运行速度会慢 5 倍。什么会导致这种情况？

我在 64 位 Ubuntu 18.04 上运行 sbcl 1.4.5。

(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

标签： common-lispbenchmarkingdead-code

解决方案

Common Lisp 允许动态重新定义函数：如果您fn在大约 第二次测试的 5 秒，运行循环将切换到调用新定义的fnwhile running。此功能对如何编译函数调用以及如何在需要时优化它们有一些限制。

正如 RainerJoswing 在评论中指出的那样，以上是过度简化，在某些情况下编译器可能会假设函数没有重新定义（递归函数，同一文件中的函数），请参见3.2.2.3 语义约束，例如：

文件中对同一文件中定义的命名函数的调用引用该函数，除非该函数已声明为 notinline。如果函数在运行时单独重新定义或在同一文件中多次定义，后果是不确定的。

一个函数混合了错误检查和您希望它执行的计算。在函数调用边界处，您通常有一个序言来检查您的输入，以及一个结果可能被“装箱”的结语：如果编译器知道本地变量始终是单浮点数，它可以在期间使用浮点数的原始表示函数的范围，但是当返回结果时，它应该是一个有效的 Lisp 类型，例如，这意味着将其强制回一个标记值。

SBCL 编译器试图确保代码是安全的，其中安全意味着永远不会调用在 Lisp 规范中具有未定义行为的代码。但是请注意，如果您fn使用字符串输入进行调用，则代码应该会检测到类型错误。与 C 不同，Lisp 中运行时的类型错误是明确定义的（只要声明的类型（默认为 T）包含运行时所有可能的值）。因此，为了安全而编译 Lisp 代码往往会在程序的多个点添加大量错误检查。

优化代码包括删除保证始终正确的检查，消除生成代码中的死分支。例如，如果你fn单独考虑，你可以看到每次调用它时都必须检查它的输入，因为它很可能用字符串输入来调用。但是当您直接内联操作时，i可以将索引静态确定为整数，这允许调用=和rem应用而无需（大量）错误检查。

SBCL 中的优化之所以发生，是因为有一个静态分析将变量映射到 Lisp 类型格的元素（and并且or基本上是类型的最大下限和最低上限，两端都有类型T和类型）。nilSBCL 只报告肯定会发生的错误：如果你调用一个接受从 0 到 5 的整数的函数，如果你用一个已知总是高于 5 或​​低于 0 的输入调用它，那么你就有一个错误（两个集合没有交集） )，但是如果使用 2 到 10 之间的整数调用它，则不会发出警告。这是安全的，因为编译器可以在运行时延迟错误检查，这与运行时没有类型感的其他语言相反（每次尝试警告代码可能考虑到 Lisp 的开放性，有错误会导致很多警告）。

您可以(declaim (inline fn))在您的文件中再将性能与第一个版本相同。一个经验法则是，在函数内部，事情比在全局环境中更加静态：不能重新定义局部函数，可以精确定义局部变量的类型等。您可以更好地控制始终正确的内容。

请注意，如果执行很长时间（相对于其余代码），错误检查的开销是一个问题。(simple-array single-float)如果您用单浮点数填充一个大数组并在其上应用数字代码，则使用专门的数组类型（如）或将局部变量声明为浮点数是有意义的(declare (type single-float x))，这样您就不会检查每个值是否为有效地浮动。在其他情况下，开销不足以花费太多时间来减少它。

推荐阅读