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 static bool check_val(intmap_index_t i, uint64_t *v, uint64_t *expected)
  65 {
  66         if (v != expected)
  67                 abort();
  68         return true;
  69 }
  70
  71 int main(int argc, char *argv[])
  72 {
  73         uint64_t i, total = 0, seed, *v;
  74         size_t max = argv[1] ? atol(argv[1]) : 100000000;
  75         isaac64_ctx isaac;
  76         struct timeabs start, end;
  77         UINTMAP(uint64_t *) map;
  78         struct hash hash;
  79         struct htable_elem *e;
  80         struct hash_iter it;
  81         uintptr_t span_min, span_max;
  82
  83         uintmap_init(&map);
  84         hash_init(&hash);
  85
  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));
  90
  91         start = time_now();
  92         for (i = 0; i < max; i++)
  93                 total += isaac64_next_uint64(&isaac);
  94         end = time_now();
  95         printf("%zu,random generation (nsec),%"PRIu64"\n", max,
  96                time_to_nsec(time_divide(time_between(end, start), max)));
  97
  98         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
  99         start = time_now();
 100         for (i = 0; i < max; i++) {
 101                 if (!uintmap_add(&map, isaac64_next_uint64(&isaac), &i))
 102                         abort();
 103         }
 104         end = time_now();
 105         printf("%zu,critbit insert (nsec),%"PRIu64"\n", max,
 106                time_to_nsec(time_divide(time_between(end, start), max)));
 107
 108         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
 109         start = time_now();
 110         for (i = 0; i < max; i++) {
 111                 if (uintmap_get(&map, isaac64_next_uint64(&isaac)) != &i)
 112                         abort();
 113         }
 114         end = time_now();
 115         printf("%zu,critbit successful lookup (nsec),%"PRIu64"\n", max,
 116                time_to_nsec(time_divide(time_between(end, start), max)));
 117
 118         start = time_now();
 119         for (i = 0; i < max; i++) {
 120                 if (uintmap_get(&map, isaac64_next_uint64(&isaac)))
 121                         abort();
 122         }
 123         end = time_now();
 124         printf("%zu,critbit failed lookup (nsec),%"PRIu64"\n", max,
 125                time_to_nsec(time_divide(time_between(end, start), max)));
 126
 127         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
 128         start = time_now();
 129         for (v = uintmap_first(&map, &i); v; v = uintmap_after(&map, &i)) {
 130                 if (v != &i)
 131                         abort();
 132         }
 133         end = time_now();
 134         printf("%zu,critbit iteration (nsec),%"PRIu64"\n", max,
 135                time_to_nsec(time_divide(time_between(end, start), max)));
 136
 137         start = time_now();
 138         uintmap_iterate(&map, check_val, &i);
 139         end = time_now();
 140         printf("%zu,critbit callback iteration (nsec),%"PRIu64"\n", max,
 141                time_to_nsec(time_divide(time_between(end, start), max)));
 142
 143         span_min = -1ULL;
 144         span_max = 0;
 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);
 148
 149         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
 150         start = time_now();
 151         for (i = 0; i < max; i++) {
 152                 if (!uintmap_del(&map, isaac64_next_uint64(&isaac)))
 153                         abort();
 154         }
 155         end = time_now();
 156         printf("%zu,critbit delete (nsec),%"PRIu64"\n", max,
 157                time_to_nsec(time_divide(time_between(end, start), max)));
 158
 159         /* Fill with consecutive values */
 160         for (i = 0; i < max; i++) {
 161                 if (!uintmap_add(&map, i, &i))
 162                         abort();
 163         }
 164         start = time_now();
 165         for (v = uintmap_first(&map, &i); v; v = uintmap_after(&map, &i)) {
 166                 if (v != &i)
 167                         abort();
 168         }
 169         end = time_now();
 170         printf("%zu,critbit consecutive iteration (nsec),%"PRIu64"\n", max,
 171                time_to_nsec(time_divide(time_between(end, start), max)));
 172
 173         start = time_now();
 174         uintmap_iterate(&map, check_val, &i);
 175         end = time_now();
 176         printf("%zu,critbit consecutive callback iteration (nsec),%"PRIu64"\n", max,
 177                time_to_nsec(time_divide(time_between(end, start), max)));
 178
 179         sipseed.u.u64[0] = isaac64_next_uint64(&isaac);
 180         sipseed.u.u64[1] = isaac64_next_uint64(&isaac);
 181
 182         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
 183         start = time_now();
 184         for (i = 0; i < max; i++) {
 185                 e = malloc(sizeof(*e));
 186                 e->v = &i;
 187                 e->index = isaac64_next_uint64(&isaac);
 188                 hash_add(&hash, e);
 189         }
 190         end = time_now();
 191         printf("%zu,hash insert (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 (i = 0; i < max; i++) {
 197                 if (hash_get(&hash, isaac64_next_uint64(&isaac))->v != &i)
 198                         abort();
 199         }
 200         end = time_now();
 201         printf("%zu,hash successful lookup (nsec),%"PRIu64"\n", max,
 202                time_to_nsec(time_divide(time_between(end, start), max)));
 203
 204         start = time_now();
 205         for (i = 0; i < max; i++) {
 206                 if (hash_get(&hash, isaac64_next_uint64(&isaac)))
 207                         abort();
 208         }
 209         end = time_now();
 210         printf("%zu,hash failed lookup (nsec),%"PRIu64"\n", max,
 211                time_to_nsec(time_divide(time_between(end, start), max)));
 212
 213         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
 214         start = time_now();
 215         for (e = hash_first(&hash, &it); e; e = hash_next(&hash, &it)) {
 216                 if (e->v != &i)
 217                         abort();
 218         }
 219         end = time_now();
 220         printf("%zu,hash iteration (nsec),%"PRIu64"\n", max,
 221                time_to_nsec(time_divide(time_between(end, start), max)));
 222
 223         span_min = -1ULL;
 224         span_max = 0;
 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);
 231
 232         isaac64_init(&isaac, (unsigned char *)&seed, sizeof(seed));
 233         start = time_now();
 234         for (i = 0; i < max; i++) {
 235                 e = hash_get(&hash, isaac64_next_uint64(&isaac));
 236                 if (!hash_del(&hash, e))
 237                         abort();
 238                 free(e);
 239         }
 240         end = time_now();
 241         printf("%zu,hash delete (nsec),%"PRIu64"\n", max,
 242                time_to_nsec(time_divide(time_between(end, start), max)));
 243
 244         /* Use total, but "never happens". */
 245         return (total == 0);
 246 }