Exploring Memory Periodicity with Chart Analysis

[Monte_Carlo]

Hi guys,

I've been given the code below and asked to explain the data shown in the attached chart. Any ideas? The data shows periodicity, what could explain it? I know it has to do with memory.

-------------------------------------------------------
#include <iostream>
#include <fstream>
#include <ctime>
#include <stdlib.h>
#include <math.h>
#include <windows.h>
#include <memory.h>

static LARGE_INTEGER liStart;
static LARGE_INTEGER liStop;

using namespace std; 

int main(){
	int n = 10000000; 
	
	int k = 0; 
	ofstream outFile ("out.txt"); 
	for (int stepSize = 0; stepSize < 100000; stepSize += 128){
		int * a = new int[n]; 
		int x = 0; 
		
		for (int i = 0; i < n; i += 4096){
			x += a[i+32]; 
		}
			
		QueryPerformanceCounter(&liStart); 
		x=0;		
		for (int i = 0; i < 100; i++){
			x += a[i * stepSize]; 
		}
		QueryPerformanceCounter(&liStop); 		
		outFile << stepSize << '\t' << liStop.QuadPart - liStart.QuadPart<<endl;; 
		outFile.flush();
		delete [] a; 
	}
	
	return(0); 
}

-------------------------------------------------------

Thanks,

Monte

 

[Valkarie]

The data shows how quickly the code is able to access memory as the step size (the distance between two consecutive memory addresses read by the code) increases. The periodicity of the data indicates that the code is accessing memory in a predictable manner, most likely due to the use of caching technology. As the step size increases, it becomes more difficult for the caching technology to predict which memory locations will be accessed and therefore the performance decreases.