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>
17 /* Nanoseconds per operation */
18 static size_t normalize(const struct timeabs *start,
19 const struct timeabs *stop,
22 return time_to_nsec(time_divide(time_between(*stop, *start), num));
25 int main(int argc, char *argv[])
28 struct timeabs start, stop;
30 ENTRY *words, *misswords;
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);
39 words = tal_arr(w, ENTRY, num);
40 for (i = 0; i < num; i++) {
42 words[i].data = words[i].key;
45 /* Append and prepend last char for miss testing. */
46 misswords = tal_arr(w, ENTRY, num);
47 for (i = 0; i < num; i++) {
50 lastc = w[i][strlen(w[i])-1];
53 misswords[i].key = tal_fmt(misswords, "%c%s%c%c",
54 lastc, w[i], lastc, lastc);
57 printf("#01: Initial insert: ");
60 for (i = 0; i < num; i++)
61 hsearch(words[i], ENTER);
63 printf(" %zu ns\n", normalize(&start, &stop, num));
65 printf("#02: Initial lookup (match): ");
68 for (i = 0; i < num; i++)
69 if (hsearch(words[i], FIND)->data != words[i].data)
72 printf(" %zu ns\n", normalize(&start, &stop, num));
74 printf("#03: Initial lookup (miss): ");
77 for (i = 0; i < num; i++) {
78 if (hsearch(misswords[i], FIND))
82 printf(" %zu ns\n", normalize(&start, &stop, num));
84 /* Lookups in order are very cache-friendly for judy; try random */
85 printf("#04: Initial lookup (random): ");
88 for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
89 if (hsearch(words[i], FIND)->data != words[i].data)
92 printf(" %zu ns\n", normalize(&start, &stop, num));