timeSXSI.cpp

   1 #include "XMLTree.h"
   2 #include "Utils.h"
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <sys/time.h>
   6 #include <time.h>
   7 #include <sys/types.h>
   8 #include <sys/stat.h>
   9 #include <errno.h>
  10 #include <strings.h>
  11 #include <fcntl.h>
  12 #include <malloc.h>
  13 #include "timings.h"
  14
  15
  16 using std::cout;
  17 using std::string;
  18 using std::left;
  19 using std::right;
  20 using std::cerr;
  21
  22
  23 #define NUM_PATHS 10000
  24 #define RANDOM(m) ((unsigned long int) (random() % (m)))
  25
  26 #define OUTPUT_LINE() (std::cerr << "------------------------------------\n\n")
  27 #define SRX_MAGIC_STRING "SXSI_INDEX\n"
  28 #define SRX_VERSION "2\n"
  29 #define READ_UCHAR(pchar,file) do {                     \
  30   if (fread((pchar),sizeof(char),1,(file)) == 0) {      \
  31   std::cerr << "Error: Invalid .srx file\n";            \
  32   return NULL;                                          \
  33   };                                                    \
  34   } while(0)                                            \
  35
  36
  37 extern "C" {
  38   typedef void ** tree_node;
  39
  40 #define SIZE(v)  (((unsigned long) ((v)[0])) >> 1)
  41 #define ISBINARY(v) (((unsigned long) ((v)[0])) & 1)
  42 #define CHILDR(v,i) (((tree_node)(v))[(i)+1])
  43 #define CHILD(v,i) ((tree_node) (((tree_node)(v))[(i)+1]))
  44
  45   static tree_node create_node(long size,int binary){
  46     tree_node node = (tree_node) malloc(sizeof(void*) * (size+1));
  47     if (node) {
  48       binary = binary & 1;
  49       node[0] = (void *) (size << 1 | binary);
  50       node[1] = NULL;
  51       node[2] = NULL;
  52     };
  53     return node;
  54   }
  55
  56   tree_node create_naive(XMLTree *tree, treeNode node, int prealloc){
  57     if (node == NULLT)
  58       return NULL;
  59     else {
  60       tree_node self;
  61       if (prealloc)
  62         self = create_node(2,1);
  63
  64       tree_node first = create_naive(tree,tree->FirstChild(node),prealloc);
  65       tree_node next = create_naive(tree,tree->NextSibling(node),prealloc);
  66       if (!prealloc)
  67         self = create_node(2,1);
  68       self[0] = (void *) (tree->NumChildren(node) << 1 | 1);
  69       self[1] = first;
  70       self[2] = next;
  71
  72       return self;
  73     };
  74   }
  75
  76   tree_node create_with_child_array(XMLTree *tree, treeNode node){
  77     if (tree==NULL)
  78       return NULL;
  79     else {
  80       long size = (long) tree->NumChildren(node);
  81       tree_node self = create_node(size,0);
  82       treeNode child = tree->FirstChild(node);
  83       for(int i = 0; i < size; i++){
  84         CHILDR(self,i) = create_with_child_array(tree,child);
  85         child = tree->NextSibling(child);
  86       };
  87       return self;
  88     };
  89
  90   }
  91
  92   static unsigned long my_malloc_idx;
  93
  94   tree_node my_malloc_create_node(tree_node pool) {
  95     tree_node ret;
  96     ret = &pool[my_malloc_idx * 3];
  97     my_malloc_idx++;
  98     return ret;
  99   }
 100
 101   tree_node create_perfect_rec(XMLTree *tree, treeNode node, tree_node pool ,int prealloc ) {
 102     if (node == NULLT)
 103       return NULL;
 104     else {
 105       tree_node self;
 106       if (prealloc)
 107         self = my_malloc_create_node(pool);
 108
 109       tree_node first = create_naive(tree,tree->FirstChild(node),prealloc);
 110       tree_node next = create_naive(tree,tree->NextSibling(node),prealloc);
 111       if (!prealloc)
 112         self = my_malloc_create_node(pool);
 113       self[0] = (void *) (tree->NumChildren(node) << 1 | 1);
 114       self[1] = first;
 115       self[2] = next;
 116
 117       return self;
 118     };
 119
 120   }
 121
 122   tree_node create_perfect(XMLTree *tree, int prealloc){
 123     tree_node v = (tree_node) malloc(sizeof(void*)*3 * tree->Size());
 124     my_malloc_idx = 0;
 125     if (v)
 126       create_perfect_rec(tree,0,v,prealloc);
 127
 128     return v;
 129
 130   }
 131
 132   void unranked_preorder(tree_node node){
 133     if (node == NULL)
 134       return;
 135     for(unsigned long i = 0; i < SIZE(node); i++)
 136       unranked_preorder(CHILD(node,i));
 137   };
 138
 139   void binary_preorder(tree_node node){
 140     if (node == NULL)
 141       return;
 142
 143     binary_preorder( (tree_node) (node[1]));
 144     binary_preorder( (tree_node) (node[2]));
 145   };
 146
 147   void nsfs_order(tree_node node){
 148     if (node == NULL)
 149       return;
 150
 151     binary_preorder( (tree_node) (node[2]));
 152     binary_preorder( (tree_node) (node[1]));
 153   };
 154
 155
 156
 157   void pre_order(tree_node node){
 158     if (node == NULL)
 159       return;
 160     if (ISBINARY(node))
 161       binary_preorder(node);
 162     else
 163       unranked_preorder(node);
 164     return;
 165   }
 166
 167
 168   tree_node binary_nth_child (tree_node node, unsigned long n){
 169     if (n >= SIZE(node))
 170       return NULL;
 171
 172     tree_node child = CHILD(node,0);
 173     for(unsigned long i = 0; i < n; i ++)
 174       child=CHILD(child,1);
 175     return child;
 176
 177   }
 178
 179
 180   void binary_random_path(tree_node node){
 181     if (node == NULL || SIZE(node) == 0)
 182       return;
 183     binary_random_path(binary_nth_child(node,RANDOM(SIZE(node))));
 184   }
 185
 186   unsigned long crc = 0;
 187
 188   void unranked_random_path(tree_node node){
 189     if (node == NULL || SIZE(node) == 0)
 190       return;
 191     unsigned long n = RANDOM(SIZE(node));
 192     crc+=n;
 193     unranked_random_path(CHILD(node,n));
 194   }
 195
 196   void random_path(tree_node node){
 197     if (ISBINARY(node))
 198       binary_random_path(node);
 199     else
 200       unranked_random_path(node);
 201
 202   }
 203
 204   void delete_tree_node(tree_node node){
 205     if (node) {
 206       if (ISBINARY(node)) {
 207         delete_tree_node((tree_node) (node[1]));
 208         delete_tree_node((tree_node) (node[2]));
 209       }
 210       else
 211         for(unsigned long i = 0; i < SIZE(node); i++)
 212           delete_tree_node(CHILD(node,i));
 213
 214       free(node);
 215     };
 216   }
 217
 218 }
 219
 220 void xml_tree_preorder(XMLTree* tree, treeNode node){
 221   if (node == NULLT)
 222     return;
 223
 224   xml_tree_preorder(tree,tree->FirstChild(node));
 225   xml_tree_preorder(tree,tree->NextSibling(node));
 226
 227 }
 228 void xml_tree_unranked_preorder(XMLTree* tree,treeNode node){
 229   if (node == NULLT|| tree->IsLeaf(node))
 230     return;
 231
 232   for(int i = 1; i <= tree->NumChildren(node); i++)
 233     xml_tree_unranked_preorder(tree,tree->Child(node,i));
 234
 235 }
 236
 237 void xml_tree_nsfc(XMLTree* tree, treeNode node){
 238   if (node == NULLT)
 239     return;
 240
 241   xml_tree_preorder(tree,tree->NextSibling(node));
 242   xml_tree_preorder(tree,tree->FirstChild(node));
 243
 244
 245 }
 246
 247
 248 void xml_tree_time_siblings(XMLTree* tree){
 249   treeNode first = tree->FirstChild(0);
 250   unsigned long children = tree->NumChildren(first);
 251   unsigned long print = children / 100;
 252   treeNode child;
 253   double max_time = 0;
 254   double max_i = 0;
 255   double time = 0;
 256   std::cerr << children << " children\n";
 257   std::cerr << "Timings:\n";
 258   for(unsigned long i = 1; i<= children;i++){
 259     STARTTIMER();
 260     for(int j = 0; j < 5; j++)
 261       child = tree->Child(first,i);
 262     STOPTIMER(Parsing);
 263     time = tParsing / 5.0;
 264     if (time >= max_time){
 265       max_time = time;
 266       max_i = i;
 267     };
 268   };
 269   std::cerr << "Peak for node " << max_i  << " : " << time << "\n";
 270   return;
 271
 272 }
 273
 274
 275 void xml_tree_lcps(XMLTree * tree, treeNode node){
 276   if (node == NULLT)
 277     return;
 278
 279   xml_tree_lcps(tree,tree->LastChild(node));
 280   xml_tree_lcps(tree,tree->PrevSibling(node));
 281 }
 282
 283 void xml_tree_random_path(XMLTree *tree, treeNode node){
 284   if (node == NULLT|| tree->IsLeaf(node))
 285     return;
 286   unsigned long n = (unsigned long) RANDOM(tree->NumChildren(node));
 287   crc+=n;
 288   xml_tree_random_path(tree,tree->Child(node,1+n));
 289 }
 290
 291
 292 XMLTree* load_srx(const char* file){
 293
 294   char buffer[1024];
 295   char * read_;
 296   int fd = open(file,O_RDONLY);
 297   FILE* fp = fdopen(fd, "r");
 298   unsigned int u32 = 0;
 299   unsigned char cbuff;
 300   XMLTree* tree;
 301
 302   if (fp == NULL) {
 303     std::cerr << "Error: " << strerror(errno) << "\n";
 304     return NULL;
 305   };
 306
 307   read_ = fgets(buffer,1023, fp);
 308
 309   if (read_ == NULL || (strncmp(buffer,SRX_MAGIC_STRING,1023) != 0)){
 310     std::cerr << "Error: Invalid .srx file\n";
 311     return NULL;
 312   };
 313
 314   read_ = fgets(buffer,1023,fp);
 315
 316   if (read_ == NULL || (strncmp(buffer,SRX_VERSION,1023) != 0)){
 317     std::cerr << "Error: Invalid .srx file\n";
 318     return NULL;
 319   };
 320
 321   //OCaml marshaled data structure
 322   //Skip the first 4 bytes = unsigned int 32
 323   READ_UCHAR(&cbuff,fp);
 324   READ_UCHAR(&cbuff,fp);
 325   READ_UCHAR(&cbuff,fp);
 326   READ_UCHAR(&cbuff,fp);
 327
 328   READ_UCHAR(&cbuff,fp);
 329   u32 = cbuff << 24;
 330   READ_UCHAR(&cbuff,fp);
 331   u32 += cbuff << 16;
 332   READ_UCHAR(&cbuff,fp);
 333   u32 += cbuff << 8;
 334   READ_UCHAR(&cbuff,fp);
 335   u32 += cbuff;
 336   // u32 is the data size, we need now to skip (data_size + 20) - (4  * 2) bytes
 337   // 20 is the header_size defined in marshal.ml
 338   if (fseek(fp,u32+20-8, SEEK_CUR) == -1){
 339     std::cerr << "Error: " << strerror(errno) << "\n";
 340     return NULL;
 341   };
 342
 343   // Now we point to the correct area in the file
 344   // We make sure that the fd is at the correct position and call XMLTree::Load
 345   if (lseek(fd,ftell(fp),SEEK_SET) == -1){
 346     std::cerr << "Error: " << strerror(errno) << "\n";
 347     return NULL;
 348   };
 349   //Sampling factor is ignored
 350   tree = XMLTree::Load(fd,true,64);
 351   fclose(fp); //also closes fd!
 352   return tree;
 353
 354 }
 355
 356 int main(int argc,char ** argv ){
 357   XMLTree *tree;
 358   tree_node naive;
 359   if (argc != 2) {
 360     std::cerr << "Usage: " << argv[0] << " file.srx\n";
 361     exit (1);
 362   };
 363
 364   STARTTIMER();
 365   tree = load_srx(argv[1]);
 366   STOPTIMER(Loading);
 367   PRINTTIME("Loading SRX file from disk",Loading);
 368
 369   OUTPUT_LINE();
 370   /*
 371   // Naive pointer structure, allocated in post order
 372   STARTTIMER();
 373   naive = create_naive(tree,0,1);
 374   STOPTIMER(Building);
 375   PRINTTIME("Building pre-order allocated binary structure",Building);
 376
 377   STARTTIMER();
 378   pre_order(naive);
 379   STOPTIMER(Parsing);
 380   PRINTTIME("Preoder traversal",Parsing);
 381
 382   STARTTIMER();
 383   nsfs_order(naive);
 384   STOPTIMER(Parsing);
 385   PRINTTIME("NextSibling/FirstChild",Parsing);
 386
 387   srandom(1);
 388   STARTTIMER();
 389   for(int i = 0; i < NUM_PATHS; i++)
 390     random_path(naive);
 391
 392   STOPTIMER(Parsing);
 393   PRINTTIME("10000 random paths",Parsing);
 394
 395   STARTTIMER();
 396   delete_tree_node(naive);
 397   STOPTIMER(Parsing);
 398   PRINTTIME("Freeing structure",Parsing);
 399
 400   OUTPUT_LINE();
 401
 402   // Naive pointer structure, allocated in pre-order
 403   STARTTIMER();
 404   naive = create_naive(tree,0,0);
 405   STOPTIMER(Building);
 406   PRINTTIME("Building post-order allocated binary pointer structure",Building);
 407   STARTTIMER();
 408   pre_order(naive);
 409   STOPTIMER(Parsing);
 410   PRINTTIME("Preoder traversal",Parsing);
 411
 412   STARTTIMER();
 413   nsfs_order(naive);
 414   STOPTIMER(Parsing);
 415   PRINTTIME("NextSibling/FirstChild",Parsing);
 416
 417   srandom(1);
 418   STARTTIMER();
 419   for(int i = 0; i < NUM_PATHS; i++)
 420     random_path(naive);
 421
 422   STOPTIMER(Parsing);
 423   PRINTTIME("10000 random paths",Parsing);
 424
 425
 426   STARTTIMER();
 427   delete_tree_node(naive);
 428   STOPTIMER(Parsing);
 429   PRINTTIME("Freeing structure",Parsing);
 430
 431   OUTPUT_LINE();
 432
 433
 434
 435   STARTTIMER();
 436   naive = create_with_child_array(tree,0);
 437   STOPTIMER(Building);
 438   PRINTTIME("Building child array structure",Building);
 439   STARTTIMER();
 440   pre_order(naive);
 441   STOPTIMER(Parsing);
 442   PRINTTIME("Preoder traversal",Parsing);
 443
 444   srandom(1);
 445   STARTTIMER();
 446   for(int i = 0; i < NUM_PATHS; i++)
 447     random_path(naive);
 448
 449   STOPTIMER(Parsing);
 450   PRINTTIME("10000 random paths",Parsing);
 451
 452   std::cerr << "crc = " << crc << "\n";
 453   STARTTIMER();
 454   delete_tree_node(naive);
 455   STOPTIMER(Parsing);
 456   PRINTTIME("Freeing structure",Parsing);
 457
 458   OUTPUT_LINE();
 459
 460
 461   // Naive pointer structure, allocated in pre-order
 462   STARTTIMER();
 463   naive = create_perfect(tree,1);
 464   STOPTIMER(Building);
 465   PRINTTIME("Building pre-order pre-allocated contiguous binary structure",Building);
 466   STARTTIMER();
 467   pre_order(naive);
 468   STOPTIMER(Parsing);
 469   PRINTTIME("Preoder traversal",Parsing);
 470
 471   STARTTIMER();
 472   nsfs_order(naive);
 473   STOPTIMER(Parsing);
 474   PRINTTIME("NextSibling/FirstChild",Parsing);
 475
 476   srandom(1);
 477   STARTTIMER();
 478   for(int i = 0; i < NUM_PATHS; i++)
 479     random_path(naive);
 480
 481   STOPTIMER(Parsing);
 482   PRINTTIME("10000 random paths",Parsing);
 483
 484   STARTTIMER();
 485   free(naive);
 486   STOPTIMER(Parsing);
 487   PRINTTIME("Freeing structure",Parsing);
 488
 489   OUTPUT_LINE();
 490
 491   // Naive pointer structure, allocated in pre-order
 492   STARTTIMER();
 493   naive = create_perfect(tree,0);
 494   STOPTIMER(Building);
 495   PRINTTIME("Building post-order pre-allocated contiguous binary structure",Building);
 496   STARTTIMER();
 497   pre_order(naive);
 498   STOPTIMER(Parsing);
 499   PRINTTIME("Preoder traversal",Parsing);
 500
 501   STARTTIMER();
 502   nsfs_order(naive);
 503   STOPTIMER(Parsing);
 504   PRINTTIME("NextSibling/FirstChild",Parsing);
 505
 506   srandom(1);
 507   STARTTIMER();
 508   for(int i = 0; i < NUM_PATHS; i++)
 509     random_path(naive);
 510
 511   STOPTIMER(Parsing);
 512   PRINTTIME("10000 random paths",Parsing);
 513   std::cerr << "crc = " << crc << "\n";
 514   STARTTIMER();
 515   free(naive);
 516   STOPTIMER(Parsing);
 517   PRINTTIME("Freeing structure",Parsing);
 518
 519   OUTPUT_LINE();
 520
 521   // XMLTree structure
 522   std::cerr << "Timing XMLTree structure\n";
 523   STARTTIMER();
 524
 525   xml_tree_preorder(tree,0);
 526   STOPTIMER(Parsing);
 527   PRINTTIME("Preoder traversal",Parsing);
 528
 529   STARTTIMER();
 530   xml_tree_nsfc(tree,0);
 531   STOPTIMER(Parsing);
 532   PRINTTIME("NextSibling/FirstChild",Parsing);
 533
 534   STARTTIMER();
 535   xml_tree_unranked_preorder(tree,0);
 536   STOPTIMER(Parsing);
 537   PRINTTIME("Unranked pre-order",Parsing);
 538
 539   srandom(1);
 540   STARTTIMER();
 541   crc = 0;
 542   for(int i = 0; i < NUM_PATHS; i++)
 543     xml_tree_random_path(tree,0);
 544
 545   STOPTIMER(Parsing);
 546   PRINTTIME("10000 random paths",Parsing);
 547   std::cerr << "crc = " << crc << "\n";
 548   OUTPUT_LINE();
 549   */
 550   xml_tree_time_siblings(tree);
 551
 552
 553   exit(0);
 554 };
 555