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