git.ozlabs.org Git - ccan/blob - 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 }