优化远离“同时”(1)C++0x中的“

cotxawn7  于 2023-01-22  发布在  其他
关注(0)|答案(9)|浏览(136)
  • 已更新,请参阅下文! *

我听说过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条)

可被实现假定为终止。[注:这是为了允许编译器转换,例如删除空循环,即使无法证明终止。-结束注解]

    • 编辑:**

This insightful article说明了该标准文本
不幸的是,没有使用"未定义的行为"这个词,但是,无论何时,只要标准说"编译器可以假设P",这就意味着一个具有属性not-P的程序具有未定义的语义。
对吗?编译器允许为上面的程序打印"Bye"吗?
还有一个更有见地的thread here,它是关于对C的一个类似的变化,由完成上述链接文章的家伙开始。除了其他有用的事实外,他们提出了一个似乎也适用于C ++0x的解决方案(* 更新 *:这将不再适用于n3225-见下文!)

endless:
  goto endless;

编译器似乎不允许优化它,因为它不是一个循环,而是一个跳转。另一个人总结了C ++0x和C201X中建议的更改
通过编写一个循环,程序员Assert * 或者 * 该循环以可见的行为执行某些操作(执行I/O,访问volatile对象,或者执行同步或原子操作),* 或者 * 它最终会终止。如果我写了一个没有副作用的无限循环,违反了这个假设,我就是在对编译器撒谎,我的程序的行为是未定义的。(如果我幸运的话,编译器可能会警告我。)该语言没有提供(不再提供?)一种方法来表达一个没有可见行为的无限循环。
2011年1月3日更新n3225:委员会将案文移至1.10/24,并说
该实现可以假设任何线程最终将执行以下操作之一:

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

goto的把戏将不再工作!

koaltpgm

koaltpgm1#

对我来说,相关的理由是:
这是为了允许编译器转换,例如删除空循环,即使无法证明终止。
据推测,这是因为机械地证明终止是“困难的”,并且无法证明终止阻碍了编译器,否则编译器可以进行有用的转换,诸如将非依赖操作从循环之前移动到循环之后或反之亦然,在一个线程中执行循环后操作而循环在另一个线程中执行,等等。一个循环可能会阻塞所有其他线程,因为它们等待一个线程完成这个循环。2(我使用“线程”来表示任何形式的并行处理,包括独立的VLIW指令流。3)
编辑:哑示例:

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的程序。2这个程序的行为在哪里定义?3标准只在假设性质X为真的情况下定义行为。4虽然标准没有明确声明行为未定义,但它通过省略声明了未定义。
考虑一个类似的论证:“编译器可以假设变量x在序列点之间至多只被赋值一次”等同于“在序列点之间不止一次地赋值x是未定义的”。

polkgigr

polkgigr2#

有人能很好地解释为什么有必要允许这样做吗?
是的,Hans Boehm在N1528: Why undefined behavior for infinite loops?中提供了这方面的依据,尽管这是WG 14文档,但该依据也适用于C++,并且该文档同时引用了WG 14和WG 21:
正如N1509所正确指出的,当前的草案本质上为6.8.5p6中的无限循环提供了未定义的行为。这样做的一个主要问题是,它允许代码在潜在的非终止循环中移动。例如,假设我们有以下循环,其中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.5p6中对无限循环的特殊豁免,这将是不允许的:如果第一个循环因为q指向循环列表而没有终止,那么原始的循环就不会写入count 2。因此,它可能会与另一个访问或更新count 2的线程并行运行。这对于转换后的版本来说不再是安全的,因为转换后的版本会访问count 2,尽管存在无限循环。因此,转换可能会引入数据竞争。
在这种情况下,编译器不太可能证明循环终止;它必须理解q指向一个非循环列表,我相信这超出了大多数主流编译器的能力,并且在没有整个程序信息的情况下通常是不可能的。
非终止循环所施加的限制是对编译器无法证明其终止性的终止循环的优化的限制,以及对实际非终止循环的优化的限制。前者比后者更常见,并且通常更值得优化。
显然,还有一些for循环带有整数循环变量,编译器很难证明其中的终止性,因此,如果没有6.8.5p6,编译器也很难重构循环。

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

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

(在前一种情况下,需要一些基本的数论来证明终止性,在后一种情况下,我们需要知道一些关于j的可能值的信息来证明终止性。对无符号整数的回绕可能会使一些推理更加复杂。)
这个问题似乎适用于几乎所有的循环重构转换,包括编译器并行化和缓存优化转换,这两种转换的重要性可能会增加,并且对于数字代码来说已经很重要了。这似乎可能会变成一个巨大的成本,以尽可能自然的方式编写无限循环。特别是因为我们大多数人很少有意编写无限循环。
与C的一个主要区别是C11 provides an exception for controlling expressions that are constant expressions,它与C++不同,使您的特定示例在C11中定义良好。

9gm1akwq

9gm1akwq3#

我认为正确的解释是来自你的编辑:空无限循环是未定义的行为。
我不会说这是特别直观的行为,但这种解释比另一种解释更有意义,即编译器被任意允许在不调用UB的情况下 * 忽略 * 无限循环。
如果无限循环是UB,那就意味着非终止程序被认为没有意义:根据C++0x,它们 * 没有 * 语义。
这在一定程度上也是有道理的。它们是一种特殊情况,许多副作用不再发生(例如,从main没有返回任何东西),并且许多编译器优化由于必须保留无限循环而受到阻碍。例如,如果循环没有副作用,则在循环中移动计算完全有效,因为最终,但如果循环永远不会终止,我们就不能安全地重新排列代码,因为我们 * 可能 * 只是在改变程序挂起前实际执行的操作,除非我们把挂起的程序当作UB。

hyrbngr7

hyrbngr74#

相关的问题是允许编译器对副作用不冲突的代码进行重新排序,即使编译器为无限循环生成了非终止机器码,也可能出现令人惊讶的执行顺序。
我相信这是正确的方法。语言规范定义了强制执行顺序的方法。如果你想要一个不能重新排序的无限循环,编写如下:

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");
hjzp0vay

hjzp0vay5#

我认为这是沿着这类问题的思路,它引用了另一个thread。优化偶尔可以删除空循环。

eulz3vhy

eulz3vhy6#

我认为这个问题最好这样表述:“如果后面的代码不依赖于前面的代码,并且前面的代码对系统的任何其他部分都没有副作用,那么编译器的输出可能会在前面的代码执行之前、之后或混合执行后面的代码,即使前面的代码包含循环without regard for when or whether the former code would actually complete。编译器可以重写:

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处理计算,另一个处理进度条更新,重写可以提高效率,但不幸的是,它会使进度条更新没有那么有用。

wlzqhblo

wlzqhblo7#

如果它是一个无限循环,那么对于非平凡的情况,编译器是不可判定的。
在不同的情况下,你的优化器可能会为你的代码达到一个更好的复杂度类(例如,它是O(n^2),而你在优化后得到O(n)或O(1))。
所以,在C++标准中加入这样一条规则,禁止删除无限循环,这会使很多优化变得不可能,大多数人不希望这样,我想这已经回答了你的问题。
还有一件事:我从来没有见过任何有效的例子,你需要一个无限循环,什么也不做。
我听说过的一个例子是一个丑陋的黑客,真的应该解决否则:它是关于嵌入式系统的,在那里触发复位的唯一方法是冻结设备,以便看门狗自动重新启动它。
如果你知道任何有效的/好的例子,你需要一个无限循环,什么也不做,请告诉我。

z6psavjg

z6psavjg8#

有人能很好地解释为什么有必要允许这样做吗?
我有一个解释,为什么有必要 * 不 * 允许,假设C仍然有野心成为一个通用语言适合性能关键的,低级编程。
这曾经是一个工作的、严格遵循的独立C
程序:

int main()
{
  setup_interrupts();
  for(;;)
  {}
}

以上是在许多低端微控制器系统中编写main()的一种非常好的通用方法。整个程序执行在中断服务例程内完成(或者在RTOS的情况下,它可以是进程)。而且main()可能绝对不允许return,因为这些是裸机系统,没有人可以返回。
可以使用上述设计的典型真实世界示例是PWM/电机驱动器微控制器、照明控制应用、简单调节器系统、传感器应用、简单家用电子产品等。
不幸的是,C的变化使得这种语言不可能用于这种嵌入式系统编程。如果移植到更新的C编译器上,现有的实际应用程序(如上面的应用程序)将以危险的方式崩溃。
C20 www.example.com前进进度[介绍进度]6.9.2.3 Forward progress [intro.progress]
该实现可以假设任何线程最终将执行以下操作之一:
(1.1)- 终止,
(1.2)- 调用库I/O函数,
(1.3)- 通过易失性glvalue执行访问,或者
(1.4)- 执行同步操作或原子操作。
让我们解决上面的每一个项目符号,以前严格符合独立的C
程序:

  • 1.1.任何嵌入式系统初学者都可以告诉委员会,裸机/RTOS微控制器系统永远不会终止,因此循环也不能终止,否则main()将变成失控代码,这将是一个严重而危险的错误条件。
  • 1.2不适用。
  • 1.3不一定。有人可能会说for(;;)循环是给看门狗提供信息的合适位置,这反过来又是它写入volatile寄存器时的副作用。但可能有一些实现原因导致你不想使用看门狗。无论如何,规定应该使用看门狗不是C++的职责。
  • 1.4不适用。

因此,C比以前更不适合嵌入式系统应用程序。
这里的另一个问题是标准谈到了"线程",这是更高层次的概念。在现实世界的计算机上,线程是通过一个被称为中断的低层次概念实现的。中断在竞争条件和并发执行方面与线程相似,但它们不是线程。在低级系统上,只有一个内核,因此通常一次只执行一个中断(有点像过去在单核PC上工作的线程)。
如果你不能有中断,你就不能有线程,所以线程必须用一种比C
更适合嵌入式系统的低级语言来实现,选择是汇编语言还是C。
通过编写一个循环,程序员Assert该循环以可见的行为(执行I/O、访问volatile对象、执行同步或原子操作)执行某些操作,或者Assert它最终终止。
这是完全误导和明确写的人谁从来没有与微控制器编程工作。
那么,那些"因为某些原因"而拒绝将代码移植到C语言的少数C++嵌入式程序员应该怎么做呢?您必须在for(;;)循环中引入一个副作用:

int main()
{
  setup_interrupts();
  for(volatile int i=0; i==0;)
  {}
}

或者,如果您已经启用了看门狗,请在for(;;)循环中输入它。

wqnecbli

wqnecbli9#

我认为值得指出的是,除了通过非易失性、非同步变量与其他线程交互之外,循环将是无限的,现在使用新的编译器可能会产生不正确的行为。
换句话说,使全局变量可变--以及通过指针/引用传递到这样一个循环中的参数。

相关问题