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 timeval *start,
385 const struct timeval *stop,
390 timersub(stop, start, &diff);
392 /* Floating point is more accurate here. */
393 return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
397 int main(int argc, char *argv[])
400 struct timeval start, stop;
402 char **words, **misswords;
404 words = strsplit(NULL, grab_file(NULL,
405 argv[1] ? argv[1] : "/usr/share/dict/words",
408 num = talloc_array_length(words) - 1;
409 printf("%zu words\n", num);
411 /* Append and prepend last char for miss testing. */
412 misswords = talloc_array(words, char *, num);
413 for (i = 0; i < num; i++) {
415 if (strlen(words[i]))
416 lastc = words[i][strlen(words[i])-1];
419 misswords[i] = talloc_asprintf(misswords, "%c%s%c%c",
420 lastc, words[i], lastc, lastc);
423 printf("#01: Initial insert: ");
426 for (i = 0; i < num; i++)
427 critbit0_insert(&ct, words[i]);
429 printf(" %zu ns\n", normalize(&start, &stop, num));
431 printf("Nodes allocated: %zu (%zu bytes)\n",
432 allocated, allocated * sizeof(critbit0_node));
434 printf("#02: Initial lookup (match): ");
437 for (i = 0; i < num; i++)
438 if (!critbit0_contains(&ct, words[i]))
441 printf(" %zu ns\n", normalize(&start, &stop, num));
443 printf("#03: Initial lookup (miss): ");
446 for (i = 0; i < num; i++) {
447 if (critbit0_contains(&ct, misswords[i]))
451 printf(" %zu ns\n", normalize(&start, &stop, num));
453 /* Lookups in order are very cache-friendly for judy; try random */
454 printf("#04: Initial lookup (random): ");
457 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
458 if (!critbit0_contains(&ct, words[j]))
461 printf(" %zu ns\n", normalize(&start, &stop, num));
463 printf("#05: Initial delete all: ");
466 for (i = 0; i < num; i++)
467 if (!critbit0_delete(&ct, words[i]))
470 printf(" %zu ns\n", normalize(&start, &stop, num));
472 printf("#06: Initial re-inserting: ");
475 for (i = 0; i < num; i++)
476 critbit0_insert(&ct, words[i]);
478 printf(" %zu ns\n", normalize(&start, &stop, num));
480 printf("#07: Deleting first half: ");
483 for (i = 0; i < num; i+=2)
484 if (!critbit0_delete(&ct, words[i]))
487 printf(" %zu ns\n", normalize(&start, &stop, num));
489 printf("#08: Adding (a different) half: ");
493 for (i = 0; i < num; i+=2)
494 critbit0_insert(&ct, misswords[i]);
496 printf(" %zu ns\n", normalize(&start, &stop, num));
498 printf("#09: Lookup after half-change (match): ");
501 for (i = 1; i < num; i+=2)
502 if (!critbit0_contains(&ct, words[i]))
504 for (i = 0; i < num; i+=2) {
505 if (!critbit0_contains(&ct, misswords[i]))
509 printf(" %zu ns\n", normalize(&start, &stop, num));
511 printf("#10: Lookup after half-change (miss): ");
514 for (i = 0; i < num; i+=2)
515 if (critbit0_contains(&ct, words[i]))
517 for (i = 1; i < num; i+=2) {
518 if (critbit0_contains(&ct, misswords[i]))
522 printf(" %zu ns\n", normalize(&start, &stop, num));
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: ");
528 for (j = 0; j < num; j+=2) {
529 if (!critbit0_delete(&ct, misswords[j]))
531 if (critbit0_insert(&ct, words[j]) != 2)
535 printf(" %zu ns\n", normalize(&start, &stop, num));
537 printf("#12: Churn 2: ");
539 for (j = 1; j < num; j+=2) {
540 if (!critbit0_delete(&ct, words[j]))
542 if (critbit0_insert(&ct, misswords[j]) != 2)
546 printf(" %zu ns\n", normalize(&start, &stop, num));
548 printf("#13: Churn 3: ");
550 for (j = 1; j < num; j+=2) {
551 if (!critbit0_delete(&ct, misswords[j]))
553 if (critbit0_insert(&ct, words[j]) != 2)
557 printf(" %zu ns\n", normalize(&start, &stop, num));
559 /* Now it's back to normal... */
560 printf("#14: Post-Churn lookup (match): ");
563 for (i = 0; i < num; i++)
564 if (!critbit0_contains(&ct, words[i]))
567 printf(" %zu ns\n", normalize(&start, &stop, num));
569 printf("#15: Post-Churn lookup (miss): ");
572 for (i = 0; i < num; i++) {
573 if (critbit0_contains(&ct, misswords[i]))
577 printf(" %zu ns\n", normalize(&start, &stop, num));
579 /* Lookups in order are very cache-friendly for judy; try random */
580 printf("#16: Post-Churn lookup (random): ");
583 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
584 if (!critbit0_contains(&ct, words[j]))
587 printf(" %zu ns\n", normalize(&start, &stop, num));