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