编译器降低程序的时间复杂度合法吗? 是否认为这是可观察到的行为?

(注意:这是一个语言律师问题;我不是在指任何特定的现有编译器。)

什么时候允许编译器降低程序的时间复杂度?
在什么情况下(如果有)将其视为“可观察到的行为”,为什么?
(例如,编译器可以合法地将多项式时间程序“简化”为指数时间程序吗?)

如果答案在C和C ++或两者的不同版本中有所不同,请说明不同之处。

Mehrdad asked 2020-08-11T04:08:31Z
4个解决方案
42 votes

C标准实际上没有时间复杂度模型,无论是针对其原始操作还是其库函数,都没有,因此允许编译器执行几乎所有保留程序语义(可观察到的行为)的事情。

C ++标准仅对其某些库函数提供了复杂性保证,并说(17.5.1.4 [structure.specifications]):

库子句中指定的复杂性要求是上限,并且提供更好的复杂性保证的实现可以满足要求。

编译器可以更好地保留这些界限(并且由于许多函数是模板化的/可以被内联,因此涉及到了编译器),但是界限取决于容器中元素的数量,并限制了对比较运算符和 喜欢。 否则,编译器可以再次自由地进行操作。

Fred Foo answered 2020-08-11T04:08:51Z
24 votes

代码的性能不被视为可观察到的行为,编译器可能会在任一方向上对其进行修改。 实际上,出于实现质量(QoI)的考虑,编译器不会降低程序的性能,但是在某些情况下,QoI不会提高性能。

赋予适当的标志的编译器可以将其检测内容添加到正在构建的程序中,以进行调试(在库实现中,例如,经过检查的迭代器,通常是这种情况)。

请注意,何时编译器会使您的程序降级的简单答案是双重的:当客户端要求它时,或者当实现者不想让编译器的用户使用时。

David Rodríguez - dribeas answered 2020-08-11T04:09:20Z
16 votes

C标准中的5.1.2.3说

本国际标准中的语义描述描述了 与优化问题无关的抽象机器。

C ++标准在1.9 [intro.execution]中具有类似的措辞

两种标准对可观察的行为都有相同的定义:

符合标准的实现的最低要求是:
—严格按照摘要规则评估对易失对象的访问 机。
—在程序终止时,写入文件的所有数据应与以下结果相同: 将根据抽象语义执行程序。
—交互式设备的输入和输出动态应按照 7.21.3。 这些要求的目的是无缓冲或行缓冲输出 尽快出现,以确保提示消息实际上早于 等待输入的程序。
这是程序的可观察行为。

等等,例如 for循环的性能或对非易失性变量执行的读/写次数被认为是不可观察的,因此对编译器没有相应的性能要求。

如果编译器想要重新评估一个代码块100次(假设它没有明显的副作用,仅更改非易失性变量的状态),并检查每次是否获得了相同的结果(并且不受宇宙影响) 光线或硬件故障)。

Jonathan Wakely answered 2020-08-11T04:10:26Z
9 votes

其他人指出,该标准并不限制C运行时的工作方式,仅限制其可观察的行为。 例如,没有理由不能解释或JIT编译C。

考虑一个C实现,其中所有存储单元都存储在某个基础系统上的链表中。 然后,指针就是该链接列表的索引。 所有的指针操作都将正常运行,除了运行时必须在每次内存访问上遍历链接列表。 各种常见算法在其复杂性上会突然获得N的额外因子,例如常见的以空字符结尾的字符串操作。

pjc50 answered 2020-08-11T04:10:51Z
translate from https://stackoverflow.com:/questions/26230791/is-it-legal-for-the-compiler-to-degrade-the-time-complexity-of-a-program-is-thi