intmap: reimplement so that intmap_after works.
[ccan] / ccan / intmap / benchmark / speed.c
1 /* Test speed of intmap */
2 #include <ccan/time/time.h>
3 #include <ccan/intmap/intmap.h>
4 #include <ccan/isaac/isaac64.h>
5 #include <ccan/htable/htable_type.h>
6 #include <ccan/crypto/siphash24/siphash24.h>
7 #include <stdlib.h>
8 #include <stdio.h>
9 #include <assert.h>
10 #include <inttypes.h>
11
12 /* hack to let us gather span. */
13 struct node {
14         /* These point to strings or nodes. */
15         struct intmap child[2];
16         /* Encoding both prefix and critbit: 1 is appended to prefix. */
17         intmap_index_t prefix_and_critbit;
18 };
19
20 static void update_span(const void *p, size_t s, uintptr_t *min, uintptr_t *max)
21 {
22         if ((uintptr_t)p < *min)
23                 *min = (uintptr_t)p;
24         if ((uintptr_t)p + s > *max)
25                 *max = (uintptr_t)p + s;
26 }
27
28 static void getspan(const struct intmap *m, uintptr_t *min, uintptr_t *max)
29 {
30         struct node *n;
31         /* Leaf node? */
32         if (m->v)
33                 return;
34
35         n = m->u.n;
36         update_span(n, sizeof(*n), min, max);
37         getspan(&n->child[0], min, max);
38         getspan(&n->child[1], min, max);
39 }
40
41 struct htable_elem {
42         uint64_t index;
43         uint64_t *v;
44 };
45
46 static struct siphash_seed sipseed;
47
48 static uint64_t keyof(const struct htable_elem *elem)
49 {
50         return elem->index;
51 }
52
53 static size_t hashfn(const uint64_t index)
54 {
55         return siphash24(&sipseed, &index, sizeof(index));
56 }
57
58 static bool eqfn(const struct htable_elem *elem, const uint64_t index)
59 {
60         return elem->index == index;
61 }
62 HTABLE_DEFINE_TYPE(struct htable_elem, keyof, hashfn, eqfn, hash);
63
64 int main(int argc, char *argv[])
65 {
66         uint64_t i, total = 0, seed, *v;
67         size_t max = argv[1] ? atol(argv[1]) : 100000000;
68         isaac64_ctx isaac;
69         struct timeabs start, end;
70         UINTMAP(uint64_t *) map;
71         struct hash hash;
72         struct htable_elem *e;
73         struct hash_iter it;
74         uintptr_t span_min, span_max;
75
76         uintmap_init(&map);
77         hash_init(&hash);
78
79         /* We don't want our randomness function to dominate the time,
80          * nor deal with duplicates (just abort, that's v. unlikely) */
81         seed = time_now().ts.tv_sec + time_now().ts.tv_nsec;
82         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
83
84         start = time_now();
85         for (i = 0; i < max; i++)
86                 total += isaac64_next_uint64(&isaac);
87         end = time_now();
88         printf("%zu,random generation (nsec),%"PRIu64"\n", max,
89                time_to_nsec(time_divide(time_between(end, start), max)));
90
91         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
92         start = time_now();
93         for (i = 0; i < max; i++) {
94                 if (!uintmap_add(&map, isaac64_next_uint64(&isaac), &i))
95                         abort();
96         }
97         end = time_now();
98         printf("%zu,critbit insert (nsec),%"PRIu64"\n", max,
99                time_to_nsec(time_divide(time_between(end, start), max)));
100
101         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
102         start = time_now();
103         for (i = 0; i < max; i++) {
104                 if (uintmap_get(&map, isaac64_next_uint64(&isaac)) != &i)
105                         abort();
106         }
107         end = time_now();
108         printf("%zu,critbit successful lookup (nsec),%"PRIu64"\n", max,
109                time_to_nsec(time_divide(time_between(end, start), max)));
110
111         start = time_now();
112         for (i = 0; i < max; i++) {
113                 if (uintmap_get(&map, isaac64_next_uint64(&isaac)))
114                         abort();
115         }
116         end = time_now();
117         printf("%zu,critbit failed lookup (nsec),%"PRIu64"\n", max,
118                time_to_nsec(time_divide(time_between(end, start), max)));
119
120         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
121         start = time_now();
122         for (v = uintmap_first(&map, &i); v; v = uintmap_after(&map, &i)) {
123                 if (v != &i)
124                         abort();
125         }
126         end = time_now();
127         printf("%zu,critbit iteration (nsec),%"PRIu64"\n", max,
128                time_to_nsec(time_divide(time_between(end, start), max)));
129
130         span_min = -1ULL;
131         span_max = 0;
132         getspan(uintmap_unwrap_(&map), &span_min, &span_max);
133         printf("%zu,critbit memory (bytes),%zu\n",
134                max, (size_t)(span_max - span_min + max / 2) / max);
135
136         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
137         start = time_now();
138         for (i = 0; i < max; i++) {
139                 if (!uintmap_del(&map, isaac64_next_uint64(&isaac)))
140                         abort();
141         }
142         end = time_now();
143         printf("%zu,critbit delete (nsec),%"PRIu64"\n", max,
144                time_to_nsec(time_divide(time_between(end, start), max)));
145
146         /* Fill with consecutive values */
147         for (i = 0; i < max; i++) {
148                 if (!uintmap_add(&map, i, &i))
149                         abort();
150         }
151         start = time_now();
152         for (v = uintmap_first(&map, &i); v; v = uintmap_after(&map, &i)) {
153                 if (v != &i)
154                         abort();
155         }
156         end = time_now();
157         printf("%zu,critbit consecutive iteration (nsec),%"PRIu64"\n", max,
158                time_to_nsec(time_divide(time_between(end, start), max)));
159
160         sipseed.u.u64[0] = isaac64_next_uint64(&isaac);
161         sipseed.u.u64[1] = isaac64_next_uint64(&isaac);
162
163         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
164         start = time_now();
165         for (i = 0; i < max; i++) {
166                 e = malloc(sizeof(*e));
167                 e->v = &i;
168                 e->index = isaac64_next_uint64(&isaac);
169                 hash_add(&hash, e);
170         }
171         end = time_now();
172         printf("%zu,hash insert (nsec),%"PRIu64"\n", max,
173                time_to_nsec(time_divide(time_between(end, start), max)));
174
175         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
176         start = time_now();
177         for (i = 0; i < max; i++) {
178                 if (hash_get(&hash, isaac64_next_uint64(&isaac))->v != &i)
179                         abort();
180         }
181         end = time_now();
182         printf("%zu,hash successful lookup (nsec),%"PRIu64"\n", max,
183                time_to_nsec(time_divide(time_between(end, start), max)));
184
185         start = time_now();
186         for (i = 0; i < max; i++) {
187                 if (hash_get(&hash, isaac64_next_uint64(&isaac)))
188                         abort();
189         }
190         end = time_now();
191         printf("%zu,hash failed lookup (nsec),%"PRIu64"\n", max,
192                time_to_nsec(time_divide(time_between(end, start), max)));
193
194         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
195         start = time_now();
196         for (e = hash_first(&hash, &it); e; e = hash_next(&hash, &it)) {
197                 if (e->v != &i)
198                         abort();
199         }
200         end = time_now();
201         printf("%zu,hash iteration (nsec),%"PRIu64"\n", max,
202                time_to_nsec(time_divide(time_between(end, start), max)));
203
204         span_min = -1ULL;
205         span_max = 0;
206         for (e = hash_first(&hash, &it); e; e = hash_next(&hash, &it))
207                 update_span(e, sizeof(*e), &span_min, &span_max);
208         /* table itself tends to be allocated in separate memory. */
209         span_max += (sizeof(uintptr_t) << hash.raw.bits);
210         printf("%zu,hash memory (bytes),%zu\n",
211                max, (size_t)(span_max - span_min + max / 2) / max);
212
213         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
214         start = time_now();
215         for (i = 0; i < max; i++) {
216                 e = hash_get(&hash, isaac64_next_uint64(&isaac));
217                 if (!hash_del(&hash, e))
218                         abort();
219                 free(e);
220         }
221         end = time_now();
222         printf("%zu,hash delete (nsec),%"PRIu64"\n", max,
223                time_to_nsec(time_divide(time_between(end, start), max)));
224
225         /* Use total, but "never happens". */
226         return (total == 0);
227 }