Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 24 | typedef struct |
| 25 | { |
Filip Tehlar | 397fd7d | 2016-10-26 14:31:24 +0200 | [diff] [blame] | 26 | u64 seed; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 27 | u32 nbuckets; |
| 28 | u32 nitems; |
| 29 | u32 search_iter; |
| 30 | int careful_delete_tests; |
| 31 | int verbose; |
| 32 | int non_random_keys; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 33 | uword *key_hash; |
| 34 | u64 *keys; |
| 35 | BVT (clib_bihash) hash; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 36 | clib_time_t clib_time; |
| 37 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 38 | unformat_input_t *input; |
| 39 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 40 | } test_main_t; |
| 41 | |
| 42 | test_main_t test_main; |
| 43 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 44 | uword |
| 45 | vl (void *v) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 46 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 47 | return vec_len (v); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 48 | } |
| 49 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 50 | static clib_error_t * |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 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 * |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 88 | test_bihash (test_main_t * tm) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 89 | { |
| 90 | int i, j; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 91 | uword *p; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 92 | uword total_searches; |
| 93 | f64 before, delta; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 94 | BVT (clib_bihash) * h; |
| 95 | BVT (clib_bihash_kv) kv; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 96 | |
| 97 | h = &tm->hash; |
| 98 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 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"); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 103 | |
| 104 | for (i = 0; i < tm->nitems; i++) |
| 105 | { |
| 106 | u64 rndkey; |
| 107 | |
| 108 | if (tm->non_random_keys == 0) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 109 | { |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 110 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 111 | again: |
| 112 | rndkey = random_u64 (&tm->seed); |
| 113 | |
| 114 | p = hash_get (tm->key_hash, rndkey); |
| 115 | if (p) |
| 116 | goto again; |
| 117 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 118 | else |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 119 | rndkey = (u64) (i + 1) << 16; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 120 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 121 | hash_set (tm->key_hash, rndkey, i + 1); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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]; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 129 | kv.value = i + 1; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 130 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 131 | BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ ); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 132 | |
| 133 | if (tm->verbose > 1) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 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 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 141 | } |
| 142 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 143 | fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ ); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 | { |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 151 | for (i = 0; i < tm->nitems; i++) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 152 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 153 | kv.key = tm->keys[i]; |
| 154 | if (BV (clib_bihash_search) (h, &kv, &kv) < 0) |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 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]); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 158 | if (kv.value != (u64) (i + 1)) |
Dave Barach | 5e6b958 | 2016-12-12 15:37:29 -0500 | [diff] [blame] | 159 | clib_warning |
| 160 | ("[%d] search for key %lld returned %lld, not %lld\n", i, |
| 161 | tm->keys, kv.value, (u64) (i + 1)); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 162 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 163 | } |
| 164 | |
| 165 | delta = clib_time_now (&tm->clib_time) - before; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 166 | total_searches = (uword) tm->search_iter * (uword) tm->nitems; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 167 | |
| 168 | if (delta > 0) |
| 169 | fformat (stdout, "%.f searches per second\n", |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 170 | ((f64) total_searches) / delta); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 171 | |
| 172 | fformat (stdout, "%lld searches in %.6f seconds\n", total_searches, delta); |
| 173 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 174 | fformat (stdout, "Standard E-hash search for items %d times...\n", |
| 175 | tm->search_iter); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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++) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 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 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 187 | } |
| 188 | |
| 189 | delta = clib_time_now (&tm->clib_time) - before; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 190 | total_searches = (uword) tm->search_iter * (uword) tm->nitems; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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", |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 196 | ((f64) total_searches) / delta); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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]; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 206 | kv.value = (u64) (i + 1); |
| 207 | rv = BV (clib_bihash_add_del) (h, &kv, 0 /* is_add */ ); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 208 | |
| 209 | if (rv < 0) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 210 | clib_warning ("delete key %lld not ok but should be", tm->keys[i]); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 211 | |
| 212 | if (tm->careful_delete_tests) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 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 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 231 | } |
| 232 | |
| 233 | fformat (stdout, "After deletions, should be empty...\n"); |
| 234 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 235 | fformat (stdout, "%U", BV (format_bihash), h, 0 /* very verbose */ ); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 236 | return 0; |
| 237 | } |
| 238 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 239 | clib_error_t * |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 240 | test_bihash_main (test_main_t * tm) |
| 241 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 242 | unformat_input_t *i = tm->input; |
| 243 | clib_error_t *error; |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 244 | int test_vec64 = 0; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 245 | |
| 246 | while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT) |
| 247 | { |
| 248 | if (unformat (i, "seed %u", &tm->seed)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 249 | ; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 250 | |
| 251 | else if (unformat (i, "nbuckets %d", &tm->nbuckets)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 252 | ; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 253 | else if (unformat (i, "non-random-keys")) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 254 | tm->non_random_keys = 1; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 255 | else if (unformat (i, "nitems %d", &tm->nitems)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 256 | ; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 257 | else if (unformat (i, "careful %d", &tm->careful_delete_tests)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 258 | ; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 259 | else if (unformat (i, "verbose %d", &tm->verbose)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 260 | ; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 261 | else if (unformat (i, "search %d", &tm->search_iter)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 262 | ; |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 263 | else if (unformat (i, "vec64")) |
| 264 | test_vec64 = 1; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 265 | else if (unformat (i, "verbose")) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 266 | tm->verbose = 1; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 267 | else |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 268 | return clib_error_return (0, "unknown input '%U'", |
| 269 | format_unformat_error, i); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 270 | } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 271 | |
Dave Barach | ba7ddfe | 2017-05-17 20:20:50 -0400 | [diff] [blame] | 272 | if (test_vec64) |
| 273 | error = test_bihash_vec64 (tm); |
| 274 | else |
| 275 | error = test_bihash (tm); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 276 | |
| 277 | return error; |
| 278 | } |
| 279 | |
| 280 | #ifdef CLIB_UNIX |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 281 | int |
| 282 | main (int argc, char *argv[]) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 283 | { |
| 284 | unformat_input_t i; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 285 | clib_error_t *error; |
| 286 | test_main_t *tm = &test_main; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 287 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 288 | clib_mem_init (0, 3ULL << 30); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 313 | |
| 314 | /* |
| 315 | * fd.io coding-style-patch-verification: ON |
| 316 | * |
| 317 | * Local Variables: |
| 318 | * eval: (c-set-style "gnu") |
| 319 | * End: |
| 320 | */ |