Code: CachePressure

#include <stdio.h>
#include <windows.h>
#include <algorithm>

#define OBJECT_SIZE    128

class StopWatch
{
public:
StopWatch()
{
QueryPerformanceFrequency(&mFrequency);
}

void Start()
{
QueryPerformanceCounter( &mTimeStart );
}

void Stop()
{
QueryPerformanceCounter( &mTimeEnd );
}

double GetTimeElasped()
{
LONGLONG timeTaken = mTimeEnd.QuadPart – mTimeStart.QuadPart;
double timeMs = ((double)timeTaken * 1000.0) / (double)mFrequency.QuadPart;
return timeMs;
}

private:
LARGE_INTEGER mFrequency;
LARGE_INTEGER mTimeStart;
LARGE_INTEGER mTimeEnd;
};

// represents some large, sortable data structure
template <int DATA_SIZE>
struct LargeObject
{
LargeObject()
{
key = rand();
memset(data, 0, DATA_SIZE);
}

inline bool operator< (const LargeObject &obj)
{
return key < obj.key;
}

int key;
char data[DATA_SIZE];
};

// indirect reference to another object
struct IndirectObject
{
inline bool operator< (const IndirectObject &obj)
{
return key < obj.key;
}

int key;
int index;
};

double RunTest(int testSize)
{
srand(0);
LargeObject<OBJECT_SIZE> *largeObjs = new LargeObject<OBJECT_SIZE>[ testSize ];

StopWatch timer;
timer.Start();

std::sort(largeObjs, largeObjs + testSize);

timer.Stop();

delete[] largeObjs;

return timer.GetTimeElasped();
}

double RunTestIndirect(int testSize)
{
srand(0);

LargeObject<OBJECT_SIZE> *largeObjs = new LargeObject<OBJECT_SIZE>[ testSize ];
IndirectObject *indObjs = new IndirectObject[ testSize ];

// point indirect objects at large object array
for ( int i = 0; i < testSize; i++ )
{
indObjs[i].key = largeObjs[i].key;
indObjs[i].index = i;
}

StopWatch timer;
timer.Start();

std::sort(indObjs, indObjs + testSize);

timer.Stop();

delete[] largeObjs;
delete[] indObjs;

return timer.GetTimeElasped();
}

double RunTestIndirectSort(int testSize)
{
srand(0);

LargeObject<OBJECT_SIZE> *largeObjs = new LargeObject<OBJECT_SIZE>[ testSize ];
LargeObject<OBJECT_SIZE> *largeObjsSorted = new LargeObject<OBJECT_SIZE>[ testSize ];
IndirectObject *indObjs = new IndirectObject[ testSize ];

// point indirect objects at large object array
for ( int i = 0; i < testSize; i++ )
{
indObjs[i].key = largeObjs[i].key;
indObjs[i].index = i;
}

StopWatch timer;
timer.Start();

std::sort(indObjs, indObjs + testSize);

// copy largeObjs
for ( int i = 0; i < testSize; i++ )
{
largeObjsSorted[i] = largeObjs[ indObjs[i].index ];
}

timer.Stop();

delete[] largeObjsSorted;
delete[] largeObjs;
delete[] indObjs;

return timer.GetTimeElasped();
}

int main()
{
char filename[256];
sprintf(filename, “results_%d.csv”, OBJECT_SIZE);
FILE *f = fopen(filename, “w”);

int testSize;
int numIterations = 8;

fprintf(f, “Direct %d\n”, OBJECT_SIZE);
printf(“Direct Sort\n”);
testSize = 1024;
do
{
double avg = 0.0;
for ( int i = 0; i < numIterations; i++)
{
avg += RunTest(testSize);
}
avg /= (double)numIterations;
fprintf(f, “%8d,%g\n”, testSize, avg);
printf(“%8d\t%g\n”, testSize, avg);
testSize *= 2;
}
while (testSize <= 1024 * 1024);

fprintf(f, “Indirect %d\n”, OBJECT_SIZE);
printf(“Indirect\n”);
testSize = 1024;
do
{
double avg = 0.0;
for ( int i = 0; i < numIterations; i++)
{
avg += RunTestIndirect(testSize);
}
avg /= (double)numIterations;
fprintf(f, “%8d,%g\n”, testSize, avg);
printf(“%8d\t%g\n”, testSize, avg);
testSize *= 2;
}
while (testSize <= 1024 * 1024);

fprintf(f, “Indirect Sort %d\n”, OBJECT_SIZE);
printf(“Indirect Sort\n”);
testSize = 1024;
do
{
double avg = 0.0;
for ( int i = 0; i < numIterations; i++)
{
avg += RunTestIndirectSort(testSize);
}
avg /= (double)numIterations;
fprintf(f, “%8d,%g\n”, testSize, avg);
printf(“%8d\t%g\n”, testSize, avg);
testSize *= 2;
}
while (testSize <= 1024 * 1024);

fclose(f);
return 0;
}