C++ Modulus operator Vs. Shift operator, which is faster and why?

Question

I was working on the code to find prime number, and during my work i became curious how exactly % operation in C++ works in low level.

Firstly, I wrote some code to compare elapsed time of '%' operator and '>>' operator, each.

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


}

And the output is this :

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 

So it seems like shift operation is slower in finding remainder. I guessed the reason is that shift version needs one more comparison than '%' version... Am I correct?

I really want to know how '%' works in lower level!

Answer 1

I really want to know how '%' works in lower level!

If you're asking how it is implemented then the answer is that chances are the CPU you're using has a single instruction for modulo (%). For example, take this C++ code:

int main()
{
    int x = 100;

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

    return 0;
}

The generated x86 assembly code (Clang 6.0.0) for it is:

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

The idiv instruction is called the Signed Divide, and it places the quotient in EAX/RAX and the remainder in EDX/RDX for (x86/x64 accordingly).

I guessed the reason is that shift version needs one more comparison than '%' version... Is my correct?

No comparisons are being done in this case, since it's a single instruction.