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

Common Lisp best practices to use type declarations for optimization

我有一个 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 说明符添加到我的代码中？但是，哪里和哪些情况我应该添加它？

有什么规律可以遵循？

为了优化目的，我是否也应该声明我的函数的类型？

风格

由于您实际上并没有以任何有用的方式使用扩展的 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 和分析器是你的朋友。

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

更好的编译器会抱怨类型错误，可以跨函数传播类型，并且可以在无法进行某些优化时抱怨。

序列函数

请注意，sequence 函数是一个特别棘手的案例。 序列有子类型列表和向量（包括字符串）。

假设一个序列函数是：

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

  • 如果序列属于同一类型，可能需要优化列表的代码版本和向量的优化代码版本。

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

  • 结果类型也有影响，根据结果类型不同算法可能possible/necessary

所以自由度还是挺高的。编译器可能有助于快速代码。而且特定序列函数的实现也可能能够在运行时进行一些优化。

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

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

文档和论文

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