如果您认为 64 位 DIV 指令是除以 2 的好方法，那么难怪编译器的 asm 输出会击败您的手写代码，即使使用-O0（编译速度快，无需额外优化，并在
/ 之后存储/重新加载到内存）在每个 C 语句之前，以便调试器可以修改变量）。

请参阅Agner Fog 的 Optimizing Assembly 指南，了解如何编写高效的
asm。他还提供指令表和微架构指南，了解特定 CPU
的具体细节。另请参阅x86标签
wiki 以获取更多性能链接。

另请参阅有关使用手写 asm 击败编译器的更一般性问题：内联汇编语言是否比本机 C++
代码慢？. TL：DR：是的，如果你做错了（比如这个问题）。

通常你可以让编译器做它的事情，特别是如果你 尝试编写可以高效编译的 C++。 其中一个答案链接到这些简洁的幻灯片，展示了各种 C
编译器如何使用很酷的技巧优化一些非常简单的函数。 Matt Godbolt 的 CppCon2017 演讲——
我的编译器最近为我做了什么？Unbolt the Compiler’s Lid’s的原理与此类似。

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

在 Intel Haswell 上， div r64 是 36 微指令， 延迟为 32-96 个周期 ，吞吐量为每 21-74
个周期一个。（加上设置 RBX 和零 RDX 的 2 个微指令，但乱序执行可以提前运行这些）。 像 DIV 这样的高 uop
指令是微编码的，这也可能导致前端瓶颈。在这种情况下，延迟是最相关的因素，因为它是循环携带的依赖链的一部分。

shr rax, 1 执行相同的无符号除法：它是 1 uop，具有 1c 延迟，并且每个时钟周期可以运行 2 次。

相比之下，32 位除法速度更快，但与移位相比仍然很糟糕。idiv r32在 Haswell 上是 9 微指令、22-29c 延迟和每 8-11c
吞吐量一个。

从查看 gcc 的-O0asm 输出（Godbolt
编译器资源管理器）可以看出，它只使用移位指令。clang-O0确实像您想象的那样天真地编译，即使使用
64 位 IDIV 两次。（在优化时，当源使用相同的操作数进行除法和取模时，编译器确实使用 IDIV 的两个输出，如果它们完全使用 IDIV）

GCC 没有完全幼稚的模式。它总是通过 GIMPLE
进行转换，这意味着不能禁用某些“优化”。这包括识别除以常数和使用移位（2的幂）或定点乘法逆（非 2 的幂）来避免 IDIV（参见div_by_13上面的上帝螺栓链接）。

gcc -Os（优化大小） 确实 使用 IDIV 进行非 2 次幂除法，不幸的是，即使在乘法逆码仅稍大但速度更快的情况下也是如此。

帮助编译器

（本案例总结：使用uint64_t n）

首先，查看优化的编译器输出很有趣。( -O3)。

查看您的 asm 输出（在 Godbolt 上，或查看如何从 GCC/clang程序集输出中删除“噪音”？）。当编译器一开始就没有生成最佳代码时：
以一种指导编译器生成更好代码的方式编写 C/C++ 源代码通常是最好的方法 。您必须了解
asm，并且知道什么是有效的，但是您间接地应用了这些知识。编译器也是一个很好的想法来源：有时 clang 会做一些很酷的事情，你可以手持 gcc
做同样的事情
这种方法是可移植的，并且在 20 年内，一些未来的编译器可以将其编译为在未来硬件（x86 或非 x86 上）上有效的任何东西，可能使用新的 ISA
扩展或自动矢量化。15 年前手写的 x86-64 asm 通常不会针对 Skylake 进行优化调整。例如，当时不存在比较&分支宏融合。
现在对于一个微体系结构的手工 asm 来说是最优的，对于其他当前和未来的 CPU 来说可能不是最优的。 讨论了 AMD Bulldozer 和 Intel Haswell
之间的主要区别，这对这段代码有很大的影响。但在理论上，g++ -O3 -march=bdver3并g++ -O3 -march=skylake会做正确的事。（或者-march=native。）或者-mtune=...只是调整，而不使用其他 CPU
可能不支持的指令。

我的感觉是，引导编译器编译出对你关心的当前 CPU
有好处的汇编，对于未来的编译器来说应该不是问题。他们希望在寻找转换代码的方法方面比当前的编译器更好，并且可以找到一种适用于未来 CPU
的方法。无论如何，未来的 x86 可能不会在当前 x86 上的任何优点方面变得糟糕，并且未来的编译器将避免任何特定于 asm 的陷阱，同时实现诸如从 C
源代码移动数据之类的东西，如果它没有看到更好的东西。

手写 asm 是优化器的黑盒，因此当内联使输入成为编译时常量时，常量传播不起作用。其他优化也会受到影响。在使用 asm
之前阅读https://gcc.gnu.org/wiki/DontUseInlineAsm
。（并避免 MSVC
风格的内联汇编：输入/输出必须经过内存，这会增加开销。）

在这种情况下 ：您n有一个有符号类型，并且 gcc 使用 SAR/SHR/ADD 序列来提供正确的舍入。（对于负输入，IDIV
和算术移位“舍入”不同，请参阅SAR insn set ref manual
entry）。（IDK，如果 gcc
尝试并未能证明它n不能是负数，或者什么。签名溢出是未定义的行为，所以它应该能够。）

你应该用过uint64_t n，所以它可以只是 SHR。因此它可以移植到long只有 32 位的系统（例如 x86-64 Windows）。

顺便说一句， gcc 的 优化 asm 输出看起来相当不错（使用unsigned long n）：它内联到的内部循环这样main()做：

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

.L9:                   # do{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # set flags based on n%2 (aka n&1)
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++count;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n

内循环是无分支的，循环携带的依赖链的关键路径为：

• 3 组分 LEA（3 个周期）
• cmov（Haswell 上 2 个周期，Broadwell 上 1c 或更高版本）。

总计：每次迭代 5 个周期，延迟瓶颈 。乱序执行与此并行处理其他所有事情（理论上：我还没有使用性能计数器测试它是否真的以 5c/iter 运行）。

cmov（由 TEST 生成）的 FLAGS 输入比 RAX 输入（来自 LEA->MOV）的生成速度更快，因此它不在关键路径上。

同样，产生 CMOV 的 RDI 输入的 MOV->SHR 不在关键路径上，因为它也比 LEA 快。IvyBridge 上的 MOV
和更高版本的延迟为零（在寄存器重命名时处理）。（它仍然需要一个微指令和一个管道中的插槽，所以它不是免费的，只是零延迟）。LEA dep 链中的额外 MOV
是其他 CPU 瓶颈的一部分。

cmp/jne 也不是关键路径的一部分：它不是循环携带的，因为控制依赖是通过分支预测 + 推测执行来处理的，这与关键路径上的数据依赖不同。

击败编译器

GCC 在这里做得很好。inc edx它可以通过使用而不是add edx, 1节省一个代码字节，因为没有人关心 P4
及其对部分标志修改指令的错误依赖性。

它还可以保存所有 MOV 指令，并且 TEST: SHR 设置 CF= 移出的位，因此我们可以使用cmovc代替test/ cmovz。

 ### Hand-optimized version of what gcc does
.L9:                       #do{
    lea     rcx, [rax+1+rax*2] # rcx = 3*n + 1
    shr     rax, 1         # n>>=1;    CF = n&1 = n%2
    cmovc   rax, rcx       # n= (n&1) ? 3*n+1 : n/2;
    inc     edx            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

请参阅@johnfound 的另一个聪明技巧的答案：通过在 SHR 的标志结果上进行分支以及将其用于 CMOV 来删除 CMP：仅当 n 为 1（或
0）开始时才为零。（有趣的事实：如果您阅读标志结果，则在 Nehalem 或更早的版本上，计数为 1 的 SHR
会导致停顿。这就是他们如何使其成为单微指令的方式。不过，shift-
by-1 特殊编码很好。）

避免 MOV 对 Haswell 的延迟完全没有帮助）。它确实对 Intel
pre-IvB 和 AMD Bulldozer 系列等 CPU 有 很大 帮助，其中 MOV 不是零延迟（以及带有更新微码的 Ice
Lake）。编译器浪费的 MOV 指令确实会影响关键路径。BD 的 complex-LEA 和 CMOV 都具有较低的延迟（分别为 2c 和
1c），因此它占延迟的比例更大。此外，吞吐量瓶颈成为一个问题，因为它只有两个整数 ALU 管道，其中他有来自 AMD CPU 的计时结果。

即使在 Haswell 上，此版本也可能会有所帮助，因为它可以避免一些偶然的延迟，即非关键 uop 从关键路径上的一个执行端口窃取执行端口，从而将执行延迟
1 个周期。（这称为资源冲突）。它还保存了一个寄存器，这n在交错循环中并行执行多个值时可能会有所帮助（见下文）。

LEA 的延迟取决于 Intel SnB 系列 CPU 上的寻址模式。3c 用于 3
个组件（[base+idx+const]，需要两个单独的添加），但只有 1c 具有 2 个或更少的组件（一个添加）。一些 CPU（如
Core2）甚至可以在一个周期内执行 3 分量 LEA，但 SnB 系列却没有。更糟糕的是，英特尔 SnB 系列对延迟进行了标准化，因此没有 2c
微指令，否则 3 组件 LEA 就像 Bulldozer一样只有 2c。（AMD 上的 3 组件 LEA 也较慢，只是没那么慢）。

因此lea rcx, [rax + rax*2]/在 Haswell 等英特尔 SnB 系列 CPU 上inc rcx只有 2c 延迟，比
快。lea rcx, [rax + rax*2 + 1]BD 实现收支平衡，Core2 则更糟。它确实需要额外的 uop，这通常不值得节省 1c
延迟，但延迟是这里的主要瓶颈，Haswell 有足够宽的管道来处理额外的 uop 吞吐量。

gcc、icc 和 clang（在 Godbolt 上）都没有使用 SHR 的 CF 输出，总是使用 AND 或 TEST 。愚蠢的编译器。:P
它们是复杂机器的伟大部件，但聪明的人通常可以在小规模问题上击败它们。（当然，考虑它的时间要长数千到数百万倍！编译器不会使用详尽的算法来搜索所有可能的做事方式，因为在优化大量内联代码时，这将花费太长时间，这就是他们做得最好。他们也没有在目标微架构中对管道进行建模，至少不像IACA或其他静态分析工具那样详细；他们只是使用一些启发式方法。）

简单的循环展开无济于事 ；这个循环瓶颈是循环携带的依赖链的延迟，而不是循环开销/吞吐量。这意味着它可以很好地处理超线程（或任何其他类型的
SMT），因为 CPU
有大量时间来交错来自两个线程的指令。这意味着将循环并行化main，但这很好，因为每个线程都可以检查一系列n值并生成一对整数作为结果。

在单个线程中手动交错也可能是可行的 。也许并行计算一对数字的序列，因为每个数字只需要几个寄存器，它们都可以更新相同的max/
maxi。这创造了更多的指令级并行性。

诀窍是决定是等到所有n值都达到1后才获得另一对起始值n，或者是否突破并仅为达到结束条件的一个获得一个新的起点，而不触及另一个序列的寄存器。可能最好让每个链都处理有用的数据，否则你必须有条件地增加它的计数器。

您甚至可以使用 SSE 打包比较的东西来执行此操作，以有条件地增加n尚未达到的向量元素的计数器1。然后为了隐藏 SIMD
条件增量实现的更长延迟，您需要保持更多的n值向量悬而未决。也许只值得使用 256b 矢量（4x uint64_t）。

我认为检测1“粘性”的最佳策略是掩盖您添加以增加计数器的全向量。因此，当您1在元素中看到 a 后，增量向量将为零，而 +=0 是无操作的。

手动矢量化的未经测试的想法

# starting with YMM0 = [ n_d, n_c, n_b, n_a ]  (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1):  increment vector
# ymm5 = all-zeros:  count vector

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1= 3*n + 1.  Maybe could do this more efficiently?

    vpsllq    ymm3, ymm0, 63                # shift bit 1 to the sign bit

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # variable blend controlled by the sign bit of each 64-bit element.  I might have the source operands backwards, I always have to look this up.

    # ymm0 = updated n  in each element.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # zero out elements of ymm4 where the compare was true

    vpaddq   ymm5, ymm5, ymm4         # count++ in elements where n has never been == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # Actually just delay doing a horizontal max until the very very end.  But you need some way to record max and maxi.

您可以并且应该使用内在函数而不是手写 asm 来实现它。

算法/实现改进：

除了用更高效的 asm 实现相同的逻辑之外，还要寻找简化逻辑或避免冗余工作的方法。例如 memoize 以检测序列的共同结尾。或者更好的是，一次查看 8
个尾随位（gnasher 的回答）

@EOF 指出tzcnt(or bsf) 可用于n/=2一步进行多次迭代。这可能比 SIMD 矢量化更好；没有 SSE 或 AVX
指令可以做到这一点。不过，它仍然兼容n在不同的整数寄存器中并行执行多个标量。

所以循环可能看起来像这样：

goto loop_entry;  // C++ structured like the asm, for illustration only
do {
   n = n*3 + 1;
  loop_entry:
   shift = _tzcnt_u64(n);
   n >>= shift;
   count += shift;
} while(n != 1);

这可能会显着减少迭代次数，但在没有 BMI2 的英特尔 SnB 系列 CPU 上，变量计数的变化很慢。3 微指令，2c 延迟。（它们对 FLAGS
有输入依赖性，因为 count=0 表示标志未修改。它们将其作为数据依赖性处理，并采用多个 uop，因为 uop 只能有 2 个输入（无论如何都是预
HSW/BDW））。这就是那些抱怨 x86 疯狂的 CISC 设计的人们所指的那种。它使 x86 CPU 比现在从头开始设计 ISA
的速度要慢，即使是以最相似的方式。（即这是消耗速度/功率的“x86 税”的一部分。） SHRX/SHLX/SARX (BMI2) 是一个巨大的胜利（1
uop / 1c 延迟）。

它还将 tzcnt（Haswell 上的 3c 及更高版本）置于关键路径上，因此它显着延长了循环承载的依赖链的总延迟。不过，它确实消除了对 CMOV
或准备寄存器持有的任何需要n>>1。 @Veedrac 的答案通过推迟多次迭代的 tzcnt/shift
克服了所有这些，这是非常有效的（见下文）。

我们可以安全地交替使用BSF或TZCNT，因为n此时永远不会为零。TZCNT
的机器代码在不支持 BMI1 的 CPU 上解码为 BSF。（无意义的前缀被忽略，所以 REP BSF 作为 BSF 运行）。

TZCNT 在支持它的 AMD CPU 上的性能比 BSF 好得多，因此使用 可能是一个好主意REP BSF，即使您不关心在输入为零而不是输出时设置
ZF。__builtin_ctzll当你使用时，一些编译器会这样做-mno-bmi。

它们在 Intel CPU 上的性能相同，所以如果这很重要，只需保存字节即可。Intel 上的 TZCNT（Skylake
之前）仍然对所谓的只写输出操作数具有错误依赖性，就像 BSF 一样，以支持输入 = 0 的 BSF
未修改其目的地的未记录行为。所以你需要解决这个问题，除非只针对 Skylake 进行优化，所以额外的 REP 字节没有任何好处。（英特尔经常超出 x86
ISA 手册的要求，以避免破坏广泛使用的代码，这些代码依赖于它不应该或追溯不允许的东西。

无论如何，Haswell 上的 LZCNT/TZCNT 与 POPCNT 具有相同的错误深度。这就是为什么在 gcc 的
@Veedrac 代码的 asm 输出中，当它不使用 dst=src 时，您会看到它在即将用作 TZCNT 目标的寄存器上通过异或零处理破坏了 dep
链。
永远不会离开未定义或未修改的目的地，因此这种对 Intel CPU
输出的错误依赖是性能错误/限制。据推测，值得一些晶体管/电源让它们像其他进入同一执行单元的微指令一样工作。唯一的性能优势是与另一个 uarch
限制的交互：它们可以将内存操作数与索引寻址模式进行微融合在 Haswell 上，但在 Skylake 上，英特尔删除了 LZCNT/TZCNT 的错误
dep，它们“取消层压”索引寻址模式，而 POPCNT 仍然可以微融合任何 addr 模式。

其他答案对想法/代码的改进：

@hidefromkgb 的回答 有一个很好的观察结果，即保证您能够在 3n+1
之后进行一次右移。您可以更有效地计算这一点，而不是仅仅省略步骤之间的检查。但是，该答案中的 asm 实现被破坏了（它取决于 OF，它在 SHRD
之后未定义且计数 > 1），并且 slow:ROR rdi,2比 快SHRD rdi,rdi,2，并且在关键路径上使用两个 CMOV 指令比额外的
TEST 慢可以并行运行。

还改进了输出打印以转换为字符串并生成一个，write()而不是一次写入一个字符。这最大限度地减少了对整个程序计时的影响perf stat ./collatz（以记录性能计数器），并且我对一些非关键的 asm 进行了去混淆处理。

@Veedrac 的代码

正如我们所知道 的那样，我从右移获得了轻微的加速，并检查以继续循环。在 Core2Duo (Merom) 上，从 limit=1e8 的 7.5
秒降低到 7.275 秒，展开因子为 16。

代码 +对
Godbolt的评论。请勿将此版本与
clang 一起使用；它对延迟循环做了一些愚蠢的事情。使用 tmp 计数器k，然后将其添加到count以后会更改 clang 的功能，但这会
稍微 伤害 gcc。

请参阅评论中的讨论： Veedrac 的代码在具有 BMI1 的 CPU 上非常 出色 （即不是 Celeron/Pentium）