Common Lisp编译和执行时间

Question

我有一个lisp文件，其中包含许多循环中的抽样、文件I/O和算术操作。(我在common lisp中进行粒子滤波。) 我使用compile-file命令编译我的lisp文件。我还在我的lisp文件开头使用(declaim (optimize (speed 3) (debug 0) (safety 0)))，因为我希望尽快得到结果。
我使用(time (load "/....../myfile.lisp")和(time (load "/......./myfile.dx64fsl")来测量速度。问题是编译对我没有任何优势，没有改善。我做错了什么吗？有没有办法改进？速度是最重要的标准，所以我可以在获取快速响应方面牺牲很多。我对这种问题一无所知，因此任何帮助将不胜感激。
此外，当我将粒子数量(每个粒子都是大小约为40的向量)增加到10000时，代码变得非常缓慢，所以可能存在一些内存问题。
非常感谢您的帮助。

编辑：这是使用1000个粒子和50次迭代的性能分析结果。

(LOAD "/.../myfile.dx64fsl") took 77,488,810 microseconds (77.488810 seconds) to run 
                    with 8 available CPU cores.
During that period, 44,925,468 microseconds (44.925470 seconds) were spent in user mode
                    32,005,440 microseconds (32.005440 seconds) were spent in system mode
2,475,291 microseconds (2.475291 seconds) was spent in GC.
 1,701,028,429 bytes of memory allocated.
 1,974 minor page faults, 0 major page faults, 0 swaps.
; Warning: Function CREATE-MY-DBN has been redefined, so times may be inaccurate.
;          MONITOR it again to record calls to the new definition.
; While executing: MONITOR::MONITOR-INFO-VALUES, in process repl-thread(10).


                                                               Cons   
                             %      %                          Per      Total     Total
Function                    Time   Cons    Calls  Sec/Call     Call     Time      Cons
------------------------------------------------------------------------------------------
SAMPLE:                    25.61   26.14  2550000  0.000005      174    13.526   443040000
DISCRETE-PARENTS:          19.66    3.12  4896000  0.000002       11    10.384    52800000
LINEAR-GAUSSIAN-MEAN:       8.86    3.12  1632000  0.000003       32     4.679    52800000
DISCRETE-PARENT-VALUES:     7.47   12.33  3264000  0.000001       64     3.946   208896000
LIST-DIFFERENCE:            6.41   25.69  6528000  0.000001       67     3.384   435392000
CONTINUOUS-PARENTS:         6.33    0.00  1632000  0.000002        0     3.343           0
PF-STEP:                    5.17    0.23       48  0.056851    80080     2.729     3843840
CONTINUOUS-PARENT-VALUES:   4.13    7.20  1632000  0.000001       75     2.184   122048000
TABLE-LOOKUP:               3.85    8.39  2197000  0.000001       65     2.035   142128000
PHI-INVERSE:                3.36    0.00  1479000  0.000001        0     1.777           0
PHI-INTEGRAL:               3.32    1.38  2958000  0.000001        8     1.755    23344000
PARENT-VALUES:              2.38   10.65  1122000  0.000001      161     1.259   180528016
CONDITIONAL-PROBABILITY:    1.41    0.00   255000  0.000003        0     0.746           0
------------------------------------------------------------------------------------------
TOTAL:                     97.96   98.24  30145048                       51.746  1664819856
Estimated monitoring overhead: 21.11 seconds
Estimated total monitoring overhead: 23.93 seconds

有10000个粒子和50次迭代：

(LOAD "/.../myfile.dx64fsl") took 809,931,702 microseconds (809.931700 seconds) to run 
                    with 8 available CPU cores.
During that period, 476,627,937 microseconds (476.627930 seconds) were spent in user mode
                    328,716,555 microseconds (328.716550 seconds) were spent in system mode
54,274,625 microseconds (54.274624 seconds) was spent in GC.
 16,973,590,588 bytes of memory allocated.
 10,447 minor page faults, 417 major page faults, 0 swaps.
; Warning: Funtion CREATE-MY-DBN has been redefined, so times may be inaccurate.
;          MONITOR it again to record calls to the new definition.
; While executing: MONITOR::MONITOR-INFO-VALUES, in process repl-thread(10).


                                                               Cons    
                             %      %                          Per       Total     Total
Function                    Time   Cons    Calls  Sec/Call     Call      Time      Cons
-------------------------------------------------------------------------------------------
SAMPLE:                    25.48   26.11  25500000  0.000006       174   144.211  4430400000
DISCRETE-PARENTS:          18.41    3.11  48960000  0.000002        11   104.179   528000000
LINEAR-GAUSSIAN-MEAN:       8.61    3.11  16320000  0.000003        32    48.751   528000000
LIST-DIFFERENCE:            7.57   25.66  65280000  0.000001        67    42.823  4353920000
DISCRETE-PARENT-VALUES:     7.50   12.31  32640000  0.000001        64    42.456  2088960000
CONTINUOUS-PARENTS:         5.83    0.00  16320000  0.000002         0    32.980           0
PF-STEP:                    5.05    0.23       48  0.595564    800080    28.587    38403840
TABLE-LOOKUP:               4.52    8.38  21970000  0.000001        65    25.608  1421280000
CONTINUOUS-PARENT-VALUES:   4.25    7.19  16320000  0.000001        75    24.041  1220480000
PHI-INTEGRAL:               3.15    1.38  29580000  0.000001         8    17.849   233440000
PHI-INVERSE:                3.12    0.00  14790000  0.000001         0    17.641           0
PARENT-VALUES:              2.87   10.64  11220000  0.000001       161    16.246  1805280000
CONDITIONAL-PROBABILITY:    1.36    0.00  2550000  0.000003         0     7.682           0
-------------------------------------------------------------------------------------------
TOTAL:                     97.71   98.12  301450048                       553.053  16648163840
Estimated monitoring overhead: 211.08 seconds
Estimated total monitoring overhead: 239.13 seconds

- jkt

---

所以，你的文件不仅包含函数定义吗？也就是说，它实际上执行了其中一个函数，对吗？ - John Pick

你应该编译那些其他文件吗？ - John Pick

我想知道这段代码是否是I/O限制的，也就是说，主要因为I/O而变慢。你有对代码进行分析以查看它在哪里花费了大量时间吗？ - John Pick

我没有进行性能分析，但问题似乎是由于粒子数量而不是输入/输出引起的。我只是在每个时间步骤输出均值和方差（因此对于任何粒子数量，我仍然输出相同的数量），但随着粒子数量的增加，代码变得非常缓慢。我很快会检查性能分析。感谢关注。 - jkt

这两个测试之间唯一的区别是一个加载.lisp文件，另一个加载.dx64fsl文件吗？如果是这样，那么在.lisp场景中，Lisp会即时编译每个函数形式，因此加载.lisp文件和加载.dx64fsl文件之间的唯一时间差异是编译时间；我假设在您的情况下几乎为零。 - Clayton Stanley

Answer 1

在Common Lisp中，典型的算术运算可能会很慢。虽然可以改进，但需要一些知识。

慢速数字操作的原因：

• Common Lisp数字不是CPU提供的（bignums、rational、complex等）
• 从fixnum自动更改为bignum和反向更改
• 通用数学运算导致运行时类型分派
• 标记使用字大小的位
• 数字的consing，数字在堆上使用额外的空间

从分析输出中可以看到的一件事情是，您生成了1.7 GB的垃圾。这是一个典型的提示，表明您的数字操作cons（分配了太多内存）。其中一个原因是临时结果需要内存，而不是重用临时内存。要摆脱这种情况通常并不容易，因为它取决于编译器和/或特定代码的优化。我只是猜测这些是数字操作，但这是一个典型的模式：代码中分配了大量内存 -> 数字操作可能负责。

Ken Anderson（不幸的是他在几年前去世了）在他的网站上提供了一些关于改进数字软件的建议：http://openmap.bbn.com/~kanderso/performance/（存档在这里：web archive）

通常的解决方案是将代码交给一些有经验的Lisp开发人员，他们对使用的编译器和/或可能的优化有一定了解。

- Rainer Joswig

---

该已经失效网页的归档链接：https://web.archive.org/web/20120527084708/http://openmap.bbn.com/~kanderso/performance/ - Holden Rohrer

@HoldenRohrer ：谢谢，我已经将它添加到文本中。 - Rainer Joswig

Answer 2

首先，永远不要在顶层（全局）与(safety 0)一起声明(speed 3)。这样做迟早会让你后悔莫及，因为在这些级别上，大多数Common Lisp编译器比C编译器进行的安全检查更少。例如，有些Lisp会在(safety 0)代码中停止中断信号的检查。其次，(safety 0)很少能够获得明显的性能提升。我建议在热点函数中声明(speed 3)(safety 1)(debug 1)，如果这可以带来明显的性能提升，则可能转到(debug 0)。

否则，如果没有实际查看一些代码，就很难提出建议。从time()来看，GC压力似乎相当高。确保在热点函数中使用开放式算术，并且不要不必要地将浮点数或整数装箱。使用（disassemble 'my-expensive-function）来仔细查看编译器生成的代码。SBCL将在高速优先级编译时提供大量有用的输出，尝试消除其中一些警告可能是值得的。

还要注意使用快速数据结构来表示粒子，如需要使用可实例化数组和宏。

- user110763

Answer 3

如果 "myfile.lisp" 文件中包含的所有代码都是你进行计算的部分，那么编译该文件不会显着提高您的运行时间。两种情况之间的区别可能只是“我们编译了几个循环”，调用在两种情况下都编译或解释的函数。

要从编译中获得改进，您需要编译被调用的代码。您还可能需要对代码进行类型注释，以使编译器能够更好地优化。SBCL 对于未注释的编译器诊断非常好（到达人们抱怨它在编译时过于冗长的程度）。

就加载时间而言，实际上加载已编译的文件可能需要更长的时间（如果您不经常更改代码但更改处理的数据，则将粒子滤波代码准备好放在内核中可能是一个优势）。

- Vatine

Answer 4

Welcome to Clozure Common Lisp Version 1.7-r14925M  (DarwinX8664)!
? (inspect 'print)
[0]     PRINT
[1]     Type: SYMBOL
[2]     Class: #<BUILT-IN-CLASS SYMBOL>
        Function
[3]     EXTERNAL in package: #<Package "COMMON-LISP">
[4]     Print name: "PRINT"
[5]     Value: #<Unbound>
[6]     Function: #<Compiled-function PRINT #x30000011C9DF>
[7]     Arglist: (CCL::OBJECT &OPTIONAL STREAM)
[8]     Plist: NIL

Inspect> (defun test (x) (+ x 1))
TEST
Inspect> (inspect 'test)
[0]     TEST
[1]     Type: SYMBOL
[2]     Class: #<BUILT-IN-CLASS SYMBOL>
        Function
[3]     INTERNAL in package: #<Package "COMMON-LISP-USER">
[4]     Print name: "TEST"
[5]     Value: #<Unbound>
[6]     Function: #<Compiled-function TEST #x302000C5EFFF>
[7]     Arglist: (X)
[8]     Plist: NIL
Inspect> 

请注意，#'print和#'test都被列为“已编译”。这意味着加载.lisp文件和加载已编译文件之间的唯一性能差异是编译时间。我假设这不是您场景中的瓶颈。通常情况下不会出现这种情况，除非您使用了大量宏，并且执行代码转换是程序的主要目的。

这是我从不处理已编译lisp文件的主要原因之一。我只需在我的核心文件中加载所有需要的共享库/包，然后在特定项目上面加载几个特定的.lisp函数/文件。对于我来说，至少对于SBCL和CCL，所有内容都被列为“已编译”。

- Clayton Stanley

---

这实际上是事实。我的.dx64fsl文件比.lisp版本需要更多的时间。这种差异就是编译时间。你有什么关于让我的代码更快的想法吗？如果你能分享一些建议，我会非常感激。 - jkt

有没有一些被反复调用且输入相同的函数？如果有的话，你可以对这些函数进行记忆化处理。我之前使用过Norvig的defun-memo（自动记忆化）。 - Clayton Stanley

在每次迭代中，循环调用pf-step。它使用上一次迭代的结果来更新自身。但是，它还调用其他各种函数，如sample、linear-gaussian-mean，这些函数只是从分布中进行随机抽样。它们查看特定节点的父节点的值，并根据这些值生成一个样本。 - jkt

你可以生成一个线程，用于生成一堆样本和线性高斯均值，并将它们缓存起来。然后当主线程请求时，它会给出结果。这是假设那些采样计算是昂贵的。因此，有一个线程负责采样，另一个线程负责利用该数据。我要说的是，在花费大量时间使单线程运行快之前，我不会采用线程。实际上，我从未在lisp中采用任何高级细粒度并行化技术，所以不要太听我的线程建议。 - Clayton Stanley

Answer 5

几点建议：

1. 如果可能的话，尽量将文件I/O移出循环；在迭代之前批量将数据读入内存。文件I/O比内存访问慢几个数量级。

2. 如果执行速度对您很重要，请尝试SBCL。

3. 输入结果增加十倍会导致大约十倍的执行时间增加，这是线性的，因此您的算法似乎很好；只需要处理常数因子。

4. 利用Lisp工作流程：编辑函数，编译函数和测试运行，而不是编辑文件，编译文件和测试。当您的项目变得更大时（或者尝试SBCL时，它将花费更长的时间来分析/优化您的程序以生成更快的代码），差异将变得明显。

- huaiyuan

---

我用向量赋值替换了文件I/O。然而，这并没有改变任何实质性的东西。如果您可以检查上面的分析，您会发现大部分时间都被“sample”和“pf-step”所占用。我可能会尝试并行化“sample”。如果您有任何进一步的建议，我很乐意听取。非常感谢您的回答。 - jkt