hsearchspeed.c (2410B)
1 /* Simple speed tests for a hash of strings using hsearch */ 2 #include <ccan/htable/htable_type.h> 3 #include <ccan/htable/htable.c> 4 #include <ccan/tal/str/str.h> 5 #include <ccan/tal/grab_file/grab_file.h> 6 #include <ccan/tal/tal.h> 7 #include <ccan/hash/hash.h> 8 #include <ccan/time/time.h> 9 #include <stdio.h> 10 #include <stdlib.h> 11 #include <string.h> 12 #include <time.h> 13 #include <unistd.h> 14 #include <sys/time.h> 15 #include <search.h> 16 17 /* Nanoseconds per operation */ 18 static size_t normalize(const struct timeabs *start, 19 const struct timeabs *stop, 20 unsigned int num) 21 { 22 return time_to_nsec(time_divide(time_between(*stop, *start), num)); 23 } 24 25 int main(int argc, char *argv[]) 26 { 27 size_t i, j, num; 28 struct timeabs start, stop; 29 char **w; 30 ENTRY *words, *misswords; 31 32 w = tal_strsplit(NULL, grab_file(NULL, 33 argv[1] ? argv[1] : "/usr/share/dict/words"), "\n", STR_NO_EMPTY); 34 num = tal_count(w) - 1; 35 printf("%zu words\n", num); 36 37 hcreate(num+num/3); 38 39 words = tal_arr(w, ENTRY, num); 40 for (i = 0; i < num; i++) { 41 words[i].key = w[i]; 42 words[i].data = words[i].key; 43 } 44 45 /* Append and prepend last char for miss testing. */ 46 misswords = tal_arr(w, ENTRY, num); 47 for (i = 0; i < num; i++) { 48 char lastc; 49 if (strlen(w[i])) 50 lastc = w[i][strlen(w[i])-1]; 51 else 52 lastc = 'z'; 53 misswords[i].key = tal_fmt(misswords, "%c%s%c%c", 54 lastc, w[i], lastc, lastc); 55 } 56 57 printf("#01: Initial insert: "); 58 fflush(stdout); 59 start = time_now(); 60 for (i = 0; i < num; i++) 61 hsearch(words[i], ENTER); 62 stop = time_now(); 63 printf(" %zu ns\n", normalize(&start, &stop, num)); 64 65 printf("#02: Initial lookup (match): "); 66 fflush(stdout); 67 start = time_now(); 68 for (i = 0; i < num; i++) 69 if (hsearch(words[i], FIND)->data != words[i].data) 70 abort(); 71 stop = time_now(); 72 printf(" %zu ns\n", normalize(&start, &stop, num)); 73 74 printf("#03: Initial lookup (miss): "); 75 fflush(stdout); 76 start = time_now(); 77 for (i = 0; i < num; i++) { 78 if (hsearch(misswords[i], FIND)) 79 abort(); 80 } 81 stop = time_now(); 82 printf(" %zu ns\n", normalize(&start, &stop, num)); 83 84 /* Lookups in order are very cache-friendly for judy; try random */ 85 printf("#04: Initial lookup (random): "); 86 fflush(stdout); 87 start = time_now(); 88 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) 89 if (hsearch(words[i], FIND)->data != words[i].data) 90 abort(); 91 stop = time_now(); 92 printf(" %zu ns\n", normalize(&start, &stop, num)); 93 94 return 0; 95 }