git.ozlabs.org Git - ccan/blob - ccan/strset/tools/cbspeed.c

   1 /* Simple speed tests using original critbit code (modified not to allocate).
   2  *
   3  * Results on my 32 bit Intel(R) Core(TM) i5 CPU M 560  @ 2.67GHz, gcc 4.5.2:
   4  * Run 100 times: Min-Max(Avg)
   5  #01: Initial insert:   237-257(239)
   6  #02: Initial lookup (match):   180-197(181)
   7  #03: Initial lookup (miss):   171-190(172)
   8  #04: Initial lookup (random):   441-455(446)
   9  #05: Initial delete all:   127-148(128)
  10  #06: Initial re-inserting:   219-298(221)
  11  #07: Deleting first half:   101-109(102)
  12  #08: Adding (a different) half:   159-165(160)
  13  #09: Lookup after half-change (match):   203-216(204)
  14  #10: Lookup after half-change (miss):   217-225(218)
  15  #11: Churn 1:   298-311(300)
  16  #12: Churn 2:   298-318(301)
  17  #13: Churn 3:   301-322(304)
  18  #14: Post-Churn lookup (match):   189-196(190)
  19  #15: Post-Churn lookup (miss):   189-197(191)
  20  #16: Post-Churn lookup (random):   500-531(506)
  21  */
  22 #include <ccan/str_talloc/str_talloc.h>
  23 #include <ccan/grab_file/grab_file.h>
  24 #include <ccan/talloc/talloc.h>
  25 #include <ccan/time/time.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <time.h>
  30 #include <unistd.h>
  31 #include <sys/time.h>
  32
  33 /* CRITBIT source */
  34 typedef struct {
  35   void *root;
  36 } critbit0_tree;
  37
  38 int critbit0_contains(critbit0_tree *t, const char *u);
  39 int critbit0_insert(critbit0_tree *t, const char *u);
  40 int critbit0_delete(critbit0_tree *t, const char *u);
  41 void critbit0_clear(critbit0_tree *t);
  42 int critbit0_allprefixed(critbit0_tree *t, const char *prefix,
  43                          int (*handle) (const char *, void *), void *arg);
  44
  45 #define uint8 uint8_t
  46 #define uint32 uint32_t
  47
  48 static size_t allocated;
  49
  50 /*2:*/
  51
  52 #include <stdint.h>
  53 #include <string.h>
  54 #include <stdlib.h>
  55
  56 #include <sys/types.h>
  57 #include <errno.h>
  58
  59 typedef struct{
  60 void*child[2];
  61 uint32 byte;
  62 uint8 otherbits;
  63 }critbit0_node;
  64
  65 /*:2*//*3:*/
  66
  67 int
  68 critbit0_contains(critbit0_tree*t,const char*u){
  69 const uint8*ubytes= (void*)u;
  70 const size_t ulen= strlen(u);
  71 uint8*p= t->root;
  72
  73 /*4:*/
  74
  75 if(!p)return 0;
  76
  77 /*:4*/
  78
  79 /*5:*/
  80
  81 while(1&(intptr_t)p){
  82 critbit0_node*q= (void*)(p-1);
  83 /*6:*/
  84
  85 uint8 c= 0;
  86 if(q->byte<ulen)c= ubytes[q->byte];
  87 const int direction= (1+(q->otherbits|c))>>8;
  88
  89 /*:6*/
  90
  91 p= q->child[direction];
  92 }
  93
  94 /*:5*/
  95
  96 /*7:*/
  97
  98 return 0==strcmp(u,(const char*)p);
  99
 100 /*:7*/
 101
 102 }
 103
 104 /*:3*//*8:*/
 105
 106 int critbit0_insert(critbit0_tree*t,const char*u)
 107 {
 108 const uint8*const ubytes= (void*)u;
 109 const size_t ulen= strlen(u);
 110 uint8*p= t->root;
 111
 112 /*9:*/
 113
 114 if(!p){
 115 #if 0
 116 char*x;
 117 int a= posix_memalign((void**)&x,sizeof(void*),ulen+1);
 118 if(a)return 0;
 119 memcpy(x,u,ulen+1);
 120 t->root= x;
 121 #else
 122 t->root = (char *)u;
 123 #endif
 124 return 2;
 125 }
 126
 127 /*:9*/
 128
 129 /*5:*/
 130
 131 while(1&(intptr_t)p){
 132 critbit0_node*q= (void*)(p-1);
 133 /*6:*/
 134
 135 uint8 c= 0;
 136 if(q->byte<ulen)c= ubytes[q->byte];
 137 const int direction= (1+(q->otherbits|c))>>8;
 138
 139 /*:6*/
 140
 141 p= q->child[direction];
 142 }
 143
 144 /*:5*/
 145
 146 /*10:*/
 147
 148 /*11:*/
 149
 150 uint32 newbyte;
 151 uint32 newotherbits;
 152
 153 for(newbyte= 0;newbyte<ulen;++newbyte){
 154 if(p[newbyte]!=ubytes[newbyte]){
 155 newotherbits= p[newbyte]^ubytes[newbyte];
 156 goto different_byte_found;
 157 }
 158 }
 159
 160 if(p[newbyte]!=0){
 161 newotherbits= p[newbyte];
 162 goto different_byte_found;
 163 }
 164 return 1;
 165
 166 different_byte_found:
 167
 168 /*:11*/
 169
 170 /*12:*/
 171
 172 while(newotherbits&(newotherbits-1))newotherbits&= newotherbits-1;
 173 newotherbits^= 255;
 174 uint8 c= p[newbyte];
 175 int newdirection= (1+(newotherbits|c))>>8;
 176
 177 /*:12*/
 178
 179
 180 /*:10*/
 181
 182 /*13:*/
 183
 184 /*14:*/
 185
 186 critbit0_node*newnode;
 187 if(posix_memalign((void**)&newnode,sizeof(void*),sizeof(critbit0_node)))return 0;
 188 allocated++;
 189 char*x;
 190 #if 0
 191 if(posix_memalign((void**)&x,sizeof(void*),ulen+1)){
 192 free(newnode);
 193 return 0;
 194 }
 195 memcpy(x,ubytes,ulen+1);
 196 #else
 197 x = (char *)u;
 198 #endif
 199 newnode->byte= newbyte;
 200 newnode->otherbits= newotherbits;
 201 newnode->child[1-newdirection]= x;
 202
 203 /*:14*/
 204
 205 /*15:*/
 206
 207 void**wherep= &t->root;
 208 for(;;){
 209 uint8*p= *wherep;
 210 if(!(1&(intptr_t)p))break;
 211 critbit0_node*q= (void*)(p-1);
 212 if(q->byte> newbyte)break;
 213 if(q->byte==newbyte&&q->otherbits> newotherbits)break;
 214 uint8 c= 0;
 215 if(q->byte<ulen)c= ubytes[q->byte];
 216 const int direction= (1+(q->otherbits|c))>>8;
 217 wherep= q->child+direction;
 218 }
 219
 220 newnode->child[newdirection]= *wherep;
 221 *wherep= (void*)(1+(char*)newnode);
 222
 223 /*:15*/
 224
 225
 226 /*:13*/
 227
 228
 229 return 2;
 230 }
 231
 232 /*:8*//*16:*/
 233
 234 int critbit0_delete(critbit0_tree*t,const char*u){
 235 const uint8*ubytes= (void*)u;
 236 const size_t ulen= strlen(u);
 237 uint8*p= t->root;
 238 void**wherep= &t->root;
 239 void**whereq= 0;
 240 critbit0_node*q= 0;
 241 int direction= 0;
 242
 243 /*17:*/
 244
 245 if(!p)return 0;
 246
 247 /*:17*/
 248
 249 /*18:*/
 250
 251 while(1&(intptr_t)p){
 252 whereq= wherep;
 253 q= (void*)(p-1);
 254 uint8 c= 0;
 255 if(q->byte<ulen)c= ubytes[q->byte];
 256 direction= (1+(q->otherbits|c))>>8;
 257 wherep= q->child+direction;
 258 p= *wherep;
 259 }
 260
 261 /*:18*/
 262
 263 /*19:*/
 264
 265 if(0!=strcmp(u,(const char*)p))return 0;
 266 #if 0
 267 free(p);
 268 #endif
 269
 270 /*:19*/
 271
 272 /*20:*/
 273
 274 if(!whereq){
 275 t->root= 0;
 276 return 1;
 277 }
 278
 279 *whereq= q->child[1-direction];
 280 free(q);
 281 allocated--;
 282 /*:20*/
 283
 284
 285 return 1;
 286 }
 287
 288 /*:16*//*21:*/
 289
 290 static void
 291 traverse(void*top){
 292 /*22:*/
 293
 294 uint8*p= top;
 295
 296 if(1&(intptr_t)p){
 297 critbit0_node*q= (void*)(p-1);
 298 traverse(q->child[0]);
 299 traverse(q->child[1]);
 300 free(q);
 301 allocated--;
 302 }else{
 303 #if 0
 304 free(p);
 305 #endif
 306 }
 307
 308 /*:22*/
 309
 310 }
 311
 312 void critbit0_clear(critbit0_tree*t)
 313 {
 314 if(t->root)traverse(t->root);
 315 t->root= NULL;
 316 }
 317
 318 /*:21*//*23:*/
 319
 320 static int
 321 allprefixed_traverse(uint8*top,
 322 int(*handle)(const char*,void*),void*arg){
 323 /*26:*/
 324
 325 if(1&(intptr_t)top){
 326 critbit0_node*q= (void*)(top-1);
 327 int direction;
 328 for(direction= 0;direction<2;++direction)
 329 switch(allprefixed_traverse(q->child[direction],handle,arg)){
 330 case 1:break;
 331 case 0:return 0;
 332 default:return-1;
 333 }
 334 return 1;
 335 }
 336
 337 /*:26*/
 338
 339 /*27:*/
 340
 341 return handle((const char*)top,arg);/*:27*/
 342
 343 }
 344
 345 int
 346 critbit0_allprefixed(critbit0_tree*t,const char*prefix,
 347 int(*handle)(const char*,void*),void*arg){
 348 const uint8*ubytes= (void*)prefix;
 349 const size_t ulen= strlen(prefix);
 350 uint8*p= t->root;
 351 uint8*top= p;
 352 size_t i;
 353
 354 if(!p)return 1;
 355 /*24:*/
 356
 357 while(1&(intptr_t)p){
 358 critbit0_node*q= (void*)(p-1);
 359 uint8 c= 0;
 360 if(q->byte<ulen)c= ubytes[q->byte];
 361 const int direction= (1+(q->otherbits|c))>>8;
 362 p= q->child[direction];
 363 if(q->byte<ulen)top= p;
 364 }
 365
 366 /*:24*/
 367
 368 /*25:*/
 369
 370 for(i= 0;i<ulen;++i){
 371 if(p[i]!=ubytes[i])return 1;
 372 }
 373
 374 /*:25*/
 375
 376
 377 return allprefixed_traverse(top,handle,arg);
 378 }
 379
 380 /*:23*/
 381 /* end critbit */
 382
 383 /* Nanoseconds per operation */
 384 static size_t normalize(const struct timeval *start,
 385                         const struct timeval *stop,
 386                         unsigned int num)
 387 {
 388         struct timeval diff;
 389
 390         timersub(stop, start, &diff);
 391
 392         /* Floating point is more accurate here. */
 393         return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
 394                 / num * 1000;
 395 }
 396
 397 int main(int argc, char *argv[])
 398 {
 399         size_t i, j, num;
 400         struct timeval start, stop;
 401         critbit0_tree ct;
 402         char **words, **misswords;
 403
 404         words = strsplit(NULL, grab_file(NULL,
 405                                          argv[1] ? argv[1] : "/usr/share/dict/words",
 406                                          NULL), "\n");
 407         ct.root = NULL;
 408         num = talloc_array_length(words) - 1;
 409         printf("%zu words\n", num);
 410
 411         /* Append and prepend last char for miss testing. */
 412         misswords = talloc_array(words, char *, num);
 413         for (i = 0; i < num; i++) {
 414                 char lastc;
 415                 if (strlen(words[i]))
 416                         lastc = words[i][strlen(words[i])-1];
 417                 else
 418                         lastc = 'z';
 419                 misswords[i] = talloc_asprintf(misswords, "%c%s%c%c",
 420                                                lastc, words[i], lastc, lastc);
 421         }
 422
 423         printf("#01: Initial insert: ");
 424         fflush(stdout);
 425         start = time_now();
 426         for (i = 0; i < num; i++)
 427                 critbit0_insert(&ct, words[i]);
 428         stop = time_now();
 429         printf(" %zu ns\n", normalize(&start, &stop, num));
 430
 431         printf("Nodes allocated: %zu (%zu bytes)\n",
 432                allocated, allocated * sizeof(critbit0_node));
 433
 434         printf("#02: Initial lookup (match): ");
 435         fflush(stdout);
 436         start = time_now();
 437         for (i = 0; i < num; i++)
 438                 if (!critbit0_contains(&ct, words[i]))
 439                         abort();
 440         stop = time_now();
 441         printf(" %zu ns\n", normalize(&start, &stop, num));
 442
 443         printf("#03: Initial lookup (miss): ");
 444         fflush(stdout);
 445         start = time_now();
 446         for (i = 0; i < num; i++) {
 447                 if (critbit0_contains(&ct, misswords[i]))
 448                         abort();
 449         }
 450         stop = time_now();
 451         printf(" %zu ns\n", normalize(&start, &stop, num));
 452
 453         /* Lookups in order are very cache-friendly for judy; try random */
 454         printf("#04: Initial lookup (random): ");
 455         fflush(stdout);
 456         start = time_now();
 457         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 458                 if (!critbit0_contains(&ct, words[j]))
 459                         abort();
 460         stop = time_now();
 461         printf(" %zu ns\n", normalize(&start, &stop, num));
 462
 463         printf("#05: Initial delete all: ");
 464         fflush(stdout);
 465         start = time_now();
 466         for (i = 0; i < num; i++)
 467                 if (!critbit0_delete(&ct, words[i]))
 468                         abort();
 469         stop = time_now();
 470         printf(" %zu ns\n", normalize(&start, &stop, num));
 471
 472         printf("#06: Initial re-inserting: ");
 473         fflush(stdout);
 474         start = time_now();
 475         for (i = 0; i < num; i++)
 476                 critbit0_insert(&ct, words[i]);
 477         stop = time_now();
 478         printf(" %zu ns\n", normalize(&start, &stop, num));
 479
 480         printf("#07: Deleting first half: ");
 481         fflush(stdout);
 482         start = time_now();
 483         for (i = 0; i < num; i+=2)
 484                 if (!critbit0_delete(&ct, words[i]))
 485                         abort();
 486         stop = time_now();
 487         printf(" %zu ns\n", normalize(&start, &stop, num));
 488
 489         printf("#08: Adding (a different) half: ");
 490         fflush(stdout);
 491
 492         start = time_now();
 493         for (i = 0; i < num; i+=2)
 494                 critbit0_insert(&ct, misswords[i]);
 495         stop = time_now();
 496         printf(" %zu ns\n", normalize(&start, &stop, num));
 497
 498         printf("#09: Lookup after half-change (match): ");
 499         fflush(stdout);
 500         start = time_now();
 501         for (i = 1; i < num; i+=2)
 502                 if (!critbit0_contains(&ct, words[i]))
 503                         abort();
 504         for (i = 0; i < num; i+=2) {
 505                 if (!critbit0_contains(&ct, misswords[i]))
 506                         abort();
 507         }
 508         stop = time_now();
 509         printf(" %zu ns\n", normalize(&start, &stop, num));
 510
 511         printf("#10: Lookup after half-change (miss): ");
 512         fflush(stdout);
 513         start = time_now();
 514         for (i = 0; i < num; i+=2)
 515                 if (critbit0_contains(&ct, words[i]))
 516                         abort();
 517         for (i = 1; i < num; i+=2) {
 518                 if (critbit0_contains(&ct, misswords[i]))
 519                         abort();
 520         }
 521         stop = time_now();
 522         printf(" %zu ns\n", normalize(&start, &stop, num));
 523
 524         /* Hashtables with delete markers can fill with markers over time.
 525          * so do some changes to see how it operates in long-term. */
 526         printf("#11: Churn 1: ");
 527         start = time_now();
 528         for (j = 0; j < num; j+=2) {
 529                 if (!critbit0_delete(&ct, misswords[j]))
 530                         abort();
 531                 if (critbit0_insert(&ct, words[j]) != 2)
 532                         abort();
 533         }
 534         stop = time_now();
 535         printf(" %zu ns\n", normalize(&start, &stop, num));
 536
 537         printf("#12: Churn 2: ");
 538         start = time_now();
 539         for (j = 1; j < num; j+=2) {
 540                 if (!critbit0_delete(&ct, words[j]))
 541                         abort();
 542                 if (critbit0_insert(&ct, misswords[j]) != 2)
 543                         abort();
 544         }
 545         stop = time_now();
 546         printf(" %zu ns\n", normalize(&start, &stop, num));
 547
 548         printf("#13: Churn 3: ");
 549         start = time_now();
 550         for (j = 1; j < num; j+=2) {
 551                 if (!critbit0_delete(&ct, misswords[j]))
 552                         abort();
 553                 if (critbit0_insert(&ct, words[j]) != 2)
 554                         abort();
 555         }
 556         stop = time_now();
 557         printf(" %zu ns\n", normalize(&start, &stop, num));
 558
 559         /* Now it's back to normal... */
 560         printf("#14: Post-Churn lookup (match): ");
 561         fflush(stdout);
 562         start = time_now();
 563         for (i = 0; i < num; i++)
 564                 if (!critbit0_contains(&ct, words[i]))
 565                         abort();
 566         stop = time_now();
 567         printf(" %zu ns\n", normalize(&start, &stop, num));
 568
 569         printf("#15: Post-Churn lookup (miss): ");
 570         fflush(stdout);
 571         start = time_now();
 572         for (i = 0; i < num; i++) {
 573                 if (critbit0_contains(&ct, misswords[i]))
 574                         abort();
 575         }
 576         stop = time_now();
 577         printf(" %zu ns\n", normalize(&start, &stop, num));
 578
 579         /* Lookups in order are very cache-friendly for judy; try random */
 580         printf("#16: Post-Churn lookup (random): ");
 581         fflush(stdout);
 582         start = time_now();
 583         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 584                 if (!critbit0_contains(&ct, words[j]))
 585                         abort();
 586         stop = time_now();
 587         printf(" %zu ns\n", normalize(&start, &stop, num));
 588
 589         return 0;
 590 }