git.ozlabs.org Git - ccan/blob - 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 <string.h>
   8 #include <time.h>
   9 #include <unistd.h>
  10 #include <sys/time.h>
  11
  12 static size_t hashcount;
  13 struct object {
  14         /* The key. */
  15         unsigned int key;
  16
  17         /* Some contents. Doubles as consistency check. */
  18         struct object *self;
  19 };
  20
  21 static const unsigned int *objkey(const struct object *obj)
  22 {
  23         return &obj->key;
  24 }
  25
  26 static size_t hash_obj(const unsigned int *key)
  27 {
  28         hashcount++;
  29         return hashl(key, 1, 0);
  30 }
  31
  32 static bool cmp(const struct object *object, const unsigned int *key)
  33 {
  34         return object->key == *key;
  35 }
  36
  37 HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, obj);
  38
  39 static unsigned int popcount(unsigned long val)
  40 {
  41 #if HAVE_BUILTIN_POPCOUNTL
  42         return __builtin_popcountl(val);
  43 #else
  44         if (sizeof(long) == sizeof(u64)) {
  45                 u64 v = val;
  46                 v = (v & 0x5555555555555555ULL)
  47                         + ((v >> 1) & 0x5555555555555555ULL);
  48                 v = (v & 0x3333333333333333ULL)
  49                         + ((v >> 1) & 0x3333333333333333ULL);
  50                 v = (v & 0x0F0F0F0F0F0F0F0FULL)
  51                         + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL);
  52                 v = (v & 0x00FF00FF00FF00FFULL)
  53                         + ((v >> 1) & 0x00FF00FF00FF00FFULL);
  54                 v = (v & 0x0000FFFF0000FFFFULL)
  55                         + ((v >> 1) & 0x0000FFFF0000FFFFULL);
  56                 v = (v & 0x00000000FFFFFFFFULL)
  57                         + ((v >> 1) & 0x00000000FFFFFFFFULL);
  58                 return v;
  59         }
  60         val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL);
  61         val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL);
  62         val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL);
  63         val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL);
  64         val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL);
  65         return val;
  66 #endif
  67 }
  68
  69 static size_t perfect(const struct htable *ht)
  70 {
  71         size_t i, placed_perfect = 0;
  72
  73         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
  74                 if (!entry_is_valid(ht->table[i]))
  75                         continue;
  76                 if (hash_bucket(ht, ht->rehash(get_raw_ptr(ht, ht->table[i]),
  77                                                ht->priv)) == i) {
  78                         assert((ht->table[i] & ht->perfect_bit)
  79                                == ht->perfect_bit);
  80                         placed_perfect++;
  81                 }
  82         }
  83         return placed_perfect;
  84 }
  85
  86 static size_t count_deleted(const struct htable *ht)
  87 {
  88         size_t i, delete_markers = 0;
  89
  90         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
  91                 if (ht->table[i] == HTABLE_DELETED)
  92                         delete_markers++;
  93         }
  94         return delete_markers;
  95 }
  96
  97 /* Nanoseconds per operation */
  98 static size_t normalize(const struct timeval *start,
  99                         const struct timeval *stop,
 100                         unsigned int num)
 101 {
 102         struct timeval diff;
 103
 104         timersub(stop, start, &diff);
 105
 106         /* Floating point is more accurate here. */
 107         return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
 108                 / num * 1000;
 109 }
 110
 111 static size_t worst_run(struct htable *ht, size_t *deleted)
 112 {
 113         size_t longest = 0, len = 0, this_del = 0, i;
 114
 115         *deleted = 0;
 116         /* This doesn't take into account end-wrap, but gives an idea. */
 117         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
 118                 if (ht->table[i]) {
 119                         len++;
 120                         if (ht->table[i] == HTABLE_DELETED)
 121                                 this_del++;
 122                 } else {
 123                         if (len > longest) {
 124                                 longest = len;
 125                                 *deleted = this_del;
 126                         }
 127                         len = 0;
 128                         this_del = 0;
 129                 }
 130         }
 131         return longest;
 132 }
 133
 134 int main(int argc, char *argv[])
 135 {
 136         struct object *objs;
 137         size_t i, j, num, deleted;
 138         struct timeval start, stop;
 139         struct htable_obj *ht;
 140         struct htable *htr;
 141         bool make_dumb = false;
 142
 143         if (argv[1] && strcmp(argv[1], "--dumb") == 0) {
 144                 argv++;
 145                 make_dumb = true;
 146         }
 147         num = argv[1] ? atoi(argv[1]) : 1000000;
 148         objs = calloc(num, sizeof(objs[0]));
 149
 150         for (i = 0; i < num; i++) {
 151                 objs[i].key = i;
 152                 objs[i].self = &objs[i];
 153         }
 154
 155         ht = htable_obj_new();
 156         htr = (void *)ht;
 157
 158         printf("Initial insert: ");
 159         fflush(stdout);
 160         gettimeofday(&start, NULL);
 161         for (i = 0; i < num; i++)
 162                 htable_obj_add(ht, objs[i].self);
 163         gettimeofday(&stop, NULL);
 164         printf(" %zu ns\n", normalize(&start, &stop, num));
 165         printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
 166                1U << htr->bits, popcount(htr->common_mask),
 167                perfect(htr) * 100.0 / htr->elems);
 168
 169         if (make_dumb) {
 170                 /* Screw with mask, to hobble us. */
 171                 update_common(htr, (void *)~htr->common_bits);
 172                 printf("Details: DUMB MODE: mask bits %u\n",
 173                        popcount(htr->common_mask));
 174         }
 175
 176         printf("Initial lookup (match): ");
 177         fflush(stdout);
 178         gettimeofday(&start, NULL);
 179         for (i = 0; i < num; i++)
 180                 if (htable_obj_get(ht, &i)->self != objs[i].self)
 181                         abort();
 182         gettimeofday(&stop, NULL);
 183         printf(" %zu ns\n", normalize(&start, &stop, num));
 184
 185         printf("Initial lookup (miss): ");
 186         fflush(stdout);
 187         gettimeofday(&start, NULL);
 188         for (i = 0; i < num; i++) {
 189                 unsigned int n = i + num;
 190                 if (htable_obj_get(ht, &n))
 191                         abort();
 192         }
 193         gettimeofday(&stop, NULL);
 194         printf(" %zu ns\n", normalize(&start, &stop, num));
 195
 196         /* Lookups in order are very cache-friendly for judy; try random */
 197         printf("Initial lookup (random): ");
 198         fflush(stdout);
 199         gettimeofday(&start, NULL);
 200         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 201                 if (htable_obj_get(ht, &j)->self != &objs[j])
 202                         abort();
 203         gettimeofday(&stop, NULL);
 204         printf(" %zu ns\n", normalize(&start, &stop, num));
 205
 206         hashcount = 0;
 207         printf("Initial delete all: ");
 208         fflush(stdout);
 209         gettimeofday(&start, NULL);
 210         for (i = 0; i < num; i++)
 211                 if (!htable_obj_del(ht, objs[i].self))
 212                         abort();
 213         gettimeofday(&stop, NULL);
 214         printf(" %zu ns\n", normalize(&start, &stop, num));
 215         printf("Details: rehashes %zu\n", hashcount);
 216
 217         printf("Initial re-inserting: ");
 218         fflush(stdout);
 219         gettimeofday(&start, NULL);
 220         for (i = 0; i < num; i++)
 221                 htable_obj_add(ht, objs[i].self);
 222         gettimeofday(&stop, NULL);
 223         printf(" %zu ns\n", normalize(&start, &stop, num));
 224
 225         hashcount = 0;
 226         printf("Deleting first half: ");
 227         fflush(stdout);
 228         gettimeofday(&start, NULL);
 229         for (i = 0; i < num; i+=2)
 230                 if (!htable_obj_del(ht, objs[i].self))
 231                         abort();
 232         gettimeofday(&stop, NULL);
 233         printf(" %zu ns\n", normalize(&start, &stop, num));
 234
 235         printf("Details: rehashes %zu, delete markers %zu\n",
 236                hashcount, count_deleted(htr));
 237
 238         printf("Adding (a different) half: ");
 239         fflush(stdout);
 240
 241         for (i = 0; i < num; i+=2)
 242                 objs[i].key = num+i;
 243
 244         gettimeofday(&start, NULL);
 245         for (i = 0; i < num; i+=2)
 246                 htable_obj_add(ht, objs[i].self);
 247         gettimeofday(&stop, NULL);
 248         printf(" %zu ns\n", normalize(&start, &stop, num));
 249
 250         printf("Details: delete markers %zu, perfect %.0f%%\n",
 251                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
 252
 253         printf("Lookup after half-change (match): ");
 254         fflush(stdout);
 255         gettimeofday(&start, NULL);
 256         for (i = 1; i < num; i+=2)
 257                 if (htable_obj_get(ht, &i)->self != objs[i].self)
 258                         abort();
 259         for (i = 0; i < num; i+=2) {
 260                 unsigned int n = i + num;
 261                 if (htable_obj_get(ht, &n)->self != objs[i].self)
 262                         abort();
 263         }
 264         gettimeofday(&stop, NULL);
 265         printf(" %zu ns\n", normalize(&start, &stop, num));
 266
 267         printf("Lookup after half-change (miss): ");
 268         fflush(stdout);
 269         gettimeofday(&start, NULL);
 270         for (i = 0; i < num; i++) {
 271                 unsigned int n = i + num * 2;
 272                 if (htable_obj_get(ht, &n))
 273                         abort();
 274         }
 275         gettimeofday(&stop, NULL);
 276         printf(" %zu ns\n", normalize(&start, &stop, num));
 277
 278         /* Hashtables with delete markers can fill with markers over time.
 279          * so do some changes to see how it operates in long-term. */
 280         for (i = 0; i < 5; i++) {
 281                 if (i == 0) {
 282                         /* We don't measure this: jmap is different. */
 283                         printf("Details: initial churn\n");
 284                 } else {
 285                         printf("Churning %s time: ",
 286                                i == 1 ? "second"
 287                                : i == 2 ? "third"
 288                                : i == 3 ? "fourth"
 289                                : "fifth");
 290                         fflush(stdout);
 291                 }
 292                 gettimeofday(&start, NULL);
 293                 for (j = 0; j < num; j++) {
 294                         if (!htable_obj_del(ht, &objs[j]))
 295                                 abort();
 296                         objs[j].key = num*i+j;
 297                         if (!htable_obj_add(ht, &objs[j]))
 298                                 abort();
 299                 }
 300                 gettimeofday(&stop, NULL);
 301                 if (i != 0)
 302                         printf(" %zu ns\n", normalize(&start, &stop, num));
 303         }
 304
 305         /* Spread out the keys more to try to make it harder. */
 306         printf("Details: reinserting with spread\n");
 307         for (i = 0; i < num; i++) {
 308                 if (!htable_obj_del(ht, objs[i].self))
 309                         abort();
 310                 objs[i].key = num * 5 + i * 9;
 311                 if (!htable_obj_add(ht, objs[i].self))
 312                         abort();
 313         }
 314         printf("Details: delete markers %zu, perfect %.0f%%\n",
 315                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
 316         i = worst_run(htr, &deleted);
 317         printf("Details: worst run %zu (%zu deleted)\n", i, deleted);
 318
 319         printf("Lookup after churn & spread (match): ");
 320         fflush(stdout);
 321         gettimeofday(&start, NULL);
 322         for (i = 0; i < num; i++) {
 323                 unsigned int n = num * 5 + i * 9;
 324                 if (htable_obj_get(ht, &n)->self != objs[i].self)
 325                         abort();
 326         }
 327         gettimeofday(&stop, NULL);
 328         printf(" %zu ns\n", normalize(&start, &stop, num));
 329
 330         printf("Lookup after churn & spread (miss): ");
 331         fflush(stdout);
 332         gettimeofday(&start, NULL);
 333         for (i = 0; i < num; i++) {
 334                 unsigned int n = num * (5 + 9) + i * 9;
 335                 if (htable_obj_get(ht, &n))
 336                         abort();
 337         }
 338         gettimeofday(&stop, NULL);
 339         printf(" %zu ns\n", normalize(&start, &stop, num));
 340
 341         printf("Lookup after churn & spread (random): ");
 342         fflush(stdout);
 343         gettimeofday(&start, NULL);
 344         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
 345                 unsigned int n = num * 5 + j * 9;
 346                 if (htable_obj_get(ht, &n)->self != &objs[j])
 347                         abort();
 348         }
 349         gettimeofday(&stop, NULL);
 350         printf(" %zu ns\n", normalize(&start, &stop, num));
 351
 352         hashcount = 0;
 353         printf("Deleting half after churn & spread: ");
 354         fflush(stdout);
 355         gettimeofday(&start, NULL);
 356         for (i = 0; i < num; i+=2)
 357                 if (!htable_obj_del(ht, objs[i].self))
 358                         abort();
 359         gettimeofday(&stop, NULL);
 360         printf(" %zu ns\n", normalize(&start, &stop, num));
 361
 362         printf("Adding (a different) half after churn & spread: ");
 363         fflush(stdout);
 364
 365         for (i = 0; i < num; i+=2)
 366                 objs[i].key = num*6+i*9;
 367
 368         gettimeofday(&start, NULL);
 369         for (i = 0; i < num; i+=2)
 370                 htable_obj_add(ht, objs[i].self);
 371         gettimeofday(&stop, NULL);
 372         printf(" %zu ns\n", normalize(&start, &stop, num));
 373
 374         printf("Details: delete markers %zu, perfect %.0f%%\n",
 375                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
 376
 377         return 0;
 378 }