#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