是否有一个循环构造重复 n 次而不计算某些条件？
Is there a loop construct that repeats n times without calculating some conditional?
这个问题是在优化代码以消除潜在的分支预测失败的上下文中产生的。实际上，是一起删除分支。
对于我的示例，典型的 for 循环使用以下语法：
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int main()
{
bool *S = calloc(N + 1, sizeof(bool));
int p = 2;
for (int i = p * p; i <= N; i += p)
S[i] = 1;
return 0;
}
据我了解，生成的汇编代码将包含某种 JMP 指令来检查 i <= N.
我能想到的在汇编中这样做的唯一方法是重复相同的汇编指令 n 次，并且 i 在每次重复中递增。但是，对于大型 n，生成的二进制文件将非常庞大。
所以，我想知道，是否有一些循环结构可以重复 n 次而不计算某些条件？
完全展开是唯一可行的方法，你是对的，它不适合大量迭代计数（通常不适用于迭代计数不是 a 的循环）编译时常量）。它非常适合具有已知迭代次数的小循环。
对于您的具体情况，在给定距离内将内存设置为 1，x86 具有 rep stosb，它在微代码 中实现了 memset。它不会受到当前 Intel CPUs 上的分支预测错误的影响，因为微代码分支无法预测/推测执行并停止（或其他），这意味着它在执行任何操作之前有大约 15 个周期的启动开销商店。见 对于大
对齐缓冲区，
所以您没有得到错误预测，但您确实得到了固定的启动开销。 （我认为这会在 rep stos 之后停止发出/执行指令，因为微码定序器接管了前端，直到它完成发出所有 uops。而且它不能知道它什么时候完成，直到它执行了一些看 rcx 的东西。问题是按顺序发生的，所以后来的独立指令甚至不能进入核心的乱序部分，直到 rep stos 之后找出要发布的 uops。商店不必执行，但微代码分支执行。）Icelake 应该有“fast short REP MOV", which may finally solve the startup-overhead issue. Possibly by adding a dedicated hardware state-machine for rep movs and rep stos, like 在英特尔的 P6 uarch 中设计快速字符串时（ppro/PII/PIII） ，当前 Intel CPUs 的祖先仍然使用非常相似的微编码实现。据我所知，AMD 是相似的，但我还没有看到他们 rep stos 启动开销的数字或细节。
大多数体系结构都没有这样的单指令memset，因此x86 绝对是计算机体系结构中的一个特例。但是一些旧计算机（如 Atari ST）可能有 "blitter" chip to offload copying memory，尤其是用于图形目的。他们会使用 DMA 与 CPU 完全分开进行复制。这与在芯片上构建硬件状态机非常相似 运行 rep movs.
正常循环分支预测失误
考虑，喜欢
.looptop: do {
# loop body includes a pointer increment
# may be unrolled some to do multiple stores per conditional branch
cmp rdi, rdx
jb .looptop } while(dst < end_dst);
在循环 运行 几次后，分支最终被强烈预测采用。
对于大量迭代计数，一个分支预测错误会在所有循环迭代中分摊并且通常可以忽略不计。 （循环底部的条件分支被预测采用，因此循环分支错误预测了一次它没有被采用。）
一些分支预测器对循环分支有特殊的支持，有一个模式预测器可以计算模式，比如采取 30 次/不采取。他们可以正确预测最大迭代次数的一些大限制。
或者现代的 TAGE 预测器（如 Intel Sandybridge 系列）使用分支历史来索引条目，因此它 "naturally" 可以为您提供一些模式预测。例如，在我的测试中，Skylake 正确预测了最多约 22 次迭代的内部循环的循环退出分支。 （当有一个简单的外部循环重新 运行 重复相同迭代计数的内部循环时。）我在 asm 中测试，而不是 C，所以我控制了展开的程度。
中等长度的循环太长而无法正确预测出口是最坏的情况。它足够短，以至于经常发生循环退出的错误预测，例如，如果它是一个内部循环，在无法预测的 CPU 上重复 运行s ~30 次迭代。
在最后一次迭代中出现一次错误预测的成本可能非常低。如果乱序执行可以 "see" 为一个简单的循环计数器提前几次迭代，它可以让分支本身执行，然后再花很多时间在那个错误预测的分支之外的实际工作上。通过对分支未命中的快速恢复（不是通过使用诸如分支顺序缓冲区之类的东西来刷新整个无序管道），您仍然会失去在循环几个周期后开始独立工作的机会。如果依赖链的延迟出现循环瓶颈，这很可能是这种情况，但计数器本身是一个单独的链。 This paper关于分支未命中的实际成本也很有趣，并提到了这一点。
（请注意，我假设分支预测已经 "primed"，因此第一次迭代正确预测了所采用的循环分支。）
不切实际的方法:
@Hadi 链接了一个有趣的想法：而不是正常的 运行ning 代码，以一种奇怪的方式编译，其中控制和指令都是数据，例如 x86 仅使用 mov 指令与 x86寻址模式+寄存器。 （以及一个大块底部的无条件分支）。 Is it possible to make decisions in assembly without using `jump` and `goto` at all? 这效率低得可笑，但实际上没有任何条件分支：一切都是数据依赖。
它使用了不同形式的 MOV（在寄存器之间，立即寄存器，以及 load/store），所以它不是单指令集计算机。
一个不那么疯狂的版本是解释器：被解释代码中的不同指令/操作变成解释器中的控制依赖（为解释创建一个难以解决的效率问题，参见Darek Mihocka's "The Common CPU Interpreter Loop Revisited" article, 但是来宾代码中的数据和控制流都是解释器中的数据。来宾程序计数器只是解释器中的另一条数据。
这个问题是在优化代码以消除潜在的分支预测失败的上下文中产生的。实际上，是一起删除分支。
对于我的示例，典型的 for 循环使用以下语法：
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int main()
{
bool *S = calloc(N + 1, sizeof(bool));
int p = 2;
for (int i = p * p; i <= N; i += p)
S[i] = 1;
return 0;
}
据我了解，生成的汇编代码将包含某种 JMP 指令来检查 i <= N.
我能想到的在汇编中这样做的唯一方法是重复相同的汇编指令 n 次，并且 i 在每次重复中递增。但是，对于大型 n，生成的二进制文件将非常庞大。
所以，我想知道，是否有一些循环结构可以重复 n 次而不计算某些条件？
完全展开是唯一可行的方法，你是对的，它不适合大量迭代计数（通常不适用于迭代计数不是 a 的循环）编译时常量）。它非常适合具有已知迭代次数的小循环。
对于您的具体情况，在给定距离内将内存设置为 1，x86 具有 rep stosb，它在微代码 中实现了 memset。它不会受到当前 Intel CPUs 上的分支预测错误的影响，因为微代码分支无法预测/推测执行并停止（或其他），这意味着它在执行任何操作之前有大约 15 个周期的启动开销商店。见
所以您没有得到错误预测，但您确实得到了固定的启动开销。 （我认为这会在 rep stos 之后停止发出/执行指令，因为微码定序器接管了前端，直到它完成发出所有 uops。而且它不能知道它什么时候完成，直到它执行了一些看 rcx 的东西。问题是按顺序发生的，所以后来的独立指令甚至不能进入核心的乱序部分，直到 rep stos 之后找出要发布的 uops。商店不必执行，但微代码分支执行。）Icelake 应该有“fast short REP MOV", which may finally solve the startup-overhead issue. Possibly by adding a dedicated hardware state-machine for rep movs and rep stos, like rep stos 启动开销的数字或细节。
大多数体系结构都没有这样的单指令memset，因此x86 绝对是计算机体系结构中的一个特例。但是一些旧计算机（如 Atari ST）可能有 "blitter" chip to offload copying memory，尤其是用于图形目的。他们会使用 DMA 与 CPU 完全分开进行复制。这与在芯片上构建硬件状态机非常相似 运行 rep movs.
正常循环分支预测失误
考虑
.looptop: do {
# loop body includes a pointer increment
# may be unrolled some to do multiple stores per conditional branch
cmp rdi, rdx
jb .looptop } while(dst < end_dst);
在循环 运行 几次后，分支最终被强烈预测采用。
对于大量迭代计数，一个分支预测错误会在所有循环迭代中分摊并且通常可以忽略不计。 （循环底部的条件分支被预测采用，因此循环分支错误预测了一次它没有被采用。）
一些分支预测器对循环分支有特殊的支持，有一个模式预测器可以计算模式，比如采取 30 次/不采取。他们可以正确预测最大迭代次数的一些大限制。
或者现代的 TAGE 预测器（如 Intel Sandybridge 系列）使用分支历史来索引条目，因此它 "naturally" 可以为您提供一些模式预测。例如，在我的测试中，Skylake 正确预测了最多约 22 次迭代的内部循环的循环退出分支。 （当有一个简单的外部循环重新 运行 重复相同迭代计数的内部循环时。）我在 asm 中测试，而不是 C，所以我控制了展开的程度。
中等长度的循环太长而无法正确预测出口是最坏的情况。它足够短，以至于经常发生循环退出的错误预测，例如，如果它是一个内部循环，在无法预测的 CPU 上重复 运行s ~30 次迭代。
在最后一次迭代中出现一次错误预测的成本可能非常低。如果乱序执行可以 "see" 为一个简单的循环计数器提前几次迭代，它可以让分支本身执行，然后再花很多时间在那个错误预测的分支之外的实际工作上。通过对分支未命中的快速恢复（不是通过使用诸如分支顺序缓冲区之类的东西来刷新整个无序管道），您仍然会失去在循环几个周期后开始独立工作的机会。如果依赖链的延迟出现循环瓶颈，这很可能是这种情况，但计数器本身是一个单独的链。 This paper关于分支未命中的实际成本也很有趣，并提到了这一点。
（请注意，我假设分支预测已经 "primed"，因此第一次迭代正确预测了所采用的循环分支。）
不切实际的方法:
@Hadi 链接了一个有趣的想法：而不是正常的 运行ning 代码，以一种奇怪的方式编译，其中控制和指令都是数据，例如 x86 仅使用 mov 指令与 x86寻址模式+寄存器。 （以及一个大块底部的无条件分支）。 Is it possible to make decisions in assembly without using `jump` and `goto` at all? 这效率低得可笑，但实际上没有任何条件分支：一切都是数据依赖。
它使用了不同形式的 MOV（在寄存器之间，立即寄存器，以及 load/store），所以它不是单指令集计算机。
一个不那么疯狂的版本是解释器：被解释代码中的不同指令/操作变成解释器中的控制依赖（为解释创建一个难以解决的效率问题，参见Darek Mihocka's "The Common CPU Interpreter Loop Revisited" article, 但是来宾代码中的数据和控制流都是解释器中的数据。来宾程序计数器只是解释器中的另一条数据。