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>
22 u32 n_iter, seed, n_keys, n_hash_keys, verbose;
28 uword * keys_in_hash_bitmap;
35 uword * lookup_key_indices;
38 u32 * get_multiple_results;
42 f64 overflow_fraction, ave_elts;
43 f64 get_time, hash_get_time;
44 f64 set_time, set_count;
45 f64 unset_time, unset_count;
46 f64 hash_set_time, hash_unset_time;
50 test_qhash_main (unformat_input_t * input)
52 clib_error_t * error = 0;
53 test_qhash_main_t _tm, * tm = &_tm;
56 memset (tm, 0, sizeof (tm[0]));
62 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
64 if (unformat (input, "iter %d", &tm->n_iter))
66 else if (unformat (input, "seed %d", &tm->seed))
68 else if (unformat (input, "keys %d", &tm->n_keys))
70 else if (unformat (input, "size %d", &tm->n_hash_keys))
72 else if (unformat (input, "vector %d", &tm->max_vector))
74 else if (unformat (input, "verbose"))
78 error = clib_error_create ("unknown input `%U'\n",
79 format_unformat_error, input);
85 tm->seed = random_default_seed ();
87 clib_time_init (&tm->time);
89 clib_warning ("iter %d, seed %u, keys %d, max vector %d, ",
90 tm->n_iter, tm->seed, tm->n_keys, tm->max_vector);
92 vec_resize (tm->keys, tm->n_keys);
93 vec_resize (tm->get_multiple_results, tm->n_keys);
94 for (i = 0; i < vec_len (tm->keys); i++)
95 tm->keys[i] = random_uword (&tm->seed);
97 if (! tm->n_hash_keys)
98 tm->n_hash_keys = 2 * max_pow2 (tm->n_keys);
99 tm->n_hash_keys = clib_max (tm->n_keys, tm->n_hash_keys);
100 qhash_resize (tm->qhash, tm->n_hash_keys);
103 qhash_t * h = qhash_header (tm->qhash);
105 for (i = 0; i < ARRAY_LEN (h->hash_seeds); i++)
106 h->hash_seeds[i] = random_uword (&tm->seed);
109 vec_resize (tm->lookup_keys, tm->max_vector);
110 vec_resize (tm->lookup_key_indices, tm->max_vector);
111 vec_resize (tm->lookup_results, tm->max_vector);
113 for (iter = 0; iter < tm->n_iter; iter++)
115 uword * p, j, n, is_set;
119 is_set = random_u32 (&tm->seed) & 1;
120 is_set |= hash_elts (tm->hash) < (tm->n_keys / 4);
121 if (hash_elts (tm->hash) > (3 * tm->n_keys) / 4)
124 _vec_len (tm->lookup_keys) = n;
125 _vec_len (tm->lookup_key_indices) = n;
129 i = random_u32 (&tm->seed) % vec_len (tm->keys);
130 if (clib_bitmap_get (tm->keys_in_hash_bitmap, i) != is_set)
133 tm->lookup_key_indices[j] = i;
134 tm->lookup_keys[j] = tm->keys[i];
135 t[0] = clib_time_now (&tm->time);
137 hash_set (tm->hash, tm->keys[i], i);
139 hash_unset (tm->hash, tm->keys[i]);
140 t[1] = clib_time_now (&tm->time);
142 tm->hash_set_time += t[1] - t[0];
144 tm->hash_unset_time += t[1] - t[0];
145 tm->keys_in_hash_bitmap
146 = clib_bitmap_set (tm->keys_in_hash_bitmap, i,
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))
215 hash_foreach (k, l, h->overflow_hash, ({
216 j = qhash_hash_mix (h, k) / QHASH_KEYS_PER_BUCKET;
217 vec_validate (tmp, j);
221 for (k = 0; k < vec_len (tmp); k++)
223 if (k >= vec_len (h->overflow_counts))
225 if (h->overflow_counts[k] != tmp[k])
228 for (; k < vec_len (h->overflow_counts); k++)
229 if (h->overflow_counts[k] != 0)
239 t[0] = clib_time_now (&tm->time);
240 qhash_get_multiple (tm->qhash, tm->keys, vec_len (tm->keys),
241 tm->get_multiple_results);
242 t[1] = clib_time_now (&tm->time);
243 tm->get_time += t[1] - t[0];
245 for (i = 0; i < vec_len (tm->keys); i++)
249 t[0] = clib_time_now (&tm->time);
250 p = hash_get (tm->hash, tm->keys[i]);
251 t[1] = clib_time_now (&tm->time);
252 tm->hash_get_time += t[1] - t[0];
254 r = qhash_get (tm->qhash, tm->keys[i]);
259 if (* vec_elt_at_index (tm->qhash, r) != i)
267 if (r != tm->get_multiple_results[i])
272 tm->overflow_fraction +=
273 ((f64) qhash_n_overflow (tm->qhash) / qhash_elts (tm->qhash));
274 tm->ave_elts += qhash_elts (tm->qhash);
277 fformat (stderr, "%d iter %.6e overflow, %.4f ave. elts\n",
279 tm->overflow_fraction / tm->n_iter,
280 tm->ave_elts / tm->n_iter);
282 tm->get_time /= tm->n_iter * vec_len (tm->keys);
283 tm->hash_get_time /= tm->n_iter * vec_len (tm->keys);
285 tm->set_time /= tm->set_count;
286 tm->unset_time /= tm->unset_count;
287 tm->hash_set_time /= tm->set_count;
288 tm->hash_unset_time /= tm->unset_count;
290 fformat (stderr, "get/set/unset clocks %.2e %.2e %.2e clib %.2e %.2e %.2e ratio %.2f %.2f %.2f\n",
291 tm->get_time * tm->time.clocks_per_second,
292 tm->set_time * tm->time.clocks_per_second,
293 tm->unset_time * tm->time.clocks_per_second,
294 tm->hash_get_time * tm->time.clocks_per_second,
295 tm->hash_set_time * tm->time.clocks_per_second,
296 tm->hash_unset_time * tm->time.clocks_per_second,
297 tm->hash_get_time / tm->get_time,
298 tm->hash_set_time / tm->set_time,
299 tm->hash_unset_time / tm->unset_time);
307 int main (int argc, char * argv[])
310 clib_error_t * error;
312 unformat_init_command_line (&i, argv);
313 error = test_qhash_main (&i);
317 clib_error_report (error);
323 #endif /* CLIB_UNIX */