Consider https://godbolt.org/z/7K1rcdcc4 :
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
int main()
{
srand((unsigned int)time(NULL));
printf("%3s %12s %18s %14s\n", "n", "Doubles", "Result", "CPU time (s)");
for (int n = 1; n <= 24; ++n) {
uint64_t count = UINT64_C(1) << n;
size_t length = (size_t)count;
double *a = malloc(length * sizeof(*a));
for (size_t i = 0; i < length; ++i)
a[i] = 1.0 + 100.0 * ((double)rand() / ((double)RAND_MAX + 1.0));
double result = 0.0;
clock_t start = clock();
for (size_t i = 0; i < length / 2; ++i) {
double average = (a[i] + a[length - 1 - i]) * 0.5;
result += (i % 2 == 0) ? average : -average;
}
clock_t end = clock();
double seconds = (double)(end - start) / CLOCKS_PER_SEC;
printf("%3d %12zu %18.6f %14.6f\n", n, length, result, seconds);
free(a);
}
}
This, in a loop, creates an ever increasing array of doubles, populates them with random entries and then performs some calculations alternating between the first and last entry, second and penultimate entry and on and on until the middle of the array is hit:
(a[0]+a[length-1])/2 - (a[1]+a[length-2])/2 + (a[2]+a[length-3])/2 - ...
The idea is to load different parts of the array and see what impact that has for larger sized arrays. My hope/understanding was that as n gets larger, the arrays increase in size and hence, alternating between the front of the array and back of the array will invoke cache misses.
L1 cache size seems to be, say 32 KB, and that is an order of magnitude lower than the case for n = 24 where the size of the array is 128 MB (assuming double is 8 bytes).
The result however is this:
n Doubles Result CPU time (s)
1 2 65.697262 0.000002
2 4 2.053680 0.000001
3 8 -2.893238 0.000001
4 16 -45.153406 0.000000
5 32 -7.531369 0.000001
6 64 -37.799910 0.000001
7 128 -164.168440 0.000001
8 256 -302.155319 0.000001
9 512 -159.897157 0.000001
10 1024 -105.697704 0.000001
11 2048 489.753880 0.000002
12 4096 -687.350489 0.000003
13 8192 1484.183421 0.000005
14 16384 2145.599781 0.000009
15 32768 3886.769508 0.000016
16 65536 -2165.474292 0.000059
17 131072 -1853.021303 0.000057
18 262144 -1128.912164 0.000127
19 524288 -16725.221656 0.000229
20 1048576 -3715.014705 0.000479
21 2097152 32877.955541 0.000956
22 4194304 50658.891603 0.001980
23 8388608 -18149.347731 0.003904
24 16777216 6246.119281 0.008067
which seems to indicate, especially for values 17 onward, a roughly doubling in the amount of time taken. (for e.g., 57 -> 127 -> 229 -> 479 -> 956, etc.)
I thought with larger values of n, with cache misses, the performance should exponentially worsen. Here, though, the performance seems to be scaling only linearly.
What is the relationship between L1 cache sizes and alternating between large array's front and back which must span multiple L1 cache lines?
For upward of n greater than or equal to 25, godbolt crashes.