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 <time.h>
   8 #include <unistd.h>
   9 #include <sys/time.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 unsigned int *key1, const unsigned int *key2)
  32 {
  33         return *key1 == *key2;
  34 }
  35
  36 HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, 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 timeval *start,
  98                         const struct timeval *stop,
  99                         unsigned int num)
 100 {
 101         struct timeval diff;
 102
 103         timersub(stop, start, &diff);
 104
 105         /* Floating point is more accurate here. */
 106         return (double)(diff.tv_sec * 1000000 + diff.tv_usec)
 107                 / num * 1000;
 108 }
 109
 110 static size_t worst_run(struct htable *ht, size_t *deleted)
 111 {
 112         size_t longest = 0, len = 0, this_del = 0, i;
 113
 114         *deleted = 0;
 115         /* This doesn't take into account end-wrap, but gives an idea. */
 116         for (i = 0; i < ((size_t)1 << ht->bits); i++) {
 117                 if (ht->table[i]) {
 118                         len++;
 119                         if (ht->table[i] == HTABLE_DELETED)
 120                                 this_del++;
 121                 } else {
 122                         if (len > longest) {
 123                                 longest = len;
 124                                 *deleted = this_del;
 125                         }
 126                         len = 0;
 127                         this_del = 0;
 128                 }
 129         }
 130         return longest;
 131 }
 132
 133 int main(int argc, char *argv[])
 134 {
 135         struct object *objs;
 136         size_t i, j, num, deleted;
 137         struct timeval start, stop;
 138         struct htable_obj *ht;
 139         struct htable *htr;
 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         ht = htable_obj_new();
 155         htr = (void *)ht;
 156
 157         printf("Initial insert: ");
 158         fflush(stdout);
 159         gettimeofday(&start, NULL);
 160         for (i = 0; i < num; i++)
 161                 htable_obj_add(ht, objs[i].self);
 162         gettimeofday(&stop, NULL);
 163         printf(" %zu ns\n", normalize(&start, &stop, num));
 164         printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n",
 165                1U << htr->bits, popcount(htr->common_mask),
 166                perfect(htr) * 100.0 / htr->elems);
 167
 168         if (make_dumb) {
 169                 /* Screw with mask, to hobble us. */
 170                 update_common(htr, (void *)~htr->common_bits);
 171                 printf("Details: DUMB MODE: mask bits %u\n",
 172                        popcount(htr->common_mask));
 173         }
 174
 175         printf("Initial lookup (match): ");
 176         fflush(stdout);
 177         gettimeofday(&start, NULL);
 178         for (i = 0; i < num; i++)
 179                 if (htable_obj_get(ht, &i)->self != objs[i].self)
 180                         abort();
 181         gettimeofday(&stop, NULL);
 182         printf(" %zu ns\n", normalize(&start, &stop, num));
 183
 184         printf("Initial lookup (miss): ");
 185         fflush(stdout);
 186         gettimeofday(&start, NULL);
 187         for (i = 0; i < num; i++) {
 188                 unsigned int n = i + num;
 189                 if (htable_obj_get(ht, &n))
 190                         abort();
 191         }
 192         gettimeofday(&stop, NULL);
 193         printf(" %zu ns\n", normalize(&start, &stop, num));
 194
 195         /* Lookups in order are very cache-friendly for judy; try random */
 196         printf("Initial lookup (random): ");
 197         fflush(stdout);
 198         gettimeofday(&start, NULL);
 199         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 200                 if (htable_obj_get(ht, &j)->self != &objs[j])
 201                         abort();
 202         gettimeofday(&stop, NULL);
 203         printf(" %zu ns\n", normalize(&start, &stop, num));
 204
 205         hashcount = 0;
 206         printf("Initial delete all: ");
 207         fflush(stdout);
 208         gettimeofday(&start, NULL);
 209         for (i = 0; i < num; i++)
 210                 if (!htable_obj_del(ht, objs[i].self))
 211                         abort();
 212         gettimeofday(&stop, NULL);
 213         printf(" %zu ns\n", normalize(&start, &stop, num));
 214         printf("Details: rehashes %zu\n", hashcount);
 215
 216         printf("Initial re-inserting: ");
 217         fflush(stdout);
 218         gettimeofday(&start, NULL);
 219         for (i = 0; i < num; i++)
 220                 htable_obj_add(ht, objs[i].self);
 221         gettimeofday(&stop, NULL);
 222         printf(" %zu ns\n", normalize(&start, &stop, num));
 223
 224         hashcount = 0;
 225         printf("Deleting first half: ");
 226         fflush(stdout);
 227         gettimeofday(&start, NULL);
 228         for (i = 0; i < num; i+=2)
 229                 if (!htable_obj_del(ht, objs[i].self))
 230                         abort();
 231         gettimeofday(&stop, NULL);
 232         printf(" %zu ns\n", normalize(&start, &stop, num));
 233
 234         printf("Details: rehashes %zu, delete markers %zu\n",
 235                hashcount, count_deleted(htr));
 236
 237         printf("Adding (a different) half: ");
 238         fflush(stdout);
 239
 240         for (i = 0; i < num; i+=2)
 241                 objs[i].key = num+i;
 242
 243         gettimeofday(&start, NULL);
 244         for (i = 0; i < num; i+=2)
 245                 htable_obj_add(ht, objs[i].self);
 246         gettimeofday(&stop, NULL);
 247         printf(" %zu ns\n", normalize(&start, &stop, num));
 248
 249         printf("Details: delete markers %zu, perfect %.0f%%\n",
 250                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
 251
 252         printf("Lookup after half-change (match): ");
 253         fflush(stdout);
 254         gettimeofday(&start, NULL);
 255         for (i = 1; i < num; i+=2)
 256                 if (htable_obj_get(ht, &i)->self != objs[i].self)
 257                         abort();
 258         for (i = 0; i < num; i+=2) {
 259                 unsigned int n = i + num;
 260                 if (htable_obj_get(ht, &n)->self != objs[i].self)
 261                         abort();
 262         }
 263         gettimeofday(&stop, NULL);
 264         printf(" %zu ns\n", normalize(&start, &stop, num));
 265
 266         printf("Lookup after half-change (miss): ");
 267         fflush(stdout);
 268         gettimeofday(&start, NULL);
 269         for (i = 0; i < num; i++) {
 270                 unsigned int n = i + num * 2;
 271                 if (htable_obj_get(ht, &n))
 272                         abort();
 273         }
 274         gettimeofday(&stop, NULL);
 275         printf(" %zu ns\n", normalize(&start, &stop, num));
 276
 277         /* Hashtables with delete markers can fill with markers over time.
 278          * so do some changes to see how it operates in long-term. */
 279         for (i = 0; i < 5; i++) {
 280                 if (i == 0) {
 281                         /* We don't measure this: jmap is different. */
 282                         printf("Details: initial churn\n");
 283                 } else {
 284                         printf("Churning %s time: ",
 285                                i == 1 ? "second"
 286                                : i == 2 ? "third"
 287                                : i == 3 ? "fourth"
 288                                : "fifth");
 289                         fflush(stdout);
 290                 }
 291                 gettimeofday(&start, NULL);
 292                 for (j = 0; j < num; j++) {
 293                         if (!htable_obj_del(ht, &objs[j]))
 294                                 abort();
 295                         objs[j].key = num*i+j;
 296                         if (!htable_obj_add(ht, &objs[j]))
 297                                 abort();
 298                 }
 299                 gettimeofday(&stop, NULL);
 300                 if (i != 0)
 301                         printf(" %zu ns\n", normalize(&start, &stop, num));
 302         }
 303
 304         /* Spread out the keys more to try to make it harder. */
 305         printf("Details: reinserting with spread\n");
 306         for (i = 0; i < num; i++) {
 307                 if (!htable_obj_del(ht, objs[i].self))
 308                         abort();
 309                 objs[i].key = num * 5 + i * 9;
 310                 if (!htable_obj_add(ht, objs[i].self))
 311                         abort();
 312         }
 313         printf("Details: delete markers %zu, perfect %.0f%%\n",
 314                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
 315         i = worst_run(htr, &deleted);
 316         printf("Details: worst run %zu (%zu deleted)\n", i, deleted);
 317
 318         printf("Lookup after churn & spread (match): ");
 319         fflush(stdout);
 320         gettimeofday(&start, NULL);
 321         for (i = 0; i < num; i++) {
 322                 unsigned int n = num * 5 + i * 9;
 323                 if (htable_obj_get(ht, &n)->self != objs[i].self)
 324                         abort();
 325         }
 326         gettimeofday(&stop, NULL);
 327         printf(" %zu ns\n", normalize(&start, &stop, num));
 328
 329         printf("Lookup after churn & spread (miss): ");
 330         fflush(stdout);
 331         gettimeofday(&start, NULL);
 332         for (i = 0; i < num; i++) {
 333                 unsigned int n = num * (5 + 9) + i * 9;
 334                 if (htable_obj_get(ht, &n))
 335                         abort();
 336         }
 337         gettimeofday(&stop, NULL);
 338         printf(" %zu ns\n", normalize(&start, &stop, num));
 339
 340         printf("Lookup after churn & spread (random): ");
 341         fflush(stdout);
 342         gettimeofday(&start, NULL);
 343         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) {
 344                 unsigned int n = num * 5 + j * 9;
 345                 if (htable_obj_get(ht, &n)->self != &objs[j])
 346                         abort();
 347         }
 348         gettimeofday(&stop, NULL);
 349         printf(" %zu ns\n", normalize(&start, &stop, num));
 350
 351         hashcount = 0;
 352         printf("Deleting half after churn & spread: ");
 353         fflush(stdout);
 354         gettimeofday(&start, NULL);
 355         for (i = 0; i < num; i+=2)
 356                 if (!htable_obj_del(ht, objs[i].self))
 357                         abort();
 358         gettimeofday(&stop, NULL);
 359         printf(" %zu ns\n", normalize(&start, &stop, num));
 360
 361         printf("Adding (a different) half after churn & spread: ");
 362         fflush(stdout);
 363
 364         for (i = 0; i < num; i+=2)
 365                 objs[i].key = num*6+i*9;
 366
 367         gettimeofday(&start, NULL);
 368         for (i = 0; i < num; i+=2)
 369                 htable_obj_add(ht, objs[i].self);
 370         gettimeofday(&stop, NULL);
 371         printf(" %zu ns\n", normalize(&start, &stop, num));
 372
 373         printf("Details: delete markers %zu, perfect %.0f%%\n",
 374                count_deleted(htr), perfect(htr) * 100.0 / htr->elems);
 375
 376         return 0;
 377 }