htable: speed benchmark
[ccan] / ccan / htable / tools / speed.c
1 /* Simple speed tests for hashtables. */
2 #include <ccan/htable/htable_type.h>
3 #include <ccan/htable/htable.c>
4 #include <ccan/hash/hash.h>
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <time.h>
8 #include <unistd.h>
9 #include <sys/time.h>
10
11 static size_t hashcount;
12 struct object {
13         /* The key. */
14         unsigned int key;
15
16         /* Some contents. Doubles as consistency check. */
17         struct object *self;
18 };
19
20 static const unsigned int *objkey(const struct object *obj)
21 {
22         return &obj->key;
23 }
24
25 static size_t hash_obj(const unsigned int *key)
26 {
27         hashcount++;
28         return hashl(key, 1, 0);
29 }
30
31 static bool cmp(const unsigned int *key1, const unsigned int *key2)
32 {
33         return *key1 == *key2;
34 }
35
36 HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, obj);
37
38 static unsigned int popcount(unsigned long val)
39 {
40 #if HAVE_BUILTIN_POPCOUNTL
41         return __builtin_popcountl(val);
42 #else
43         if (sizeof(long) == sizeof(u64)) {
44                 u64 v = val;
45                 v = (v & 0x5555555555555555ULL)
46                         + ((v >> 1) & 0x5555555555555555ULL);
47                 v = (v & 0x3333333333333333ULL)
48                         + ((v >> 1) & 0x3333333333333333ULL);
49                 v = (v & 0x0F0F0F0F0F0F0F0FULL)
50                         + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL);
51                 v = (v & 0x00FF00FF00FF00FFULL)
52                         + ((v >> 1) & 0x00FF00FF00FF00FFULL);
53                 v = (v & 0x0000FFFF0000FFFFULL)
54                         + ((v >> 1) & 0x0000FFFF0000FFFFULL);
55                 v = (v & 0x00000000FFFFFFFFULL)
56                         + ((v >> 1) & 0x00000000FFFFFFFFULL);
57                 return v;
58         }
59         val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL);
60         val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL);
61         val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL);
62         val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL);
63         val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL);
64         return val;
65 #endif
66 }
67
68 static size_t perfect(const struct htable *ht)
69 {
70         size_t i, placed_perfect = 0;
71
72         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
73                 if (!entry_is_valid(ht->table[i]))
74                         continue;
75                 if (hash_bucket(ht, ht->rehash(get_raw_ptr(ht, ht->table[i]),
76                                                ht->priv)) == i)
77                         placed_perfect++;
78         }
79         return placed_perfect;
80 }
81
82 static size_t count_deleted(const struct htable *ht)
83 {
84         size_t i, delete_markers = 0;
85
86         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
87                 if (ht->table[i] == HTABLE_DELETED)
88                         delete_markers++;
89         }
90         return delete_markers;
91 }
92
93 /* Nanoseconds per operation */
94 static size_t normalize(const struct timeval *start,
95                         const struct timeval *stop,
96                         unsigned int num)
97 {
98         struct timeval diff;
99
100         timersub(stop, start, &diff);
101
102         /* Floating point is more accurate here. */
103         return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
104                 / num * 1000;
105 }
106
107 static size_t worst_run(struct htable *ht, size_t *deleted)
108 {
109         size_t longest = 0, len = 0, this_del = 0, i;
110
111         *deleted = 0;
112         /* This doesn't take into account end-wrap, but gives an idea. */
113         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
114                 if (ht->table[i]) {
115                         len++;
116                         if (ht->table[i] == HTABLE_DELETED)
117                                 this_del++;
118                 } else {
119                         if (len > longest) {
120                                 longest = len;
121                                 *deleted = this_del;
122                         }
123                         len = 0;
124                         this_del = 0;
125                 }
126         }
127         return longest;
128 }
129
130 int main(int argc, char *argv[])
131 {
132         struct object *objs;
133         size_t i, j, num, deleted;
134         struct timeval start, stop;
135         struct htable_obj *ht;
136         struct htable *htr;
137         bool make_dumb = false;
138
139         if (argv[1] && strcmp(argv[1], "--dumb") == 0) {
140                 argv++;
141                 make_dumb = true;
142         }
143         num = argv[1] ? atoi(argv[1]) : 1000000;
144         objs = calloc(num, sizeof(objs[0]));
145
146         for (i = 0; i < num; i++) {
147                 objs[i].key = i;
148                 objs[i].self = &objs[i];
149         }
150
151         ht = htable_obj_new();
152         htr = (void *)ht;
153
154         printf("Initial insert: ");
155         fflush(stdout);
156         gettimeofday(&start, NULL);
157         for (i = 0; i < num; i++)
158                 htable_obj_add(ht, objs[i].self);
159         gettimeofday(&stop, NULL);
160         printf(" %zu ns\n", normalize(&start, &stop, num));
161         printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
162                1U << htr->bits, popcount(htr->common_mask),
163                perfect(htr) * 100.0 / htr->elems);
164
165         if (make_dumb) {
166                 /* Screw with mask, to hobble us. */
167                 update_common(htr, (void *)~htr->common_bits);
168                 printf("Details: DUMB MODE: mask bits %u\n",
169                        popcount(htr->common_mask));
170         }
171
172         printf("Initial lookup (match): ");
173         fflush(stdout);
174         gettimeofday(&start, NULL);
175         for (i = 0; i < num; i++)
176                 if (htable_obj_get(ht, &i)->self != objs[i].self)
177                         abort();
178         gettimeofday(&stop, NULL);
179         printf(" %zu ns\n", normalize(&start, &stop, num));
180
181         printf("Initial lookup (miss): ");
182         fflush(stdout);
183         gettimeofday(&start, NULL);
184         for (i = 0; i < num; i++) {
185                 unsigned int n = i + num;
186                 if (htable_obj_get(ht, &n))
187                         abort();
188         }
189         gettimeofday(&stop, NULL);
190         printf(" %zu ns\n", normalize(&start, &stop, num));
191
192         /* Lookups in order are very cache-friendly for judy; try random */
193         printf("Initial lookup (random): ");
194         fflush(stdout);
195         gettimeofday(&start, NULL);
196         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
197                 if (htable_obj_get(ht, &j)->self != &objs[j])
198                         abort();
199         gettimeofday(&stop, NULL);
200         printf(" %zu ns\n", normalize(&start, &stop, num));
201
202         hashcount = 0;
203         printf("Initial delete all: ");
204         fflush(stdout);
205         gettimeofday(&start, NULL);
206         for (i = 0; i < num; i++)
207                 if (!htable_obj_del(ht, objs[i].self))
208                         abort();
209         gettimeofday(&stop, NULL);
210         printf(" %zu ns\n", normalize(&start, &stop, num));
211         printf("Details: rehashes %zu\n", hashcount);
212
213         printf("Initial re-inserting: ");
214         fflush(stdout);
215         gettimeofday(&start, NULL);
216         for (i = 0; i < num; i++)
217                 htable_obj_add(ht, objs[i].self);
218         gettimeofday(&stop, NULL);
219         printf(" %zu ns\n", normalize(&start, &stop, num));
220
221         hashcount = 0;
222         printf("Deleting first half: ");
223         fflush(stdout);
224         gettimeofday(&start, NULL);
225         for (i = 0; i < num; i+=2)
226                 if (!htable_obj_del(ht, objs[i].self))
227                         abort();
228         gettimeofday(&stop, NULL);
229         printf(" %zu ns\n", normalize(&start, &stop, num));
230
231         printf("Details: rehashes %zu, delete markers %zu\n",
232                hashcount, count_deleted(htr));
233
234         printf("Adding (a different) half: ");
235         fflush(stdout);
236
237         for (i = 0; i < num; i+=2)
238                 objs[i].key = num+i;
239
240         gettimeofday(&start, NULL);
241         for (i = 0; i < num; i+=2)
242                 htable_obj_add(ht, objs[i].self);
243         gettimeofday(&stop, NULL);
244         printf(" %zu ns\n", normalize(&start, &stop, num));
245
246         printf("Details: delete markers %zu, perfect %.0f%%\n",
247                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
248
249         printf("Lookup after half-change (match): ");
250         fflush(stdout);
251         gettimeofday(&start, NULL);
252         for (i = 1; i < num; i+=2)
253                 if (htable_obj_get(ht, &i)->self != objs[i].self)
254                         abort();
255         for (i = 0; i < num; i+=2) {
256                 unsigned int n = i + num;
257                 if (htable_obj_get(ht, &n)->self != objs[i].self)
258                         abort();
259         }
260         gettimeofday(&stop, NULL);
261         printf(" %zu ns\n", normalize(&start, &stop, num));
262
263         printf("Lookup after half-change (miss): ");
264         fflush(stdout);
265         gettimeofday(&start, NULL);
266         for (i = 0; i < num; i++) {
267                 unsigned int n = i + num * 2;
268                 if (htable_obj_get(ht, &n))
269                         abort();
270         }
271         gettimeofday(&stop, NULL);
272         printf(" %zu ns\n", normalize(&start, &stop, num));
273
274         /* Hashtables with delete markers can fill with markers over time.
275          * so do some changes to see how it operates in long-term. */
276         for (i = 0; i < 5; i++) {
277                 if (i == 0) {
278                         /* We don't measure this: jmap is different. */
279                         printf("Details: initial churn\n");
280                 } else {
281                         printf("Churning %s time: ",
282                                i == 1 ? "second"
283                                : i == 2 ? "third"
284                                : i == 3 ? "fourth"
285                                : "fifth");
286                         fflush(stdout);
287                 }
288                 gettimeofday(&start, NULL);
289                 for (j = 0; j < num; j++) {
290                         if (!htable_obj_del(ht, &objs[j]))
291                                 abort();
292                         objs[j].key = num*i+j;
293                         if (!htable_obj_add(ht, &objs[j]))
294                                 abort();
295                 }
296                 gettimeofday(&stop, NULL);
297                 if (i != 0)
298                         printf(" %zu ns\n", normalize(&start, &stop, num));
299         }
300
301         /* Spread out the keys more to try to make it harder. */
302         printf("Details: reinserting with spread\n");
303         for (i = 0; i < num; i++) {
304                 if (!htable_obj_del(ht, objs[i].self))
305                         abort();
306                 objs[i].key = num * 5 + i * 9;
307                 if (!htable_obj_add(ht, objs[i].self))
308                         abort();
309         }
310         printf("Details: delete markers %zu, perfect %.0f%%\n",
311                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
312         i = worst_run(htr, &deleted);
313         printf("Details: worst run %zu (%zu deleted)\n", i, deleted);
314
315         printf("Lookup after churn & spread (match): ");
316         fflush(stdout);
317         gettimeofday(&start, NULL);
318         for (i = 0; i < num; i++) {
319                 unsigned int n = num * 5 + i * 9;
320                 if (htable_obj_get(ht, &n)->self != objs[i].self)
321                         abort();
322         }
323         gettimeofday(&stop, NULL);
324         printf(" %zu ns\n", normalize(&start, &stop, num));
325
326         printf("Lookup after churn & spread (miss): ");
327         fflush(stdout);
328         gettimeofday(&start, NULL);
329         for (i = 0; i < num; i++) {
330                 unsigned int n = num * 6 + i * 9;
331                 if (htable_obj_get(ht, &n))
332                         abort();
333         }
334         gettimeofday(&stop, NULL);
335         printf(" %zu ns\n", normalize(&start, &stop, num));
336
337         printf("Lookup after churn & spread (random): ");
338         fflush(stdout);
339         gettimeofday(&start, NULL);
340         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
341                 unsigned int n = num * 5 + j * 9;
342                 if (htable_obj_get(ht, &n)->self != &objs[j])
343                         abort();
344         }
345         gettimeofday(&stop, NULL);
346         printf(" %zu ns\n", normalize(&start, &stop, num));
347
348         hashcount = 0;
349         printf("Deleting half after churn & spread: ");
350         fflush(stdout);
351         gettimeofday(&start, NULL);
352         for (i = 0; i < num; i+=2)
353                 if (!htable_obj_del(ht, objs[i].self))
354                         abort();
355         gettimeofday(&stop, NULL);
356         printf(" %zu ns\n", normalize(&start, &stop, num));
357
358         printf("Adding (a different) half after churn & spread: ");
359         fflush(stdout);
360
361         for (i = 0; i < num; i+=2)
362                 objs[i].key = num*6+i*9;
363
364         gettimeofday(&start, NULL);
365         for (i = 0; i < num; i+=2)
366                 htable_obj_add(ht, objs[i].self);
367         gettimeofday(&stop, NULL);
368         printf(" %zu ns\n", normalize(&start, &stop, num));
369
370         printf("Details: delete markers %zu, perfect %.0f%%\n",
371                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
372
373         return 0;
374 }