htable: reduce size of htable by storing perfect bitnum, not mask.
[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 <ccan/time/time.h>
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9 #include <unistd.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 struct object *object, const unsigned int *key)
32 {
33         return object->key == *key;
34 }
35
36 HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, htable_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                         assert((ht->table[i] & ht_perfect_mask(ht))
78                                == ht_perfect_mask(ht));
79                         placed_perfect++;
80                 }
81         }
82         return placed_perfect;
83 }
84
85 static size_t count_deleted(const struct htable *ht)
86 {
87         size_t i, delete_markers = 0;
88
89         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
90                 if (ht->table[i] == HTABLE_DELETED)
91                         delete_markers++;
92         }
93         return delete_markers;
94 }
95
96 /* Nanoseconds per operation */
97 static size_t normalize(const struct timeabs *start,
98                         const struct timeabs *stop,
99                         unsigned int num)
100 {
101         return time_to_nsec(time_divide(time_between(*stop, *start), num));
102 }
103
104 static size_t worst_run(struct htable *ht, size_t *deleted)
105 {
106         size_t longest = 0, len = 0, this_del = 0, i;
107
108         *deleted = 0;
109         /* This doesn't take into account end-wrap, but gives an idea. */
110         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
111                 if (ht->table[i]) {
112                         len++;
113                         if (ht->table[i] == HTABLE_DELETED)
114                                 this_del++;
115                 } else {
116                         if (len > longest) {
117                                 longest = len;
118                                 *deleted = this_del;
119                         }
120                         len = 0;
121                         this_del = 0;
122                 }
123         }
124         return longest;
125 }
126
127 int main(int argc, char *argv[])
128 {
129         struct object *objs;
130         unsigned int i, j;
131         size_t num, deleted;
132         struct timeabs start, stop;
133         struct htable_obj ht;
134         bool make_dumb = false;
135
136         if (argv[1] && strcmp(argv[1], "--dumb") == 0) {
137                 argv++;
138                 make_dumb = true;
139         }
140         num = argv[1] ? atoi(argv[1]) : 1000000;
141         objs = calloc(num, sizeof(objs[0]));
142
143         for (i = 0; i < num; i++) {
144                 objs[i].key = i;
145                 objs[i].self = &objs[i];
146         }
147
148         htable_obj_init(&ht);
149
150         printf("Initial insert: ");
151         fflush(stdout);
152         start = time_now();
153         for (i = 0; i < num; i++)
154                 htable_obj_add(&ht, objs[i].self);
155         stop = time_now();
156         printf(" %zu ns\n", normalize(&start, &stop, num));
157         printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
158                1U << ht.raw.bits, popcount(ht.raw.common_mask),
159                perfect(&ht.raw) * 100.0 / ht.raw.elems);
160
161         if (make_dumb) {
162                 /* Screw with mask, to hobble us. */
163                 update_common(&ht.raw, (void *)~ht.raw.common_bits);
164                 printf("Details: DUMB MODE: mask bits %u\n",
165                        popcount(ht.raw.common_mask));
166         }
167
168         printf("Initial lookup (match): ");
169         fflush(stdout);
170         start = time_now();
171         for (i = 0; i < num; i++)
172                 if (htable_obj_get(&ht, &i)->self != objs[i].self)
173                         abort();
174         stop = time_now();
175         printf(" %zu ns\n", normalize(&start, &stop, num));
176
177         printf("Initial lookup (miss): ");
178         fflush(stdout);
179         start = time_now();
180         for (i = 0; i < num; i++) {
181                 unsigned int n = i + num;
182                 if (htable_obj_get(&ht, &n))
183                         abort();
184         }
185         stop = time_now();
186         printf(" %zu ns\n", normalize(&start, &stop, num));
187
188         /* Lookups in order are very cache-friendly for judy; try random */
189         printf("Initial lookup (random): ");
190         fflush(stdout);
191         start = time_now();
192         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
193                 if (htable_obj_get(&ht, &j)->self != &objs[j])
194                         abort();
195         stop = time_now();
196         printf(" %zu ns\n", normalize(&start, &stop, num));
197
198         hashcount = 0;
199         printf("Initial delete all: ");
200         fflush(stdout);
201         start = time_now();
202         for (i = 0; i < num; i++)
203                 if (!htable_obj_del(&ht, objs[i].self))
204                         abort();
205         stop = time_now();
206         printf(" %zu ns\n", normalize(&start, &stop, num));
207         printf("Details: rehashes %zu\n", hashcount);
208
209         printf("Initial re-inserting: ");
210         fflush(stdout);
211         start = time_now();
212         for (i = 0; i < num; i++)
213                 htable_obj_add(&ht, objs[i].self);
214         stop = time_now();
215         printf(" %zu ns\n", normalize(&start, &stop, num));
216
217         hashcount = 0;
218         printf("Deleting first half: ");
219         fflush(stdout);
220         start = time_now();
221         for (i = 0; i < num; i+=2)
222                 if (!htable_obj_del(&ht, objs[i].self))
223                         abort();
224         stop = time_now();
225         printf(" %zu ns\n", normalize(&start, &stop, num));
226
227         printf("Details: rehashes %zu, delete markers %zu\n",
228                hashcount, count_deleted(&ht.raw));
229
230         printf("Adding (a different) half: ");
231         fflush(stdout);
232
233         for (i = 0; i < num; i+=2)
234                 objs[i].key = num+i;
235
236         start = time_now();
237         for (i = 0; i < num; i+=2)
238                 htable_obj_add(&ht, objs[i].self);
239         stop = time_now();
240         printf(" %zu ns\n", normalize(&start, &stop, num));
241
242         printf("Details: delete markers %zu, perfect %.0f%%\n",
243                count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
244
245         printf("Lookup after half-change (match): ");
246         fflush(stdout);
247         start = time_now();
248         for (i = 1; i < num; i+=2)
249                 if (htable_obj_get(&ht, &i)->self != objs[i].self)
250                         abort();
251         for (i = 0; i < num; i+=2) {
252                 unsigned int n = i + num;
253                 if (htable_obj_get(&ht, &n)->self != objs[i].self)
254                         abort();
255         }
256         stop = time_now();
257         printf(" %zu ns\n", normalize(&start, &stop, num));
258
259         printf("Lookup after half-change (miss): ");
260         fflush(stdout);
261         start = time_now();
262         for (i = 0; i < num; i++) {
263                 unsigned int n = i + num * 2;
264                 if (htable_obj_get(&ht, &n))
265                         abort();
266         }
267         stop = time_now();
268         printf(" %zu ns\n", normalize(&start, &stop, num));
269
270         /* Hashtables with delete markers can fill with markers over time.
271          * so do some changes to see how it operates in long-term. */
272         for (i = 0; i < 5; i++) {
273                 if (i == 0) {
274                         /* We don't measure this: jmap is different. */
275                         printf("Details: initial churn\n");
276                 } else {
277                         printf("Churning %s time: ",
278                                i == 1 ? "second"
279                                : i == 2 ? "third"
280                                : i == 3 ? "fourth"
281                                : "fifth");
282                         fflush(stdout);
283                 }
284                 start = time_now();
285                 for (j = 0; j < num; j++) {
286                         if (!htable_obj_del(&ht, &objs[j]))
287                                 abort();
288                         objs[j].key = num*i+j;
289                         if (!htable_obj_add(&ht, &objs[j]))
290                                 abort();
291                 }
292                 stop = time_now();
293                 if (i != 0)
294                         printf(" %zu ns\n", normalize(&start, &stop, num));
295         }
296
297         /* Spread out the keys more to try to make it harder. */
298         printf("Details: reinserting with spread\n");
299         for (i = 0; i < num; i++) {
300                 if (!htable_obj_del(&ht, objs[i].self))
301                         abort();
302                 objs[i].key = num * 5 + i * 9;
303                 if (!htable_obj_add(&ht, objs[i].self))
304                         abort();
305         }
306         printf("Details: delete markers %zu, perfect %.0f%%\n",
307                count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
308         i = worst_run(&ht.raw, &deleted);
309         printf("Details: worst run %u (%zu deleted)\n", i, deleted);
310
311         printf("Lookup after churn & spread (match): ");
312         fflush(stdout);
313         start = time_now();
314         for (i = 0; i < num; i++) {
315                 unsigned int n = num * 5 + i * 9;
316                 if (htable_obj_get(&ht, &n)->self != objs[i].self)
317                         abort();
318         }
319         stop = time_now();
320         printf(" %zu ns\n", normalize(&start, &stop, num));
321
322         printf("Lookup after churn & spread (miss): ");
323         fflush(stdout);
324         start = time_now();
325         for (i = 0; i < num; i++) {
326                 unsigned int n = num * (5 + 9) + i * 9;
327                 if (htable_obj_get(&ht, &n))
328                         abort();
329         }
330         stop = time_now();
331         printf(" %zu ns\n", normalize(&start, &stop, num));
332
333         printf("Lookup after churn & spread (random): ");
334         fflush(stdout);
335         start = time_now();
336         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
337                 unsigned int n = num * 5 + j * 9;
338                 if (htable_obj_get(&ht, &n)->self != &objs[j])
339                         abort();
340         }
341         stop = time_now();
342         printf(" %zu ns\n", normalize(&start, &stop, num));
343
344         hashcount = 0;
345         printf("Deleting half after churn & spread: ");
346         fflush(stdout);
347         start = time_now();
348         for (i = 0; i < num; i+=2)
349                 if (!htable_obj_del(&ht, objs[i].self))
350                         abort();
351         stop = time_now();
352         printf(" %zu ns\n", normalize(&start, &stop, num));
353
354         printf("Adding (a different) half after churn & spread: ");
355         fflush(stdout);
356
357         for (i = 0; i < num; i+=2)
358                 objs[i].key = num*6+i*9;
359
360         start = time_now();
361         for (i = 0; i < num; i+=2)
362                 htable_obj_add(&ht, objs[i].self);
363         stop = time_now();
364         printf(" %zu ns\n", normalize(&start, &stop, num));
365
366         printf("Details: delete markers %zu, perfect %.0f%%\n",
367                count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
368
369         return 0;
370 }