htable: clean up interface, document htable_type better.
[ccan] / ccan / htable / tools / stringspeed.c
1 /* Simple speed tests for a hash of strings. */
2 #include <ccan/htable/htable_type.h>
3 #include <ccan/htable/htable.c>
4 #include <ccan/str_talloc/str_talloc.h>
5 #include <ccan/grab_file/grab_file.h>
6 #include <ccan/talloc/talloc.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
16 static size_t hashcount;
17
18 static const char *strkey(const char *str)
19 {
20         return str;
21 }
22
23 static size_t hash_str(const char *key)
24 {
25         hashcount++;
26         return hash(key, strlen(key), 0);
27 }
28
29 static bool cmp(const char *obj, const char *key)
30 {
31         return strcmp(obj, key) == 0;
32 }
33
34 HTABLE_DEFINE_TYPE(char, strkey, hash_str, cmp, htable_str);
35
36 /* Nanoseconds per operation */
37 static size_t normalize(const struct timeval *start,
38                         const struct timeval *stop,
39                         unsigned int num)
40 {
41         struct timeval diff;
42
43         timersub(stop, start, &diff);
44
45         /* Floating point is more accurate here. */
46         return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
47                 / num * 1000;
48 }
49
50 int main(int argc, char *argv[])
51 {
52         size_t i, j, num;
53         struct timeval start, stop;
54         struct htable_str ht;
55         char **words, **misswords;
56
57         words = strsplit(NULL, grab_file(NULL,
58                                          argv[1] ? argv[1] : "/usr/share/dict/words",
59                                          NULL), "\n");
60         htable_str_init(&ht);
61         num = talloc_array_length(words) - 1;
62         printf("%zu words\n", num);
63
64         /* Append and prepend last char for miss testing. */
65         misswords = talloc_array(words, char *, num);
66         for (i = 0; i < num; i++) {
67                 char lastc;
68                 if (strlen(words[i]))
69                         lastc = words[i][strlen(words[i])-1];
70                 else
71                         lastc = 'z';
72                 misswords[i] = talloc_asprintf(misswords, "%c%s%c%c",
73                                                lastc, words[i], lastc, lastc);
74         }
75
76         printf("#01: Initial insert: ");
77         fflush(stdout);
78         start = time_now();
79         for (i = 0; i < num; i++)
80                 htable_str_add(&ht, words[i]);
81         stop = time_now();
82         printf(" %zu ns\n", normalize(&start, &stop, num));
83
84         printf("Bytes allocated: %zu\n",
85                sizeof(ht.raw.table[0]) << ht.raw.bits);
86
87         printf("#02: Initial lookup (match): ");
88         fflush(stdout);
89         start = time_now();
90         for (i = 0; i < num; i++)
91                 if (htable_str_get(&ht, words[i]) != words[i])
92                         abort();
93         stop = time_now();
94         printf(" %zu ns\n", normalize(&start, &stop, num));
95
96         printf("#03: Initial lookup (miss): ");
97         fflush(stdout);
98         start = time_now();
99         for (i = 0; i < num; i++) {
100                 if (htable_str_get(&ht, misswords[i]))
101                         abort();
102         }
103         stop = time_now();
104         printf(" %zu ns\n", normalize(&start, &stop, num));
105
106         /* Lookups in order are very cache-friendly for judy; try random */
107         printf("#04: Initial lookup (random): ");
108         fflush(stdout);
109         start = time_now();
110         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
111                 if (htable_str_get(&ht, words[j]) != words[j])
112                         abort();
113         stop = time_now();
114         printf(" %zu ns\n", normalize(&start, &stop, num));
115
116         hashcount = 0;
117         printf("#05: Initial delete all: ");
118         fflush(stdout);
119         start = time_now();
120         for (i = 0; i < num; i++)
121                 if (!htable_str_del(&ht, words[i]))
122                         abort();
123         stop = time_now();
124         printf(" %zu ns\n", normalize(&start, &stop, num));
125
126         printf("#06: Initial re-inserting: ");
127         fflush(stdout);
128         start = time_now();
129         for (i = 0; i < num; i++)
130                 htable_str_add(&ht, words[i]);
131         stop = time_now();
132         printf(" %zu ns\n", normalize(&start, &stop, num));
133
134         hashcount = 0;
135         printf("#07: Deleting first half: ");
136         fflush(stdout);
137         start = time_now();
138         for (i = 0; i < num; i+=2)
139                 if (!htable_str_del(&ht, words[i]))
140                         abort();
141         stop = time_now();
142         printf(" %zu ns\n", normalize(&start, &stop, num));
143
144         printf("#08: Adding (a different) half: ");
145         fflush(stdout);
146
147         start = time_now();
148         for (i = 0; i < num; i+=2)
149                 htable_str_add(&ht, misswords[i]);
150         stop = time_now();
151         printf(" %zu ns\n", normalize(&start, &stop, num));
152
153         printf("#09: Lookup after half-change (match): ");
154         fflush(stdout);
155         start = time_now();
156         for (i = 1; i < num; i+=2)
157                 if (htable_str_get(&ht, words[i]) != words[i])
158                         abort();
159         for (i = 0; i < num; i+=2) {
160                 if (htable_str_get(&ht, misswords[i]) != misswords[i])
161                         abort();
162         }
163         stop = time_now();
164         printf(" %zu ns\n", normalize(&start, &stop, num));
165
166         printf("#10: Lookup after half-change (miss): ");
167         fflush(stdout);
168         start = time_now();
169         for (i = 0; i < num; i+=2)
170                 if (htable_str_get(&ht, words[i]))
171                         abort();
172         for (i = 1; i < num; i+=2) {
173                 if (htable_str_get(&ht, misswords[i]))
174                         abort();
175         }
176         stop = time_now();
177         printf(" %zu ns\n", normalize(&start, &stop, num));
178
179         /* Hashtables with delete markers can fill with markers over time.
180          * so do some changes to see how it operates in long-term. */
181         printf("#11: Churn 1: ");
182         start = time_now();
183         for (j = 0; j < num; j+=2) {
184                 if (!htable_str_del(&ht, misswords[j]))
185                         abort();
186                 if (!htable_str_add(&ht, words[j]))
187                         abort();
188         }
189         stop = time_now();
190         printf(" %zu ns\n", normalize(&start, &stop, num));
191
192         printf("#12: Churn 2: ");
193         start = time_now();
194         for (j = 1; j < num; j+=2) {
195                 if (!htable_str_del(&ht, words[j]))
196                         abort();
197                 if (!htable_str_add(&ht, misswords[j]))
198                         abort();
199         }
200         stop = time_now();
201         printf(" %zu ns\n", normalize(&start, &stop, num));
202
203         printf("#13: Churn 3: ");
204         start = time_now();
205         for (j = 1; j < num; j+=2) {
206                 if (!htable_str_del(&ht, misswords[j]))
207                         abort();
208                 if (!htable_str_add(&ht, words[j]))
209                         abort();
210         }
211         stop = time_now();
212         printf(" %zu ns\n", normalize(&start, &stop, num));
213
214         /* Now it's back to normal... */
215         printf("#14: Post-Churn lookup (match): ");
216         fflush(stdout);
217         start = time_now();
218         for (i = 0; i < num; i++)
219                 if (htable_str_get(&ht, words[i]) != words[i])
220                         abort();
221         stop = time_now();
222         printf(" %zu ns\n", normalize(&start, &stop, num));
223
224         printf("#15: Post-Churn lookup (miss): ");
225         fflush(stdout);
226         start = time_now();
227         for (i = 0; i < num; i++) {
228                 if (htable_str_get(&ht, misswords[i]))
229                         abort();
230         }
231         stop = time_now();
232         printf(" %zu ns\n", normalize(&start, &stop, num));
233
234         /* Lookups in order are very cache-friendly for judy; try random */
235         printf("#16: Post-Churn lookup (random): ");
236         fflush(stdout);
237         start = time_now();
238         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
239                 if (htable_str_get(&ht, words[j]) != words[j])
240                         abort();
241         stop = time_now();
242         printf(" %zu ns\n", normalize(&start, &stop, num));
243
244         return 0;
245 }