为什么这个C ++代码比testingCollat​​z猜想的手写组件更快？

我在汇编和C ++中为Project Euler Q14编写了这两个解决scheme。 它们是testingCollat​​z猜想的完全相同的蛮力方法。 assembly解决scheme是与组装 

nasm -felf64 p14.asm && gcc p14.o -o p14

C ++编译了 

 g++ p14.cpp -o p14

大会， p14.asm 

 section .data fmt db "%d", 10, 0 global main extern printf section .text main: mov rcx, 1000000 xor rdi, rdi ; max i xor rsi, rsi ; i l1: dec rcx xor r10, r10 ; count mov rax, rcx l2: test rax, 1 jpe even mov rbx, 3 mul rbx inc rax jmp c1 even: mov rbx, 2 xor rdx, rdx div rbx c1: inc r10 cmp rax, 1 jne l2 cmp rdi, r10 cmovl rdi, r10 cmovl rsi, rcx cmp rcx, 2 jne l1 mov rdi, fmt xor rax, rax call printf ret

C ++，p14.cpp 

 #include <iostream> using namespace std; int sequence(long n) { int count = 1; while (n != 1) { if (n % 2 == 0) n /= 2; else n = n*3 + 1; ++count; } return count; } int main() { int max = 0, maxi; for (int i = 999999; i > 0; --i) { int s = sequence(i); if (s > max) { max = s; maxi = i; } } cout << maxi << endl; }

我知道编译器优化，以提高速度和一切，但我没有看到很多方法来进一步优化我的程序集解决scheme（说话不是math）。

C ++代码每个术语和每个阶段都有模数，每个阶段汇编只有一个分区。

但是程序集平均比C ++解决scheme平均要长1秒。 为什么是这样？ 主要是好奇心。

编辑：按要求执行时间

我的系统：1.4 GHz Intel Celeron 2955U（Haswell微架构）上的64位Linux。

  • g++ （未优化）：平均1272毫秒

  • g++ -O3 avg 578 ms

  • 原始asm（div）平均2650毫秒

  • Asm (shr) avg 679 ms

  • @johnfound asm ，与nasm avg 501 ms汇编

  • @hidefromkgb asm avg 200 ms

  • @hidefromkgb asm由@Peter Cordes avg 145 ms 优化

  • @Veedrac C ++平均81毫秒与-O3,305毫秒与-O0

如果你认为64位的DIV指令是一个很好的分割方法，那么难怪编译器的asm输出超过你的手写代码，即使是-O0 （编译速度快，没​​有额外的优化，并且存储/重新加载到内存在每个C语句之后/之前，所以debugging器可以修改variables）。

请参阅Agner Fog的优化汇编指南以了解如何编写高效的汇编。 他还拥有指令表和微指南，以便了解特定CPU的具体细节。 另请参阅x86标记wiki以获取更多的perf链接。

另请参阅关于使用手写asm敲击编译器的更常见问题： 内联汇编语言比本机C ++代码慢吗？ 。 TL：DR：是的，如果你做错了（就像这个问题）。

通常你可以让编译器完成它的工作，特别是如果你试图编写可以高效编译的C ++ 。 另请参阅组装语言比编译语言更快吗？ 。 其中一个答案链接到这些整齐的幻灯片，展示了各种C编译器如何用一些很酷的技巧来优化一些非常简单的function。 

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

在Intel Haswell上， div r64为36 div r64 ， 延迟时间为 32-96个周期 ，吞吐量为每21-74个周期一个。 （加上2个微软build立RBX和零RDX，但乱序执行可以运行那些早）。 像DIV这样的高级计数指令是微码的，这也会造成前端瓶颈。 在这种情况下，延迟是最相关的因素，因为它是循环运行的依赖链的一部分。

shr rax, 1做同样的未签名的划分：它是1 uop，具有1c的延迟 ，并且可以在每个时钟周期运行2。

相比之下，32比特的分割速度更快，但对比转换依然可怕。 idiv r32在Haswell上的吞吐量是9 uops，22-29c延迟，每8-11c吞吐量一个。

正如你可以看到gcc的-O0 asm输出（ Godbolt编译器资源pipe理器 ），它只使用移位指令 。 铛-O0确实像你想象的那样天真地编译，甚至两次使用64位的IDIV。 （当进行优化时，编译器确实使用IDIV的两个输出，如果源使用相同的操作数进行除法和模数（如果它们完全使用IDIV的话）

GCC没有完全天真的模式; 它总是通过GIMPLE转换，这意味着一些“优化”不能被禁用 。 这包括识别常数除法和使用移位（2的幂）或定点乘法逆 （2的非幂）来避免IDIV（见上面的godbolt链接中的div_by_13）。

gcc -Os （对大小进行优化） 确实使用了IDIV来进行非2次方的除法运算，不幸的是，即使在乘法逆码只稍大但慢得多的情况下。

帮助编译器

（这个案例的总结：使用uint64_t n ）

首先，看看优化的编译器输出是很有意思的。 （ -O3 ）。 -O0速度基本上是毫无意义的。

看看你的asm输出（在Godbolt上，或者参阅如何从GCC / clang程序集输出中删除“noise” ）。 当编译器并没有做出最佳的代码时： 编写C / C ++源代码的方式是指导编译器创build更好的代码通常是最好的方法 。 你必须知道，知道什么是有效的，但你间接应用这些知识。 编译器也是一个很好的想法来源：有时候clang会做一些很酷的事情，你可以用gcc来做同样的事情：看下面的答案 ，以及我在下面的@ Veedrac代码中展开的未展开循环。

这种方法是可移植的，在未来的20年中，一些将来的编译器可以将它编译成任何在未来的硬件（x86或者没有）上都是有效的，也许使用新的ISA扩展或者自动向量化。 从15年前手写的x86-64 asm通常不会被优化调整为Skylake。 例如比较＆分支macros融合当时不存在。 对于一个微架构来说，现在手工制作的asm最适合其他当前和未来的CPU。 @ johnfound回答的评论讨论AMD推土机和英特尔Haswell之间的主要区别，这对这个代码有很大的影响。 但从理论上讲， g++ -O3 -march=bdver3和g++ -O3 -march=skylake会做正确的事情。 （或-march=native 。）或者-mtune=...来调整，而不使用其他CPU可能不支持的指令。

我的感觉是，指导编译器对于当前你关心的CPU来说是不错的，对于未来的编译器来说应该不成问题。 他们希望比当前的编译器更好地find转换代码的方法，并且可以find一种适用于未来CPU的方法。 无论如何，未来的x86可能对目前x86上的任何好东西都不会太糟糕，未来的编译器将会避免任何特定于asm的陷阱，同时执行类似于C源代码的数据移动，如果它没有看到更好的东西。

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

在这种情况下 ：你的n有一个签名types，gcc使用SAR / SHR / ADD序列给出正确的四舍五入。 （对于负input，IDIV和算术移位“round”不同，见SAR insn set ref手动input ）。 （IDC如果gcc尝试过，并且未能certificaten不能是负数，或者是什么，Signed-overflow是未定义的行为，所以应该可以）。

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

顺便说一句， 海湾合作委员会的优化 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

内环是无分支的，环路依赖链的关键path是：

  • 3组分LEA（3个循环）
  • cmov（Haswell 2个周期，Broadwell 1个或更晚）。

总共：每次迭代5个周期，延迟瓶颈 。 乱序执行需要处理与此并行的所有其他事情（理论上说：我没有用perf计数器来testing它是否真的以5c / iter运行）。

cmov （由TEST产生）的FLAGSinput比RAXinput（从LEA-> MOV）产生更快，所以它不在关键path上。

类似地，产生CMOV的RDIinput的MOV-> SHR不在关键path上，因为它也比LEA快。 IvyBridge上的MOV和后来的零延迟（在寄存器重命名时处理）。 （它仍然需要一个uop和一个插槽，所以它不是免费的，只是零延迟）。 LEA dep链中额外的MOV是其他CPU上瓶颈的一部分。

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

击败编译器

海湾合作委员会在这里做了很好的工作。 通过使用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的标志结果上分支来移除CMP，并将其用于CMOV：仅当n为1（或0）时才为零。 （有趣的是，在Nehalem或更早的时候，如果你阅读了标志结果，那么在Nehalem或更早的时候SHR的计数！= 1会导致失速，这就是他们如何使它成为单一的上升沿，尽pipe如此，shift-by-1特殊的编码还是不错的。

避免MOV对Haswell的延迟毫无帮助（ x86的MOV真的可以“免费”吗？为什么我不能重现这一点？ ）。 它对英特尔IvB之前的CPU以及AMD推土机系列产品（MOV不是零延迟）有显着的帮助。 编译器浪费的MOV指令会影响关键path。 BD的复合LEA和CMOV都是较低的延迟（分别是2c和1c），所以它是延迟的一小部分。 此外，吞吐量瓶颈成为一个问题，因为它只有两个整数ALUpipe道。 请参阅@ johnfound的答案 ，他从AMD CPU获得计时结果。

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

LEA的延迟取决于寻址模式 ，在Intel SnB系列CPU上。 3c用于3个组件（ [base+idx+const] ，它需要两个单独的添加），但只有1个2个或更less的组件（一个添加）。 一些CPU（如Core2）在单个周期内甚至可以执行3个组件的LEA，但是SnB系列不支持。 更糟糕的是， Intel SnB系列标准化了延迟，所以没有2c uop ，否则3分量LEA将只有推土机2c。 （三分量LEA在AMD上也是比较慢的，而不是那么多）。

因此，在像Haswell这样的Intel SnB系列CPU上lea rcx, [rax + rax*2] / inc rcx只有2c的延迟，比lea rcx, [rax + rax*2 + 1]快lea rcx, [rax + rax*2 + 1] 。 在BD上保持平衡，在Core2上更糟糕。 它确实需要一个额外的uop，通常不值得它来节省1c的延迟，但延迟是这里的主要瓶颈，Haswell有足够的stream水线来处理额外的uop吞吐量。

gcc，icc和clang（在godbolt上）都不使用SHR的CF输出，总是使用AND或TEST 。 傻编译器。 ：P它们是复杂机械的绝佳组成部分，但聪明的人往往可以在小问题上殴打他们。 （当然，考虑到数千甚至数百万倍的时间来考虑它！编译器不使用穷举algorithm来search每一种可能的方式来做事情，因为在优化大量的内联代码时，这将花费太长的时间，这就是他们做得最好，他们也没有在目标微架构中build立pipe道模型，他们只是使用一些启发式的方法。

简单的循环展开将无济于事 。 这个循环在循环承载依赖链的延迟上是瓶颈的，而不是循环开销/吞吐量。 这意味着它可以和超线程（或任何其他种类的SMT）配合使用，因为CPU有很多时间来交叉来自两个线程的指令。 这将意味着在main并行化循环，但这很好，因为每个线程都可以检查n值的范围，并产生一对整数。

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

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

你甚至可以用SSE打包比较的东西做到这一点，以有条件地增加n尚未达到1向量元素的计数器。 然后，为了隐藏SIMD条件增量实现的更长的延迟，您需要将更多的n个向量保持在空中。 也许只值得256bvector（4x uint64_t ）。

我认为检测1 “粘性”的最佳策略是屏蔽所添加的所有元素的向量以增加计数器。 所以在元素中看到1之后，增量向量将会有一个零，而+ = 0是一个无操作。

未经testing的手动vector化的想法 

 # 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? vprllq ymm3, ymm0, 63 # shift bit 1 to the sign bit vpsrlq ymm0, ymm0, 1 # n /= 2 # There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure. Probably worth it 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.

你可以也应该用intrinsics来实现这个，而不是手写的asm。

algorithm/实现改进：

除了用更高效的asm来实现相同的逻辑之外，还可以寻求简化逻辑或避免重复工作的方法。 例如记忆以检测序列的共同结尾。 甚至更好，一次查看8个尾随位（gnasher的答案）

@EOF指出tzcnt （或bsf ）可以用来在一个步骤中执行多个n/=2次迭代。 这可能比SIMDvector化要好，因为没有SSE或AVX指令可以做到这一点。 尽pipe如此，它仍然与在不同的整数寄存器中并行执行多个标量ns兼容。

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

 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);

这可能会明显减less迭代次数，但是在没有BMI2的Intel SnB系列CPU上，可变计数偏移很慢。 3个uops，2c延迟。 （它们对FLAGS有input依赖关系，因为count = 0意味着标志没有被修改，它们把它作为一个数据依赖来处理，并且由于一个uop只能有2个input（pre-HSW / BDW）而采用多个uops。 人们抱怨x86的疯狂CISCdevise就是指那种。 它使得x86 CPU比现在从头开始deviseISA的速度更慢，即使采用大部分类似的方式。 （即这是成本速度/功耗的“x86税收”的一部分。）SHRX / SHLX / SARX（BMI2）是一个巨大的胜利（1 uop / 1c延迟）。

它还将关键path上的tzcnt（3c在Haswell和更高版本上）放在关键path上，因此显着延长了循环运行的依赖链的总延迟。 它确实消除了对CMOV的需求，或者准备了一个持有n>>1的寄存器。 @ Veedrac的答案克服了所有这一切，推迟了tzcnt / shift多次迭代，这是非常有效的（见下文）。

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

TZCNT在支持AMD处理器的CPU上performance比BSF好得多，所以使用REP BSF是一个好主意，即使你不关心如果input是零而不是输出的情况下设置ZF。 有些编译器在使用__builtin_ctzll甚至可以使用-mno-bmi 。

他们在Intel CPU上执行相同的操作，所以只要保存这个字节就行了。 英特尔（Skylake之前）的TZCNT仍然错误地依赖于所谓的只写输出操作数，就像BSF一样，以支持input为0的BSF未修改目的地的未logging行为。 所以你需要解决这个问题，除非只为Skylake优化，所以没有什么可以从额外的REP字节中获得。 （英特尔经常超出x86 ISA手册要求的范围，以避免打破广泛使用的代码，这些代码依赖于不应该的东西，或者被追溯地禁止使用。例如， Windows 9x不假设TLB条目的预测性预取 ，这是安全的在编写代码时， 在英特尔更新TLBpipe理规则之前 ）。

无论如何，Haswell上的LZCNT / TZCNT与POPCNT具有相同的假定：请参阅本问答 。 这就是为什么在@ Veedrac代码的gcc的asm输出中，当它不使用dst = src时，你会发现它在将要用作TZCNT的目的地的寄存器上用xor- zeroing 打破dep链 。 由于TZCNT / LZCNT / POPCNT永远不会将其目的地置于未定义或未经修改的位置，因此这种错误依赖于Intel CPU上的输出纯粹是性能错误/限制。 据推测，有一些晶体pipe/电源可以让它们像其他微处理器一样执行相同的执行单元。 唯一软件可见的优势在于与另一个微架构限制的相互作用： 它们可以在Haswell上使用索引寻址模式来微内存操作数 ，但在Skylake上，Intel解除了LZCNT / TZCNT的错误依赖关系，索引寻址模式，而POPCNT仍然可以对任何addr模式进行微熔丝。

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

@ hidefromkgb的回答有一个很好的观察，你保证能够做一个3n + 1后一个右移。 您可以更加高效地计算这个值，而不是忽略步骤之间的检查。 尽pipe（这取决于OF，在SHRD之后，计数> 1），但是在这个答案中的asm实现被破坏了，并且慢： ROR rdi,2比SHRD rdi,rdi,2更快，并且使用两个CMOV指令在关键path上比可以并行运行的额外testing慢。

我整理/改进了C（指导编译器生成更好的asm），并且testing了+工作速度更快的asm（在C语言下面），在Godbolt上：请参阅@ hidefromkgb答案中的链接。 （这个答案从大的Godbolturl中打出了30k字符的限制，但是短链接可能会腐烂 ，而且对于goo.gl来说太长了。）

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

@ Veedrac的代码

尽pipe我们知道需要做的事情，但是从正确的转变中得到了很小的加速，并且检查继续循环。 在Core2Duo（Merom）上，从7.5s的极限= 1e8降到7.275s，展开因子为16。

代码+ 对Godbolt的评论。 不要使用这个版本的铿锵; 它在延迟循环中做了一些愚蠢的事情。 使用tmp计数器k ，然后加上它来count更改clang的作用，但这会伤害gcc。

在评论中看到讨论：Veedrac的代码在BMI1（即不是赛扬/奔腾）

声称C ++编译器比一个合格的汇编语言程序员能产生更优化的代码是一个非常糟糕的错误。 特别是在这种情况下。 人们总是可以使编译器能够更好的编写代码，而这个特殊的情况就是这个说法的很好的例子。

你看到的时间差异是因为在内部循环中问题中的汇编代码是非常不理想的。

（下面的代码是32位，但可以很容易地转换为64位）

例如，序列函数可以优化为只有5条指令： 

  .seq: inc esi ; counter lea edx, [3*eax+1] ; edx = 3*n+1 shr eax, 1 ; eax = n/2 cmovc eax, edx ; if CF eax = edx jnz .seq ; jmp if n<>1

整个代码看起来像： 

 include "%lib%/freshlib.inc" @BinaryType console, compact options.DebugMode = 1 include "%lib%/freshlib.asm" start: InitializeAll mov ecx, 999999 xor edi, edi ; max xor ebx, ebx ; max i .main_loop: xor esi, esi mov eax, ecx .seq: inc esi ; counter lea edx, [3*eax+1] ; edx = 3*n+1 shr eax, 1 ; eax = n/2 cmovc eax, edx ; if CF eax = edx jnz .seq ; jmp if n<>1 cmp edi, esi cmovb edi, esi cmovb ebx, ecx dec ecx jnz .main_loop OutputValue "Max sequence: ", edi, 10, -1 OutputValue "Max index: ", ebx, 10, -1 FinalizeAll stdcall TerminateAll, 0

为了编译这个代码，需要FreshLib 。

在我的testing中，（1 GHz AMD A4-1200处理器），上述代码比问题中的C ++代码（当用-O0编译时：430毫秒比1900毫秒）大约快四倍，而速度提高了两倍（430毫秒与830毫秒），当C ++代码编译-O3 。

两个程序的输出是相同的：在i = 837799上的最大序列= 525。

更多的performance：一个简单的变化就是观察到n = 3n + 1之后，n将是偶数，所以你可以立即除以2。 而n不会是1，所以你不需要testing它。 所以你可以保存一些如果语句和写： 

 while (n % 2 == 0) n /= 2; if (n > 1) for (;;) { n = (3*n + 1) / 2; if (n % 2 == 0) { do n /= 2; while (n % 2 == 0); if (n == 1) break; } }

这是一个很大的胜利：如果你看看n的最低8位，所有的步骤直到你被8除以2完全由这8位决定。 例如，如果最后八位是0x01，那是二进制的，你的号码是？ 0000 0001然后接下来的步骤是： 

 3n+1 -> ???? 0000 0100 / 2 -> ???? ?000 0010 / 2 -> ???? ??00 0001 3n+1 -> ???? ??00 0100 / 2 -> ???? ???0 0010 / 2 -> ???? ???? 0001 3n+1 -> ???? ???? 0100 / 2 -> ???? ???? ?010 / 2 -> ???? ???? ??01 3n+1 -> ???? ???? ??00 / 2 -> ???? ???? ???0 / 2 -> ???? ???? ????

所以所有这些步骤都可以预测，而256k + 1被81k + 1replace。所有的组合都会发生类似的情况。 所以你可以用一个大的switch语句做一个循环： 

 k = n / 256; m = n % 256; switch (m) { case 0: n = 1 * k + 0; break; case 1: n = 81 * k + 1; break; case 2: n = 81 * k + 1; break; ... case 155: n = 729 * k + 425; break; ... }

运行循环直到n≤128，因为那时n可以变成1，less于八个分数减2，每次执行八步或更多的步骤会使你错过第一次达到1的点。 然后继续“正常”循环 – 或者准备一个表格，告诉你需要多less步才能达到1。

PS。 我强烈怀疑彼得·科德斯的build议会使它更快。 除了一个之外，将不会有任何条件分支，除非循环实际结束，否则将被正确预测。 所以代码会是这样的 

 static const unsigned int multipliers [256] = { ... } static const unsigned int adders [256] = { ... } while (n > 128) { size_t lastBits = n % 256; n = (n >> 8) * multipliers [lastBits] + adders [lastBits]; }

在实践中，你会测量一次处理n的最后9,10,11,12位是否会更快。 对于每一位，表中的条目数量都会增加一倍，而且当表格不再适合L1caching时，我将忽略缓慢下降的情况。

PPS。 如果你需要的操作次数：在每次迭代中，我们都是由两个正好八个部分和可变数目的（3n + 1）操作，所以一个明显的方法来计算操作将是另一个数组。 但是我们实际上可以计算步数（根据循环的迭代次数）。

我们可以重新定义这个问题：用（3n + 1）/ 2replacen，如果奇数，用n / 2replacen。 那么每一次迭代都会执行8个步骤，但是你可以考虑作弊:-)所以假设有r个运算n <-3n + 1和s运算n <-n / 2。 因为n < – 3n + 1意味着n < – 3n *（1 + 1 / 3n），所以结果将完全是n'= n * 3 ^ r / 2 ^ s。 取对数，我们发现r =（s + log2（n'/ n））/ log2（3）。

如果我们执行循环，直到n≤1,000,000，并且有一个预先计算的表，从任何起始点n≤1,000,000需要多less次迭代，那么如上所述计算r，四舍五入到最接近的整数，除非s确实很大，否则将给出正确的结果。

On a rather unrelated note: more performance hacks!

  • [the first «conjecture» has been finally debunked by @ShreevatsaR; removed]

  • When traversing the sequence, we can only get 3 possible cases in the 2-neighborhood of the current element N (shown first):

    1. [even] [odd]
    2. [odd] [even]
    3. [even] [even]

    To leap past these 2 elements means to compute (N >> 1) + N + 1 , ((N << 1) + N + 1) >> 1 and N >> 2 , respectively.

    Let`s prove that for both cases (1) and (2) it is possible to use the first formula, (N >> 1) + N + 1 .

    Case (1) is obvious. Case (2) implies (N & 1) == 1 , so if we assume (without loss of generality) that N is 2-bit long and its bits are ba from most- to least-significant, then a = 1 , and the following holds: 

     (N << 1) + N + 1: (N >> 1) + N + 1: b10 b1 b1 b + 1 + 1 ---- --- bBb0 bBb

    where B = !b . Right-shifting the first result gives us exactly what we want.

    QED: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1 .

    As proven, we can traverse the sequence 2 elements at a time, using a single ternary operation. Another 2× time reduction.

The resulting algorithm looks like this: 

 uint64_t sequence(uint64_t size, uint64_t *path) { uint64_t n, i, c, maxi = 0, maxc = 0; for (n = i = (size - 1) | 1; i > 2; n = i -= 2) { c = 2; while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2) c += 2; if (n == 2) c++; if (c > maxc) { maxi = i; maxc = c; } } *path = maxc; return maxi; } int main() { uint64_t maxi, maxc; maxi = sequence(1000000, &maxc); printf("%llu, %llu\n", maxi, maxc); return 0; }

Here we compare n > 2 because the process may stop at 2 instead of 1 if the total length of the sequence is odd.

[EDIT:]

Let`s translate this into assembly! 

 MOV RCX, 1000000; DEC RCX; AND RCX, -2; XOR RAX, RAX; MOV RBX, RAX; @main: XOR RSI, RSI; LEA RDI, [RCX + 1]; @loop: ADD RSI, 2; LEA RDX, [RDI + RDI*2 + 2]; SHR RDX, 1; SHRD RDI, RDI, 2; ror rdi,2 would do the same thing CMOVL RDI, RDX; Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs. CMOVS RDI, RDX; CMP RDI, 2; JA @loop; LEA RDX, [RSI + 1]; CMOVE RSI, RDX; CMP RAX, RSI; CMOVB RAX, RSI; CMOVB RBX, RCX; SUB RCX, 2; JA @main; MOV RDI, RCX; ADD RCX, 10; PUSH RDI; PUSH RCX; @itoa: XOR RDX, RDX; DIV RCX; ADD RDX, '0'; PUSH RDX; TEST RAX, RAX; JNE @itoa; PUSH RCX; LEA RAX, [RBX + 1]; TEST RBX, RBX; MOV RBX, RDI; JNE @itoa; POP RCX; INC RDI; MOV RDX, RDI; @outp: MOV RSI, RSP; MOV RAX, RDI; SYSCALL; POP RAX; TEST RAX, RAX; JNE @outp; LEA RAX, [RDI + 59]; DEC RDI; SYSCALL;

Use these commands to compile: 

 nasm -f elf64 file.asm ld -o file file.o

See the C and an improved/bugfixed version of the asm by Peter Cordes on Godbolt . (editor's note: Sorry for putting my stuff in your answer, but my answer hit the 30k char limit from Godbolt links + text!)

C++ programs are translated to assembly programs during the generation of machine code from the source code. It would be virtually wrong to say assembly is slower than C++. Moreover, the binary code generated differs from compiler to compiler. So a smart C++ compiler may produce binary code more optimal and efficient than a dumb assembler's code.

However I believe your profiling methodology has certain flaws. The following are general guidelines for profiling:

  1. Make sure your system is in its normal/idle state. Stop all running processes (applications) that you started or that use CPU intensively (or poll over the network).
  2. Your datasize must be greater in size.
  3. Your test must run for something more than 5-10 seconds.
  4. Do not rely on just one sample. Perform your test N times. Collect results and calculate the mean or median of the result.

You did not post the code generated by the compiler, so there' some guesswork here, but even without having seen it, one can say that this: 

 test rax, 1 jpe even

… has a 50% chance of mispredicting the branch, and that will come expensive.

The compiler almost certainly does both computations (which costs neglegibly more since the div/mod is quite long latency, so the multiply-add is "free") and follows up with a CMOV. Which, of course, has a zero percent chance of being mispredicted.

Even without looking at assembly, the most obvious reason is that /= 2 is probably optimized as >>=1 and many processors have a very quick shift operation. But even if a processor doesn't have a shift operation, the integer division is faster than floating point division.

Edit: your milage may vary on the "integer division is faster than floating point division" statement above. The comments below reveal that the modern processors have prioritized optimizing fp division over integer division. So if someone were looking for the most likely reason for the speedup which this thread's question asks about, then compiler optimizing /=2 as >>=1 would be the best 1st place to look.

On an unrelated note , if n is odd, the expression n*3+1 will always be even. So there is no need to check. You can change that branch to 

 { n = (n*3+1) >> 1; count += 2; }

So the whole statement would then be 

 if (n & 1) { n = (n*3 + 1) >> 1; count += 2; } else { n >>= 1; ++count; }

From comments:

But, this code never stops (because of integer overflow) !?! Yves Daoust

For many numbers it will not overflow.

If it will overflow – for one of those unlucky initial seeds, the overflown number will very likely converge toward 1 without another overflow.

Still this poses interesting question, is there some overflow-cyclic seed number?

Any simple final converging series starts with power of two value (obvious enough?).

2^64 will overflow to zero, which is undefined infinite loop according to algorithm (ends only with 1), but the most optimal solution in answer will finish due to shr rax producing ZF=1.

Can we produce 2^64? If the starting number is 0x5555555555555555 , it's odd number, next number is then 3n+1, which is 0xFFFFFFFFFFFFFFFF + 1 = 0 . Theoretically in undefined state of algorithm, but the optimized answer of johnfound will recover by exiting on ZF=1. The cmp rax,1 of Peter Cordes will end in infinite loop (QED variant 1, "cheapo" through undefined 0 number).

How about some more complex number, which will create cycle without 0 ? Frankly, I'm not sure, my Math theory is too hazy to get any serious idea, how to deal with it in serious way. But intuitively I would say the series will converge to 1 for every number : 0 < number, as the 3n+1 formula will slowly turn every non-2 prime factor of original number (or intermediate) into some power of 2, sooner or later. So we don't need to worry about infinite loop for original series, only overflow can hamper us.

So I just put few numbers into sheet and took a look on 8 bit truncated numbers.

There are three values overflowing to 0 : 227 , 170 and 85 ( 85 going directly to 0 , other two progressing toward 85 ).

But there's no value creating cyclic overflow seed.

Funnily enough I did a check, which is the first number to suffer from 8 bit truncation, and already 27 is affected! It does reach value 9232 in proper non-truncated series (first truncated value is 322 in 12th step), and the maximum value reached for any of the 2-255 input numbers in non-truncated way is 13120 (for the 255 itself), maximum number of steps to converge to 1 is about 128 (+-2, not sure if "1" is to count, etc…).

Interestingly enough (for me) the number 9232 is maximum for many other source numbers, what's so special about it? :-O 9232 = 0x2410 … hmmm.. no idea.

Unfortunately I can't get any deep grasp of this series, why does it converge and what are the implications of truncating them to k bits, but with cmp number,1 terminating condition it's certainly possible to put the algorithm into infinite loop with particular input value ending as 0 after truncation.

But the value 27 overflowing for 8 bit case is sort of alerting, this looks like if you count the number of steps to reach value 1 , you will get wrong result for majority of numbers from the total k-bit set of integers. For the 8 bit integers the 146 numbers out of 256 have affected series by truncation (some of them may still hit the correct number of steps by accident maybe, I'm too lazy to check).

As a generic answer, not specifically directed at this task: In many cases, you can significantly speed up any program by making improvements at a high level. Like calculating data once instead of multiple times, avoiding unnecessary work completely, using caches in the best way, and so on. These things are much easier to do in a high level language.

Writing assembler code, it is possible to improve on what an optimising compiler does, but it is hard work. And once it's done, your code is much harder to modify, so it is much more difficult to add algorithmic improvements. Sometimes the processor has functionality that you cannot use from a high level language, inline assembly is often useful in these cases and still lets you use a high level language.

In the Euler problems, most of the time you succeed by building something, finding why it is slow, building something better, finding why it is slow, and so on and so on. That is very, very hard using assembler. A better algorithm at half the possible speed will usually beat a worse algorithm at full speed, and getting the full speed in assembler isn't trivial.

For the Collatz problem, you can get a significant boost in performance by caching the "tails". This is a time/memory trade-off. See: memoization ( https://en.wikipedia.org/wiki/Memoization ). You could also look into dynamic programming solutions for other time/memory trade-offs.

Example python implementation: 

 import sys inner_loop = 0 def collatz_sequence(N, cache): global inner_loop l = [ ] stop = False n = N tails = [ ] while not stop: inner_loop += 1 tmp = n l.append(n) if n <= 1: stop = True elif n in cache: stop = True elif n % 2: n = 3*n + 1 else: n = n // 2 tails.append((tmp, len(l))) for key, offset in tails: if not key in cache: cache[key] = l[offset:] return l def gen_sequence(l, cache): for elem in l: yield elem if elem in cache: yield from gen_sequence(cache[elem], cache) raise StopIteration if __name__ == "__main__": le_cache = {} for n in range(1, 4711, 5): l = collatz_sequence(n, le_cache) print("{}: {}".format(n, len(list(gen_sequence(l, le_cache))))) print("inner_loop = {}".format(inner_loop))

The simple answer:

  • doing a MOV RBX, 3 and MUL RBX is expensive; just ADD RBX, RBX twice

  • ADD 1 is probably faster than INC here

  • MOV 2 and DIV is very expensive; just shift right

  • 64-bit code is usually noticeably slower than 32-bit code and the alignment issues are more complicated; with small programs like this you have to pack them so you are doing parallel computation to have any chance of being faster than 32-bit code

If you generate the assembly listing for your C++ program, you can see how it differs from your assembly.

Interesting Posts

现代C ++编译器的有效优化策略

C＃中的内联函数？

展开列表（不规则）列表

为什么在Python中“.join（）比+ =快？

你将如何尽快做出这个转换声明？

为什么提前回报比其他回报慢？

为什么妈妈在Haswell上只有3个周期，与Agner的指令表不同？

优化C＃/。NET程序的提示

如何有效地使用MySQLDB的SScursor？

在Python中没有“+”运算符的string连接