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 timespec *start,
 385                         const struct timespec *stop,
 386                         unsigned int num)
 387 {
 388         return time_to_nsec(time_divide(time_sub(*stop, *start), num));
 389 }
 390
 391 int main(int argc, char *argv[])
 392 {
 393         size_t i, j, num;
 394         struct timespec start, stop;
 395         critbit0_tree ct;
 396         char **words, **misswords;
 397
 398         words = strsplit(NULL, grab_file(NULL,
 399                                          argv[1] ? argv[1] : "/usr/share/dict/words",
 400                                          NULL), "\n");
 401         ct.root = NULL;
 402         num = talloc_array_length(words) - 1;
 403         printf("%zu words\n", num);
 404
 405         /* Append and prepend last char for miss testing. */
 406         misswords = talloc_array(words, char *, num);
 407         for (i = 0; i < num; i++) {
 408                 char lastc;
 409                 if (strlen(words[i]))
 410                         lastc = words[i][strlen(words[i])-1];
 411                 else
 412                         lastc = 'z';
 413                 misswords[i] = talloc_asprintf(misswords, "%c%s%c%c",
 414                                                lastc, words[i], lastc, lastc);
 415         }
 416
 417         printf("#01: Initial insert: ");
 418         fflush(stdout);
 419         start = time_now();
 420         for (i = 0; i < num; i++)
 421                 critbit0_insert(&ct, words[i]);
 422         stop = time_now();
 423         printf(" %zu ns\n", normalize(&start, &stop, num));
 424
 425         printf("Nodes allocated: %zu (%zu bytes)\n",
 426                allocated, allocated * sizeof(critbit0_node));
 427
 428         printf("#02: Initial lookup (match): ");
 429         fflush(stdout);
 430         start = time_now();
 431         for (i = 0; i < num; i++)
 432                 if (!critbit0_contains(&ct, words[i]))
 433                         abort();
 434         stop = time_now();
 435         printf(" %zu ns\n", normalize(&start, &stop, num));
 436
 437         printf("#03: Initial lookup (miss): ");
 438         fflush(stdout);
 439         start = time_now();
 440         for (i = 0; i < num; i++) {
 441                 if (critbit0_contains(&ct, misswords[i]))
 442                         abort();
 443         }
 444         stop = time_now();
 445         printf(" %zu ns\n", normalize(&start, &stop, num));
 446
 447         /* Lookups in order are very cache-friendly for judy; try random */
 448         printf("#04: Initial lookup (random): ");
 449         fflush(stdout);
 450         start = time_now();
 451         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 452                 if (!critbit0_contains(&ct, words[j]))
 453                         abort();
 454         stop = time_now();
 455         printf(" %zu ns\n", normalize(&start, &stop, num));
 456
 457         printf("#05: Initial delete all: ");
 458         fflush(stdout);
 459         start = time_now();
 460         for (i = 0; i < num; i++)
 461                 if (!critbit0_delete(&ct, words[i]))
 462                         abort();
 463         stop = time_now();
 464         printf(" %zu ns\n", normalize(&start, &stop, num));
 465
 466         printf("#06: Initial re-inserting: ");
 467         fflush(stdout);
 468         start = time_now();
 469         for (i = 0; i < num; i++)
 470                 critbit0_insert(&ct, words[i]);
 471         stop = time_now();
 472         printf(" %zu ns\n", normalize(&start, &stop, num));
 473
 474         printf("#07: Deleting first half: ");
 475         fflush(stdout);
 476         start = time_now();
 477         for (i = 0; i < num; i+=2)
 478                 if (!critbit0_delete(&ct, words[i]))
 479                         abort();
 480         stop = time_now();
 481         printf(" %zu ns\n", normalize(&start, &stop, num));
 482
 483         printf("#08: Adding (a different) half: ");
 484         fflush(stdout);
 485
 486         start = time_now();
 487         for (i = 0; i < num; i+=2)
 488                 critbit0_insert(&ct, misswords[i]);
 489         stop = time_now();
 490         printf(" %zu ns\n", normalize(&start, &stop, num));
 491
 492         printf("#09: Lookup after half-change (match): ");
 493         fflush(stdout);
 494         start = time_now();
 495         for (i = 1; i < num; i+=2)
 496                 if (!critbit0_contains(&ct, words[i]))
 497                         abort();
 498         for (i = 0; i < num; i+=2) {
 499                 if (!critbit0_contains(&ct, misswords[i]))
 500                         abort();
 501         }
 502         stop = time_now();
 503         printf(" %zu ns\n", normalize(&start, &stop, num));
 504
 505         printf("#10: Lookup after half-change (miss): ");
 506         fflush(stdout);
 507         start = time_now();
 508         for (i = 0; i < num; i+=2)
 509                 if (critbit0_contains(&ct, words[i]))
 510                         abort();
 511         for (i = 1; i < num; i+=2) {
 512                 if (critbit0_contains(&ct, misswords[i]))
 513                         abort();
 514         }
 515         stop = time_now();
 516         printf(" %zu ns\n", normalize(&start, &stop, num));
 517
 518         /* Hashtables with delete markers can fill with markers over time.
 519          * so do some changes to see how it operates in long-term. */
 520         printf("#11: Churn 1: ");
 521         start = time_now();
 522         for (j = 0; j < num; j+=2) {
 523                 if (!critbit0_delete(&ct, misswords[j]))
 524                         abort();
 525                 if (critbit0_insert(&ct, words[j]) != 2)
 526                         abort();
 527         }
 528         stop = time_now();
 529         printf(" %zu ns\n", normalize(&start, &stop, num));
 530
 531         printf("#12: Churn 2: ");
 532         start = time_now();
 533         for (j = 1; j < num; j+=2) {
 534                 if (!critbit0_delete(&ct, words[j]))
 535                         abort();
 536                 if (critbit0_insert(&ct, misswords[j]) != 2)
 537                         abort();
 538         }
 539         stop = time_now();
 540         printf(" %zu ns\n", normalize(&start, &stop, num));
 541
 542         printf("#13: Churn 3: ");
 543         start = time_now();
 544         for (j = 1; j < num; j+=2) {
 545                 if (!critbit0_delete(&ct, misswords[j]))
 546                         abort();
 547                 if (critbit0_insert(&ct, words[j]) != 2)
 548                         abort();
 549         }
 550         stop = time_now();
 551         printf(" %zu ns\n", normalize(&start, &stop, num));
 552
 553         /* Now it's back to normal... */
 554         printf("#14: Post-Churn lookup (match): ");
 555         fflush(stdout);
 556         start = time_now();
 557         for (i = 0; i < num; i++)
 558                 if (!critbit0_contains(&ct, words[i]))
 559                         abort();
 560         stop = time_now();
 561         printf(" %zu ns\n", normalize(&start, &stop, num));
 562
 563         printf("#15: Post-Churn lookup (miss): ");
 564         fflush(stdout);
 565         start = time_now();
 566         for (i = 0; i < num; i++) {
 567                 if (critbit0_contains(&ct, misswords[i]))
 568                         abort();
 569         }
 570         stop = time_now();
 571         printf(" %zu ns\n", normalize(&start, &stop, num));
 572
 573         /* Lookups in order are very cache-friendly for judy; try random */
 574         printf("#16: Post-Churn lookup (random): ");
 575         fflush(stdout);
 576         start = time_now();
 577         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 578                 if (!critbit0_contains(&ct, words[j]))
 579                         abort();
 580         stop = time_now();
 581         printf(" %zu ns\n", normalize(&start, &stop, num));
 582
 583         return 0;
 584 }