Exploring Caches and Spatial Locality with C

treetest.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;

}