Liu Renjie Liu Renjie - 1 month ago 17
C++ Question

Why this c++ code is not faster?

all:
I have two pieces of code. The first one is:

#include <iostream>

using namespace std;

static constexpr long long n = 1000000000;

int main() {
int sum = 0;
int* a = new int[n];
int* b = new int[n];

for (long long i=0; i<n; i++) {
a[i] = static_cast<int>(i);
}

for (long long i=0; i<n; i++) {
sum *= a[i];
sum += a[i];
}

for (long long i=0; i<n; i++) {
b[i] = static_cast<int>(i);
}

for (long long i=0; i<n; i++) {
sum *= b[i];
sum += b[i];
}

cout<<sum<<endl;
}


The second one is:

#include <iostream>

using namespace std;

constexpr long long n = 1000000000;

int main() {
int* a = new int[n];
int* b = new int[n];
int sum = 0;

for (long long i=0; i<n; i++) {
a[i] = static_cast<int>(i);
b[i] = static_cast<int>(i);
}

for (long long i=0; i<n; i++) {
sum *= a[i];
sum += a[i];
sum *= b[i];
sum += b[i];
}

cout<<sum<<endl;
}


I think the first programs should be much faster than the second one, since it's more cache friendly. However, the truth is the second one is a litter faster. On my server, the first one takes 23s while the second one takes 20s, can some one explain this?

sh1 sh1
Answer

You're not seeing cache-friendliness advantages because the access pattern is still much too simple even in the version you predict to be slower.

Two (or more) concurrent streams of straight-line input is something a modern CPU can detect and stream into L1 ahead of it being needed.

It can also allow multiple SDRAM banks to be put to useful work at the same time. If you're using Linux you don't get much control over that because pages are mapped randomly (I think; is this still true?), but you can try allocating memory using mmap() with the MAP_HUGETLB argument and then try different offsets from the start of the allocation.

If you want to see the advantage of arranging your computations in a cache-friendly order you should perhaps experiment with different access patterns in two-dimensional arrays.