test_real.cpp

// test framework
#define NDEBUG
//#define cilk_for for
//#define usleep(a)
#define batch_size 10000
#include <set>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
// #include <pair>
#include "AdjacencyList.cpp"
#include "AdjacencyHashMap.cpp"
#include "AdjacencyMatrix.cpp"
#include "AdjacencyVector.cpp"
#include "CSR.cpp"
#include "Graph.hpp"
#include "OFM.cpp"
#include <ctime>
#include <iostream>
#include <random>
#include <sys/time.h>
#define MAXVAL 100

#define batch_size_for_test 10

/*
static uint32_t x = 123456789;
static uint32_t y = 362436069;
static uint32_t z = 521288629;
static uint32_t w = 88675123;

uint32_t xor128(void) {
  uint32_t t;
  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
void srand() {
  x = 123456789;
  y = 362436069;
  z = 521288629;
  w = 88675123;
}
*/
uint32_t rand_in_range(uint32_t max) { return rand() % max; }

bool compare_matrices(Graph *g1, Graph *g2, int num_nodes) {
  for (int i = 0; i < num_nodes; i++) {
    for (int j = 0; j < num_nodes; j++) {
      if (g1->find_value(i, j) != g2->find_value(i, j)) {
        printf("i: %d, j: %d, g1_val: %d, g2_vl: %d\n", i, j,
               g1->find_value(i, j), g2->find_value(i, j));
        if (j + 1 < num_nodes) {
          printf("i: %d, j: %d, g1_val: %d, g2_vl: %d\n", i, j + 1,
                 g1->find_value(i, j + 1), g2->find_value(i, j + 1));
        }
        if (j - 1 >= 0) {
          printf("i: %d, j: %d, g1_val: %d, g2_vl: %d\n", i, j - 1,
                 g1->find_value(i, j - 1), g2->find_value(i, j - 1));
        }
        return false;
      }
    }
  }
  return true;
}

bool verify_structure(Graph *g, uint32_t num_nodes, uint32_t num_edges, int trials) {
      // printf("########## starting trial %d out of %d, nodes = %u, edges = %u "
      //        "##########\n",
      //        j, trials, num_nodes, num_edges);
      AdjacencyMatrix matrix = AdjacencyMatrix(num_nodes);
      // AdjacencyHashMap adjhash = AdjacencyHashMap(num_nodes);
      uint32_t srcs[batch_size_for_test] = {0};
      uint32_t dests[batch_size_for_test] = {0};
      uint32_t vals[batch_size_for_test] = {0};
      for (uint32_t i = 0; i <= num_edges / batch_size_for_test; i++) {
        for (uint32_t b = 0; b < batch_size_for_test; b++) {
          uint32_t src = rand_in_range(num_nodes);
          uint32_t dest = rand_in_range(num_nodes);
          while (matrix.find_value(src, dest) != 0) {
            src = rand_in_range(num_nodes);
            dest = rand_in_range(num_nodes);
          }
          uint32_t val = rand_in_range(MAXVAL) + 1;

          matrix.add_edge(src, dest, val);
          srcs[b] = src;
          dests[b] = dest;
          vals[b] = val;
        }
        for (uint32_t b = 0; b < batch_size_for_test; b++) {
          // printf("about to add edge %d, %d, %d by worker %lu\n",srcs[b],
          // dests[b], vals[b], get_worker_num());
          g->add_edge(srcs[b], dests[b], vals[b]);
        }
      }
      if (!compare_matrices(&matrix, g, num_nodes)) {
        printf("failed in add edges, nodes = %u, edges = %u\n", num_nodes,
               num_edges);
        matrix.print_graph();
        printf("\n");
        g->print_graph();
        return false;
      }

      for (uint32_t i = 0; i <= num_edges / batch_size_for_test; i++) {
        for (uint32_t b = 0; b < batch_size_for_test; b++) {
          uint32_t src = rand_in_range(num_nodes);
          uint32_t dest = rand_in_range(num_nodes);
          while (matrix.find_value(src, dest) != 0) {
            src = rand_in_range(num_nodes);
            dest = rand_in_range(num_nodes);
          }
          uint32_t val = rand_in_range(MAXVAL) + 1;

          matrix.add_edge_update(src, dest, val);
          srcs[b] = src;
          dests[b] = dest;
          vals[b] = val;
        }

        for (uint32_t b = 0; b < batch_size_for_test; b++) {
          g->add_edge_update(srcs[b], dests[b], vals[b]);
        }
      }

      if (!compare_matrices(&matrix, g, num_nodes)) {
        printf("failed in add edges update, nodes = %u, edges = %u\n",
               num_nodes, num_edges);
        matrix.print_graph();
        printf("\n");
        g->print_graph();
        return false;
      }

      vector<uint32_t> test_vector(num_nodes, 0);
      for (uint32_t i = 0; i < num_nodes; i++) {
        test_vector[i] = rand_in_range(MAXVAL);
      }
      vector<uint32_t> r1 =
          matrix.sparse_matrix_vector_multiplication(test_vector);
      vector<uint32_t> r2 =
          g->sparse_matrix_vector_multiplication(test_vector);
      if (r1 != r2) {
        printf("failed spvm, nodes = %u, edges = %u\n", num_nodes, num_edges);
        for (auto const &c : r1) {
          printf("%d ", c);
        }
        printf("\n");
        for (auto const &c : r2) {
          printf("%d ", c);
        }
        printf("\n");
        return false;
      }

      int start_node = rand_in_range(num_nodes);
      vector<uint32_t> r3 = matrix.bfs(start_node);
      vector<uint32_t> r4 = g->bfs(start_node);
      if (r3 != r4) {
        printf("failed bfs, nodes = %u, edges = %u\n", num_nodes, num_edges);
        matrix.print_graph();
        printf("\n");
        g->print_graph();
        for (auto const &c : r3) {
          printf("%d ", c);
        }
        printf("\n");
        for (auto const &c : r4) {
          printf("%d ", c);
        }
        printf("\n");
        return false;
      }

      vector<uint32_t> test_vector2(num_nodes, 0);
      for (uint32_t i = 0; i < num_nodes; i++) {
        test_vector2[i] = ((uint32_t)rand_in_range(MAXVAL)) / MAXVAL;
      }
      vector<uint32_t> r5 = matrix.pagerank(test_vector2);
      vector<uint32_t> r6 = g->pagerank(test_vector2);
      if (r5 != r6) {
        printf("failed pagerank, nodes = %u, edges = %u\n", num_nodes,
               num_edges);
        matrix.print_graph();
        printf("\n");
        g->print_graph();
        for (auto const &c : test_vector2) {
          printf("%u ", c);
        }
        printf("\n");
        for (auto const &c : r5) {
          printf("%u ", c);
        }
        printf("\n");
        for (auto const &c : r6) {
          printf("%u ", c);
        }
        printf("\n");
        return false;
      }
  return true;
}

bool verify_adjacency_hashmap() {
  srand(0);
  uint32_t node_counts[4] = {5, 10, 30, 100};
  uint32_t edge_counts[4] = {5, 20, 100, 1000};
  int trials = 1000;
  for (int a = 0; a < 4; a++) {
    for (int j = 1; j < trials; j++) {
      uint32_t num_nodes = node_counts[a];
      uint32_t num_edges = edge_counts[a];
      /*
      printf("########## starting trial %d out of %d, nodes = %u, edges = %u "
             "##########\n",
             j, trials, num_nodes, num_edges);
       */
      // AdjacencyMatrix matrix = AdjacencyMatrix(num_nodes);
      AdjacencyHashMap adjhash = AdjacencyHashMap(num_nodes);

      if(!verify_structure(&adjhash, num_nodes, num_edges, trials)){
        return false;
      }
    }
  }
  return true;
}

bool verify_adjacency_list() {
  srand(0);
  uint32_t node_counts[4] = {5, 10, 30, 100};
  uint32_t edge_counts[4] = {5, 20, 100, 1000};
  int trials = 1000;
  for (int a = 0; a < 4; a++) {
    for (int j = 1; j < trials; j++) {
      uint32_t num_nodes = node_counts[a];
      uint32_t num_edges = edge_counts[a];
      AdjacencyList adjlist = AdjacencyList(num_nodes);
      if(!verify_structure(&adjlist, num_nodes, num_edges, trials)) {
        return false;
      }
    }
  }
  return true;
}


bool verify_adjacency_vector() {
  srand(0);
  uint32_t node_counts[4] = {5, 10, 30, 100};
  uint32_t edge_counts[4] = {5, 20, 100, 1000};
  int trials = 1000;
  for (int a = 0; a < 4; a++) {
    for (int j = 1; j < trials; j++) {
      uint32_t num_nodes = node_counts[a];
      uint32_t num_edges = edge_counts[a];
      AdjacencyVector adjvec = AdjacencyVector(num_nodes);
      if(!verify_structure(&adjvec, num_nodes, num_edges, trials)) {
        return false;
      }
    }
  }
  return true;
}

bool verify_csr() {
  srand(0);
  uint32_t node_counts[4] = {5, 10, 30, 100};
  uint32_t edge_counts[4] = {5, 20, 100, 1000};
  int trials = 1000;
  for (int a = 0; a < 4; a++) {
    for (int j = 1; j < trials; j++) {
      uint32_t num_nodes = node_counts[a];
      uint32_t num_edges = edge_counts[a];
      CSR *csr = new CSR(num_nodes);
      if(!verify_structure(csr, num_nodes, num_edges, trials)) {
        return false;
      }
    }
  }
  return true;
}


bool verify_pcsr() {
  srand(0);
  uint32_t node_counts[4] = {5, 10, 30, 100};
  uint32_t edge_counts[4] = {5, 20, 100, 1000};
  int trials = 1000;
  for (int a = 0; a < 4; a++) {
    for (int j = 1; j < trials; j++) {
      uint32_t num_nodes = node_counts[a];
      uint32_t num_edges = edge_counts[a];
      OFM *ofm = new OFM(num_nodes);
      if(!verify_structure(ofm, num_nodes, num_edges, trials)) {
        return false;
      }
    }
  }
  return true;
}

/******* timing functions ********/
bool time_structure(Graph* g, uint32_t num_nodes, uint32_t num_edges) {
  srand(0);

  struct timeval start, end;
  uint32_t duration;

  
  // add edge update
  uint32_t *srcs = (uint32_t *) malloc(sizeof(uint32_t) * num_edges);
  uint32_t *dests = (uint32_t *) malloc(sizeof(uint32_t) * num_edges);
  uint32_t *vals = (uint32_t *) malloc(sizeof(uint32_t) * num_edges);

  for (uint32_t k = 0; k < num_edges; k++) {
    srcs[k] = rand_in_range(num_nodes);
    dests[k] = rand_in_range(num_nodes);
    vals[k] = rand_in_range(MAXVAL) + 1;
  }
  gettimeofday(&start, NULL);
  for(int i = 0; i < num_edges; i+=batch_size) {
    g->add_edge_batch_update(&srcs[i], &dests[i], &vals[i], batch_size);
  }

  gettimeofday(&end, NULL);
  free(srcs);
  free(dests);
  free(vals);
  duration =
            (end.tv_sec - start.tv_sec) * 1000000u + (end.tv_usec - start.tv_usec);
  if (num_edges > 0) {
    printf("add_edge_update :%f: \n", ((double)duration) / (1000000));
  } else {
    printf("add_edge_update :N/A: ");
  }


    vector<uint32_t> test_vector(num_nodes, 0);
    for (uint32_t i = 0; i < num_nodes; i++) {
      test_vector[i] = rand_in_range(MAXVAL);
    }

  // spvm
    /*
    gettimeofday(&start, NULL);
    // start = std::clock();
    for (int spvm_iters = 0; spvm_iters < 100; spvm_iters++) {
      test_vector = g->sparse_matrix_vector_multiplication(test_vector);
    }

    gettimeofday(&end, NULL);
    duration = (end.tv_sec-start.tv_sec)*1000000u+(end.tv_usec-start.tv_usec);
    printf("spvm: %f: ", ((double)duration)/1000000);
    printf("spvm[0]: %d: ", test_vector[0]);
    gettimeofday(&start, NULL);
*/
  // bfs
  /*
    int start_node = rand_in_range(num_nodes);
    gettimeofday(&start, NULL);
    for (int bfs_iters = 0; bfs_iters < 100; bfs_iters++) {
      vector<uint32_t> r4 = g->bfs(start_node);
      start_node = r4[0] % num_nodes;
    }
    gettimeofday(&end, NULL);
    duration = (end.tv_sec-start.tv_sec)*1000000u+(end.tv_usec-start.tv_usec);
    printf("bfs in %f,", ((double)duration)/1000000);
    printf("sn = %d,", start_node);
    */
/*
  // pagerank
  vector<uint32_t> test_vector2(num_nodes, 0);
  for (uint32_t i = 0; i < num_nodes; i++) {
    test_vector2[i] = ((uint32_t)rand_in_range(MAXVAL)) / MAXVAL;
  }
  gettimeofday(&start, NULL);
  for (int pr_iters = 0; pr_iters < 100; pr_iters++) {
    vector<uint32_t> test_vector2 = g->pagerank(test_vector2);
  }
  gettimeofday(&end, NULL);
  duration = (end.tv_sec-start.tv_sec)*1000000u+(end.tv_usec-start.tv_usec);
  printf("pagerank: %f:", ((double)duration)/1000000);
  printf("pr[0]: %u\n", test_vector2[0]);
*/
  return true;

}



bool time_adjlist(uint32_t num_nodes, uint32_t num_edges, int trials) {
  srand(0);
  struct timeval start, end;
  uint32_t duration;
  for (int j = 0; j < trials; j++) {
    gettimeofday(&start, NULL);
    AdjacencyList *al = new AdjacencyList(num_nodes);
    gettimeofday(&end, NULL);
    duration =
        (end.tv_sec - start.tv_sec) * 1000000u + (end.tv_usec - start.tv_usec);
    printf("nodes: %d: edges : %d: ", num_nodes, num_edges);
    printf("created structure in :%f: ", ((double)duration) / 1000000);

    time_structure(al, num_nodes, num_edges);
    delete al;
  }
  return true;
}

bool time_pcsr(uint32_t num_nodes, uint32_t num_edges, int trials) {
  srand(0);
  struct timeval start, end;
  uint32_t duration;
  for (int j = 0; j < trials; j++) {
    gettimeofday(&start, NULL);
    OFM *ofm = new OFM(num_nodes);
    gettimeofday(&end, NULL);
    duration =
        (end.tv_sec - start.tv_sec) * 1000000u + (end.tv_usec - start.tv_usec);
    printf("nodes: %d: edges : %d: ", num_nodes, num_edges);
    printf("created structure in :%f: ", ((double)duration) / 1000000);
    gettimeofday(&start, NULL);

    time_structure(ofm, num_nodes, num_edges);
    delete ofm;
  }
  return true;
}

bool time_csr(uint32_t num_nodes, uint32_t num_edges, int trials) {
  srand(0);
  for (int j = 0; j < trials; j++) {
    OFM *ofm = new OFM(num_nodes);

    for (uint32_t k = 0; k < num_edges; k++) {
      uint32_t src = rand_in_range(num_nodes);
      uint32_t dest = rand_in_range(num_nodes);
      uint32_t val = rand_in_range(MAXVAL) + 1;

      ofm->add_edge_update(src, dest, val);
    }
    CSR csr = CSR(1);
    csr.convert(ofm);
    delete ofm;
    printf("nodes: %d: edges : %d: ", num_nodes, num_edges);
    printf("created structure in :N/A: ");
    time_structure(&csr, num_nodes, 0);

  }
  return true;
}

bool time_adjhashmap(uint32_t num_nodes, uint32_t num_edges, int trials) {
  srand(0);

  struct timeval start, end;
  uint32_t duration;
  for (int j = 0; j < trials; j++) {
    // start = std::clock();
    gettimeofday(&start, NULL);
    AdjacencyHashMap *ahm = new AdjacencyHashMap(num_nodes);
    gettimeofday(&end, NULL);
    // duration = (std::clock() - start) / (double)CLOCKS_PER_SEC;
    duration = (end.tv_sec - start.tv_sec) * 1000000u + (end.tv_usec - start.tv_usec);
    printf("nodes: %d: edges : %d: ", num_nodes, num_edges);
    printf("created structure in :%f: ", ((double)duration) / 1000000);
    gettimeofday(&start, NULL);

    time_structure(ahm, num_nodes, num_edges);
    delete ahm;
  }
  return true;
}
bool time_adjvector(uint32_t num_nodes, uint32_t num_edges, int trials) {
  srand(0);

  struct timeval start, end;
  uint32_t duration;
  for (int j = 0; j < trials; j++) {
    // start = std::clock();
    gettimeofday(&start, NULL);
    AdjacencyVector *av = new AdjacencyVector(num_nodes);
    gettimeofday(&end, NULL);
    duration = (end.tv_sec - start.tv_sec) * 1000000u + (end.tv_usec - start.tv_usec);
    printf("nodes: %d: edges : %d: ", num_nodes, num_edges);
    printf("created structure in :%f: ", ((double)duration) / 1000000);

    time_structure(av, num_nodes, num_edges);
    delete av;
  }
  return true;
}

bool time_structure_real_world_graphs(Graph* g, int graph_num) {
  srand(0);

  struct timeval start, end;
  uint32_t duration;

  
  // add edge update
  std::vector<uint32_t> srcs;
  std::vector<uint32_t> dests;
  std::vector<uint32_t> vals;
  string filename;
  if (graph_num == 0) {
    filename = "graphs/rand-out-soc-Slashdot0811.txt";
  }
  else if (graph_num == 1) {
    filename = "graphs/rand-soc-pokec-relationships.txt";
  }
  else if (graph_num == 2) {
    filename = "graphs/rand-out-soc-LiveJournal1.txt";
  } else {
    printf("bad graph_num\n");
    return false;
  }
  ifstream myfile(filename.c_str());
  string line;
  if (myfile.is_open()) {
    while (getline(myfile, line)) {
      vector<string> elems = split(line, '\t');
      int src = atoi(elems[0].c_str()) - 1;

      while (src >= g->get_n()) {
        g->add_node();
      }
      int dest = atoi(elems[1].c_str()) - 1;

      while (dest >= g->get_n()) {
        g->add_node();
      }
      srcs.push_back(src);
      dests.push_back(dest);
      vals.push_back(rand_in_range(MAXVAL));
    }
    myfile.close();
    // return 0;
  } else {
    printf("file was not opened\n");
  }
  uint32_t num_edges = srcs.size();
  gettimeofday(&start, NULL);
  int i = 0;
  for(; i < num_edges-batch_size; i+=batch_size) {
    g->add_edge_batch_update(&srcs[i], &dests[i], &vals[i], batch_size);
  }
  g->add_edge_batch_update(&srcs[i], &dests[i], &vals[i], num_edges % batch_size);

  uint32_t num_nodes = g->get_n();

  gettimeofday(&end, NULL);
  duration =
            (end.tv_sec - start.tv_sec) * 1000000u + (end.tv_usec - start.tv_usec);
  if (num_edges > 0) {
    printf("add_edge_update :%f:", ((double)duration) / (1000000));
  } else {
    printf("add_edge_update :N/A: ");
  }

    vector<uint32_t> test_vector(num_nodes, 0);
    for (uint32_t i = 0; i < num_nodes; i++) {
      test_vector[i] = rand_in_range(MAXVAL);
    }

  // spvm
    
    gettimeofday(&start, NULL);
    // start = std::clock();
    for (int spvm_iters = 0; spvm_iters < 100; spvm_iters++) {
      test_vector = g->sparse_matrix_vector_multiplication(test_vector);
    }

    gettimeofday(&end, NULL);
    duration = (end.tv_sec-start.tv_sec)*1000000u+(end.tv_usec-start.tv_usec);
    printf("spvm: %f: ", ((double)duration)/1000000);
    printf("spvm[0]: %d: ", test_vector[0]);
    gettimeofday(&start, NULL);
  // bfs
  /*
    int start_node = rand_in_range(num_nodes);
    gettimeofday(&start, NULL);
    for (int bfs_iters = 0; bfs_iters < 100; bfs_iters++) {
      vector<uint32_t> r4 = g->bfs(start_node);
      start_node = r4[0] % num_nodes;
    }
    gettimeofday(&end, NULL);
    duration = (end.tv_sec-start.tv_sec)*1000000u+(end.tv_usec-start.tv_usec);
    printf("bfs in %f,", ((double)duration)/1000000);
    printf("sn = %d,", start_node);
    */
  // pagerank
  vector<uint32_t> test_vector2(num_nodes, 0);
  for (uint32_t i = 0; i < num_nodes; i++) {
    test_vector2[i] = ((uint32_t)rand_in_range(MAXVAL)) / MAXVAL;
  }
  gettimeofday(&start, NULL);
  for (int pr_iters = 0; pr_iters < 100; pr_iters++) {
    vector<uint32_t> test_vector2 = g->pagerank(test_vector2);
  }
  gettimeofday(&end, NULL);
  duration = (end.tv_sec-start.tv_sec)*1000000u+(end.tv_usec-start.tv_usec);
  printf("pagerank: %f:", ((double)duration)/1000000);
  printf("pr[0]: %u\n", test_vector2[0]);
  return true;

}

int main(int argc, char *argv[]) {
  if (argc == 2) {
    if (string(argv[1]) == "-v") {
      if (!verify_pcsr()) {
        return 0;
      } else {
        printf("pcsr verified\n");
      }
      if (!verify_adjacency_list()) {
        return 0;
      } else {
        printf("adjlist verified\n");
      }
     if (!verify_adjacency_vector()) {
        return 0;
      } else {
        printf("adjvec verified\n");
      }
      if (!verify_adjacency_hashmap()) {
        return 0;
      } else {
        printf("ahm verified\n");
      }
      if (!verify_csr()) {
        return 0;
      } else {
        printf("csr verified\n");
      }
      return 0;
    }
  }

  uint32_t starting_size = 2048;
  assert(starting_size >= batch_size);
  if (argc==3) {
    if(string(argv[1]) == "-s") {
      starting_size = atoi(argv[2]);
    }
  }

  int trials = 1;
  uint32_t num_nodes =  100000;
  uint32_t starting_degree = starting_size;
  uint32_t max_degree = 0+1;
  uint32_t num_edges = num_nodes * starting_degree;



  while(num_edges < max_degree * 100000) {
    for (int i = 1; i <= 16; i*=2) {
      char str[2];
      sprintf(str, "%d", i);
      __cilkrts_end_cilk(); 
      __cilkrts_set_param("nworkers", str);
      int workers = __cilkrts_get_nworkers();

      //printf("Adjacency List: workers: %d: ", workers);
      //time_adjlist(num_nodes, num_edges, trials);

      printf("Adjacency Hash Map: workers: %d: ", workers);
      time_adjhashmap(num_nodes, num_edges, trials);
 
/*
      printf("Adjacency Vector: workers: %d: ", workers);
      time_adjvector(num_nodes, num_edges, trials);

   
      printf("CSR: workers: %d: ", workers);
      time_csr(num_nodes, num_edges, trials);


      printf("PCSR: workers: %d: ", workers);
      time_pcsr(num_nodes, num_edges, trials);
*/
    }


    num_edges *= 2;
  }

  //real_world_graphs
  AdjacencyList *list = new AdjacencyList(0);
  OFM *ofm = new OFM(num_nodes);
  AdjacencyHashMap *ahm = new AdjacencyHashMap(num_nodes);
  AdjacencyVector *av = new AdjacencyVector(num_nodes);
  printf("\n");
  for (int i = 1; i < 3; i++) {
    for (int j = 1; j <= 16; j*=2) {
      char str[2];
      sprintf(str, "%d", j);
      __cilkrts_end_cilk();
      __cilkrts_set_param("nworkers", str);
          
      int workers = __cilkrts_get_nworkers();
      printf("Adjacency List: workers: %d: ", workers);
      time_structure_real_world_graphs(list, i);
      printf("Adjacency Hash Map: workers: %d: ", workers);
      time_structure_real_world_graphs(ahm, i);
      printf("Adjacency Vector: workers: %d: ", workers);
      time_structure_real_world_graphs(av, i);
      printf("PCSR: workers: %d: ", workers);
      time_structure_real_world_graphs(ofm, i);
      printf("\n");
    }
  }
}