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>
12 /* hack to let us gather span. */
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;
20 static void update_span(const void *p, size_t s, uintptr_t *min, uintptr_t *max)
22 if ((uintptr_t)p < *min)
24 if ((uintptr_t)p + s > *max)
25 *max = (uintptr_t)p + s;
28 static void getspan(const struct intmap *m, uintptr_t *min, uintptr_t *max)
36 update_span(n, sizeof(*n), min, max);
37 getspan(&n->child[0], min, max);
38 getspan(&n->child[1], min, max);
46 static struct siphash_seed sipseed;
48 static uint64_t keyof(const struct htable_elem *elem)
53 static size_t hashfn(const uint64_t index)
55 return siphash24(&sipseed, &index, sizeof(index));
58 static bool eqfn(const struct htable_elem *elem, const uint64_t index)
60 return elem->index == index;
62 HTABLE_DEFINE_TYPE(struct htable_elem, keyof, hashfn, eqfn, hash);
64 static bool check_val(intmap_index_t i, uint64_t *v, uint64_t *expected)
71 int main(int argc, char *argv[])
73 uint64_t i, total = 0, seed, *v;
74 size_t max = argv[1] ? atol(argv[1]) : 100000000;
76 struct timeabs start, end;
77 UINTMAP(uint64_t *) map;
79 struct htable_elem *e;
81 uintptr_t span_min, span_max;
86 /* We don't want our randomness function to dominate the time,
87 * nor deal with duplicates (just abort, that's v. unlikely) */
88 seed = time_now().ts.tv_sec + time_now().ts.tv_nsec;
89 isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
92 for (i = 0; i < max; i++)
93 total += isaac64_next_uint64(&isaac);
95 printf("%zu,random generation (nsec),%"PRIu64"\n", max,
96 time_to_nsec(time_divide(time_between(end, start), max)));
98 isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
100 for (i = 0; i < max; i++) {
101 if (!uintmap_add(&map, isaac64_next_uint64(&isaac), &i))
105 printf("%zu,critbit insert (nsec),%"PRIu64"\n", max,
106 time_to_nsec(time_divide(time_between(end, start), max)));
108 isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
110 for (i = 0; i < max; i++) {
111 if (uintmap_get(&map, isaac64_next_uint64(&isaac)) != &i)
115 printf("%zu,critbit successful lookup (nsec),%"PRIu64"\n", max,
116 time_to_nsec(time_divide(time_between(end, start), max)));
119 for (i = 0; i < max; i++) {
120 if (uintmap_get(&map, isaac64_next_uint64(&isaac)))
124 printf("%zu,critbit failed lookup (nsec),%"PRIu64"\n", max,
125 time_to_nsec(time_divide(time_between(end, start), max)));
127 isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
129 for (v = uintmap_first(&map, &i); v; v = uintmap_after(&map, &i)) {
134 printf("%zu,critbit iteration (nsec),%"PRIu64"\n", max,
135 time_to_nsec(time_divide(time_between(end, start), max)));
138 uintmap_iterate(&map, check_val, &i);
140 printf("%zu,critbit callback iteration (nsec),%"PRIu64"\n", max,
141 time_to_nsec(time_divide(time_between(end, start), max)));
145 getspan(uintmap_unwrap_(&map), &span_min, &span_max);
146 printf("%zu,critbit memory (bytes),%zu\n",
147 max, (size_t)(span_max - span_min + max / 2) / max);
149 isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
151 for (i = 0; i < max; i++) {
152 if (!uintmap_del(&map, isaac64_next_uint64(&isaac)))
156 printf("%zu,critbit delete (nsec),%"PRIu64"\n", max,
157 time_to_nsec(time_divide(time_between(end, start), max)));
159 /* Fill with consecutive values */
160 for (i = 0; i < max; i++) {
161 if (!uintmap_add(&map, i, &i))
165 for (v = uintmap_first(&map, &i); v; v = uintmap_after(&map, &i)) {
170 printf("%zu,critbit consecutive iteration (nsec),%"PRIu64"\n", max,
171 time_to_nsec(time_divide(time_between(end, start), max)));
174 uintmap_iterate(&map, check_val, &i);
176 printf("%zu,critbit consecutive callback iteration (nsec),%"PRIu64"\n", max,
177 time_to_nsec(time_divide(time_between(end, start), max)));
179 sipseed.u.u64[0] = isaac64_next_uint64(&isaac);
180 sipseed.u.u64[1] = isaac64_next_uint64(&isaac);
182 isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
184 for (i = 0; i < max; i++) {
185 e = malloc(sizeof(*e));
187 e->index = isaac64_next_uint64(&isaac);
191 printf("%zu,hash insert (nsec),%"PRIu64"\n", max,
192 time_to_nsec(time_divide(time_between(end, start), max)));
194 isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
196 for (i = 0; i < max; i++) {
197 if (hash_get(&hash, isaac64_next_uint64(&isaac))->v != &i)
201 printf("%zu,hash successful lookup (nsec),%"PRIu64"\n", max,
202 time_to_nsec(time_divide(time_between(end, start), max)));
205 for (i = 0; i < max; i++) {
206 if (hash_get(&hash, isaac64_next_uint64(&isaac)))
210 printf("%zu,hash failed lookup (nsec),%"PRIu64"\n", max,
211 time_to_nsec(time_divide(time_between(end, start), max)));
213 isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
215 for (e = hash_first(&hash, &it); e; e = hash_next(&hash, &it)) {
220 printf("%zu,hash iteration (nsec),%"PRIu64"\n", max,
221 time_to_nsec(time_divide(time_between(end, start), max)));
225 for (e = hash_first(&hash, &it); e; e = hash_next(&hash, &it))
226 update_span(e, sizeof(*e), &span_min, &span_max);
227 /* table itself tends to be allocated in separate memory. */
228 span_max += (sizeof(uintptr_t) << hash.raw.bits);
229 printf("%zu,hash memory (bytes),%zu\n",
230 max, (size_t)(span_max - span_min + max / 2) / max);
232 isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
234 for (i = 0; i < max; i++) {
235 e = hash_get(&hash, isaac64_next_uint64(&isaac));
236 if (!hash_del(&hash, e))
241 printf("%zu,hash delete (nsec),%"PRIu64"\n", max,
242 time_to_nsec(time_divide(time_between(end, start), max)));
244 /* Use total, but "never happens". */