src/vppinfra/test_bihash_template.c

   1 /*
   2  * Copyright (c) 2015 Cisco and/or its affiliates.
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15 #include <vppinfra/time.h>
  16 #include <vppinfra/cache.h>
  17 #include <vppinfra/error.h>
  18
  19 #include <vppinfra/bihash_8_8.h>
  20 #include <vppinfra/bihash_template.h>
  21
  22 #include <vppinfra/bihash_template.c>
  23
  24 typedef struct
  25 {
  26   u64 seed;
  27   u32 nbuckets;
  28   u32 nitems;
  29   u32 search_iter;
  30   int careful_delete_tests;
  31   int verbose;
  32   int non_random_keys;
  33   uword *key_hash;
  34   u64 *keys;
  35     BVT (clib_bihash) hash;
  36   clib_time_t clib_time;
  37
  38   unformat_input_t *input;
  39
  40 } test_main_t;
  41
  42 test_main_t test_main;
  43
  44 uword
  45 vl (void *v)
  46 {
  47   return vec_len (v);
  48 }
  49
  50 static clib_error_t *
  51 test_bihash_vec64 (test_main_t * tm)
  52 {
  53   u32 user_buckets = 1228800;
  54   u32 user_memory_size = 209715200;
  55   BVT (clib_bihash_kv) kv;
  56   int i, j;
  57   f64 before;
  58   f64 *cum_times = 0;
  59   BVT (clib_bihash) * h;
  60
  61   h = &tm->hash;
  62
  63   BV (clib_bihash_init) (h, "test", user_buckets, user_memory_size);
  64
  65   before = clib_time_now (&tm->clib_time);
  66
  67   for (j = 0; j < 10; j++)
  68     {
  69       for (i = 1; i <= j * 1000 + 1; i++)
  70         {
  71           kv.key = i;
  72           kv.value = 1;
  73
  74           BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
  75         }
  76
  77       vec_add1 (cum_times, clib_time_now (&tm->clib_time) - before);
  78     }
  79
  80   for (j = 0; j < vec_len (cum_times); j++)
  81     fformat (stdout, "Cum time for %d: %.4f (us)\n", (j + 1) * 1000,
  82              cum_times[j] * 1e6);
  83
  84   return 0;
  85 }
  86
  87 static clib_error_t *
  88 test_bihash (test_main_t * tm)
  89 {
  90   int i, j;
  91   uword *p;
  92   uword total_searches;
  93   f64 before, delta;
  94   BVT (clib_bihash) * h;
  95   BVT (clib_bihash_kv) kv;
  96
  97   h = &tm->hash;
  98
  99   BV (clib_bihash_init) (h, "test", tm->nbuckets, 3ULL << 30);
 100
 101   fformat (stdout, "Pick %lld unique %s keys...\n",
 102            tm->nitems, tm->non_random_keys ? "non-random" : "random");
 103
 104   for (i = 0; i < tm->nitems; i++)
 105     {
 106       u64 rndkey;
 107
 108       if (tm->non_random_keys == 0)
 109         {
 110
 111         again:
 112           rndkey = random_u64 (&tm->seed);
 113
 114           p = hash_get (tm->key_hash, rndkey);
 115           if (p)
 116             goto again;
 117         }
 118       else
 119         rndkey = (u64) (i + 1) << 16;
 120
 121       hash_set (tm->key_hash, rndkey, i + 1);
 122       vec_add1 (tm->keys, rndkey);
 123     }
 124
 125   fformat (stdout, "Add items...\n");
 126   for (i = 0; i < tm->nitems; i++)
 127     {
 128       kv.key = tm->keys[i];
 129       kv.value = i + 1;
 130
 131       BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
 132
 133       if (tm->verbose > 1)
 134         {
 135           fformat (stdout, "--------------------\n");
 136           fformat (stdout, "After adding key %llu value %lld...\n",
 137                    tm->keys[i], (u64) (i + 1));
 138           fformat (stdout, "%U", BV (format_bihash), h,
 139                    2 /* very verbose */ );
 140         }
 141     }
 142
 143   fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ );
 144
 145   fformat (stdout, "Search for items %d times...\n", tm->search_iter);
 146
 147   before = clib_time_now (&tm->clib_time);
 148
 149   for (j = 0; j < tm->search_iter; j++)
 150     {
 151       for (i = 0; i < tm->nitems; i++)
 152         {
 153           kv.key = tm->keys[i];
 154           if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
 155             if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
 156               clib_warning ("[%d] search for key %lld failed unexpectedly\n",
 157                             i, tm->keys[i]);
 158           if (kv.value != (u64) (i + 1))
 159             clib_warning
 160               ("[%d] search for key %lld returned %lld, not %lld\n", i,
 161                tm->keys, kv.value, (u64) (i + 1));
 162         }
 163     }
 164
 165   delta = clib_time_now (&tm->clib_time) - before;
 166   total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 167
 168   if (delta > 0)
 169     fformat (stdout, "%.f searches per second\n",
 170              ((f64) total_searches) / delta);
 171
 172   fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta);
 173
 174   fformat (stdout, "Standard E-hash search for items %d times...\n",
 175            tm->search_iter);
 176
 177   before = clib_time_now (&tm->clib_time);
 178
 179   for (j = 0; j < tm->search_iter; j++)
 180     {
 181       for (i = 0; i < tm->nitems; i++)
 182         {
 183           p = hash_get (tm->key_hash, tm->keys[i]);
 184           if (p == 0 || p[0] != (uword) (i + 1))
 185             clib_warning ("ugh, couldn't find %lld\n", tm->keys[i]);
 186         }
 187     }
 188
 189   delta = clib_time_now (&tm->clib_time) - before;
 190   total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 191
 192   fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta);
 193
 194   if (delta > 0)
 195     fformat (stdout, "%.f searches per second\n",
 196              ((f64) total_searches) / delta);
 197
 198   fformat (stdout, "Delete items...\n");
 199
 200   for (i = 0; i < tm->nitems; i++)
 201     {
 202       int j;
 203       int rv;
 204
 205       kv.key = tm->keys[i];
 206       kv.value = (u64) (i + 1);
 207       rv = BV (clib_bihash_add_del) (h, &kv, 0 /* is_add */ );
 208
 209       if (rv < 0)
 210         clib_warning ("delete key %lld not ok but should be", tm->keys[i]);
 211
 212       if (tm->careful_delete_tests)
 213         {
 214           for (j = 0; j < tm->nitems; j++)
 215             {
 216               kv.key = tm->keys[j];
 217               rv = BV (clib_bihash_search) (h, &kv, &kv);
 218               if (j <= i && rv >= 0)
 219                 {
 220                   clib_warning
 221                     ("i %d j %d search ok but should not be, value %lld",
 222                      i, j, kv.value);
 223                 }
 224               if (j > i && rv < 0)
 225                 {
 226                   clib_warning ("i %d j %d search not ok but should be",
 227                                 i, j);
 228                 }
 229             }
 230         }
 231     }
 232
 233   fformat (stdout, "After deletions, should be empty...\n");
 234
 235   fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ );
 236   return 0;
 237 }
 238
 239 clib_error_t *
 240 test_bihash_main (test_main_t * tm)
 241 {
 242   unformat_input_t *i = tm->input;
 243   clib_error_t *error;
 244   int test_vec64 = 0;
 245
 246   while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
 247     {
 248       if (unformat (i, "seed %u", &tm->seed))
 249         ;
 250
 251       else if (unformat (i, "nbuckets %d", &tm->nbuckets))
 252         ;
 253       else if (unformat (i, "non-random-keys"))
 254         tm->non_random_keys = 1;
 255       else if (unformat (i, "nitems %d", &tm->nitems))
 256         ;
 257       else if (unformat (i, "careful %d", &tm->careful_delete_tests))
 258         ;
 259       else if (unformat (i, "verbose %d", &tm->verbose))
 260         ;
 261       else if (unformat (i, "search %d", &tm->search_iter))
 262         ;
 263       else if (unformat (i, "vec64"))
 264         test_vec64 = 1;
 265       else if (unformat (i, "verbose"))
 266         tm->verbose = 1;
 267       else
 268         return clib_error_return (0, "unknown input '%U'",
 269                                   format_unformat_error, i);
 270     }
 271
 272   if (test_vec64)
 273     error = test_bihash_vec64 (tm);
 274   else
 275     error = test_bihash (tm);
 276
 277   return error;
 278 }
 279
 280 #ifdef CLIB_UNIX
 281 int
 282 main (int argc, char *argv[])
 283 {
 284   unformat_input_t i;
 285   clib_error_t *error;
 286   test_main_t *tm = &test_main;
 287
 288   clib_mem_init (0, 3ULL << 30);
 289
 290   tm->input = &i;
 291   tm->seed = 0xdeaddabe;
 292
 293   tm->nbuckets = 2;
 294   tm->nitems = 5;
 295   tm->verbose = 1;
 296   tm->search_iter = 1;
 297   tm->careful_delete_tests = 0;
 298   tm->key_hash = hash_create (0, sizeof (uword));
 299   clib_time_init (&tm->clib_time);
 300
 301   unformat_init_command_line (&i, argv);
 302   error = test_bihash_main (tm);
 303   unformat_free (&i);
 304
 305   if (error)
 306     {
 307       clib_error_report (error);
 308       return 1;
 309     }
 310   return 0;
 311 }
 312 #endif /* CLIB_UNIX */
 313
 314 /*
 315  * fd.io coding-style-patch-verification: ON
 316  *
 317  * Local Variables:
 318  * eval: (c-set-style "gnu")
 319  * End:
 320  */