00ad2790cd4cc13e7c58d9ea86f4152d47f7d89d
[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, 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         ht = htable_str_new();
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(((struct htable *)ht)->table[0])
86                << ((struct htable *)ht)->bits);
87
88         printf("#02: Initial lookup (match): ");
89         fflush(stdout);
90         start = time_now();
91         for (i = 0; i < num; i++)
92                 if (htable_str_get(ht, words[i]) != words[i])
93                         abort();
94         stop = time_now();
95         printf(" %zu ns\n", normalize(&start, &stop, num));
96
97         printf("#03: Initial lookup (miss): ");
98         fflush(stdout);
99         start = time_now();
100         for (i = 0; i < num; i++) {
101                 if (htable_str_get(ht, misswords[i]))
102                         abort();
103         }
104         stop = time_now();
105         printf(" %zu ns\n", normalize(&start, &stop, num));
106
107         /* Lookups in order are very cache-friendly for judy; try random */
108         printf("#04: Initial lookup (random): ");
109         fflush(stdout);
110         start = time_now();
111         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
112                 if (htable_str_get(ht, words[j]) != words[j])
113                         abort();
114         stop = time_now();
115         printf(" %zu ns\n", normalize(&start, &stop, num));
116
117         hashcount = 0;
118         printf("#05: Initial delete all: ");
119         fflush(stdout);
120         start = time_now();
121         for (i = 0; i < num; i++)
122                 if (!htable_str_del(ht, words[i]))
123                         abort();
124         stop = time_now();
125         printf(" %zu ns\n", normalize(&start, &stop, num));
126
127         printf("#06: Initial re-inserting: ");
128         fflush(stdout);
129         start = time_now();
130         for (i = 0; i < num; i++)
131                 htable_str_add(ht, words[i]);
132         stop = time_now();
133         printf(" %zu ns\n", normalize(&start, &stop, num));
134
135         hashcount = 0;
136         printf("#07: Deleting first half: ");
137         fflush(stdout);
138         start = time_now();
139         for (i = 0; i < num; i+=2)
140                 if (!htable_str_del(ht, words[i]))
141                         abort();
142         stop = time_now();
143         printf(" %zu ns\n", normalize(&start, &stop, num));
144
145         printf("#08: Adding (a different) half: ");
146         fflush(stdout);
147
148         start = time_now();
149         for (i = 0; i < num; i+=2)
150                 htable_str_add(ht, misswords[i]);
151         stop = time_now();
152         printf(" %zu ns\n", normalize(&start, &stop, num));
153
154         printf("#09: Lookup after half-change (match): ");
155         fflush(stdout);
156         start = time_now();
157         for (i = 1; i < num; i+=2)
158                 if (htable_str_get(ht, words[i]) != words[i])
159                         abort();
160         for (i = 0; i < num; i+=2) {
161                 if (htable_str_get(ht, misswords[i]) != misswords[i])
162                         abort();
163         }
164         stop = time_now();
165         printf(" %zu ns\n", normalize(&start, &stop, num));
166
167         printf("#10: Lookup after half-change (miss): ");
168         fflush(stdout);
169         start = time_now();
170         for (i = 0; i < num; i+=2)
171                 if (htable_str_get(ht, words[i]))
172                         abort();
173         for (i = 1; i < num; i+=2) {
174                 if (htable_str_get(ht, misswords[i]))
175                         abort();
176         }
177         stop = time_now();
178         printf(" %zu ns\n", normalize(&start, &stop, num));
179
180         /* Hashtables with delete markers can fill with markers over time.
181          * so do some changes to see how it operates in long-term. */
182         printf("#11: Churn 1: ");
183         start = time_now();
184         for (j = 0; j < num; j+=2) {
185                 if (!htable_str_del(ht, misswords[j]))
186                         abort();
187                 if (!htable_str_add(ht, words[j]))
188                         abort();
189         }
190         stop = time_now();
191         printf(" %zu ns\n", normalize(&start, &stop, num));
192
193         printf("#12: Churn 2: ");
194         start = time_now();
195         for (j = 1; j < num; j+=2) {
196                 if (!htable_str_del(ht, words[j]))
197                         abort();
198                 if (!htable_str_add(ht, misswords[j]))
199                         abort();
200         }
201         stop = time_now();
202         printf(" %zu ns\n", normalize(&start, &stop, num));
203
204         printf("#13: Churn 3: ");
205         start = time_now();
206         for (j = 1; j < num; j+=2) {
207                 if (!htable_str_del(ht, misswords[j]))
208                         abort();
209                 if (!htable_str_add(ht, words[j]))
210                         abort();
211         }
212         stop = time_now();
213         printf(" %zu ns\n", normalize(&start, &stop, num));
214
215         /* Now it's back to normal... */
216         printf("#14: Post-Churn lookup (match): ");
217         fflush(stdout);
218         start = time_now();
219         for (i = 0; i < num; i++)
220                 if (htable_str_get(ht, words[i]) != words[i])
221                         abort();
222         stop = time_now();
223         printf(" %zu ns\n", normalize(&start, &stop, num));
224
225         printf("#15: Post-Churn lookup (miss): ");
226         fflush(stdout);
227         start = time_now();
228         for (i = 0; i < num; i++) {
229                 if (htable_str_get(ht, misswords[i]))
230                         abort();
231         }
232         stop = time_now();
233         printf(" %zu ns\n", normalize(&start, &stop, num));
234
235         /* Lookups in order are very cache-friendly for judy; try random */
236         printf("#16: Post-Churn lookup (random): ");
237         fflush(stdout);
238         start = time_now();
239         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
240                 if (htable_str_get(ht, words[j]) != words[j])
241                         abort();
242         stop = time_now();
243         printf(" %zu ns\n", normalize(&start, &stop, num));
244
245         return 0;
246 }