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/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>
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 timeabs *start,
385 const struct timeabs *stop,
388 return time_to_nsec(time_divide(time_between(*stop, *start), num));
391 int main(int argc, char *argv[])
394 struct timeabs start, stop;
396 char **words, **misswords;
398 words = tal_strsplit(NULL, grab_file(NULL,
399 argv[1] ? argv[1] : "/usr/share/dict/words"), "\n", STR_NO_EMPTY);
401 num = tal_count(words) - 1;
402 printf("%zu words\n", num);
404 /* Append and prepend last char for miss testing. */
405 misswords = tal_arr(words, char *, num);
406 for (i = 0; i < num; i++) {
408 if (strlen(words[i]))
409 lastc = words[i][strlen(words[i])-1];
412 misswords[i] = tal_fmt(misswords, "%c%s%c%c",
413 lastc, words[i], lastc, lastc);
416 printf("#01: Initial insert: ");
419 for (i = 0; i < num; i++)
420 critbit0_insert(&ct, words[i]);
422 printf(" %zu ns\n", normalize(&start, &stop, num));
424 printf("Nodes allocated: %zu (%zu bytes)\n",
425 allocated, allocated * sizeof(critbit0_node));
427 printf("#02: Initial lookup (match): ");
430 for (i = 0; i < num; i++)
431 if (!critbit0_contains(&ct, words[i]))
434 printf(" %zu ns\n", normalize(&start, &stop, num));
436 printf("#03: Initial lookup (miss): ");
439 for (i = 0; i < num; i++) {
440 if (critbit0_contains(&ct, misswords[i]))
444 printf(" %zu ns\n", normalize(&start, &stop, num));
446 /* Lookups in order are very cache-friendly for judy; try random */
447 printf("#04: Initial lookup (random): ");
450 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
451 if (!critbit0_contains(&ct, words[j]))
454 printf(" %zu ns\n", normalize(&start, &stop, num));
456 printf("#05: Initial delete all: ");
459 for (i = 0; i < num; i++)
460 if (!critbit0_delete(&ct, words[i]))
463 printf(" %zu ns\n", normalize(&start, &stop, num));
465 printf("#06: Initial re-inserting: ");
468 for (i = 0; i < num; i++)
469 critbit0_insert(&ct, words[i]);
471 printf(" %zu ns\n", normalize(&start, &stop, num));
473 printf("#07: Deleting first half: ");
476 for (i = 0; i < num; i+=2)
477 if (!critbit0_delete(&ct, words[i]))
480 printf(" %zu ns\n", normalize(&start, &stop, num));
482 printf("#08: Adding (a different) half: ");
486 for (i = 0; i < num; i+=2)
487 critbit0_insert(&ct, misswords[i]);
489 printf(" %zu ns\n", normalize(&start, &stop, num));
491 printf("#09: Lookup after half-change (match): ");
494 for (i = 1; i < num; i+=2)
495 if (!critbit0_contains(&ct, words[i]))
497 for (i = 0; i < num; i+=2) {
498 if (!critbit0_contains(&ct, misswords[i]))
502 printf(" %zu ns\n", normalize(&start, &stop, num));
504 printf("#10: Lookup after half-change (miss): ");
507 for (i = 0; i < num; i+=2)
508 if (critbit0_contains(&ct, words[i]))
510 for (i = 1; i < num; i+=2) {
511 if (critbit0_contains(&ct, misswords[i]))
515 printf(" %zu ns\n", normalize(&start, &stop, num));
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: ");
521 for (j = 0; j < num; j+=2) {
522 if (!critbit0_delete(&ct, misswords[j]))
524 if (critbit0_insert(&ct, words[j]) != 2)
528 printf(" %zu ns\n", normalize(&start, &stop, num));
530 printf("#12: Churn 2: ");
532 for (j = 1; j < num; j+=2) {
533 if (!critbit0_delete(&ct, words[j]))
535 if (critbit0_insert(&ct, misswords[j]) != 2)
539 printf(" %zu ns\n", normalize(&start, &stop, num));
541 printf("#13: Churn 3: ");
543 for (j = 1; j < num; j+=2) {
544 if (!critbit0_delete(&ct, misswords[j]))
546 if (critbit0_insert(&ct, words[j]) != 2)
550 printf(" %zu ns\n", normalize(&start, &stop, num));
552 /* Now it's back to normal... */
553 printf("#14: Post-Churn lookup (match): ");
556 for (i = 0; i < num; i++)
557 if (!critbit0_contains(&ct, words[i]))
560 printf(" %zu ns\n", normalize(&start, &stop, num));
562 printf("#15: Post-Churn lookup (miss): ");
565 for (i = 0; i < num; i++) {
566 if (critbit0_contains(&ct, misswords[i]))
570 printf(" %zu ns\n", normalize(&start, &stop, num));
572 /* Lookups in order are very cache-friendly for judy; try random */
573 printf("#16: Post-Churn lookup (random): ");
576 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
577 if (!critbit0_contains(&ct, words[j]))
580 printf(" %zu ns\n", normalize(&start, &stop, num));