htable: clean up interface, document htable_type better.
[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, htable_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         bool make_dumb = false;
141
142         if (argv[1] && strcmp(argv[1], "--dumb") == 0) {
143                 argv++;
144                 make_dumb = true;
145         }
146         num = argv[1] ? atoi(argv[1]) : 1000000;
147         objs = calloc(num, sizeof(objs[0]));
148
149         for (i = 0; i < num; i++) {
150                 objs[i].key = i;
151                 objs[i].self = &objs[i];
152         }
153
154         htable_obj_init(&ht);
155
156         printf("Initial insert: ");
157         fflush(stdout);
158         gettimeofday(&start, NULL);
159         for (i = 0; i < num; i++)
160                 htable_obj_add(&ht, objs[i].self);
161         gettimeofday(&stop, NULL);
162         printf(" %zu ns\n", normalize(&start, &stop, num));
163         printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
164                1U << ht.raw.bits, popcount(ht.raw.common_mask),
165                perfect(&ht.raw) * 100.0 / ht.raw.elems);
166
167         if (make_dumb) {
168                 /* Screw with mask, to hobble us. */
169                 update_common(&ht.raw, (void *)~ht.raw.common_bits);
170                 printf("Details: DUMB MODE: mask bits %u\n",
171                        popcount(ht.raw.common_mask));
172         }
173
174         printf("Initial lookup (match): ");
175         fflush(stdout);
176         gettimeofday(&start, NULL);
177         for (i = 0; i < num; i++)
178                 if (htable_obj_get(&ht, &i)->self != objs[i].self)
179                         abort();
180         gettimeofday(&stop, NULL);
181         printf(" %zu ns\n", normalize(&start, &stop, num));
182
183         printf("Initial lookup (miss): ");
184         fflush(stdout);
185         gettimeofday(&start, NULL);
186         for (i = 0; i < num; i++) {
187                 unsigned int n = i + num;
188                 if (htable_obj_get(&ht, &n))
189                         abort();
190         }
191         gettimeofday(&stop, NULL);
192         printf(" %zu ns\n", normalize(&start, &stop, num));
193
194         /* Lookups in order are very cache-friendly for judy; try random */
195         printf("Initial lookup (random): ");
196         fflush(stdout);
197         gettimeofday(&start, NULL);
198         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
199                 if (htable_obj_get(&ht, &j)->self != &objs[j])
200                         abort();
201         gettimeofday(&stop, NULL);
202         printf(" %zu ns\n", normalize(&start, &stop, num));
203
204         hashcount = 0;
205         printf("Initial delete all: ");
206         fflush(stdout);
207         gettimeofday(&start, NULL);
208         for (i = 0; i < num; i++)
209                 if (!htable_obj_del(&ht, objs[i].self))
210                         abort();
211         gettimeofday(&stop, NULL);
212         printf(" %zu ns\n", normalize(&start, &stop, num));
213         printf("Details: rehashes %zu\n", hashcount);
214
215         printf("Initial re-inserting: ");
216         fflush(stdout);
217         gettimeofday(&start, NULL);
218         for (i = 0; i < num; i++)
219                 htable_obj_add(&ht, objs[i].self);
220         gettimeofday(&stop, NULL);
221         printf(" %zu ns\n", normalize(&start, &stop, num));
222
223         hashcount = 0;
224         printf("Deleting first half: ");
225         fflush(stdout);
226         gettimeofday(&start, NULL);
227         for (i = 0; i < num; i+=2)
228                 if (!htable_obj_del(&ht, objs[i].self))
229                         abort();
230         gettimeofday(&stop, NULL);
231         printf(" %zu ns\n", normalize(&start, &stop, num));
232
233         printf("Details: rehashes %zu, delete markers %zu\n",
234                hashcount, count_deleted(&ht.raw));
235
236         printf("Adding (a different) half: ");
237         fflush(stdout);
238
239         for (i = 0; i < num; i+=2)
240                 objs[i].key = num+i;
241
242         gettimeofday(&start, NULL);
243         for (i = 0; i < num; i+=2)
244                 htable_obj_add(&ht, objs[i].self);
245         gettimeofday(&stop, NULL);
246         printf(" %zu ns\n", normalize(&start, &stop, num));
247
248         printf("Details: delete markers %zu, perfect %.0f%%\n",
249                count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
250
251         printf("Lookup after half-change (match): ");
252         fflush(stdout);
253         gettimeofday(&start, NULL);
254         for (i = 1; i < num; i+=2)
255                 if (htable_obj_get(&ht, &i)->self != objs[i].self)
256                         abort();
257         for (i = 0; i < num; i+=2) {
258                 unsigned int n = i + num;
259                 if (htable_obj_get(&ht, &n)->self != objs[i].self)
260                         abort();
261         }
262         gettimeofday(&stop, NULL);
263         printf(" %zu ns\n", normalize(&start, &stop, num));
264
265         printf("Lookup after half-change (miss): ");
266         fflush(stdout);
267         gettimeofday(&start, NULL);
268         for (i = 0; i < num; i++) {
269                 unsigned int n = i + num * 2;
270                 if (htable_obj_get(&ht, &n))
271                         abort();
272         }
273         gettimeofday(&stop, NULL);
274         printf(" %zu ns\n", normalize(&start, &stop, num));
275
276         /* Hashtables with delete markers can fill with markers over time.
277          * so do some changes to see how it operates in long-term. */
278         for (i = 0; i < 5; i++) {
279                 if (i == 0) {
280                         /* We don't measure this: jmap is different. */
281                         printf("Details: initial churn\n");
282                 } else {
283                         printf("Churning %s time: ",
284                                i == 1 ? "second"
285                                : i == 2 ? "third"
286                                : i == 3 ? "fourth"
287                                : "fifth");
288                         fflush(stdout);
289                 }
290                 gettimeofday(&start, NULL);
291                 for (j = 0; j < num; j++) {
292                         if (!htable_obj_del(&ht, &objs[j]))
293                                 abort();
294                         objs[j].key = num*i+j;
295                         if (!htable_obj_add(&ht, &objs[j]))
296                                 abort();
297                 }
298                 gettimeofday(&stop, NULL);
299                 if (i != 0)
300                         printf(" %zu ns\n", normalize(&start, &stop, num));
301         }
302
303         /* Spread out the keys more to try to make it harder. */
304         printf("Details: reinserting with spread\n");
305         for (i = 0; i < num; i++) {
306                 if (!htable_obj_del(&ht, objs[i].self))
307                         abort();
308                 objs[i].key = num * 5 + i * 9;
309                 if (!htable_obj_add(&ht, objs[i].self))
310                         abort();
311         }
312         printf("Details: delete markers %zu, perfect %.0f%%\n",
313                count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
314         i = worst_run(&ht.raw, &deleted);
315         printf("Details: worst run %zu (%zu deleted)\n", i, deleted);
316
317         printf("Lookup after churn & spread (match): ");
318         fflush(stdout);
319         gettimeofday(&start, NULL);
320         for (i = 0; i < num; i++) {
321                 unsigned int n = num * 5 + i * 9;
322                 if (htable_obj_get(&ht, &n)->self != objs[i].self)
323                         abort();
324         }
325         gettimeofday(&stop, NULL);
326         printf(" %zu ns\n", normalize(&start, &stop, num));
327
328         printf("Lookup after churn & spread (miss): ");
329         fflush(stdout);
330         gettimeofday(&start, NULL);
331         for (i = 0; i < num; i++) {
332                 unsigned int n = num * (5 + 9) + i * 9;
333                 if (htable_obj_get(&ht, &n))
334                         abort();
335         }
336         gettimeofday(&stop, NULL);
337         printf(" %zu ns\n", normalize(&start, &stop, num));
338
339         printf("Lookup after churn & spread (random): ");
340         fflush(stdout);
341         gettimeofday(&start, NULL);
342         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
343                 unsigned int n = num * 5 + j * 9;
344                 if (htable_obj_get(&ht, &n)->self != &objs[j])
345                         abort();
346         }
347         gettimeofday(&stop, NULL);
348         printf(" %zu ns\n", normalize(&start, &stop, num));
349
350         hashcount = 0;
351         printf("Deleting half after churn & spread: ");
352         fflush(stdout);
353         gettimeofday(&start, NULL);
354         for (i = 0; i < num; i+=2)
355                 if (!htable_obj_del(&ht, objs[i].self))
356                         abort();
357         gettimeofday(&stop, NULL);
358         printf(" %zu ns\n", normalize(&start, &stop, num));
359
360         printf("Adding (a different) half after churn & spread: ");
361         fflush(stdout);
362
363         for (i = 0; i < num; i+=2)
364                 objs[i].key = num*6+i*9;
365
366         gettimeofday(&start, NULL);
367         for (i = 0; i < num; i+=2)
368                 htable_obj_add(&ht, objs[i].self);
369         gettimeofday(&stop, NULL);
370         printf(" %zu ns\n", normalize(&start, &stop, num));
371
372         printf("Details: delete markers %zu, perfect %.0f%%\n",
373                count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
374
375         return 0;
376 }