声称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。

在我的测试中，(1 GHz AMD A4-1200处理器)，上面的代码大约比问题中的c++代码快四倍(当用-O0编译时:430毫秒vs. 1900毫秒)，当用-O3编译时，快两倍多(430毫秒vs. 830毫秒)。

两个程序的输出是相同的:在i = 837799上，max sequence = 525。

评论:

但是，这段代码从未停止(因为整数溢出)!?!伊夫Daoust

对于许多数字，它不会溢出。

如果它会溢出——对于那些不幸的初始种子之一，溢出的数字很可能会收敛到1而不会再次溢出。

这仍然提出了一个有趣的问题，是否存在一些溢出循环的种子数?

任何简单的最终收敛级数都以2的幂值开始(够明显了吗?)

2^64会溢出到零，根据算法，这是一个未定义的无限循环(仅以1结束)，但由于shr rax产生ZF=1, answer中的最优解将结束。

能得到2^64吗?如果起始数是0x5555555555555555，它是奇数，那么下一个数是3n+1，它是0xFFFFFFFFFFFFFFFF +1 = 0。理论上算法处于未定义状态，但johnfound的优化答案在ZF=1时退出即可恢复。cmp rax, Peter Cordes的1将在无限循环中结束(QED变体1，“cheapo”通过未定义的0数)。

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.

我只是把一些数字写在表格里，然后看了看8位截断的数字。

有三个值溢出到0:227、170和85(85直接到0，其他两个递增到85)。

但是创建循环溢出种子没有任何价值。

有趣的是，我做了一个检查，这是第一个遭受8位截断的数字，已经有27个受到影响!在正确的非截断序列中，它确实达到了值9232(第一个截断值在第12步中是322)，在非截断的方式中，2-255输入数字中的任何一个达到的最大值是13120(对于255本身)，收敛到1的最大步数大约是128(+-2，不确定“1”是否算数，等等……)

有趣的是(对我来说)数字9232是许多其他源数字的最大值，它有什么特别之处?:-O 9232 = 0x2410…嗯. .不知道。

不幸的是，我无法深入了解这个系列，为什么它会收敛，截断它们到k位的含义是什么，但随着cmp数，1终止条件，当然可以将算法放入无限循环，特定的输入值在截断后以0结束。

但是对于8位的情况，值27溢出有点警告，这看起来像如果你计算到达值1的步数，你会得到错误的结果，对于整个k位整数集的大多数数字。对于8位整数，256个数字中的146个数字通过截断影响了序列(其中一些可能仍然意外地命中了正确的步数，我太懒了，没有检查)。

c++程序在从源代码生成机器码的过程中被转换为汇编程序。说汇编比c++慢实际上是错误的。此外，生成的二进制代码因编译器而异。因此，一个聪明的c++编译器可能会生成比愚蠢的汇编器代码更优、更有效的二进制代码。

但我认为你的分析方法有一定缺陷。以下是概要分析的一般准则:

确保您的系统处于正常/空闲状态。停止所有已启动或大量使用CPU的正在运行的进程(应用程序)(或在网络上轮询)。 您的数据必须更大。 您的测试必须运行5-10秒以上。 不要仅仅依赖于一个样本。执行测试N次。收集结果并计算结果的平均值或中位数。

对于Collatz问题，可以通过缓存“尾部”来显著提高性能。这是一个时间和内存的权衡。看:记忆 (https://en.wikipedia.org/wiki/Memoization)。您还可以考虑其他时间/内存权衡的动态编程解决方案。

python实现示例:

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

即使不考虑汇编，最明显的原因是/= 2可能被优化为>>=1，许多处理器具有非常快的移位操作。但即使处理器没有移位操作，整数除法也比浮点除法快。

编辑:在上面的“整数除法比浮点除法快”语句中，您的里程数可能会有所不同。下面的注释表明，现代处理器已经优先优化fp除法而不是整数除法。因此，如果有人正在寻找这个线程的问题所要求的最可能的加速原因，那么编译器优化/=2为>>=1将是最好的第一个地方。

与此无关的是，如果n是奇数，表达式n*3+1总是偶数。所以不需要检查。您可以将分支更改为

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

所以整个表述就是

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

答案很简单:

做一个MOV RBX, 3和MUL RBX是昂贵的;只要加上RBX, RBX两次 add1在这里可能比INC更快 MOV 2和DIV非常昂贵;向右平移 64位代码通常明显比32位代码慢，对齐问题更复杂;对于这样的小程序，你必须打包它们，这样你才能进行并行计算，从而有可能比32位代码更快

如果为c++程序生成程序集列表，可以看到它与程序集的区别。