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 */
normalize(const struct timeabs * start,const struct timeabs * stop,unsigned int num)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
main(int argc,char * argv[])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 }
96