Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Exploring Caches and Spatial Locality with C
#define DEFAULTTREEHEIGHT 20
#define DEFAULTITERATIONS 1000
#include <sys/time.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
typedef struct{
void* right;
void* left;
int value;
}treenode;
typedef struct{
void* next;
void* prev;
void* data;
}lnode;
typedef struct{
lnode* front;
lnode* back;
}list;
int addfront(list* l, void* data){
lnode* newnode = malloc(sizeof(lnode));
if(newnode == NULL) return -1;
newnode->data = data;
newnode->next = l->front;
newnode->prev = NULL;
if(l->front != NULL){
l->front->prev = newnode;
l->front = newnode;
}
else{
l->front = newnode;
l->back = newnode;
}
return 0;
}
void* removeback(list* l){
if(l->back == NULL) return NULL;
lnode* back = l->back;
void* data = back->data;
l->back = back->prev;
if(l->back != NULL) l->back->next = NULL;
else l->front = NULL;
free(back);
return data;
}
treenode* buildtree(int h){
if(h < 0) return NULL;
treenode* t = malloc(sizeof(treenode));
if(t == NULL){
printf("Could not allocate memory");
exit(1);
}
t->value = rand() % 10;
//t->value = 1;
--h;
t->right = buildtree(h);
t->left = buildtree(h);
return t;
}
treenode* newnode(){
treenode* t = malloc(sizeof(treenode));
if(t == NULL){
printf("Could not allocate memory");
exit(1);
}
t->value = rand() % 10;
//t->value = 1;
t->left = NULL;
t->right = NULL;
return t;
}
int ipow(int base, int exp)
{
int result = 1;
while (exp)
{
if (exp & 1)
result *= base;
exp >>= 1;
base *= base;
}
return result;
}
treenode* buildtreeBFS(int height){
if(height < 0) return NULL;
treenode* t = newnode();
list* l = malloc(sizeof(list));
if(l == NULL){
printf("Could not allocate memory");
exit(1);
}
addfront(l, t);
int nodes = pow(2, height+1) - 2;
printf("%d\n", nodes);
while(nodes > 0){
treenode* node = removeback(l);
node->left = newnode();
node->right = newnode();
addfront(l, node->left);
addfront(l, node->right);
nodes -= 2;
}
while(removeback(l) != NULL); //clear out the list
free(l);
return t;
}
int addtree(treenode* t){
if(t == NULL) return 0;
else return t->value + addtree(t->right) + addtree(t->left);
}
int addtree_prefetch(treenode* t){
if(t == NULL) return 0;
__builtin_prefetch(t->left);
__builtin_prefetch(t->right);
return t->value + addtree(t->right) + addtree(t->left);
}
int main(int argc, char** argv){
struct timeval start, end;
int h = DEFAULTTREEHEIGHT, iterations = DEFAULTITERATIONS;
if(argc > 1) h = atoi(argv[1]);
if(argc > 2) iterations = atoi(argv[2]);
printf("Building tree...\n");
treenode* t;
if(argc > 3) t = buildtreeBFS(h);
else t = buildtree(h);
printf("Tree sum = %d\n", addtree(t));
printf("Starting timer\n");
gettimeofday(&start, NULL);
int i;
for(i=0; i < iterations; i++) {
addtree(t);
}
gettimeofday(&end, NULL);
printf("Stopping timer\n");
float microseconds = ((end.tv_sec - start.tv_sec) * 1000000.0) + (end.tv_usec - start.tv_usec);
printf("%s height %d, %d iterations: %f seconds without prefetching\n", argv[0], h, iterations, microseconds / 1000000.0);
printf("Starting timer with prefetch\n");
gettimeofday(&start, NULL);
for(i=0; i < iterations; i++) {
addtree_prefetch(t);
}
gettimeofday(&end, NULL);
printf("Stopping timer with prefetch\n");
microseconds = ((end.tv_sec - start.tv_sec) * 1000000.0) + (end.tv_usec - start.tv_usec);
printf("%s height %d, %d iterations: %f seconds with prefetching\n", argv[0], h, iterations, microseconds / 1000000.0);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment