1 /* Simple speed tests using original critbit code (modified not to allocate).
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)
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>
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);
46 #define uint32 uint32_t
48 static size_t allocated;
56 #include <sys/types.h>
68 critbit0_contains(critbit0_tree*t,const char*u){
69 const uint8*ubytes= (void*)u;
70 const size_t ulen= strlen(u);
82 critbit0_node*q= (void*)(p-1);
86 if(q->byte<ulen)c= ubytes[q->byte];
87 const int direction= (1+(q->otherbits|c))>>8;
91 p= q->child[direction];
98 return 0==strcmp(u,(const char*)p);
106 int critbit0_insert(critbit0_tree*t,const char*u)
108 const uint8*const ubytes= (void*)u;
109 const size_t ulen= strlen(u);
117 int a= posix_memalign((void**)&x,sizeof(void*),ulen+1);
131 while(1&(intptr_t)p){
132 critbit0_node*q= (void*)(p-1);
136 if(q->byte<ulen)c= ubytes[q->byte];
137 const int direction= (1+(q->otherbits|c))>>8;
141 p= q->child[direction];
153 for(newbyte= 0;newbyte<ulen;++newbyte){
154 if(p[newbyte]!=ubytes[newbyte]){
155 newotherbits= p[newbyte]^ubytes[newbyte];
156 goto different_byte_found;
161 newotherbits= p[newbyte];
162 goto different_byte_found;
166 different_byte_found:
172 while(newotherbits&(newotherbits-1))newotherbits&= newotherbits-1;
175 int newdirection= (1+(newotherbits|c))>>8;
186 critbit0_node*newnode;
187 if(posix_memalign((void**)&newnode,sizeof(void*),sizeof(critbit0_node)))return 0;
191 if(posix_memalign((void**)&x,sizeof(void*),ulen+1)){
195 memcpy(x,ubytes,ulen+1);
199 newnode->byte= newbyte;
200 newnode->otherbits= newotherbits;
201 newnode->child[1-newdirection]= x;
207 void**wherep= &t->root;
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;
215 if(q->byte<ulen)c= ubytes[q->byte];
216 const int direction= (1+(q->otherbits|c))>>8;
217 wherep= q->child+direction;
220 newnode->child[newdirection]= *wherep;
221 *wherep= (void*)(1+(char*)newnode);
234 int critbit0_delete(critbit0_tree*t,const char*u){
235 const uint8*ubytes= (void*)u;
236 const size_t ulen= strlen(u);
238 void**wherep= &t->root;
251 while(1&(intptr_t)p){
255 if(q->byte<ulen)c= ubytes[q->byte];
256 direction= (1+(q->otherbits|c))>>8;
257 wherep= q->child+direction;
265 if(0!=strcmp(u,(const char*)p))return 0;
279 *whereq= q->child[1-direction];
297 critbit0_node*q= (void*)(p-1);
298 traverse(q->child[0]);
299 traverse(q->child[1]);
312 void critbit0_clear(critbit0_tree*t)
314 if(t->root)traverse(t->root);
321 allprefixed_traverse(uint8*top,
322 int(*handle)(const char*,void*),void*arg){
326 critbit0_node*q= (void*)(top-1);
328 for(direction= 0;direction<2;++direction)
329 switch(allprefixed_traverse(q->child[direction],handle,arg)){
341 return handle((const char*)top,arg);/*:27*/
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);
357 while(1&(intptr_t)p){
358 critbit0_node*q= (void*)(p-1);
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;
370 for(i= 0;i<ulen;++i){
371 if(p[i]!=ubytes[i])return 1;
377 return allprefixed_traverse(top,handle,arg);
383 /* Nanoseconds per operation */
384 static size_t normalize(const struct timespec *start,
385 const struct timespec *stop,
388 return time_to_nsec(time_divide(time_sub(*stop, *start), num));
391 int main(int argc, char *argv[])
394 struct timespec start, stop;
396 char **words, **misswords;
398 words = strsplit(NULL, grab_file(NULL,
399 argv[1] ? argv[1] : "/usr/share/dict/words",
402 num = talloc_array_length(words) - 1;
403 printf("%zu words\n", num);
405 /* Append and prepend last char for miss testing. */
406 misswords = talloc_array(words, char *, num);
407 for (i = 0; i < num; i++) {
409 if (strlen(words[i]))
410 lastc = words[i][strlen(words[i])-1];
413 misswords[i] = talloc_asprintf(misswords, "%c%s%c%c",
414 lastc, words[i], lastc, lastc);
417 printf("#01: Initial insert: ");
420 for (i = 0; i < num; i++)
421 critbit0_insert(&ct, words[i]);
423 printf(" %zu ns\n", normalize(&start, &stop, num));
425 printf("Nodes allocated: %zu (%zu bytes)\n",
426 allocated, allocated * sizeof(critbit0_node));
428 printf("#02: Initial lookup (match): ");
431 for (i = 0; i < num; i++)
432 if (!critbit0_contains(&ct, words[i]))
435 printf(" %zu ns\n", normalize(&start, &stop, num));
437 printf("#03: Initial lookup (miss): ");
440 for (i = 0; i < num; i++) {
441 if (critbit0_contains(&ct, misswords[i]))
445 printf(" %zu ns\n", normalize(&start, &stop, num));
447 /* Lookups in order are very cache-friendly for judy; try random */
448 printf("#04: Initial lookup (random): ");
451 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
452 if (!critbit0_contains(&ct, words[j]))
455 printf(" %zu ns\n", normalize(&start, &stop, num));
457 printf("#05: Initial delete all: ");
460 for (i = 0; i < num; i++)
461 if (!critbit0_delete(&ct, words[i]))
464 printf(" %zu ns\n", normalize(&start, &stop, num));
466 printf("#06: Initial re-inserting: ");
469 for (i = 0; i < num; i++)
470 critbit0_insert(&ct, words[i]);
472 printf(" %zu ns\n", normalize(&start, &stop, num));
474 printf("#07: Deleting first half: ");
477 for (i = 0; i < num; i+=2)
478 if (!critbit0_delete(&ct, words[i]))
481 printf(" %zu ns\n", normalize(&start, &stop, num));
483 printf("#08: Adding (a different) half: ");
487 for (i = 0; i < num; i+=2)
488 critbit0_insert(&ct, misswords[i]);
490 printf(" %zu ns\n", normalize(&start, &stop, num));
492 printf("#09: Lookup after half-change (match): ");
495 for (i = 1; i < num; i+=2)
496 if (!critbit0_contains(&ct, words[i]))
498 for (i = 0; i < num; i+=2) {
499 if (!critbit0_contains(&ct, misswords[i]))
503 printf(" %zu ns\n", normalize(&start, &stop, num));
505 printf("#10: Lookup after half-change (miss): ");
508 for (i = 0; i < num; i+=2)
509 if (critbit0_contains(&ct, words[i]))
511 for (i = 1; i < num; i+=2) {
512 if (critbit0_contains(&ct, misswords[i]))
516 printf(" %zu ns\n", normalize(&start, &stop, num));
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: ");
522 for (j = 0; j < num; j+=2) {
523 if (!critbit0_delete(&ct, misswords[j]))
525 if (critbit0_insert(&ct, words[j]) != 2)
529 printf(" %zu ns\n", normalize(&start, &stop, num));
531 printf("#12: Churn 2: ");
533 for (j = 1; j < num; j+=2) {
534 if (!critbit0_delete(&ct, words[j]))
536 if (critbit0_insert(&ct, misswords[j]) != 2)
540 printf(" %zu ns\n", normalize(&start, &stop, num));
542 printf("#13: Churn 3: ");
544 for (j = 1; j < num; j+=2) {
545 if (!critbit0_delete(&ct, misswords[j]))
547 if (critbit0_insert(&ct, words[j]) != 2)
551 printf(" %zu ns\n", normalize(&start, &stop, num));
553 /* Now it's back to normal... */
554 printf("#14: Post-Churn lookup (match): ");
557 for (i = 0; i < num; i++)
558 if (!critbit0_contains(&ct, words[i]))
561 printf(" %zu ns\n", normalize(&start, &stop, num));
563 printf("#15: Post-Churn lookup (miss): ");
566 for (i = 0; i < num; i++) {
567 if (critbit0_contains(&ct, misswords[i]))
571 printf(" %zu ns\n", normalize(&start, &stop, num));
573 /* Lookups in order are very cache-friendly for judy; try random */
574 printf("#16: Post-Churn lookup (random): ");
577 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
578 if (!critbit0_contains(&ct, words[j]))
581 printf(" %zu ns\n", normalize(&start, &stop, num));