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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
15 #include <vppinfra/bitmap.h>
16 #include <vppinfra/os.h>
17 #include <vppinfra/qhash.h>
18 #include <vppinfra/random.h>
19 #include <vppinfra/time.h>
23 u32 n_iter, seed, n_keys, n_hash_keys, verbose;
29 uword *keys_in_hash_bitmap;
36 uword *lookup_key_indices;
39 u32 *get_multiple_results;
43 f64 overflow_fraction, ave_elts;
44 f64 get_time, hash_get_time;
45 f64 set_time, set_count;
46 f64 unset_time, unset_count;
47 f64 hash_set_time, hash_unset_time;
51 test_qhash_main (unformat_input_t * input)
53 clib_error_t *error = 0;
54 test_qhash_main_t _tm, *tm = &_tm;
57 memset (tm, 0, sizeof (tm[0]));
63 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
65 if (unformat (input, "iter %d", &tm->n_iter))
67 else if (unformat (input, "seed %d", &tm->seed))
69 else if (unformat (input, "keys %d", &tm->n_keys))
71 else if (unformat (input, "size %d", &tm->n_hash_keys))
73 else if (unformat (input, "vector %d", &tm->max_vector))
75 else if (unformat (input, "verbose"))
79 error = clib_error_create ("unknown input `%U'\n",
80 format_unformat_error, input);
86 tm->seed = random_default_seed ();
88 clib_time_init (&tm->time);
90 clib_warning ("iter %d, seed %u, keys %d, max vector %d, ",
91 tm->n_iter, tm->seed, tm->n_keys, tm->max_vector);
93 vec_resize (tm->keys, tm->n_keys);
94 vec_resize (tm->get_multiple_results, tm->n_keys);
95 for (i = 0; i < vec_len (tm->keys); i++)
96 tm->keys[i] = random_uword (&tm->seed);
99 tm->n_hash_keys = 2 * max_pow2 (tm->n_keys);
100 tm->n_hash_keys = clib_max (tm->n_keys, tm->n_hash_keys);
101 qhash_resize (tm->qhash, tm->n_hash_keys);
104 qhash_t *h = qhash_header (tm->qhash);
106 for (i = 0; i < ARRAY_LEN (h->hash_seeds); i++)
107 h->hash_seeds[i] = random_uword (&tm->seed);
110 vec_resize (tm->lookup_keys, tm->max_vector);
111 vec_resize (tm->lookup_key_indices, tm->max_vector);
112 vec_resize (tm->lookup_results, tm->max_vector);
114 for (iter = 0; iter < tm->n_iter; iter++)
116 uword *p, j, n, is_set;
120 is_set = random_u32 (&tm->seed) & 1;
121 is_set |= hash_elts (tm->hash) < (tm->n_keys / 4);
122 if (hash_elts (tm->hash) > (3 * tm->n_keys) / 4)
125 _vec_len (tm->lookup_keys) = n;
126 _vec_len (tm->lookup_key_indices) = n;
130 i = random_u32 (&tm->seed) % vec_len (tm->keys);
131 if (clib_bitmap_get (tm->keys_in_hash_bitmap, i) != is_set)
134 tm->lookup_key_indices[j] = i;
135 tm->lookup_keys[j] = tm->keys[i];
136 t[0] = clib_time_now (&tm->time);
138 hash_set (tm->hash, tm->keys[i], i);
140 hash_unset (tm->hash, tm->keys[i]);
141 t[1] = clib_time_now (&tm->time);
143 tm->hash_set_time += t[1] - t[0];
145 tm->hash_unset_time += t[1] - t[0];
146 tm->keys_in_hash_bitmap
147 = clib_bitmap_set (tm->keys_in_hash_bitmap, i, is_set);
157 t[0] = clib_time_now (&tm->time);
158 qhash_set_multiple (tm->qhash,
160 vec_len (tm->lookup_keys),
162 t[1] = clib_time_now (&tm->time);
163 tm->set_time += t[1] - t[0];
164 tm->set_count += vec_len (tm->lookup_keys);
165 for (i = 0; i < vec_len (tm->lookup_keys); i++)
167 uword r = tm->lookup_results[i];
168 *vec_elt_at_index (tm->qhash, r) = tm->lookup_key_indices[i];
173 t[0] = clib_time_now (&tm->time);
174 qhash_unset_multiple (tm->qhash,
176 vec_len (tm->lookup_keys),
178 t[1] = clib_time_now (&tm->time);
179 tm->unset_time += t[1] - t[0];
180 tm->unset_count += vec_len (tm->lookup_keys);
182 for (i = 0; i < vec_len (tm->lookup_keys); i++)
184 uword r = tm->lookup_results[i];
185 *vec_elt_at_index (tm->qhash, r) = ~0;
190 if (qhash_elts (tm->qhash) != hash_elts (tm->hash))
195 uword i, k, l, count;
197 h = qhash_header (tm->qhash);
199 for (i = k = 0; k < vec_len (h->hash_key_valid_bitmap); k++)
200 i += count_set_bits (h->hash_key_valid_bitmap[k]);
201 k = hash_elts (h->overflow_hash);
202 l = qhash_elts (tm->qhash);
206 count = hash_elts (h->overflow_hash);
207 for (i = 0; i < (1 << h->log2_hash_size); i++)
208 count += tm->qhash[i] != ~0;
209 if (count != qhash_elts (tm->qhash))
216 hash_foreach (k, l, h->overflow_hash, ({
217 j = qhash_hash_mix (h, k) / QHASH_KEYS_PER_BUCKET;
218 vec_validate (tmp, j);
223 for (k = 0; k < vec_len (tmp); k++)
225 if (k >= vec_len (h->overflow_counts))
227 if (h->overflow_counts[k] != tmp[k])
230 for (; k < vec_len (h->overflow_counts); k++)
231 if (h->overflow_counts[k] != 0)
241 t[0] = clib_time_now (&tm->time);
242 qhash_get_multiple (tm->qhash, tm->keys, vec_len (tm->keys),
243 tm->get_multiple_results);
244 t[1] = clib_time_now (&tm->time);
245 tm->get_time += t[1] - t[0];
247 for (i = 0; i < vec_len (tm->keys); i++)
251 t[0] = clib_time_now (&tm->time);
252 p = hash_get (tm->hash, tm->keys[i]);
253 t[1] = clib_time_now (&tm->time);
254 tm->hash_get_time += t[1] - t[0];
256 r = qhash_get (tm->qhash, tm->keys[i]);
261 if (*vec_elt_at_index (tm->qhash, r) != i)
269 if (r != tm->get_multiple_results[i])
274 tm->overflow_fraction +=
275 ((f64) qhash_n_overflow (tm->qhash) / qhash_elts (tm->qhash));
276 tm->ave_elts += qhash_elts (tm->qhash);
279 fformat (stderr, "%d iter %.6e overflow, %.4f ave. elts\n",
281 tm->overflow_fraction / tm->n_iter, tm->ave_elts / tm->n_iter);
283 tm->get_time /= tm->n_iter * vec_len (tm->keys);
284 tm->hash_get_time /= tm->n_iter * vec_len (tm->keys);
286 tm->set_time /= tm->set_count;
287 tm->unset_time /= tm->unset_count;
288 tm->hash_set_time /= tm->set_count;
289 tm->hash_unset_time /= tm->unset_count;
292 "get/set/unset clocks %.2e %.2e %.2e clib %.2e %.2e %.2e ratio %.2f %.2f %.2f\n",
293 tm->get_time * tm->time.clocks_per_second,
294 tm->set_time * tm->time.clocks_per_second,
295 tm->unset_time * tm->time.clocks_per_second,
296 tm->hash_get_time * tm->time.clocks_per_second,
297 tm->hash_set_time * tm->time.clocks_per_second,
298 tm->hash_unset_time * tm->time.clocks_per_second,
299 tm->hash_get_time / tm->get_time, tm->hash_set_time / tm->set_time,
300 tm->hash_unset_time / tm->unset_time);
309 main (int argc, char *argv[])
314 unformat_init_command_line (&i, argv);
315 error = test_qhash_main (&i);
319 clib_error_report (error);
325 #endif /* CLIB_UNIX */
328 * fd.io coding-style-patch-verification: ON
331 * eval: (c-set-style "gnu")