在 C + + 0x 中优化掉“ while (1) ;”

更新，见下面！

我听说和读到，C + + 0x 允许编译器为下面的代码片段打印“ Hello”

#include <iostream>


int main() {
while(1)
;
std::cout << "Hello" << std::endl;
}

它显然与线程和优化能力有关。不过在我看来，这可能会让很多人感到惊讶。

有人能解释一下为什么有必要允许这样做吗？作为参考，最新的 C + + 0x 草案说在 6.5/5

在 for 语句的情况下，在 for-init 语句之外的一个循环,

  • 不调用库 I/O 函数，并且
  • 不访问或修改易失性对象，并且
  • 不执行同步操作(1.10)或原子操作(条款29)

可能被实现假定为终止。[注意: 这是为了允许编译器转换- 即使无法证明终止，也可以删除空循环。ーー结束注释]

编辑:

这篇有见地的文章 谈到了标准文本

不幸的是，“未定义行为”这个词并没有被使用。然而，任何时候标准说“编译器可以假设 P”，这意味着具有非 P 属性的程序具有未定义的语义。

是否正确，编译器是否允许为上面的程序打印“再见”？

还有一个更有见地的 这里有线，这是一个类似于 C 的变化，由 Guy 开始完成上面的链接文章。在其他有用的事实中，他们提出了一个似乎也适用于 C + + 0x 的解决方案(更新: 这在 n3225中不再有效——见下文!)

endless:
goto endless;

编译器似乎不允许优化它，因为它不是一个循环，而是一个跳转。另一个人总结了 C + + 0x 和 C201X 中提出的更改

通过编写一个循环，程序员断言 都不是 Loop 使用可见行为执行某些操作(执行 I/O，访问 或执行同步操作或原子操作) , 如果我违背了这个假设 通过编写一个没有副作用的无限循环，我在欺骗 编译器，我的程序的行为是未定义的。(如果我幸运, 编译器可能会警告我) (不再提供?)表达无限循环的方法 看得见的行为。

2011年3月1日 n3225更新: 委员会将文本移至1.10/24，并说

实现可能假设任何线程最终将执行下列操作之一:

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

goto的技巧将 没有工作了！

16528 次浏览
小开

我认为这是沿着这种类型的 有个问题的路线，它引用了另一个 线。优化偶尔可以消除空循环。

小开

对我来说，相关的理由是:

这是为了允许编译器转换，例如删除空循环，即使无法证明终止。

这可能是因为机械地证明终止是 很难，而无法证明终止会妨碍编译器进行有用的转换，比如将非依赖性操作从循环前移动到循环后，或者相反，在一个线程中执行后循环操作，而循环在另一个线程中执行，等等。如果没有这些转换，循环可能会在所有其他线程等待一个线程完成所述循环时阻塞它们。(我使用“线程”宽松地表示任何形式的并行处理，包括单独的 VLIW 指令流。)

编辑: 愚蠢的例子:

while (complicated_condition()) {
x = complicated_but_externally_invisible_operation(x);
}
complex_io_operation();
cout << "Results:" << endl;
cout << x << endl;

在这里，如果一个线程执行 complex_io_operation，而另一个线程在循环中执行所有复杂的计算，那么速度会更快。但是如果没有您引用的子句，编译器在进行优化之前必须证明两件事: 1) complex_io_operation()不依赖于循环的结果; 2) 循环将终止。证明1)是相当容易的，证明2)是停顿的问题。使用这个子句，它可以假设循环终止并且获得并行化胜利。

我还想象到，设计人员认为在生产代码中出现无限循环的情况非常罕见，通常是像以某种方式访问 I/O 的事件驱动循环这样的情况。因此，他们对罕见的情况(无限循环)持悲观态度，而倾向于优化更常见的情况(非无限循环，但很难机械地证明非无限循环)。

然而，这确实意味着在学习示例中使用的无限循环会因此受到影响，并且会增加初学者代码中的陷阱。我不能说这完全是件好事。

编辑: 关于你现在链接的这篇有见地的文章，我想说“编译器可能假设程序是 X”在逻辑上等同于“如果程序不满足 X，那么行为是未定义的”。我们可以如下所示: 假设存在一个不满足属性 X 的程序。在哪里可以定义这个程序的行为？标准只定义了假设属性 X 为真的行为。虽然标准没有明确宣布行为未定义，它已宣布它未定义的遗漏。

考虑一个类似的参数: “编译器可以假设变量 x 在序列点之间最多只被赋值一次”等同于“在序列点之间未定义的变量 x 不止一次被赋值”。

小开

我认为正确的解释是你编辑的那个: 空的无限循环是未定义行为的。

我不会说这是特别直观的行为，但是这种解释比另一种解释更有意义，即编译器被任意允许在不调用 UB 的情况下进行 忽略无限循环。

如果无限循环是 UB，那就意味着非终止程序没有意义: 根据 C + + 0x，它们 有没有语义。

这也说得通。它们是一种特殊的情况，其中许多副作用不再发生(例如，从 main中不再返回任何内容) ，并且许多编译器优化由于必须保留无限循环而受到阻碍。例如，如果循环没有副作用，则在循环中移动计算是完全有效的，因为最终将在任何情况下执行计算。 但是，如果循环永远不会终止，我们就不能安全地跨循环重新排列代码，因为我们 也许吧只是在程序挂起之前更改实际执行的操作。除非我们把绞刑程序当作 UB。

小开

相关的问题是允许编译器对副作用不冲突的代码重新排序。即使编译器为无限循环生成未终止的机器代码，也可能出现令人惊讶的执行顺序。

我相信这是正确的方法。语言规范定义了强制执行顺序的方法。如果您想要一个无法重新排序的无限循环，请编写以下代码:

volatile int dummy_side_effect;


while (1) {
dummy_side_effect = 0;
}


printf("Never prints.\n");
小开

我认为这个问题最好这样说，“如果后面的一段代码不依赖于前面的一段代码，而前面的一段代码对系统的任何其他部分都没有副作用，那么编译器的输出可能会在前面的代码执行之前、之后或者与前面的代码混合执行之后执行后面的一段代码，即使前面的代码包含循环 而不考虑以前的代码实际上何时或是否会完成。例如，编译器可以重写:

void testfermat(int n)
{
int a=1,b=1,c=1;
while(pow(a,n)+pow(b,n) != pow(c,n))
{
if (b > a) a++; else if (c > b) {a=1; b++}; else {a=1; b=1; c++};
}
printf("The result is ");
printf("%d/%d/%d", a,b,c);
}

作为

void testfermat(int n)
{
if (fork_is_first_thread())
{
int a=1,b=1,c=1;
while(pow(a,n)+pow(b,n) != pow(c,n))
{
if (b > a) a++; else if (c > b) {a=1; b++}; else {a=1; b=1; c++};
}
signal_other_thread_and_die();
}
else // Second thread
{
printf("The result is ");
wait_for_other_thread();
}
printf("%d/%d/%d", a,b,c);
}

一般来说并非不合理，尽管我可能会担心:

int total=0;
for (i=0; num_reps > i; i++)
{
update_progress_bar(i);
total+=do_something_slow_with_no_side_effects(i);
}
show_result(total);

会变成

int total=0;
if (fork_is_first_thread())
{
for (i=0; num_reps > i; i++)
total+=do_something_slow_with_no_side_effects(i);
signal_other_thread_and_die();
}
else
{
for (i=0; num_reps > i; i++)
update_progress_bar(i);
wait_for_other_thread();
}
show_result(total);

通过让一个 CPU 处理计算，另一个 CPU 处理进度条更新，重写将提高效率。不幸的是，这会使进度条更新的用处大打折扣。

小开

对于非平凡的情况，如果它是一个无限循环，那么它对于编译器来说是不可判定的。

在不同的情况下，您的优化器可能会为您的代码达到一个更好的复杂度类(例如，它是 O (n ^ 2) ，优化后您会得到 O (n)或 O (1))。

因此，在 C + + 标准中包含这样一个不允许移除无限循环的规则将使许多优化成为不可能。大多数人都不想这样。我想这很好地回答了你的问题。

还有一件事: 我从来没有见过任何有效的例子，你需要一个无限循环，什么也不做。

我听说过的一个例子是一个丑陋的黑客行为，真的应该解决，否则: 这是关于嵌入式系统，触发重置的唯一方法是冻结设备，以便看门狗自动重新启动它。

如果你知道任何有效的/好的例子，你需要一个无限循环什么也不做，请告诉我。

小开

我认为值得指出的是，除了它们通过非易失性、非同步变量与其他线程交互这一事实之外，那些无限循环现在可以在新编译器中产生不正确的行为。

换句话说，让你的全局变量以及通过指针/引用传递到这样一个循环中的参数是可变的。

小开
最佳答案

有人能解释一下为什么有必要允许这样做吗？

是的，Hans Boehm 在 N1528: 为什么未定义行为无限循环？中为此提供了一个基本原理，尽管这是 WG14文档，但是这个基本原理也适用于 C + + ，而且这个文档同时涉及了 WG14和 WG21:

正如 N1509正确指出的那样，目前的草案基本上给出了 在6.8.5 p6中未定义行为到无限循环 这样做是因为它允许代码在潜在的 非终止循环。例如，假设我们有以下循环, 其中 count 和 count 2是全局变量(或者有它们的地址 P 是一个局部变量，其地址未被采用:

for (p = q; p != 0; p = p -> next) {
++count;
}
for (p = q; p != 0; p = p -> next) {
++count2;
}

这两个循环可以合并并用下面的循环代替吗？

for (p = q; p != 0; p = p -> next) {
++count;
++count2;
}

如果没有6.8.5 p6中对无限循环的特殊分配，这个 将被禁止: 如果第一个循环不终止，因为 q 指向一个循环列表，原始列表从不写到 count 2 它可以与另一个线程并行运行，这个线程可以访问或 这在转换后的版本中不再安全 尽管存在无限循环，它仍然访问 count 2 转换可能引入数据竞争。

在这种情况下，编译器不太可能 证明循环终止; 它必须理解 q 点 到一个无环列表，我相信这超出了大多数人的能力 主流编译器，往往不可能没有整个程序 资料。

非终止循环施加的限制是对 编译器不能优化的终止循环 证明终止，以及对实际的优化 非终止循环。前者比 后者，往往更有趣的优化。

中还有一个带整数循环变量的 for 循环 编译器很难证明终止 因此，编译器很难重新构造循环 没有6.8.5 p6

for (i = 1; i != 15; i += 2)

或者

for (i = 1; i <= 10; i += j)

(在前一种情况下，一些基本的数字 理论需要证明终止，在后一种情况下，我们需要 了解关于 j 的可能值的一些信息 因为无符号整数可能会使这个推理进一步复杂化。)

这个问题似乎适用于几乎所有的循环重组 转换，包括编译器并行化和 缓存优化转换，两者都可能获得 在重要性，并已经往往是重要的数字代码。 这似乎有可能变成一个巨大的成本，为受益者 能够以最自然的方式写出无限循环, 特别是因为我们大多数人很少故意写无限循环。

与 C 的一个主要区别是 C11为控制常量表达式提供了异常不同于 C + + ，它使您的特定示例在 C11中得到了很好的定义。


提交答案