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