optimization - 使用类型声明进行优化的 Common Lisp 最佳实践

Question

我有一个 Common Lisp 函数，它合并两个有序的符号列表，没有重复(两个有序集):

(defun my-merge (x y)
  "merge two lists of symbols *already sorted and without duplicates*
   (and return the resulting list sorted and without duplicates)"
  (let* ((first (cons nil nil))
         (last first))
    (loop while (and x y)
       for cx = (car x)
       for cy = (car y)
       if (string= cx cy)
       do (setf x (cdr x))
       else if (string< cx cy)
       do (rplacd last (cons cx nil))
       and do (setf last (cdr last) 
                    x (cdr x))
       else do (rplacd last (cons cy nil))
       and do (setf last (cdr last) 
                    y (cdr y)))
    (rplacd last (or x y))
    (cdr first)))

由于我发现关于在实际情况下使用类型声明以有效编译代码的信息很少，我不确定声明变量是否足够，例如以这种方式:

(defun my-merge (x y)
  "merge two list of symbols *already sorted and without duplicates*"
  (declare (list x y))
  (let* ((first (cons nil nil))
         (last first))
    (declare (cons first last))
    (loop while (and x y)
       for cx symbol = (car x)
       for cy symbol = (car y)
       ...

或者，如我所想，如果还需要添加 the我的代码的说明符？但是，我应该在哪里以及在哪些情况下添加它？

有什么规则可以遵循吗？

为了优化，我还应该声明函数的类型吗？

Answer 1

款式

由于您实际上并未使用扩展 LOOP以任何有用的方式提供的功能和 LOOP语法对你的例子来说不是很好，我建议用原始 LOOP 来写它。 .看看如何COND使其对 Lisp 程序员更具可读性:

(defun my-merge (x y &aux (first (list nil)) (last first) cx cy)
  (macrolet ((cdr! (v)
               `(setf ,v (cdr ,v))))
    (loop (unless (and x y)
            (return))
          (setf cx (car x) cy (car y))
          (cond ((string= cx cy)
                 (cdr! x))
                ((string< cx cy)
                 (rplacd last (list cx))
                 (cdr! last)
                 (cdr! x))
                (t
                 (rplacd last (list cy))
                 (cdr! last)
                 (cdr! y))))
    (rplacd last (or x y))
    (cdr first)))

编译

鉴于编译器的复杂程度:

完全愚蠢 = 编译器忽略所有声明 -> 声明没有帮助

大多是愚蠢的 = 编译器到处都需要声明，但是优化了 -> 你需要写很多声明

例子:

(let ((a 1) (b 2))
  (declare (integer a b))
  (let ((c (the integer (* (the integer (+ a b))
                           (the integer (- a b))))))
     (declare (integer c))
     (the integer (* c c))))

请注意，仅知道参数类型是什么可能还不够，可能需要声明结果的类型。于是使用 the . DISASSEMBLE分析器是您的 friend 。

basic = 编译器需要类型声明、优化，但也可以推断某些类型。标准语言的类型是已知的。

更好的编译器会提示类型错误，可以跨函数传播类型，并且可以在某些优化不可能时提示。

序列函数

请注意，序列函数是一个特别棘手的情况。序列具有子类型列表和向量(包括字符串)。

假设一个序列函数是:

(foo result-type sequence-1 sequence-2 fn)

如果序列的类型相同，则可能希望为列表提供优化的代码版本，而为向量提供另一个优化的代码版本。

如果序列的类型不同，将一个序列转换为不同的类型可能会很有用。也许不吧。

结果类型也有影响，根据结果类型，可能/需要不同的算法

所以自由度相当高。编译器可能有助于快速编写代码。但特定序列函数的实现也可能在运行时进行一些优化。

然后 fn是一个接受元素并产生新元素的函数。知道它的类型签名可能会有所帮助 - 或者不知道。

我真的不能说当前的哪个 Common Lisp 有一个复杂的序列函数实现。虽然我记得 Symbolics Common Lisp 的实现付出了一些努力。

文档和论文

通常编译器可以优化什么以及如何优化，如果有的话。有一些关于这个主题的论文，但它们通常是旧的和/或过时的。

CMUCL的Python编译器:The Compiler .

CMUCL的Python编译器:Advanced Compiler Use .

The Python compiler for CMU Common Lisp (后记)

SBCL Compiler

快板 CL:Compiling

LispWorks:Optimizing your code

Performance beyond expectations

How to make Lisp code go faster than C

An evaluation of major Lisp compilers