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, htable_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         bool make_dumb = false;
 141
 142         if (argv[1] && strcmp(argv[1], "--dumb") == 0) {
 143                 argv++;
 144                 make_dumb = true;
 145         }
 146         num = argv[1] ? atoi(argv[1]) : 1000000;
 147         objs = calloc(num, sizeof(objs[0]));
 148
 149         for (i = 0; i < num; i++) {
 150                 objs[i].key = i;
 151                 objs[i].self = &objs[i];
 152         }
 153
 154         htable_obj_init(&ht);
 155
 156         printf("Initial insert: ");
 157         fflush(stdout);
 158         gettimeofday(&start, NULL);
 159         for (i = 0; i < num; i++)
 160                 htable_obj_add(&ht, objs[i].self);
 161         gettimeofday(&stop, NULL);
 162         printf(" %zu ns\n", normalize(&start, &stop, num));
 163         printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
 164                1U << ht.raw.bits, popcount(ht.raw.common_mask),
 165                perfect(&ht.raw) * 100.0 / ht.raw.elems);
 166
 167         if (make_dumb) {
 168                 /* Screw with mask, to hobble us. */
 169                 update_common(&ht.raw, (void *)~ht.raw.common_bits);
 170                 printf("Details: DUMB MODE: mask bits %u\n",
 171                        popcount(ht.raw.common_mask));
 172         }
 173
 174         printf("Initial lookup (match): ");
 175         fflush(stdout);
 176         gettimeofday(&start, NULL);
 177         for (i = 0; i < num; i++)
 178                 if (htable_obj_get(&ht, &i)->self != objs[i].self)
 179                         abort();
 180         gettimeofday(&stop, NULL);
 181         printf(" %zu ns\n", normalize(&start, &stop, num));
 182
 183         printf("Initial lookup (miss): ");
 184         fflush(stdout);
 185         gettimeofday(&start, NULL);
 186         for (i = 0; i < num; i++) {
 187                 unsigned int n = i + num;
 188                 if (htable_obj_get(&ht, &n))
 189                         abort();
 190         }
 191         gettimeofday(&stop, NULL);
 192         printf(" %zu ns\n", normalize(&start, &stop, num));
 193
 194         /* Lookups in order are very cache-friendly for judy; try random */
 195         printf("Initial lookup (random): ");
 196         fflush(stdout);
 197         gettimeofday(&start, NULL);
 198         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 199                 if (htable_obj_get(&ht, &j)->self != &objs[j])
 200                         abort();
 201         gettimeofday(&stop, NULL);
 202         printf(" %zu ns\n", normalize(&start, &stop, num));
 203
 204         hashcount = 0;
 205         printf("Initial delete all: ");
 206         fflush(stdout);
 207         gettimeofday(&start, NULL);
 208         for (i = 0; i < num; i++)
 209                 if (!htable_obj_del(&ht, objs[i].self))
 210                         abort();
 211         gettimeofday(&stop, NULL);
 212         printf(" %zu ns\n", normalize(&start, &stop, num));
 213         printf("Details: rehashes %zu\n", hashcount);
 214
 215         printf("Initial re-inserting: ");
 216         fflush(stdout);
 217         gettimeofday(&start, NULL);
 218         for (i = 0; i < num; i++)
 219                 htable_obj_add(&ht, objs[i].self);
 220         gettimeofday(&stop, NULL);
 221         printf(" %zu ns\n", normalize(&start, &stop, num));
 222
 223         hashcount = 0;
 224         printf("Deleting first half: ");
 225         fflush(stdout);
 226         gettimeofday(&start, NULL);
 227         for (i = 0; i < num; i+=2)
 228                 if (!htable_obj_del(&ht, objs[i].self))
 229                         abort();
 230         gettimeofday(&stop, NULL);
 231         printf(" %zu ns\n", normalize(&start, &stop, num));
 232
 233         printf("Details: rehashes %zu, delete markers %zu\n",
 234                hashcount, count_deleted(&ht.raw));
 235
 236         printf("Adding (a different) half: ");
 237         fflush(stdout);
 238
 239         for (i = 0; i < num; i+=2)
 240                 objs[i].key = num+i;
 241
 242         gettimeofday(&start, NULL);
 243         for (i = 0; i < num; i+=2)
 244                 htable_obj_add(&ht, objs[i].self);
 245         gettimeofday(&stop, NULL);
 246         printf(" %zu ns\n", normalize(&start, &stop, num));
 247
 248         printf("Details: delete markers %zu, perfect %.0f%%\n",
 249                count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
 250
 251         printf("Lookup after half-change (match): ");
 252         fflush(stdout);
 253         gettimeofday(&start, NULL);
 254         for (i = 1; i < num; i+=2)
 255                 if (htable_obj_get(&ht, &i)->self != objs[i].self)
 256                         abort();
 257         for (i = 0; i < num; i+=2) {
 258                 unsigned int n = i + num;
 259                 if (htable_obj_get(&ht, &n)->self != objs[i].self)
 260                         abort();
 261         }
 262         gettimeofday(&stop, NULL);
 263         printf(" %zu ns\n", normalize(&start, &stop, num));
 264
 265         printf("Lookup after half-change (miss): ");
 266         fflush(stdout);
 267         gettimeofday(&start, NULL);
 268         for (i = 0; i < num; i++) {
 269                 unsigned int n = i + num * 2;
 270                 if (htable_obj_get(&ht, &n))
 271                         abort();
 272         }
 273         gettimeofday(&stop, NULL);
 274         printf(" %zu ns\n", normalize(&start, &stop, num));
 275
 276         /* Hashtables with delete markers can fill with markers over time.
 277          * so do some changes to see how it operates in long-term. */
 278         for (i = 0; i < 5; i++) {
 279                 if (i == 0) {
 280                         /* We don't measure this: jmap is different. */
 281                         printf("Details: initial churn\n");
 282                 } else {
 283                         printf("Churning %s time: ",
 284                                i == 1 ? "second"
 285                                : i == 2 ? "third"
 286                                : i == 3 ? "fourth"
 287                                : "fifth");
 288                         fflush(stdout);
 289                 }
 290                 gettimeofday(&start, NULL);
 291                 for (j = 0; j < num; j++) {
 292                         if (!htable_obj_del(&ht, &objs[j]))
 293                                 abort();
 294                         objs[j].key = num*i+j;
 295                         if (!htable_obj_add(&ht, &objs[j]))
 296                                 abort();
 297                 }
 298                 gettimeofday(&stop, NULL);
 299                 if (i != 0)
 300                         printf(" %zu ns\n", normalize(&start, &stop, num));
 301         }
 302
 303         /* Spread out the keys more to try to make it harder. */
 304         printf("Details: reinserting with spread\n");
 305         for (i = 0; i < num; i++) {
 306                 if (!htable_obj_del(&ht, objs[i].self))
 307                         abort();
 308                 objs[i].key = num * 5 + i * 9;
 309                 if (!htable_obj_add(&ht, objs[i].self))
 310                         abort();
 311         }
 312         printf("Details: delete markers %zu, perfect %.0f%%\n",
 313                count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
 314         i = worst_run(&ht.raw, &deleted);
 315         printf("Details: worst run %zu (%zu deleted)\n", i, deleted);
 316
 317         printf("Lookup after churn & spread (match): ");
 318         fflush(stdout);
 319         gettimeofday(&start, NULL);
 320         for (i = 0; i < num; i++) {
 321                 unsigned int n = num * 5 + i * 9;
 322                 if (htable_obj_get(&ht, &n)->self != objs[i].self)
 323                         abort();
 324         }
 325         gettimeofday(&stop, NULL);
 326         printf(" %zu ns\n", normalize(&start, &stop, num));
 327
 328         printf("Lookup after churn & spread (miss): ");
 329         fflush(stdout);
 330         gettimeofday(&start, NULL);
 331         for (i = 0; i < num; i++) {
 332                 unsigned int n = num * (5 + 9) + i * 9;
 333                 if (htable_obj_get(&ht, &n))
 334                         abort();
 335         }
 336         gettimeofday(&stop, NULL);
 337         printf(" %zu ns\n", normalize(&start, &stop, num));
 338
 339         printf("Lookup after churn & spread (random): ");
 340         fflush(stdout);
 341         gettimeofday(&start, NULL);
 342         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
 343                 unsigned int n = num * 5 + j * 9;
 344                 if (htable_obj_get(&ht, &n)->self != &objs[j])
 345                         abort();
 346         }
 347         gettimeofday(&stop, NULL);
 348         printf(" %zu ns\n", normalize(&start, &stop, num));
 349
 350         hashcount = 0;
 351         printf("Deleting half after churn & spread: ");
 352         fflush(stdout);
 353         gettimeofday(&start, NULL);
 354         for (i = 0; i < num; i+=2)
 355                 if (!htable_obj_del(&ht, objs[i].self))
 356                         abort();
 357         gettimeofday(&stop, NULL);
 358         printf(" %zu ns\n", normalize(&start, &stop, num));
 359
 360         printf("Adding (a different) half after churn & spread: ");
 361         fflush(stdout);
 362
 363         for (i = 0; i < num; i+=2)
 364                 objs[i].key = num*6+i*9;
 365
 366         gettimeofday(&start, NULL);
 367         for (i = 0; i < num; i+=2)
 368                 htable_obj_add(&ht, objs[i].self);
 369         gettimeofday(&stop, NULL);
 370         printf(" %zu ns\n", normalize(&start, &stop, num));
 371
 372         printf("Details: delete markers %zu, perfect %.0f%%\n",
 373                count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems);
 374
 375         return 0;
 376 }