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