Lisp:测量函数的性能

Question

到目前为止,在测试编写相同功能的不同方法的速度时,我一直在使用该time功能,并且通常它给我一个很好的指示不同功能的相对速度(因为它们通常相差大约100k周期).

factorial然而,time虽然一直缺乏尝试找到功能的最快方法.这些方法不仅仅相差10k-30k周期,而且它们的总时间也相差大约一半(我猜这是预期的).

三个factorial功能:

(defun factorial-recusion (n)   ; 1st      
  (if (equal n 1) 
      1
      (* n (factorial (- n 1)))))

(defun factorial-loop (n)   ; 2nd
  (let ((solution 1))
    (loop for x from n downto 2
       do (setf solution (* solution x))
       finally (return solution))))

(defun factorial-do (n)     ; 3rd
  (let ((solution 1))
    (do ((x n (1- x)))
    ((< x 2) (return solution))
      (setf solution (* solution x)))))

所以,我想我有两个问题:

1.)哪种方法factorial应该最快(如果有的话),为什么？

2.)如果我通过一般方法找到更快的功能,那么最好的方法是什么(出于某种原因,我认为LOC是一个速度不好的指标)？也许有办法查看Lisp字节码的反汇编？或者也许有更好,更严谨的方式？

我目前在Ubuntu 12.04 x86-64上运行Linux 3.2.0-26,SBCL.

Answer 1

SBCL不会编译为'bytecode'.它编译为本机机器代码.

您可以使用反汇编Lisp函数DISASSEMBLE.

一旦数字进入bignum范围,你的阶乘函数的速度由bignum算术乘法支配.

为了更清楚:你使用哪个迭代构造,DO或LOOP,并不重要.大部分时间花在倍增的bignums上.递归版本也没有多大区别.

这是一个典型的基准问题:许多简单的数字基准测试主要由几个算术运算的运行时间(如bignums的乘法)决定.它们不会测量一般语言操作速度的不同(例如各种类型的控制流程).

具有快速bignum库的慢Lisp可能比使用Lisp编写的Bignum代码的优化Lisp编译器更快.