Exploring Caches and Spatial Locality with C
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
#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