Time measurement of array access patterns

arr_cache_test.c

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

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 :)

@jfunction Can you kindly provide specific information about your machine, command to compile and execute the code.