Created
April 6, 2016 22:26
-
-
Save anonymous/e326bc9b764e3f04c494a213f704a669 to your computer and use it in GitHub Desktop.
Time measurement of array access patterns
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdlib.h> | |
#include <stdio.h> | |
#include <time.h> | |
void do_work(int *mem, int size, int step) { | |
for (int i = 0; i < size; i += step) | |
mem[i] *= 3; | |
} | |
double gather_time(int *mem, int size, int step) { | |
clock_t start, end; | |
start = clock(); | |
do_work(mem, size, step); | |
end = clock(); | |
// return diff in millis | |
return (1.0 * end - start) / (CLOCKS_PER_SEC / 1000); | |
} | |
int main(int argc, char* argv[]) { | |
int size = 64 * 1024 * 1024; | |
int *arr; | |
int steps[] = {1, 2, 4, 8, 16, 32, 64, 128, 256}; | |
double times[9]; | |
arr = malloc(size * sizeof(int)); | |
if (!arr) | |
return 1; | |
for (int i = 0; i < sizeof(steps) / sizeof(int); i++) { | |
times[i] = gather_time(arr, size, steps[i]); | |
} | |
for (int i = 0; i < sizeof(times) / sizeof(double); i++ ) { | |
printf("time[%d] = %.3f\n", steps[i], times[i]); | |
} | |
return 0; | |
} |
@jfunction Can you kindly provide specific information about your machine, command to compile and execute the code.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Saw your post on http://igoro.com/archive/gallery-of-processor-cache-effects/ - how were you compiling? I get the same results as Igor when compiling with -O3 but when compiling with -O0 I get what you describe in your comment. Be careful passing in the altered array in L31 by the way - you should start each timed test with the same initial conditions (though 0*3=0 presumably).
If you think about it, the number of trips to memory is num_elements_to_process * likelihood_of_cache_miss = N/s * min(s/c,1) where N=number of elements in the array, s=step size (elements), c=chunk size (elements, ie 16 for 64 byte line size). When s<c, you see that the number of trips to main memory is fixed at N/c for any step size. Anyway, I've just spent some time thinking about it, so I thought I'd pass this on. Even if it's a year late :)