C++ 取模运算符 Vs. 移位运算符，哪个更快，为什么？

Question

C++ 取模运算符 Vs. 移位运算符，哪个更快，为什么？

3

我正在编写查找质数的代码，期间我对C ++中的%运算符在低层次上如何工作产生了好奇。

首先，我编写了一些代码来比较'％'运算符和 '>>'运算符的每个所花费的时间。

#include <iostream>
#include <chrono>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

bool remainder1(int x);
bool remainder2(int y);
void timeCompare(bool(*f)(int), bool(*g)(int));

// I want to check which one is faster, x % 2 Vs. (x >> 1) & 1
int main()
{
    srand(time(NULL));

    for (int i = 0; i < 10; i++) {
        timeCompare(remainder1, remainder2);
    }

    return 0;
}

// % 2 operation
bool remainder1(int x) {

    if (x % 128) return true;
    else return false;
}

bool remainder2(int x) {

    if ((x >> 7) & 1) return true;
    else return false;
}

void timeCompare(bool(*f)(int), bool(*g)(int)) {

    srand(time(NULL));

    auto start = chrono::steady_clock::now();

    for (int i = 0; i < 10000000; i++) {
        int x = rand();
        f(x);
    }

    auto end = chrono::steady_clock::now();

    cout << "Elapsed time in nanoseconds : "
         << chrono::duration_cast<chrono::nanoseconds>(end - start).count()
         << " ns";


    auto start2 = chrono::steady_clock::now();

    for (int i = 0; i < 10000000; i++) {
        int x = rand();
        g(x);
    }

    auto end2 = chrono::steady_clock::now();


    cout << " Vs. "
         << chrono::duration_cast<chrono::nanoseconds>(end2 - start2).count()
         << " ns" << endl;


}

输出结果如下：

Elapsed time in nanoseconds : 166158000 ns Vs. 218736000 ns
Elapsed time in nanoseconds : 151776000 ns Vs. 214823000 ns
Elapsed time in nanoseconds : 162193000 ns Vs. 217248000 ns
Elapsed time in nanoseconds : 151338000 ns Vs. 211793000 ns
Elapsed time in nanoseconds : 150346000 ns Vs. 211295000 ns
Elapsed time in nanoseconds : 155799000 ns Vs. 215265000 ns
Elapsed time in nanoseconds : 148801000 ns Vs. 212839000 ns
Elapsed time in nanoseconds : 149813000 ns Vs. 226175000 ns
Elapsed time in nanoseconds : 152324000 ns Vs. 213338000 ns
Elapsed time in nanoseconds : 149353000 ns Vs. 216809000 ns

看起来位移操作在查找余数时比较慢。我猜想原因是位移版本需要比“%”版本多一次比较... 我的猜测正确吗？

我真的很想知道“%”在低层级是如何工作的！

- Hashnut

2

取模运算应该会比较慢，但是你的函数可能被优化成类似于 return x & 127; 这样的形式，所以它比位移版本少了一些操作。另外请注意，你的第二个函数实际上并没有和第一个函数做相同的事情（如果你想要找到除以2的余数，那么就不需要位移，这样做有点奇怪）。 - Qubit

1

顺便提一下，位移操作应该用于无符号整数。在有符号整数上使用它们可能会导致问题，虽然这很可能不会发生，但不能保证。 - Qubit

2

我猜你没有启用编译器优化（即使用调试构建），否则你的计时循环应该已经被优化掉了。 - Paul R

2

打开调试器，查看您代码的汇编。 - Ves

2

很明显，C++对于移位或取模运算符的速度没有具体规定。这完全取决于编译器和硬件。如果其中任何一个发生变化，你得到的结果可能会有所不同。 - john

1

个人讨厌的是 if (...) return true else return false 而不是 return ...。 - Caleth

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Geezer · Accepted Answer

我真的想知道在底层 '%' 是如何工作的！

如果你想知道它是如何实现的，答案是很可能 你使用的 CPU 有一个单独的模运算指令（%）。例如，看下这段 C++ 代码：

int main()
{
    int x = 100;

    int mod = x % 128;
    int shift = x >> 7;

    return 0;
}

生成的 x86 汇编代码（Clang 6.0.0）如下所示：

main:
    push    rbp
    mov     rbp, rsp
    xor     eax, eax
    mov     ecx, 128
    mov     dword ptr [rbp - 4], 0
    mov     dword ptr [rbp - 8], 100
    mov     edx, dword ptr [rbp - 8]  # Start of modulo boilerplater
    mov     dword ptr [rbp - 20], eax 
    mov     eax, edx
    cdq
    idiv    ecx                       # Modulo CPU instruction
    mov     dword ptr [rbp - 12], edx # End of modulo sequence
    mov     ecx, dword ptr [rbp - 8]  # Start of shift boilerplate
    sar     ecx, 7                    # Shift CPU instruction
    mov     dword ptr [rbp - 16], ecx # End of shift sequence
    mov     ecx, dword ptr [rbp - 20]
    mov     eax, ecx
    pop     rbp
    ret

idiv指令被称为有符号除法，它将商放在EAX/RAX中，余数放在EDX/RDX中。（适用于x86/x64）

我猜测这是因为移位版本需要比“%”版本多进行一次比较...我的猜测正确吗？

在这种情况下不需要进行比较，因为这是一个单独的指令。