通过Lisp编译时评估进行的所有代码优化都可以由其他语言(如C++)中的理想编译器实现吗？

Question

在Lisp中，您可以通过在编译时在宏中计算条件来优化代码。与中一样，您有一个宏(compute-for-N 1) evaluate为code-1，(compute-for-N 2) evaluate为code-2。

如果您用C++编写类似的代码，一个非常天真的编译器会在执行过程中计算条件，从而减慢程序的运行速度。

我的问题是，所有可能的Lisp计算时间优化也可以由理想的编译器完成吗？作为后续，如果理想的编译器实际上可以实现与任何手动编写的编译时优化类似或更好的结果，那么尝试编写手动代码优化是不是一种糟糕的代码实践？

PS:使用Lisp这样的语言显然有更多的优点，所以这个问题并不是在质疑Lisp的潜在效用。

Answer 1

是的，允许C++编译器生成高效的代码，理想的C++编译器应该能够使代码尽可能高效。

理想的编译器应该利用你能想到的每一种优化技术。与真正的编译器不同，理想的编译器不受时间和空间(以及人类的独创性)的那些令人讨厌的限制，因此它甚至可以实现最奇怪的优化想法。目前在另一种语言(比如Lisp)中可以实现的优化并不奇怪，当然也在理想的C++编译器的能力范围之内。

我认为以上内容适用于所有编译语言，而不仅仅是C++。但是，C++标准在as-if rule中明确规定了这一点，该标准规定该标准只要求可观察到的行为；允许编译器以其认为合适的方式实现此行为。事实上，就标准而言，只要水晶球导致正确的可观察行为，编译器就可以生成魔术水晶球并符合标准。

诚然，C++标准并不禁止速度。

好吧，对一些人来说，调用魔法可能太夸张了。对于一个更切合实际的极端示例，请考虑排序。假设有一个对数组进行排序的函数，该函数没有可观察到的副作用；该函数唯一可观察到的行为是数组从任意顺序转换为排序。这一点对许多读者来说应该是相当熟悉的。

如果C++编译器被赋予了这个功能，那么唯一的任务就是生成的机器代码必须对数组进行排序，而不会有任何副作用。想想看。该函数的机器代码必须保留可观察到的行为；它不必完全符合程序员编写的代码。理论上，编译器可以将冒泡排序的实现替换为堆排序的实现。它具有相同的可观察行为。

据我所知，没有一个开发编译器的人考虑过这个级别的优化(在我看来，他们也不应该)。但是，C++标准明确允许这样做。这展示了as-if规则可以推送到什么程度。任何可以想象到的有效优化都是允许的。理想的编译器应该实现所有可能的优化(与现实的编译器相反，现实的编译器充其量只能努力实现那些合理的优化)。特别是，Lisp所能做的任何优化也可以由理想的C++编译器来完成。

对于后续问题，是的，这将是一种糟糕的做法，但原因不同于您提出的原因。

手动代码优化很可能打着premature optimization, "the root of all evil"的旗号。过早地编写优化是糟糕的代码实践。如果您的手动优化还不成熟，那么(要么是例行公事，要么是)已经进行了性能测试，以确定是否需要手动优化。相同的测试例程可以确定手动优化是否比您的编译器获得了更好的结果，从而使后续问题变得毫无意义。

此外，由于不存在理想的编译器，因此让实际代码受到理想编译器的功能的影响将是一个坏主意。

Answer 2

编译器通常(通常也应该如此，看起来似乎C++规范明确地允许这样做)可以做任何他们想做的事情来提高程序的性能，同时不会改变它明显的行为方式，并且(我想说)也不会引起过度的编译时副作用:你不希望编译程序的过程来发射核导弹，即使程序本身是打算这样做的。也许您还想添加编译器应该终止的约束:这并不总是适用于真正的编译器。

Lisp系列语言与大多数其他语言之间的唯一区别是，用户代码在Lisp中可能更容易做这类事情，或者历史上一直是这样。

例如，在Common Lisp中，考虑以下内容：

(defun sum-to-n (n)
  (declare (type (integer 0) n))
  (if (zerop n)
      0
    (+ n (sum-to-n (1- n)))))

好吧，这是一个糟糕的函数，但是：

(define-compiler-macro sum-to-n (n)
  (typecase n
    ((integer 0)
     (/ (* n (1+ n)) 2))
    (number
     (error "you are a sponge"))
    (t
     `(let ((m ,n))
        (declare (type (integer 0) m))
        (/ (* m (1+ m)) 2)))))

现在，(sum-to-n 101010101)是一个编译时常量(实际上是5101520302520151)，(sum-to-n (f q))被转换为

(let ((m (f q)))
  (declare (type (integer 0) m))
  (/ (* m (1+ m)) 2))

而(sum-to-n 12.0)是一个编译时错误。

所以这很好，而且很容易做，而且它和类似的事情很容易做，因为在Lisp中，程序很容易根据自己的源代码进行推理。

但绝对没有什么能阻止C++或任何其他编译器做它认为可能做的任何优化，甚至是非常英勇的优化。事实上，除了用户的努力之外，确实没有什么可以阻止任何人编写以C++程序为参数的程序，并发出相同代码的优化版本。

Answer 3

正如人们指出的那样，你有constexpr和这类东西，大多数C++优化器非常积极地不断折叠，并在那里做近乎魔术的东西。

但是，如果您将LISP编译器甚至C++编译器视为JIT，那么常量折叠有一个概念上的优势。我不确定这是否是你想要的，但作为一个涉足编译器设计的人，这是我的兴趣所在。

即使是最激进的优化器也无法预测用户在运行时会做什么。因此，假设用户在运行时为N键入一个值128，然后我们使用N作为输入执行一些密集的任务(例如，路径跟踪，这可能涉及数十亿次迭代)。如果我们为N动态编译128个代码，并且编译的开销与处理涉及N的代码所花费的时间相比相形见绌，那么常量折叠适用于N，前提是我们在编译代码之前对其赋值，如果在编译时没有为N赋值，则在任何语言/编译器中都不能这样做。如果N在这种情况下发生变化，我们会在运行中重新编译代码。

因此，对我来说，这似乎是响应用户输入而动态编译的代码的一个巨大的潜在优化来源。我不知道这在多大程度上回答了你的问题，但总是有一个差距，即使是最激进的优化器也不知道用户在运行时会做什么。也就是说，C++优化器使用在编译/链接时可以获知的信息做了一项惊人的工作。

我总是发现C++优化器和优化器在某些情况下看起来非常愚蠢，而在另一些情况下似乎非常聪明。例如，我在我们的代码中发现了一个分析器热点，涉及对一个变量进行除法和模运算，这个变量通过我们的运行时代码(但不是在编译时，因为它是基于用户输入)保证是两倍大小的幂。但它不是在编译时确定的，所以优化器实际上使用了昂贵的除法和模运算指令。所以我发现我可以通过预计算log2(N)和N-1并使用手动位移位和除法和模数的位与运算来优化大约30%的性能。