我在做Collatz猜想的时候发现C++比我自己编的汇编代码运行还要快,为什么呢?

0 投票
最新提问 2月 21 用户: 西山路人甲 (120 分)

我在做Collate猜想 Project Euler Q14 时用了汇编和C++,两种方案的时间复杂度是一样的,汇编编译器用的是:

nasm -felf64 p14.asm && gcc p14.o -o p14
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++的编译用的是

g++ p14.cpp -o p14
#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;
}

我知道C++会做编译器优化来提高速度,不过我觉得我的汇编代码也足够优化了。

C++代码编译时会产生很多模块和区段,我的汇编代码只有1个区块,但汇编的执行要比C++至少多1秒多,为什么呢?

我的系统:64 bit Linux on ‎1.4 GHz Intel Celeron 2955U (Haswell microarchitecture).

  • g++ (unoptimized): avg 1272 ms

  • g++ -O3 avg 578 ms

  • original asm (div) avg 2650 ms

  • Asm (shr) avg 679 ms

1个回答

0 投票
最新回答 2月 21 用户: 云在飞 (300 分)

DIV指令的效率可不高,即便你用-O0快速编译也不行。

看看《Agner Fog's Optimizing Assembly guide》这本书,这是讲如何编写高效率asm代码的。书里还有针对不同CPU的不同代码优化指导。总之多学习吧!

欢迎来到编程助手,编程方面有什么不懂的问题可以尽管在这里提问,你将会收到热心爱好者的回答。
...