git.ozlabs.org Git - ccan/blob - ccan/btree/test/run-benchmark.c

   1 /* Include the main header first, to test it works */
   2 #include <ccan/btree/btree.h>
   3 /* Include the C files directly. */
   4 #include <ccan/btree/btree.c>
   5 #include <ccan/tap/tap.h>
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10
  11 uint32_t rand32_state = 0;
  12
  13 /*
  14  * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
  15  * Uses the BCPL linear congruential generator method.
  16  */
  17 static uint32_t rand32(void)
  18 {
  19         rand32_state *= (uint32_t)0x7FF8A3ED;
  20         rand32_state += (uint32_t)0x2AA01D31;
  21         return rand32_state;
  22 }
  23
  24 static void scramble(void *base, size_t nmemb, size_t size)
  25 {
  26         char *i = base;
  27         char *o;
  28         size_t sd;
  29         for (;nmemb>1;nmemb--) {
  30                 o = i + size*(rand32()%nmemb);
  31                 for (sd=size;sd--;) {
  32                         char tmp = *o;
  33                         *o++ = *i;
  34                         *i++ = tmp;
  35                 }
  36         }
  37 }
  38
  39 struct test_item {
  40         size_t key;
  41         uint32_t value;
  42 };
  43
  44 /* For ordering a btree of test_item pointers. */
  45 static btree_search_implement (
  46         order_by_key,
  47         const struct test_item *,
  48         ,
  49         a == b,
  50         a < b
  51 )
  52
  53 /* For qsorting an array of test_item pointers. */
  54 static int compare_test_item(const void *ap, const void *bp)
  55 {
  56         const struct test_item *a = *(const struct test_item * const*)ap;
  57         const struct test_item *b = *(const struct test_item * const*)bp;
  58         if (a == b)
  59                 return 0;
  60         if (a < b)
  61                 return -1;
  62         return 1;
  63 }
  64
  65 /*
  66  * If lr == 0, make sure iter points to the item given.
  67  * If lr == 1, make sure iter points to after the item given.
  68  */
  69 static int check_iter(btree_iterator iter_orig, const void *item, int lr)
  70 {
  71         btree_iterator iter = {*iter_orig};
  72         if (iter->item != item)
  73                 return 0;
  74         if (lr) {
  75                 if (!btree_prev(iter))
  76                         return 0;
  77         } else {
  78                 if (!btree_deref(iter))
  79                         return 0;
  80         }
  81         if (iter->item != item)
  82                 return 0;
  83         if (iter->node->item[iter->k] != iter->item)
  84                 return 0;
  85
  86         return 1;
  87 }
  88
  89 /*
  90  * Returns 1 on insert, 0 on duplicate,
  91  * -1 on bad iterator returned by find, and
  92  * -2 on bad iterator returned by insert.
  93  */
  94 static int insert_test_item(struct btree *btree, struct test_item *item)
  95 {
  96         btree_iterator iter;
  97         int lr;
  98
  99         /* Find the first or last matching item, randomly choosing between the two. */
 100         lr = rand32() & 1;
 101         if (btree_find_lr(btree, item, iter, lr)) {
 102                 if (!check_iter(iter, item, lr))
 103                         return -1;
 104                 return 0;
 105         }
 106
 107         btree_insert_at(iter, item);
 108
 109         if (iter->item != item)
 110                 return -2;
 111
 112         return 1;
 113 }
 114
 115 /*
 116  * Returns 1 on remove, 0 on missing,
 117  * -1 on bad iterator returned by find, and
 118  * -2 on bad iterator returned by remove.
 119  */
 120 static int remove_test_item(struct btree *btree, struct test_item *item)
 121 {
 122         btree_iterator iter;
 123
 124         if (!btree_find(btree, item, iter))
 125                 return 0;
 126
 127         if (!check_iter(iter, item, 0))
 128                 return -1;
 129
 130         btree_remove_at(iter);
 131
 132         if (iter->item != item)
 133                 return -2;
 134
 135         return 1;
 136 }
 137
 138 static struct {
 139         size_t success;
 140
 141         size_t excess;
 142         size_t duplicate;
 143         size_t missing;
 144         size_t incorrect;
 145         size_t failed;
 146
 147         size_t bad_iter_find;
 148         size_t bad_iter_insert;
 149         size_t bad_iter_remove;
 150         size_t bad_iter_next;
 151 } stats;
 152
 153 static void clear_stats(void) {
 154         memset(&stats, 0, sizeof(stats));
 155 }
 156
 157 static int print_stats(const char *success_label, size_t expected_success) {
 158         int failed = 0;
 159
 160         printf("      %s:  \t%zu\n", success_label, stats.success);
 161         if (stats.success != expected_success)
 162                 failed = 1;
 163
 164         if (stats.excess)
 165                 failed = 1, printf("      Excess:     \t%zu\n", stats.excess);
 166         if (stats.duplicate)
 167                 failed = 1, printf("      Duplicate:  \t%zu\n", stats.duplicate);
 168         if (stats.missing)
 169                 failed = 1, printf("      Missing:    \t%zu\n", stats.missing);
 170         if (stats.incorrect)
 171                 failed = 1, printf("      Incorrect:  \t%zu\n", stats.incorrect);
 172         if (stats.failed)
 173                 failed = 1, printf("      Failed:     \t%zu\n", stats.failed);
 174
 175         if (stats.bad_iter_find || stats.bad_iter_insert ||
 176             stats.bad_iter_remove || stats.bad_iter_next) {
 177                 failed = 1;
 178                 printf("      Bad iterators yielded by:\n");
 179                 if (stats.bad_iter_find)
 180                         printf("          btree_find_lr(): %zu\n", stats.bad_iter_find);
 181                 if (stats.bad_iter_insert)
 182                         printf("          btree_insert_at(): %zu\n", stats.bad_iter_insert);
 183                 if (stats.bad_iter_remove)
 184                         printf("          btree_remove_at(): %zu\n", stats.bad_iter_remove);
 185                 if (stats.bad_iter_next)
 186                         printf("          btree_next(): %zu\n", stats.bad_iter_next);
 187         }
 188
 189         return !failed;
 190 }
 191
 192 static void benchmark(size_t max_per_trial, size_t round_count, int random_counts)
 193 {
 194         struct test_item **test_item;
 195         struct test_item *test_item_array;
 196         size_t i, count;
 197         size_t round = 0;
 198
 199         test_item = malloc(max_per_trial * sizeof(*test_item));
 200         test_item_array = malloc(max_per_trial * sizeof(*test_item_array));
 201
 202         if (!test_item || !test_item_array) {
 203                 fail("Not enough memory for %zu keys per trial\n",
 204                         max_per_trial);
 205                 return;
 206         }
 207
 208         /* Initialize test_item pointers. */
 209         for (i=0; i<max_per_trial; i++)
 210                 test_item[i] = &test_item_array[i];
 211
 212         /*
 213          * If round_count is not zero, run round_count trials.
 214          * Otherwise, run forever.
 215          */
 216         for (round = 1; round_count==0 || round <= round_count; round++) {
 217                 struct btree *btree;
 218                 btree_iterator iter;
 219
 220                 printf("Round %zu\n", round);
 221
 222                 if (random_counts)
 223                         count = rand32() % (max_per_trial+1);
 224                 else
 225                         count = max_per_trial;
 226
 227                 /*
 228                  * Initialize test items by giving them sequential keys and
 229                  * random values. Scramble them so the order of insertion
 230                  * will be random.
 231                  */
 232                 for (i=0; i<count; i++) {
 233                         test_item[i]->key = i;
 234                         test_item[i]->value = rand32();
 235                 }
 236                 scramble(test_item, count, sizeof(*test_item));
 237
 238                 btree = btree_new(order_by_key);
 239
 240                 clear_stats();
 241                 printf("   Inserting %zu items...\n", count);
 242                 for (i=0; i<count; i++) {
 243                         switch (insert_test_item(btree, test_item[i])) {
 244                                 case 1: stats.success++; break;
 245                                 case 0: stats.duplicate++; break;
 246                                 case -1: stats.bad_iter_find++; break;
 247                                 case -2: stats.bad_iter_insert++; break;
 248                                 default: stats.failed++; break;
 249                         }
 250                 }
 251                 ok1(print_stats("Inserted", count));
 252
 253                 scramble(test_item, count, sizeof(*test_item));
 254
 255                 printf("   Finding %zu items...\n", count);
 256                 clear_stats();
 257                 for (i=0; i<count; i++) {
 258                         int lr = rand32() & 1;
 259
 260                         if (!btree_find_lr(btree, test_item[i], iter, lr)) {
 261                                 stats.missing++;
 262                                 continue;
 263                         }
 264
 265                         if (!check_iter(iter, test_item[i], lr)) {
 266                                 stats.bad_iter_find++;
 267                                 continue;
 268                         }
 269
 270                         stats.success++;
 271                 }
 272                 ok1(print_stats("Retrieved", count));
 273
 274                 qsort(test_item, count, sizeof(*test_item), compare_test_item);
 275
 276                 printf("   Traversing forward through %zu items...\n", count);
 277                 clear_stats();
 278                 i = 0;
 279                 for (btree_begin(btree, iter); btree_next(iter);) {
 280                         if (i >= count) {
 281                                 stats.excess++;
 282                                 continue;
 283                         }
 284
 285                         if (iter->item == test_item[i])
 286                                 stats.success++;
 287                         else
 288                                 stats.incorrect++;
 289
 290                         i++;
 291                 }
 292                 ok1(print_stats("Retrieved", count));
 293
 294                 printf("   Traversing backward through %zu items...\n", count);
 295                 clear_stats();
 296                 i = count;
 297                 for (btree_end(btree, iter); btree_prev(iter);) {
 298                         if (!i) {
 299                                 stats.excess++;
 300                                 continue;
 301                         }
 302                         i--;
 303
 304                         if (iter->item == test_item[i])
 305                                 stats.success++;
 306                         else
 307                                 stats.incorrect++;
 308                 }
 309                 ok1(print_stats("Retrieved", count));
 310
 311                 ok1(btree->count == count);
 312
 313                 //static int remove_test_item(struct btree *btree, struct test_item *item);
 314                 scramble(test_item, count, sizeof(*test_item));
 315
 316                 printf("   Deleting %zu items...\n", count);
 317                 clear_stats();
 318                 for (i=0; i<count; i++) {
 319                         int s = remove_test_item(btree, test_item[i]);
 320                         if (s != 1)
 321                                 printf("remove_test_item failed\n");
 322                         switch (s) {
 323                                 case 1: stats.success++; break;
 324                                 case 0: stats.missing++; break;
 325                                 case -1: stats.bad_iter_find++; break;
 326                                 case -2: stats.bad_iter_remove++; break;
 327                                 default: stats.failed++; break;
 328                         }
 329                 }
 330                 ok1(btree->count == 0);
 331                 ok1(print_stats("Deleted", count));
 332                 ok1(btree->root->depth == 0 && btree->root->count == 0);
 333
 334                 btree_delete(btree);
 335         }
 336
 337         free(test_item);
 338         free(test_item_array);
 339 }
 340
 341 int main(void)
 342 {
 343         plan_tests(32);
 344
 345         benchmark(300000, 4, 0);
 346
 347         return exit_status();
 348 }