C/C++对最小执行时间有任何保证吗?

41

为什么编译器似乎对不执行任何操作的循环很有礼貌,而且不会消除它们?

C标准是否要求循环需要花费一些时间?

例如,以下代码:

void foo(void) {
    while(1) {
        for(int k = 0; k < 1000000000; ++k);
        printf("Foo\n");
    }
}

比这个运行得慢:

void foo(void) {
    while(1) {
        for(int k = 0; k < 1000; ++k);
        printf("Foo\n");
    }
}

即使启用了-O3优化级别,我仍然希望删除空循环并在两个代码上获得相同的速度。

"时间消耗"是编译器应该保留的副作用吗?


6
什么是粗鲁的编译器? - Ed Heal
4
我认为C/C++标准中没有关于“运行时间”的概念。 - user1196549
9
粗鲁的编译器是一种非常注重将代码中的"未定义行为"转化为你最糟糕噩梦的编译器。 - BitTickler
19
这是一个关于“仿佛法则”以及什么行为算作可观察行为的不错问题。 - Lightness Races in Orbit
2
你只是在测量启动开销或其他难以预测的开销。基本上是随机数。在提出这样的问题之前,你应该先查看反汇编代码。 - Ivan Aksamentov - Drop
显示剩余13条评论
4个回答

43

不,花费的时间不算作可以受到as-if规则保护的可观察行为:

[C++14: 1.8/5]: 执行一个良好形式的程序的符合规范实现必须产生与相应的抽象机器实例使用相同程序和相同输入的可能执行之一相同的可观测行为。 但是,如果任何这样的执行包含未定义的操作,则此国际标准对于执行该程序与该输入(甚至对于在第一个未定义操作之前的操作)不要求实现进行任何要求。

[C++14: 1.5/8]: 符合规范的实现的最少要求是:

  • 对易失性对象的访问严格按照抽象机器的规则进行评估。
  • 在程序终止时,写入文件的所有数据都必须与根据抽象语义执行该程序所产生的可能结果之一相同。
  • 交互设备的输入和输出动态应以实际传递提示输出的方式进行,然后程序等待输入。 什么构成交互设备是由实现定义的。

它们统称为程序的可观察行为 [注:每个实现可以定义抽象和实际语义之间更严格的对应关系。 —结束注]

那些循环可以合法地进行优化,事实上,标准甚至有意试图使这样做更加容易:

[C++14: 1.10/24]: 实现可以假定任何线程最终都会执行以下操作之一:

  • 终止,
  • 调用库I/O函数,
  • 访问或修改易失性对象,或
  • 执行同步操作或原子操作。

[ 注意: 这旨在允许编译器转换,例如删除空循环,即使不能证明终止。 —注解]

实际上,您的编译器可能会“礼貌地”注意到,在这些程序中,循环的意图似乎是减缓重复文本输出的速度。 :)


4
很烦人的是,问题本身规定了“C标准”。 - kfsone
我希望规则明确指定执行循环所需的时间,即使是无限的,本身并不被视为副作用。这样的规则不会像上述引用的规则那样否定因果关系定律。例如,给定 do {x=expr_that_might_never_yield_1(...);} while (x != 1); printf("Done..."); if (x==1) printf("Hooray!"); 我可以看到允许编译器将 printf("Done...") 移动到循环之前的有用性,但不允许编译器假设 x 将以某种方式等于 1。 - supercat
我认为更“礼貌”的做法是优化循环,以便通知程序员这是易碎的代码,可能随时会出现问题。 - usr
编译器的工作不是要手把手地教你,程序员应该对自己的学习负责,没有其他人可以替代。 - Lightness Races in Orbit

28

你没有指定编译器,但是假设它是gcc

根据文档,gcc不会删除空循环。其中包含以下文本:

历史上,GCC未删除“空”循环,因为您在程序中放置一个循环的最可能原因是要延迟,因此删除它们不会使真正的程序运行更快。

但是,如果优化器将循环外可以移动的代码放在循环内,并且结果循环为空,则它可以删除空循环。

从文档中无法确定最新版本是否仍然如此。手册提到“历史上”,但没有说明原因。如果您更新有关您的确切平台和编译器的信息,可能可以得出更好的答案。


你能具体说明一下“被优化器清空”的意思吗?你是指启用了优化吗? - Banex
@Banex 只有在启用优化时,优化器才会处于活动状态,因此是的,启用了优化。 :) 如果循环包含可以移出循环或完全删除的代码,因为编译器可以证明它永远不会被使用,那么gcc可以完全删除该循环。 - pipe
非常好的观点。如果OP将“int i = 0;”放在循环内部,他的代码会运行得多快? - Mike
8
例如,对于int main(void) { int i, k; for (i = 0; i < 1000000; ++i) ++k; puts("Done"); },变量k的值从未被使用,因此编译器可以优化掉它。因为k的增量永远不会发生,所以循环甚至不需要用来递增k,因为这是它唯一的任务。因此,编译器可以优化掉整个循环。变量i的值现在也没有被使用,所以它也可以被优化掉,留下int main(void){puts("Done");}作为最终优化程序。这在我使用GCC 5.2.0编译64位Windows代码时发生。 - user539810
2
@ChronoKitsune 更进一步,假设你返回的是 k 而不是忽略它。在这种特定情况下,编译器仍然可以删除循环,并将程序优化为类似于 int main(void){return 0xf4240;} 的东西。 - Ryan Pendleton

7

C或C++可执行文件没有最短执行时间,因为执行时间取决于许多平台特定的问题,例如:

  1. 处理器时钟速率。
  2. 每条指令的时钟周期数。
  3. 内部处理器执行优化。
  4. 中断。
  5. 处理器指令集/功能。

一些处理器支持乘法,而另一些则不支持。不支持乘法的处理器执行程序需要比具有乘法指令的处理器花费更长的时间。同样适用于浮点运算。

处理器的内部操作速度是不同的,有一个称为“时钟周期”的常见时间单位。大多数处理器供应商在时钟周期中指定了指令的持续时间。此计量可能会由于内部支持(如高速缓存管理)而变得困难。

一些处理器具有可以优化指令或指令模式执行的逻辑。其中一种优化是 分支预测

许多平台都有中断,例如,“系统滴答”中断,允许操作系统知道何时将执行切换到另一个程序。还有一些不那么周期性的,例如 I/O 发生时。当程序被中断时,无法保证最小执行时间。

声明最小执行时间会对 C 和 C++ 语言的可移植性造成混乱。某些平台希望比最短时间更快地执行代码,而其他平台可能无法实现最短执行时间(但它们可以从像 C 这样的高级语言中受益)。

此外,如何测量时间?

最短执行时间适用于延迟循环或轮询吗?


此外,许多操作系统的时钟频率会因负载而异。甚至术语“时钟周期”也与此相关。 - BitTickler

4

不,没有任何保证:(引自N1570,5.1.2.3程序执行

1本国际标准中的语义描述描述了一个抽象机器的行为,其中优化问题是无关紧要的。

无论如何,C标准仅在抽象机器上执行程序时规定了程序的行为,该机器可以具有无穷大的内存和/或CPU。


4
因此,作为必然结果,“编译器”如果只将每个输入翻译成一个无限循环,那么它将严格符合标准;可以认为它正在执行正确的行为,只是极其缓慢。 - M.M
@M.M 我认为如果输入终止,输出也必须终止。"极慢"和"永不"之间是有区别的。 - kasperd
@M.M 不,这样的编译器不会严格符合标准。不要混淆无法证明任何给定程序将终止(停机问题)与无法为任何特定程序执行它。如果可以证明(例如)编译器对“Hello, world!”的翻译输出永远不会打印“Hello, world!”,则编译器不符合规范,我们可以尽可能地全面和巧妙地证明(而编译器在混淆非终止方面显然受到限制)。 - Jeroen Mostert
@JeroenMostert find_collatz_counterexample(); printf("Hello world");@JeroenMostert find_collatz_counterexample(); printf("你好,世界"); - mbrig
@mbrig:通过“Hello, world!”我指的当然是经典程序,而不是任意一个我们自己无法确定其是否终止的程序。我们不能使用这样的程序来得出有关编译器的任何结论。 - Jeroen Mostert
显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接