C和C++编译器是否会优化带有函数调用的比较操作？

Question

C和C++编译器通常会对函数比较进行优化吗？

例如，此页面建议，在某些标准库实现中，C++中std :: lists的size函数可能具有线性复杂度O（N）（这对于链表是有意义的）。

但在这种情况下，如果myList是一个巨大的列表，像这样的语句会怎么样？

    if (myList.size() < 5) return 1;
    else return 2;

size()函数是否会查找并计数所有N个列表成员，还是在找到5个成员后就被优化为短路？

- Wander Nauta

---

如果将 size 内联，这可能是有潜力的，但我认为很难发现它可以打破正在增加计数器的循环。 - Rup

我并不是很担心。虽然C++03标准没有要求size()的O(1)复杂度，但它确实建议这样做，并且实现起来很简单。如果您的实现没有跟踪容器中元素的数量（您可以通过阅读<list>头文件轻松检查此问题），那么我会感到惊讶。 - David Rodríguez - dribeas

@WanderNauta：想要提出一个普遍问题并询问一个具体问题的问题在于你将得到关于具体问题的答案。如果问题是普遍的，那么答案是编译器在大多数情况下无法做到。对于列表上的size()这种情况来说，它是一个特例，因为作为一个模板，编译器有函数的定义，并且有一些很小的可能性可以弄清楚它。总的来说，编译器无法访问函数的定义，优化的机会更加困难。 - David Rodríguez - dribeas

所以你的意思是编译器会为你的“自己的”代码做到这一点，即使该函数没有内联展开？ - Wander Nauta

相反的是，即使进行了内联，也很少有机会，在没有内联的情况下，就别想了，函数必须在完成运行之前才能进行比较。 - David Rodríguez - dribeas

Answer 1

理论上，如果size()被内联，那么可能存在这种可能性，但是为了执行优化，编译器必须：

1. 检测到您正在特定测试“小于”条件
2. 证明循环（假设一个循环存在于此讨论的目的）导致变量单调增加
3. 证明循环体没有任何可观察的副作用

在我看来，这是一大堆需要依赖的东西，并且还包括其他上下文中不太“显然有用”的功能。请记住，编译器供应商的资源有限，因此必须有非常好的理由实现这些先决条件，并让编译器将所有部分组合起来优化此案例。

考虑到即使对某人而言这是性能问题，“问题可以轻松解决”，我并不认为会有这样的理由。因此，通常您不应该期望像这样的情况得到优化。

- Jon

---

我有点困惑。为什么值必须单调递增呢？ - Wander Nauta

因为如果不这样做，就只能执行所有迭代来确定最终值是否小于5。 - Oliver Charlesworth

其实，这并没有那么糟糕。列表长度计算并不是那么复杂。而且我知道现代优化器甚至利用带符号整数溢出的 UB 来确定一系列增量是否导致单调递增的变量。（unsigned 不会，因为 UINT_MAX+1 < UINT_MAX）。 - MSalters

Answer 2

实际上，在C++11中，std::list已经进行了优化，size()的时间复杂度为常数。

对于C++03来说，size()的时间复杂度确实是线性的，因为它需要每次都统计元素个数。

size()函数会查找并计算所有N个列表成员，还是在找到5个成员后就停止计算？

我从未见过这种优化在实践中发生过。虽然这是合法的，但我怀疑任何编译器都没有实现类似的优化。

- Luchian Grigore

---

只是作为一个旁注，类似的代码在函数式编程语言（如Haskell）中，只会扩展到所需的深度。 - Jaywalker

@Jaywalker：我不像你那么确定。我认为你需要创建一个“比…更长”的方法。 - Matthieu M.

@Jaywalker：我认为 GHC（主要的优化 Haskell 编译器）不会进行这种优化。如果我理解正确，它会进行分离编译而不是内联 length。 - Fred Foo

在C++中，可以通过令人头痛的运算符重载来优化“<”运算符。 - R.. GitHub STOP HELPING ICE

目前，GHC中的 length xs < k 将遍历整个列表，我不知道有哪种实现可以快捷地完成它。您可以使用 genericLength xs < k 和适当的惰性数字类型来进行快捷操作。或者使用重写规则 forall k xs. length xs < k = if k < 1 then False else null (drop (k-1) xs)，但这是您自己的工作，而不是编译器的工作。 这将更改例如 length (1:2:undefined) < 2 的行为，所以编译器不能提供它。 - Daniel Fischer

Answer 3

myList.size()函数本身没有办法为你使用的目的进行编译，因此它将确定整个大小。为了获得您建议的优化，您需要一个专用的谓词函数，而不是通用的size()，类似于bool sizeLessThan(int);。

- mah

---

但是从理论上讲，这是编译器可以观察到的一种优化。问题是，这种情况在实践中是否会发生？ - Oliver Charlesworth

如果编译器能够证明其余部分并不重要，只要可观察的行为是正确的，它就完全有权不再费心。理论上，编译器可以证明这一点，但在实践中有一些棘手的问题。 - Flexo

当然可以，但要实现这一点需要一些非通用的东西。你必须预计（在一般情况下），像这样的代码要么在库中，要么至少是一个不同的对象，因此以通用方式链接（消除了这种专门优化的可能性）。 - mah

Answer 4

不行你在询问编译器是否可以使函数根据其结果的使用方式而表现出不同的行为。这只有在调用者和函数同时被编译在一起的内联函数中才有可能实现。除此之外，似乎很难达成。

- phkahler