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

Question

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

是否允许编译器降低程序的时间复杂度？
在什么情况下(如果有的话)这被认为是"可观察的行为",为什么？
(例如,编译器能否合法地将多项式时间程序"减少"到指数时间程序？)

如果答案在C和C++中有所不同,或者在两者的不同版本中都有所不同,那么请解释这些差异.

Answer 1

C标准实际上没有时间复杂度模型,既不是它的原始操作,也不是它的库函数,因此允许编译器做任何保留程序语义(可观察行为)的东西.

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

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

编译器更好地保留这些边界(并且因为许多函数是模板化的/可能是内联的,所以涉及编译器),但是边界是根据容器中的元素数量来限制对比较运算符的调用次数和喜欢.否则,编译器可以随意自由地进行操作.

Answer 2

代码的性能不被视为可观察的行为,并且可能被编译器在任一方向上修改.实际上,对于实现质量(QoI)的原因,编译器不会降低程序的性能,但有些情况下QoI不是性能.

在给定适当标志的情况下,编译器可以将检测添加到它正在构建的程序中以进行调试(在库实现中通常就是这种情况,例如使用已检查的迭代器).

请注意,编译器何时降级程序的简单答案有两个:当客户端请求它时,或者实现者不希望有编译器的用户时.

Answer 3

5.1.2.3在C标准中说

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

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

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

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

所以其他任何东西,例如for循环的性能,或者为非易失性变量完成的读/写次数,都不被认为是可观察的,因此对编译器没有相应的性能要求.

如果编译器想要重新评估一段代码100次(假设它没有可观察到的副作用,只改变非易失性变量的状态)并检查每次都获得相同的结果(并且不受宇宙影响)标准允许的射线或有缺陷的硬件).

Answer 4

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

考虑一个C实现,其中所有存储器单元存储在某个底层系统的链表中.指针是这个链表的索引.所有指针操作都将正常运行,但运行时必须在每次内存访问时迭代链表.各种常见算法会突然在其复杂性中获得额外的N因子,例如常见的以空值终止的字符串操作.