src/vppinfra/test_bihash_vec88.c

   1 /*
   2  * Copyright (c) 2017 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_vec8_8.h>
  20 #include <vppinfra/bihash_template.h>
  21
  22 #include <vppinfra/bihash_template.c>
  23
  24 typedef struct
  25 {
  26   u32 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   u8 **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 (test_main_t * tm)
  52 {
  53   int i, j;
  54   uword *p;
  55   uword total_searches;
  56   f64 before, delta;
  57   BVT (clib_bihash) * h;
  58   BVT (clib_bihash_kv) kv;
  59
  60   h = &tm->hash;
  61
  62   BV (clib_bihash_init) (h, "test", tm->nbuckets, 3ULL << 30);
  63
  64   fformat (stdout, "Pick %lld unique %s keys...\n",
  65            tm->nitems, tm->non_random_keys ? "non-random" : "random");
  66
  67   for (i = 0; i < tm->nitems; i++)
  68     {
  69       u8 *random_vec8;
  70
  71       if (tm->non_random_keys == 0)
  72         {
  73           u32 len;
  74
  75         again:
  76           do
  77             {
  78               len = random_u32 (&tm->seed);
  79               len %= 64;
  80             }
  81           while (len == 0);
  82
  83           random_vec8 = random_string (&tm->seed, len);
  84           vec_add1 (random_vec8, 0);
  85
  86           p = hash_get_mem (tm->key_hash, random_vec8);
  87           if (p)
  88             goto again;
  89         }
  90       else
  91         {
  92           random_vec8 = format (0, "String%d%c", i, 0);
  93         }
  94
  95       hash_set_mem (tm->key_hash, random_vec8, i + 1);
  96       vec_add1 (tm->keys, random_vec8);
  97     }
  98
  99   fformat (stdout, "Add items...\n");
 100   for (i = 0; i < tm->nitems; i++)
 101     {
 102       kv.key = (u64) tm->keys[i];
 103       kv.value = i + 1;
 104
 105       BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ );
 106
 107       if (tm->verbose > 1)
 108         {
 109           fformat (stdout, "--------------------\n");
 110           fformat (stdout, "After adding key %llu value %lld...\n",
 111                    tm->keys[i], (u64) (i + 1));
 112           fformat (stdout, "%U", BV (format_bihash), h,
 113                    2 /* very verbose */ );
 114         }
 115     }
 116
 117   fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ );
 118
 119   fformat (stdout, "Search for items %d times...\n", tm->search_iter);
 120
 121   before = clib_time_now (&tm->clib_time);
 122
 123   for (j = 0; j < tm->search_iter; j++)
 124     {
 125       for (i = 0; i < tm->nitems; i++)
 126         {
 127           kv.key = (u64) tm->keys[i];
 128           if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
 129             if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
 130               clib_warning ("[%d] search for key %lld failed unexpectedly\n",
 131                             i, tm->keys[i]);
 132           if (kv.value != (u64) (i + 1))
 133             clib_warning
 134               ("[%d] search for key %lld returned %lld, not %lld\n", i,
 135                tm->keys, kv.value, (u64) (i + 1));
 136         }
 137     }
 138
 139   delta = clib_time_now (&tm->clib_time) - before;
 140   total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 141
 142   if (delta > 0)
 143     fformat (stdout, "%.f searches per second\n",
 144              ((f64) total_searches) / delta);
 145
 146   fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta);
 147
 148   fformat (stdout, "Standard E-hash search for items %d times...\n",
 149            tm->search_iter);
 150
 151   before = clib_time_now (&tm->clib_time);
 152
 153   for (j = 0; j < tm->search_iter; j++)
 154     {
 155       for (i = 0; i < tm->nitems; i++)
 156         {
 157           p = hash_get_mem (tm->key_hash, tm->keys[i]);
 158           if (p == 0 || p[0] != (uword) (i + 1))
 159             clib_warning ("ugh, couldn't find %lld\n", tm->keys[i]);
 160         }
 161     }
 162
 163   delta = clib_time_now (&tm->clib_time) - before;
 164   total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 165
 166   fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta);
 167
 168   if (delta > 0)
 169     fformat (stdout, "%.f searches per second\n",
 170              ((f64) total_searches) / delta);
 171
 172   fformat (stdout, "Delete items...\n");
 173
 174   for (i = 0; i < tm->nitems; i++)
 175     {
 176       int j;
 177       int rv;
 178
 179       kv.key = (u64) tm->keys[i];
 180       kv.value = (u64) (i + 1);
 181       rv = BV (clib_bihash_add_del) (h, &kv, 0 /* is_add */ );
 182
 183       if (rv < 0)
 184         clib_warning ("delete key %lld not ok but should be", tm->keys[i]);
 185
 186       if (tm->careful_delete_tests)
 187         {
 188           for (j = 0; j < tm->nitems; j++)
 189             {
 190               kv.key = (u64) tm->keys[j];
 191               rv = BV (clib_bihash_search) (h, &kv, &kv);
 192               if (j <= i && rv >= 0)
 193                 {
 194                   clib_warning
 195                     ("i %d j %d search ok but should not be, value %lld",
 196                      i, j, kv.value);
 197                 }
 198               if (j > i && rv < 0)
 199                 {
 200                   clib_warning ("i %d j %d search not ok but should be",
 201                                 i, j);
 202                 }
 203             }
 204         }
 205     }
 206
 207   fformat (stdout, "After deletions, should be empty...\n");
 208
 209   fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ );
 210   return 0;
 211 }
 212
 213 clib_error_t *
 214 test_bihash_main (test_main_t * tm)
 215 {
 216   unformat_input_t *i = tm->input;
 217   clib_error_t *error;
 218   int which = 0;
 219
 220   while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
 221     {
 222       if (unformat (i, "seed %u", &tm->seed))
 223         ;
 224
 225       else if (unformat (i, "nbuckets %d", &tm->nbuckets))
 226         ;
 227       else if (unformat (i, "non-random-keys"))
 228         tm->non_random_keys = 1;
 229       else if (unformat (i, "nitems %d", &tm->nitems))
 230         ;
 231       else if (unformat (i, "careful %d", &tm->careful_delete_tests))
 232         ;
 233       else if (unformat (i, "verbose %d", &tm->verbose))
 234         ;
 235       else if (unformat (i, "search %d", &tm->search_iter))
 236         ;
 237       else if (unformat (i, "vec64"))
 238         which = 1;
 239       else if (unformat (i, "cache"))
 240         which = 2;
 241
 242       else if (unformat (i, "verbose"))
 243         tm->verbose = 1;
 244       else
 245         return clib_error_return (0, "unknown input '%U'",
 246                                   format_unformat_error, i);
 247     }
 248
 249   switch (which)
 250     {
 251     case 0:
 252       error = test_bihash (tm);
 253       break;
 254
 255     default:
 256       return clib_error_return (0, "no such test?");
 257     }
 258
 259   return error;
 260 }
 261
 262 #ifdef CLIB_UNIX
 263 int
 264 main (int argc, char *argv[])
 265 {
 266   unformat_input_t i;
 267   clib_error_t *error;
 268   test_main_t *tm = &test_main;
 269
 270   clib_mem_init (0, 3ULL << 30);
 271
 272   tm->input = &i;
 273   tm->seed = 0xdeaddabe;
 274
 275   tm->nbuckets = 2;
 276   tm->nitems = 5;
 277   tm->verbose = 1;
 278   tm->search_iter = 1;
 279   tm->careful_delete_tests = 0;
 280   tm->key_hash = hash_create_string (0, sizeof (uword));
 281   clib_time_init (&tm->clib_time);
 282
 283   unformat_init_command_line (&i, argv);
 284   error = test_bihash_main (tm);
 285   unformat_free (&i);
 286
 287   if (error)
 288     {
 289       clib_error_report (error);
 290       return 1;
 291     }
 292   return 0;
 293 }
 294 #endif /* CLIB_UNIX */
 295
 296 /*
 297  * fd.io coding-style-patch-verification: ON
 298  *
 299  * Local Variables:
 300  * eval: (c-set-style "gnu")
 301  * End:
 302  */