Performance of size_t in C++

Question

I translated the code here into C++ as follows

#include <iostream>

using namespace std;

int t = 20;

bool is_evenly_divisible(const int a, const int b) {
    for (int i=2; i<=b; ++i) { // Line 1
        if (a%i != 0)
            return false;
    }
    return true;
}

void run() {
    int i = 10;
    while (!is_evenly_divisible(i, t)) {
        i += 2;
    }
    cout << i << endl;
}

int main(int argc, char** argv) {
    run();
    return 0;
}

With the -O3 flag on compiler g++ 4.8.1 on Mac OSX 10.8.4, I get time 0.568s user time.

Now if I change the counter i in Line 1 in function is_evenly_divisible to size_t, the time suddenly jumps to 1.588s. This persists even if I change all of the variables to size_t, the time increases to 1.646s

What's happening? Shouldn't size_t increase performance rather than decreasing it as it's a more specific type than int?

Answer 1

int is usually the fastest all-round type. This property isn't mandated by the standard, but it's usually the case for today's platforms. We've also got things like cstdint's int_fast32_t which is more properly guaranteed to be the fastest type that can hold at least 32 bits -- highly recommend them for perf-sensitive code!

size_t isn't intended to give a fast integer. Its purpose is to provide an integer that can hold the size of the largest sized object your platform's address space can contain. Typically size_t is equivalent to the largest "native" integer your CPU supports, but it doesn't have to be.

I'm going to guess that you're on a 64-bit platform. Generally a 64-bit platform has about equal perf for 32-bit and 64-bit ops, but you've hit the one place they typically aren't: div/mod can actually be 2-3x slower on a 64-bit integer. In this case if int is 32-bit and size_t is 64-bit, it explains the issue nicely.

See Agner Fog's instruction tables document for more info. For Intel's Sandy Bridge platform, it shows 32-bit div has a latency of 20-28 cycles while 64-bit div takes 30-94 cycles.

Answer 2

Size of size_t is implementation-defined and if you are running 64-bit machine most of the compilers would make it 8-byte long.

Operations with 8-byte integers are usually slower than with 4-byte analogs.