performance - 在这个 Common Lisp 函数中消除 "mystery-consing"？

Question

这个 Common Lisp 函数使用极其简单的幼儿园级算法和一些“案例”测试来简单地计算墙壁线框边缘的四个顶点，似乎负责为每个渲染帧动态分配 196608 字节； SBCL 的分析器告诉我，就 consing 而言，这是我最有问题的功能。为了大致了解我在做什么，这是一个小型的第一人称地牢爬行游戏，地牢正好是 32x32 的单元格，每个单元格有 4 面墙。 32 * 32 * 4 * x = 196608，所以 x 结果是 48，恰好是 4 * 12(4 面墙 * 每面墙 12 个浮点数？也许不是)。

现在，我可以通过在游戏模式中使用 OpenGL 显示列表轻松缓解这个性能问题，我想这就是我将继续做的事情。尽管如此，1) 我通常不会过早地优化，更重要的是 2) 我仍然不喜欢让某些烦人的瘙痒像这样不被划伤，我想知道我还能做些什么。我的功能如下:

(defun calculate-wall-points (x y wall)
  (declare (integer x y)
           (keyword wall))
  "Return the 4 vertices (12 floats) of a given dungeon cell wall"
  (let ((xf (coerce x 'float))
        (yf (coerce y 'float)))
    (case wall
      (:SOUTH
       (values xf yf 0.0
               (1+ xf) yf 0.0
               (1+ xf) yf 1.0
               xf yf 1.0))
      (:WEST
       (values xf yf 0.0
               xf yf 1.0
               xf (1+ yf) 1.0
               xf (1+ yf) 0.0))
      (:NORTH
       (values xf (1+ yf) 0.0
               xf (1+ yf) 1.0
               (1+ xf) (1+ yf) 1.0
               (1+ xf) (1+ yf) 0.0))
      (:EAST
       (values (1+ xf) (1+ yf) 0.0
               (1+ xf) (1+ yf) 1.0
               (1+ xf) yf 1.0
               (1+ xf) yf 0.0))

      (otherwise
       (error "Not a valid heading passed for wall in function calculate-wall-points: ~A" wall)))))

总结一下我试图解决的一些问题:

对 3 处的“速度”和 0 处的其他所有内容进行“声明”以“优化”(均在此函数中，以及调用它的唯一函数中)。奇怪的是，分析器确实报告了这个函数的 consing 稍微少了一些……但它仍然 consed。我的目标是零认知。算术不应该是缺点。

然后我认为“值(value)观”可能正在这样做。也许，我想，它在内部就像函数“list”一样，毫无疑问，它是 conses(“list”函数在宇宙中的唯一用途)。我做了什么来试图减轻这种情况？只是为了实验，我修改了文件以创建一个单一的墙顶点缓冲区全局数组，大小适合 12 个浮点类型的元素，并修改了这个函数来修改它，以及在调用它之后从它读取的调用函数函数(因此它将不断更新保存在内存中同一位置的一组 12 个浮点数，而不是分配任何内容)。奇怪的是，这并没有阻止这个函数成为一个 consing-piggy!那么......是'case'在做consing吗？我确实觉得很有趣，前面提到过，那个神秘数字是 48。48 = 4 * 12，也许这 4 个案例测试乘以每个“值”调用的 12 个浮点数。或者，这可能是巧合，48 个字节意味着别的东西(因为浮点数不是 1 个字节，我怀疑是其他东西)。这看起来很重要，但我不能完全理解我的下一个方法应该是什么。

尝试用“cond”等价物替换“case”，此时只是捕获稻草，也没有做任何事情。

那么这个函数的“神秘consing”是从哪里来的呢？更有经验的 Lisp 程序员如何处理这个棘手的问题？

(编辑)@FaheemMitha，是使用calculate-wall-points 函数的函数；这个麻烦的函数后来被内联了 (declaim (inline calculate-wall-points)) 就在calculate-wall-points的定义之前:

(defun render-dungeon-room (dungeon-object x y)
  (declare (optimize (speed 3) (space 0) (debug 0)))
  (declare (type fixnum x y))
  (let ((cell (cell-at dungeon-object x y)))
    (unless (null cell)
      (dolist (wall-heading +basic-headings+)
    (unless (eq wall-heading (opposite-heading *active-player-heading*))
      (when (eql (get-wall-type cell wall-heading) :NORMAL)
        (multiple-value-bind (v1x v1y v1z v2x v2y v2z v3x v3y v3z v4x v4y v4z)
        (calculate-wall-points x y wall-heading)
          (declare (type float v1x v1y v1z v2x v2y v2z v3x v3y v3z v4x v4y v4z))

      (gl:with-primitive :quads
    (if (is-edit-mode)
        (case wall-heading
          (:NORTH
           (gl:color 0.4 0.4 0.4))
          (:WEST
           (gl:color 0.4 0.0 0.0))
          (:SOUTH
           (gl:color 0.0 0.0 0.4))
          (:EAST
           (gl:color 0.0 0.4 0.0)))
        (gl:color 0.1 0.1 0.1))
    (gl:vertex (the float v1x)
           (the float v1y)
           (the float v1z))
    (gl:vertex (the float v2x)
           (the float v2y)
           (the float v2z))
    (gl:vertex (the float v3x)
           (the float v3y)
           (the float v3z))
    (gl:vertex (the float v4x)
           (the float v4y)
           (the float v4z)))

      (gl:color 1.0 1.0 1.0)
      (gl:with-primitive :line-loop
    (gl:vertex (the float v1x)
           (the float v1y)
           (the float v1z))
    (gl:vertex (the float v2x)
           (the float v2y)
           (the float v2z))
    (gl:vertex (the float v3x)
           (the float v3y)
           (the float v3z))
    (gl:vertex (the float v4x)
           (the float v4y)
           (the float v4z)))))))))

零)

Answer 1

consed 内存是由分配浮点数引起的。每个函数调用都返回浮点数，实际上是 32 位 single-floats . Consing 意味着在堆上分配了一些数据:cons 单元格、数字、数组……

一个 single-float是 32 位内存对象。 4字节。

(+ 1.0 2.0)  ->  3.0

在上述情况下 3.0是一个新的 float ，可能是新的。

(+ (+ 1.0 2.0) 4.0)  -> 7.0)

现在上面的计算是什么？内部 +操作返回一个浮点数 3.0 .它会发生什么？

它可以在处理器寄存器中返回并在那里用于下一个操作。

它可能会在堆栈上返回并在那里用于下一个操作

在更复杂的操作中，它可能在堆中分配并作为指向堆值的指针返回。如果没有足够的寄存器用于所有返回值或堆栈帧的大小不足以容纳所有返回值，则可能会出现这种情况。

现在这些 float 会发生什么？它们是否以某种方式存储？在列表中？在一个新数组中？在新 structure ?在一个新的 CLOS 对象中？

上面清楚地表明它取决于处理器架构和编译器策略。 x86 没有很多寄存器。 64位版本有更多。 RISC 处理器可能有更多的寄存器。那么栈有多大，典型的栈帧有多大呢？

对于涉及多个函数的更复杂的计算，优化编译器可能能够优化哪些值留在寄存器中，从而减少 consing。

上面也清楚地表明，对于 Common Lisp，没有完全通用的方法来使 float 操作不受约束。减少 consing 的能力取决于一些一般性的想法和许多编译器/架构特定的技巧。

由于您使用的是 SBCL，因此最好在 SBCL 邮件列表中寻求建议，并告诉他们操作系统、架构(intel、arm 等)以及它是在 32 位还是 64 位模式下运行。还需要更多的上下文代码来更好地了解如何减少 consing。

一些阅读背景资料:

Fast Floating-Point Processing in Common Lisp

Ken Anderson(他不幸于几年前去世，非常乐于助人的 Lisper)收集了一些关于 Lisp and Performance 的信息。 , Files (存档版本)。