在C++0X中优化“时(1)”

有人能很好地解释为什么必须允许这样做吗?

是的,汉斯·博姆在 N1528: Why undefined behavior for infinite loops? 虽然这是WG14文档,其原理也适用于C++,该文档同时涉及WG14和WG21:

正如N1509正确指出的,当前的草案基本上给出了 6.8.5p6中无限循环的未定义行为。一个主要问题 这样做是为了允许代码在 非终止循环。例如,假设我们有以下循环, 其中count和count2是全局变量(或具有其地址) taken),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而未终止 指向循环列表,原始列表从不写入count2。因此 它可以与另一个访问或 更新count2。这对于转换版本不再安全 它可以访问count2,尽管有无限循环。因此 转换可能会引入数据竞争。

在这种情况下,编译器不太可能 为了证明回路终止,必须理解Q点 到一个非循环的列表,我认为这是最不可能的 主流的编译器,如果没有整个程序通常是不可能的 信息。

非端接回路施加的限制是对 编译程序无法完成的终止循环的优化 证明终止,以及对实际 非端接回路。前者比后者更常见 后者,往往更有趣的是优化。

显然,在 编译器很难证明终止,以及 因此,编译器很难重新构造循环 无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中得到了很好的定义。

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

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

大概是因为机械地证明终止是 困难的 ,并且无法证明终止会妨碍编译器进行有用的转换,例如将非依赖操作从循环之前移动到循环之后,或者反之亦然,在一个线程中执行循环后操作,而在另一个线程中执行循环,等等。如果没有这些转换,一个循环可能会在等待一个线程完成所述循环时阻塞所有其他线程。(我松散地使用“线程”来表示任何形式的并行处理,包括单独的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。因此,他们对极少数情况(无限循环)持悲观态度,赞成优化更常见的情况(非有限,但难以机械证明非有限循环)。

然而,它确实意味着学习示例中使用的无限循环将因此而受到影响,并且将在初学者代码中引发gotchas。我不能说这完全是好事。

编辑:关于你现在链接的有见地的文章,我会说“编译器可能假设x关于程序”在逻辑上等同于“如果程序不满足x,行为是未定义的”。我们可以这样表示:假设存在一个不满足属性x的程序,那么该程序的行为将在哪里定义呢?该标准仅定义假定属性x为真的行为。虽然该标准没有明确声明行为未定义,但它已通过省略声明行为未定义。

考虑一个类似的参数:“编译器可能假设变量x在序列点之间最多分配一次”相当于“在序列点之间多次分配给x未定义”。

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

我不会说它是特别直观的行为,但是这种解释比另一种解释更合理,编译器被任意地允许 忽视 无限循环而不调用ub。

如果无限循环是UB,那就意味着非终结程序没有被认为是有意义的:根据C++0x,它们 有 没有语义。

这也确实有一定的道理。它们是一种特殊情况,其中一些副作用不再发生(例如,没有任何东西从 main )和一些编译器优化由于必须保留无限循环而受到阻碍。例如,如果循环没有副作用,则在循环中移动计算是完全有效的,因为最终,计算将在任何情况下执行。 但是如果循环永不终止,我们就不能安全地在循环中重新排列代码,因为我们 可以 只需更改在程序挂起之前实际执行的操作。除非我们将挂起的程序视为UB,否则就是。

我认为这是沿着这类 question ,它引用了另一个 thread . 优化有时可以删除空循环。

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

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

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++标准中会使许多优化变得不可能。大多数人不想这样。我认为这完全回答了你的问题。

另一件事:我从来没有见过任何有效的例子,在这里你需要一个不做任何事情的无限循环。

我听过的一个例子是一个丑陋的黑客,如果不是这样的话,那真的应该解决:它是关于嵌入式系统的,触发重置的唯一方法就是冻结设备,以便看门狗自动重启它。

如果您知道任何有效/良好的例子,您需要一个不做任何事情的无限循环,请告诉我。

我认为值得指出的是,循环将是无限的,除非它们通过非易失性的、非同步的变量与其他线程交互,现在使用新的编译器可以产生错误的行为。

换句话说,使全局变量不稳定——以及通过指针/引用传递到此类循环中的参数。