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)))

编译

鉴于编译器的复杂程度:

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

• 大多数是stupid =编译器需要在任何地方声明,但是优化 - >你需要编写很多声明

例:

(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 =编译器需要类型声明,优化,但也可以推断出某些类型.标准语言的类型是已知的.

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

序列功能

请注意,序列函数是一个特别棘手的案例.序列具有子类型列表和向量(包括字符串).

假设一个序列函数是:

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

• 如果序列属于同一类型,则可能希望为列表提供优化的代码版本,为向量提供另一个.

• 如果序列是不同类型的,则将一个序列转换为不同类型可能是有用的.也许不吧.

• 结果类型也有影响,取决于结果类型,可能/必要的不同算法

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

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

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

文件和文件

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

• CMUCL 的Python编译器:编译器.
• CMUCL 的Python编译器:高级编译器使用.
• CMU Common Lisp的Python编译器(Postscript)
• SBCL编译器
• Allegro CL:编译
• LispWorks:优化代码
• 表现超出预期
• 如何让Lisp代码比C更快
• 对主要Lisp编译器的评估