与 C 相比,无休止循环在 C++ 中没有副作用的好处是未定义的行为?

Benefit of endless-loops without side effects in C++ being undefined behavior compared to C?

提问人:wimalopaan 提问时间:8/23/2023 最后编辑:Peter Mortensenwimalopaan 更新时间:8/27/2023 访问量:3413

问:

在 C++ 循环中,作为

for(;;) {}

是未定义的行为,而它们不在 C(?) 中。

P2809R0。琐碎的无限循环不是未定义的行为,它表示这样做是有充分理由的。有没有简单的例子可以说明这一点?

C++ C 循环 优化 undefined-behavior

评论

0赞 463035818_is_not_an_ai 8/23/2023
我想你有“充分的理由”提到基本原理,但正在寻找一个具体的例子,对吧?
0赞 wimalopaan 8/23/2023
是的,没错!我正在寻找一个根据这种可能性进行优化的简单示例。
16赞 Lundin 8/23/2023
主要的好处是将另一个UB案例添加到无尽UB的浩瀚巨著中,有时被称为C++......
0赞 U. Windl 8/24/2023
我猜:由于现代 C 编译器会“优化”结构,例如没有任何影响(除了设置,也许),它也可能优化类似的无限循环(除非已编码异常)。为了评估整个循环的副作用,编译器必须检查循环后的状态(根据定义,在无限循环之后不存在)。此外,由于循环永无止境,因此考虑循环之后的语句是没有意义的。所以也许最好取消定义语义......for (i=0;i<9;++i) ;i = 10
1赞 Dmitry Grigoryev 8/25/2023
附带问题:如果是 UB,停止执行的 C++ 成语是什么?while(true);

答:

60赞 Quimby 8/23/2023 #1

原因只是优化。

如果编译器可以假设所有没有副作用的循环都终止,则不必证明这一点。

如果允许非终止循环,则只有在可以证明终止的情况下,编译器才被允许执行某些优化,这通常是不可能的,因此它将变成模式识别游戏。有什么好处?

根本问题是,不终止本身就是一种副作用。当且仅当循环终止时,即使循环没有任何影响,也会观察到循环终止后肯定会发生的任何可观察效果。

当然,可以进行完全相同的推理。编译器不允许在之前移动内容,除非它可以证明是假的。但这是基本的控制流机制,而非终止循环则不是(恕我直言)。if(expr) return;ififexprif

采用以下代码。

int collatz_conjecture(int i){
    while(i!=1){
        if ((i%2)==0)
            i/=2;
        else
            i=i*3+1;
    }
    return i;
}

int main(){
    collatz_conjecture(10);

    return 5;
}

使用 -O3,gcc 将其编译为:

collatz_conjecture(int):
        mov     eax, 1
        ret
main:
        mov     eax, 5
        ret

那么,编译器是否证明了 Collatz 猜想,以确定它应该返回所有数字?当然不是,这只是终止假设允许的优化之一(以及 UB 可能发生的地方)。循环可以终止的唯一方法是,如果它可以在循环之后假设并使用它来进一步优化 - >函数总是返回 1,因此可以简化为它。1i==1i==1

更有用的例子可以是交错复制。如果你有

loop A
loop B

编译器可以交错它们,即使不知道终止。许多矢量化操作都依赖于此假设。A

同样,在循环之前对一些独立的后循环操作进行重新排序,假设循环将终止。

评论

2赞 wimalopaan 8/23/2023
这是否意味着,在 C 语言中,这种优化是不可能的?
20赞 Cubic 8/23/2023
@Peter什么?NP难题可以在有限的时间内解决。这几乎就是“NP-hard”的定义。环路终止是不可决定的,不是NP硬或任何其他类型的硬。可以证明给定的循环是否会终止,但不可能设计出一种算法来确定任何循环的终止。一个多世纪前,CS的一篇基础论文证明了这一点,证明我们在过去一个世纪里是错误的,可能会付出代价,但我不会把钱花在实际发生的这件事上。
7赞 Cubic 8/23/2023
同样值得指出的是,“NP硬”并不意味着“不切实际”。这是一个普遍的神话。许多NP难题非常适合于随机方法、启发式方法和实际问题输入的近似方法。在编译器中出现 NP 困难甚至无法确定的问题并不少见,这些问题通常分别通过启发式和“尽力而为,如果不起作用,请报告错误”来解决。
4赞 Matthieu M. 8/24/2023
我确实注意到,在 Rust 中,循环是允许不终止的——事实上,它通常用作小型嵌入式平台上的实现。因此,虽然优化可能是UB缺乏进展的原因,但这是否是一个好理由是有争议的,因为C / C++ / Rust程序的性能往往相当。loop {}abort
2赞 Peter Cordes 8/25/2023
@wimalopaan:请参阅我之前的评论:C 与 C++。在 ISO C 中,只有具有常数作为循环控制的循环才允许无限大。仍可假定 Collatz 环路已终止。但这无助于真正的编译器矢量化。
5赞 supercat 8/24/2023 #2

主要优点是规范简单。假设规则不能真正适应这样一种概念,即程序可以具有已定义的行为,但可能明显与顺序程序执行不一致。此外,C 和 C++ 标准的作者使用短语“未定义行为”作为他们认为没有必要行使管辖权的情况的统称,在许多情况下,因为他们希望编译器编写者比委员会更了解其客户的需求。

大多数有用的优化都是通过指定以下方式实现的:如果循环中没有单个操作相对于后面的一段代码进行排序,则整个循环的执行也不需要被视为已排序。对于“在”无限循环之后出现的代码来说,这有点“手摇欲坠”,但它清楚地表明了它允许编译器做什么。除其他事项外,如果在程序终止之前没有对循环中的单个操作进行排序,则可以完全省略整个循环的执行

这种规则将体现的一个重要原则是,在循环内的代码和循环外的代码之间引入依赖关系的转换也将引入排序关系。如果某个循环在某个条件为真时退出,并且循环检查该条件后的代码,则编译器可以使用先前检查的结果来避免重复测试,但这意味着循环之后的代码依赖于循环中计算的值。

下面是一个具体的例子,说明可以应用该规则的有用和鲁莽的方式:

char arr[65537];
unsigned test(unsigned x, unsigned y)
{
    unsigned i=1;
    while((i & y) != x)
        i*=17;
    return i;
}
void test2(unsigned x)
{
    test(x, 65535);
    if (x < 65536)
        arr[x] = 2;
}

编译器在内联到中时可以应用两个单独有用的优化:testtest2

  1. 编译器可以识别出测试是否只能在小于 65536 的情况下报告“true”,从而使测试变得多余。x == (i & 65535)xiftest2()

  2. 编译器可以认识到,因为循环的唯一作用是计算,而当从内部调用时,的值最终会被忽略,所以循环的代码是多余的。iitest()test2()

在保持隔离的同时消除循环可能比相反的做法要好,但代码是否能够满足一个基本要求——它不写过元素 65535——取决于循环或测试被保留。在另一个存在的情况下,任何一个都是多余的,但缺少任何一个都会使另一个变得必不可少。ifarrif

请注意,如果在某些情况下需要使用外部手段终止应用程序是可以接受的,那么在保留数据依赖关系的同时,让编译器自由地对代码进行重新排序并不能排除正确的应用程序在输入一些可能的输入时可能陷入无限循环的可能性。然而,允许它们对代码进行重新排序而不考虑由此产生的数据依赖关系,将产生具有讽刺意味的效果,即加速主要“错误”的程序,这些程序不能依靠这些程序来满足应用程序要求,并且对大多数程序没有任何好处,这些程序增加了额外的检查或虚拟副作用(否则不需要满足应用程序要求)以防止无休止的循环。

PS -- 作为两段代码在另一段代码存在的情况下单独冗余的一般概念的进一步示例,请考虑以下函数:

double x,y,z;
void f1(void) {
  x=sin(z);
}
void f2(void)
{
  f1();
  y=sin(z);
  x=0;
}

赋值在编写的代码中是多余的,可以优化出来,因为没有任何东西使用存储在 中的值。within 的计算在编写的代码中是多余的,可以替换为 因为 will 已经保存了需要存储到 的值。然而,显而易见的是,任何一种转换本身都可以合法地应用,这并不意味着两者都可以合法地同时应用。这个原则应该适用于第一个示例片段中使用的优化类型的想法对于编写标准的人来说可能是显而易见的,但不幸的是,对于编写 clang 和 gcc 的人来说却不是。x=sin(z);xsin(z)f2y=x;xy

评论

1赞 kc9jud 8/25/2023
“他们希望编译器编写者比委员会更了解客户的需求”,这难道不是实现定义的行为而不是未定义的行为吗?
0赞 Peter Cordes 8/25/2023
@kc9jud:实现可以定义任何 ISO C++未定义的行为。例如,定义 的行为,而 MSVC 始终定义行为(它没有启用基于类型的别名分析的选项。并将有符号整数溢出的行为定义为 2 的补码换行。GCC(及其编译的 CPU)还定义了对象上数据争用的行为;Linux 内核(以及一些 C++ 之前的多线程代码)依赖于此。gcc -fno-strict-aliasing*(int*)&my_floatgcc -fwrapvvolatile
2赞 supercat 8/25/2023
@kc9jud:这个神话从何而来?实现定义的行为和未定义的行为之间的区别在于是否要求所有实现指定它们的行为方式。该标准承认,UB可能发生在不可移植但正确的程序中,甚至在正确和可移植的程序接收错误数据时。请参阅 open-std.org/jtc1/sc22/wg14/www/C99RationaleV5.10.pdf 第 11 页从第 23 行开始,并告诉我是否有任何迹象表明 UB 旨在邀请无端的荒谬行为。
0赞 kc9jud 8/26/2023
@supercat 撇开鼻魔不谈,我主要的意思是你的描述似乎比“未定义”更适合“实现定义”或“未指定”——我的理解是,许多事情被保留为未定义的行为,不是因为委员会谨慎地将决定权留给实施者,而是因为从形式上不可能定义一般的行为.不过,也许你确实对委员会的谨慎有一点看法——他们知道什么时候应该让编译器开发人员去做不可能的事情。:-)
1赞 supercat 8/26/2023
@kc9jud:C++ 标准的一个关键特征仍然存在于该草案中,一些编译器作者及其支持者忽略了这一点,即“尽管本文档仅陈述了对C++实现的要求,但如果将它们表述为对程序、程序部分或程序执行的要求,则这些要求通常更容易理解。该标准没有试图将可能的程序完全划分为正确的程序和不正确的程序,也没有做出与设计实现无关的区分。
-2赞 WPCNT 8/27/2023 #3

在 C 和 C++ 中,没有副作用的无限循环表现出未定义的行为。但是,编译器在两种语言之间处理这种情况的方式可能略有不同。最终,不建议依赖任何一种语言中的未定义行为,因为它可能导致不可预测的结果。最好避免编写故意依赖未定义行为的代码。

评论

1赞 Bob__ 8/27/2023
在发布您的答案之前,请仔细阅读问题、链接材料和已经发布的答案。