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.
16 Copyright (c) 2010 Eliot Dresselhaus
18 Permission is hereby granted, free of charge, to any person obtaining
19 a copy of this software and associated documentation files (the
20 "Software"), to deal in the Software without restriction, including
21 without limitation the rights to use, copy, modify, merge, publish,
22 distribute, sublicense, and/or sell copies of the Software, and to
23 permit persons to whom the Software is furnished to do so, subject to
24 the following conditions:
26 The above copyright notice and this permission notice shall be
27 included in all copies or substantial portions of the Software.
29 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33 LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
44 #include <vppinfra/bitmap.h>
45 #include <vppinfra/error.h>
46 #include <vppinfra/os.h>
47 #include <vppinfra/random.h>
48 #include <vppinfra/time.h>
49 #include <vppinfra/vhash.h>
51 #ifdef CLIB_HAVE_VEC128
67 u32 * vhash_get_key_indices;
68 u32 * vhash_get_results;
70 u32 * vhash_key_indices;
81 } get_stats, set_stats, unset_stats;
85 test_vhash_key_gather (void * _tm, u32 vi, u32 wi, u32 n_key_u32s)
87 test_vhash_main_t * tm = _tm;
88 ASSERT (n_key_u32s == tm->n_key_u32);
89 ASSERT (wi < n_key_u32s);
90 vi = vec_elt (tm->vhash_key_indices, vi);
91 return vec_elt (tm->keys, vi * n_key_u32s + wi);
95 test_vhash_4key_gather (void * _tm, u32 vi, u32 wi, u32 n_key_u32s)
97 test_vhash_main_t * tm = _tm;
101 ASSERT (n_key_u32s == tm->n_key_u32);
102 ASSERT (wi < n_key_u32s);
104 p = vec_elt_at_index (tm->vhash_key_indices, vi + 0);
105 x.as_u32[0] = tm->keys[p[0] * n_key_u32s + wi];
106 x.as_u32[1] = tm->keys[p[1] * n_key_u32s + wi];
107 x.as_u32[2] = tm->keys[p[2] * n_key_u32s + wi];
108 x.as_u32[3] = tm->keys[p[3] * n_key_u32s + wi];
113 test_vhash_get_result (void * _tm,
118 test_vhash_main_t * tm = _tm;
119 u32 * p = vec_elt_at_index (tm->vhash_results, vector_index);
125 test_vhash_get_4result (void * _tm,
130 test_vhash_main_t * tm = _tm;
131 u32 * p = vec_elt_at_index (tm->vhash_results, vector_index);
132 *(u32x4 *)p = results;
137 test_vhash_set_result (void * _tm,
142 test_vhash_main_t * tm = _tm;
143 u32 * p = vec_elt_at_index (tm->vhash_results, vector_index);
144 u32 new_result = p[0];
150 test_vhash_unset_result (void * _tm, u32 i, u32 old_result, u32 n_key_u32s)
152 test_vhash_main_t * tm = _tm;
153 u32 * p = vec_elt_at_index (tm->vhash_results, i);
158 #define _(N_KEY_U32) \
160 test_vhash_key_gather_##N_KEY_U32 (void * _tm, u32 vi, u32 i) \
161 { return test_vhash_key_gather (_tm, vi, i, N_KEY_U32); } \
163 always_inline u32x4 \
164 test_vhash_key_gather_4_##N_KEY_U32 (void * _tm, u32 vi, u32 i) \
165 { return test_vhash_4key_gather (_tm, vi, i, N_KEY_U32); } \
167 clib_pipeline_stage \
168 (test_vhash_gather_keys_stage_##N_KEY_U32, \
169 test_vhash_main_t *, tm, i, \
171 vhash_gather_4key_stage \
173 /* vector_index */ i, \
174 test_vhash_key_gather_4_##N_KEY_U32, \
179 clib_pipeline_stage_no_inline \
180 (test_vhash_gather_keys_mod_stage_##N_KEY_U32, \
181 test_vhash_main_t *, tm, i, \
183 vhash_gather_key_stage \
185 /* vector_index */ tm->n_vectors_div_4, \
186 /* n_vectors */ tm->n_vectors_mod_4, \
187 test_vhash_key_gather_##N_KEY_U32, \
192 clib_pipeline_stage \
193 (test_vhash_hash_finalize_stage_##N_KEY_U32, \
194 test_vhash_main_t *, tm, i, \
196 vhash_finalize_stage (&tm->vhash, i, N_KEY_U32); \
199 clib_pipeline_stage_no_inline \
200 (test_vhash_hash_finalize_mod_stage_##N_KEY_U32, \
201 test_vhash_main_t *, tm, i, \
203 vhash_finalize_stage (&tm->vhash, tm->n_vectors_div_4, N_KEY_U32); \
206 clib_pipeline_stage \
207 (test_vhash_get_stage_##N_KEY_U32, \
208 test_vhash_main_t *, tm, i, \
210 vhash_get_4_stage (&tm->vhash, \
211 /* vector_index */ i, \
212 test_vhash_get_4result, \
216 clib_pipeline_stage_no_inline \
217 (test_vhash_get_mod_stage_##N_KEY_U32, \
218 test_vhash_main_t *, tm, i, \
220 vhash_get_stage (&tm->vhash, \
221 /* vector_index */ tm->n_vectors_div_4, \
222 /* n_vectors */ tm->n_vectors_mod_4, \
223 test_vhash_get_result, \
227 clib_pipeline_stage \
228 (test_vhash_set_stage_##N_KEY_U32, \
229 test_vhash_main_t *, tm, i, \
231 vhash_set_stage (&tm->vhash, \
232 /* vector_index */ i, \
233 /* n_vectors */ VECTOR_WORD_TYPE_LEN (u32), \
234 test_vhash_set_result, \
238 clib_pipeline_stage_no_inline \
239 (test_vhash_set_mod_stage_##N_KEY_U32, \
240 test_vhash_main_t *, tm, i, \
242 vhash_set_stage (&tm->vhash, \
243 /* vector_index */ tm->n_vectors_div_4, \
244 /* n_vectors */ tm->n_vectors_mod_4, \
245 test_vhash_set_result, \
249 clib_pipeline_stage \
250 (test_vhash_unset_stage_##N_KEY_U32, \
251 test_vhash_main_t *, tm, i, \
253 vhash_unset_stage (&tm->vhash, \
254 /* vector_index */ i, \
255 /* n_vectors */ VECTOR_WORD_TYPE_LEN (u32), \
256 test_vhash_unset_result, \
260 clib_pipeline_stage_no_inline \
261 (test_vhash_unset_mod_stage_##N_KEY_U32, \
262 test_vhash_main_t *, tm, i, \
264 vhash_unset_stage (&tm->vhash, \
265 /* vector_index */ tm->n_vectors_div_4, \
266 /* n_vectors */ tm->n_vectors_mod_4, \
267 test_vhash_unset_result, \
280 #define _(N_KEY_U32) \
281 clib_pipeline_stage \
282 (test_vhash_hash_mix_stage_##N_KEY_U32, \
283 test_vhash_main_t *, tm, i, \
285 vhash_mix_stage (&tm->vhash, i, N_KEY_U32); \
288 clib_pipeline_stage_no_inline \
289 (test_vhash_hash_mix_mod_stage_##N_KEY_U32, \
290 test_vhash_main_t *, tm, i, \
292 vhash_mix_stage (&tm->vhash, tm->n_vectors_div_4, N_KEY_U32); \
306 test_vhash_op (test_vhash_main_t * tm,
312 vhash_validate_sizes (&tm->vhash, tm->n_key_u32, n_keys);
314 tm->vhash_results = results;
315 tm->vhash_key_indices = key_indices;
316 tm->n_vectors_div_4 = n_keys / 4;
317 tm->n_vectors_mod_4 = n_keys % 4;
319 if (tm->n_vectors_div_4 > 0)
321 switch (tm->n_key_u32)
327 #define _(N_KEY_U32) \
330 clib_pipeline_run_3_stage \
331 (tm->n_vectors_div_4, \
333 test_vhash_gather_keys_stage_##N_KEY_U32, \
334 test_vhash_hash_finalize_stage_##N_KEY_U32, \
335 test_vhash_get_stage_##N_KEY_U32); \
336 else if (op == SET) \
337 clib_pipeline_run_3_stage \
338 (tm->n_vectors_div_4, \
340 test_vhash_gather_keys_stage_##N_KEY_U32, \
341 test_vhash_hash_finalize_stage_##N_KEY_U32, \
342 test_vhash_set_stage_##N_KEY_U32); \
344 clib_pipeline_run_3_stage \
345 (tm->n_vectors_div_4, \
347 test_vhash_gather_keys_stage_##N_KEY_U32, \
348 test_vhash_hash_finalize_stage_##N_KEY_U32, \
349 test_vhash_unset_stage_##N_KEY_U32); \
358 #define _(N_KEY_U32) \
361 clib_pipeline_run_4_stage \
362 (tm->n_vectors_div_4, \
364 test_vhash_gather_keys_stage_##N_KEY_U32, \
365 test_vhash_hash_mix_stage_##N_KEY_U32, \
366 test_vhash_hash_finalize_stage_##N_KEY_U32, \
367 test_vhash_get_stage_##N_KEY_U32); \
368 else if (op == SET) \
369 clib_pipeline_run_4_stage \
370 (tm->n_vectors_div_4, \
372 test_vhash_gather_keys_stage_##N_KEY_U32, \
373 test_vhash_hash_mix_stage_##N_KEY_U32, \
374 test_vhash_hash_finalize_stage_##N_KEY_U32, \
375 test_vhash_set_stage_##N_KEY_U32); \
377 clib_pipeline_run_4_stage \
378 (tm->n_vectors_div_4, \
380 test_vhash_gather_keys_stage_##N_KEY_U32, \
381 test_vhash_hash_mix_stage_##N_KEY_U32, \
382 test_vhash_hash_finalize_stage_##N_KEY_U32, \
383 test_vhash_unset_stage_##N_KEY_U32); \
395 if (tm->n_vectors_mod_4 > 0)
397 switch (tm->n_key_u32)
403 #define _(N_KEY_U32) \
406 clib_pipeline_run_3_stage \
409 test_vhash_gather_keys_mod_stage_##N_KEY_U32, \
410 test_vhash_hash_finalize_mod_stage_##N_KEY_U32, \
411 test_vhash_get_mod_stage_##N_KEY_U32); \
412 else if (op == SET) \
413 clib_pipeline_run_3_stage \
416 test_vhash_gather_keys_mod_stage_##N_KEY_U32, \
417 test_vhash_hash_finalize_mod_stage_##N_KEY_U32, \
418 test_vhash_set_mod_stage_##N_KEY_U32); \
420 clib_pipeline_run_3_stage \
423 test_vhash_gather_keys_mod_stage_##N_KEY_U32, \
424 test_vhash_hash_finalize_mod_stage_##N_KEY_U32, \
425 test_vhash_unset_mod_stage_##N_KEY_U32); \
434 #define _(N_KEY_U32) \
437 clib_pipeline_run_4_stage \
440 test_vhash_gather_keys_mod_stage_##N_KEY_U32, \
441 test_vhash_hash_mix_mod_stage_##N_KEY_U32, \
442 test_vhash_hash_finalize_mod_stage_##N_KEY_U32, \
443 test_vhash_get_mod_stage_##N_KEY_U32); \
444 else if (op == SET) \
445 clib_pipeline_run_4_stage \
448 test_vhash_gather_keys_mod_stage_##N_KEY_U32, \
449 test_vhash_hash_mix_mod_stage_##N_KEY_U32, \
450 test_vhash_hash_finalize_mod_stage_##N_KEY_U32, \
451 test_vhash_set_mod_stage_##N_KEY_U32); \
453 clib_pipeline_run_4_stage \
456 test_vhash_gather_keys_mod_stage_##N_KEY_U32, \
457 test_vhash_hash_mix_mod_stage_##N_KEY_U32, \
458 test_vhash_hash_finalize_mod_stage_##N_KEY_U32, \
459 test_vhash_unset_mod_stage_##N_KEY_U32); \
471 int test_vhash_main (unformat_input_t * input)
473 clib_error_t * error = 0;
474 test_vhash_main_t _tm, * tm = &_tm;
475 vhash_t * vh = &tm->vhash;
478 memset (tm, 0, sizeof (tm[0]));
486 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
488 if (unformat (input, "iter %d", &tm->n_iter))
490 else if (unformat (input, "seed %d", &tm->seed))
492 else if (unformat (input, "n-keys %d", &tm->n_keys))
494 else if (unformat (input, "log2-size %d", &tm->log2_size))
496 else if (unformat (input, "key-words %d", &tm->n_key_u32))
498 else if (unformat (input, "verbose %=", &tm->verbose, 1))
502 error = clib_error_create ("unknown input `%U'\n",
503 format_unformat_error, input);
509 tm->seed = random_default_seed ();
511 clib_warning ("iter %d seed %d n-keys %d log2-size %d key-words %d",
512 tm->n_iter, tm->seed, tm->n_keys, tm->log2_size, tm->n_key_u32);
516 seeds[0] = seeds[1] = seeds[2] = 0xdeadbeef;
517 vhash_init (vh, tm->log2_size, tm->n_key_u32, seeds);
520 /* Choose unique keys. */
521 vec_resize (tm->keys, tm->n_keys * tm->n_key_u32);
522 vec_resize (tm->key_hash, tm->n_key_u32);
523 for (i = j = 0; i < vec_len (tm->keys); i++, j++)
525 j = j == tm->n_key_u32 ? 0 : j;
527 tm->keys[i] = random_u32 (&tm->seed);
528 } while (hash_get (tm->key_hash[j], tm->keys[i]));
529 hash_set (tm->key_hash[j], tm->keys[i], 0);
532 vec_resize (tm->results, tm->n_keys);
533 for (i = 0; i < vec_len (tm->results); i++)
536 tm->results[i] = random_u32 (&tm->seed);
537 } while (tm->results[i] == ~0);
540 vec_resize_aligned (tm->vhash_get_results, tm->n_keys, CLIB_CACHE_LINE_BYTES);
541 vec_clone (tm->vhash_get_key_indices, tm->results);
542 for (i = 0; i < vec_len (tm->vhash_get_key_indices); i++)
543 tm->vhash_get_key_indices[i] = i;
546 uword * is_set_bitmap = 0;
547 uword * to_set_bitmap = 0;
548 uword * to_unset_bitmap = 0;
549 u32 * to_set = 0, * to_unset = 0;
550 u32 * to_set_results = 0, * to_unset_results = 0;
553 for (i = 0; i < tm->n_iter; i++)
555 vec_reset_length (to_set);
556 vec_reset_length (to_unset);
557 vec_reset_length (to_set_results);
558 vec_reset_length (to_unset_results);
561 to_set_bitmap = clib_bitmap_random (to_set_bitmap,
562 tm->n_keys, &tm->seed);
563 } while (clib_bitmap_is_zero (to_set_bitmap));
564 to_unset_bitmap = clib_bitmap_dup_and (to_set_bitmap, is_set_bitmap);
565 to_set_bitmap = clib_bitmap_andnot (to_set_bitmap, to_unset_bitmap);
567 clib_bitmap_foreach (j, to_set_bitmap, ({
568 vec_add1 (to_set, j);
569 vec_add1 (to_set_results, tm->results[j]);
571 clib_bitmap_foreach (j, to_unset_bitmap, ({
572 vec_add1 (to_unset, j);
573 vec_add1 (to_unset_results, 0xdeadbeef);
576 if (vec_len (to_set) > 0)
578 t[0] = clib_cpu_time_now ();
579 test_vhash_op (tm, to_set, to_set_results,
582 t[1] = clib_cpu_time_now ();
583 tm->set_stats.n_clocks += t[1] - t[0];
584 tm->set_stats.n_vectors += vec_len (to_set);
585 tm->set_stats.n_calls += 1;
586 is_set_bitmap = clib_bitmap_or (is_set_bitmap, to_set_bitmap);
589 t[0] = clib_cpu_time_now ();
590 test_vhash_op (tm, tm->vhash_get_key_indices,
591 tm->vhash_get_results,
592 vec_len (tm->vhash_get_key_indices),
594 t[1] = clib_cpu_time_now ();
595 tm->get_stats.n_clocks += t[1] - t[0];
596 tm->get_stats.n_vectors += vec_len (tm->vhash_get_key_indices);
597 tm->get_stats.n_calls += 1;
599 for (j = 0; j < vec_len (tm->vhash_get_results); j++)
601 u32 r0 = tm->vhash_get_results[j];
602 u32 r1 = tm->results[j];
603 if (clib_bitmap_get (is_set_bitmap, j))
615 if (vh->n_elts != clib_bitmap_count_set_bits (is_set_bitmap))
618 if (vec_len (to_unset) > 0)
620 t[0] = clib_cpu_time_now ();
621 test_vhash_op (tm, to_unset, to_unset_results,
624 t[1] = clib_cpu_time_now ();
625 tm->unset_stats.n_clocks += t[1] - t[0];
626 tm->unset_stats.n_vectors += vec_len (to_unset);
627 tm->unset_stats.n_calls += 1;
628 is_set_bitmap = clib_bitmap_andnot (is_set_bitmap, to_unset_bitmap);
631 t[0] = clib_cpu_time_now ();
632 test_vhash_op (tm, tm->vhash_get_key_indices,
633 tm->vhash_get_results,
634 vec_len (tm->vhash_get_key_indices),
636 t[1] = clib_cpu_time_now ();
637 tm->get_stats.n_clocks += t[1] - t[0];
638 tm->get_stats.n_vectors += vec_len (tm->vhash_get_key_indices);
639 tm->get_stats.n_calls += 1;
641 for (j = 0; j < vec_len (tm->vhash_get_results); j++)
643 u32 r0 = tm->vhash_get_results[j];
644 u32 r1 = tm->results[j];
645 if (clib_bitmap_get (is_set_bitmap, j))
657 if (vh->n_elts != clib_bitmap_count_set_bits (is_set_bitmap))
661 vhash_resize (vh, tm->log2_size + 1);
663 test_vhash_op (tm, tm->vhash_get_key_indices,
664 tm->vhash_get_results,
665 vec_len (tm->vhash_get_key_indices),
668 for (j = 0; j < vec_len (tm->vhash_get_results); j++)
670 u32 r0 = tm->vhash_get_results[j];
671 u32 r1 = tm->results[j];
672 if (clib_bitmap_get (is_set_bitmap, j))
684 if (vh->n_elts != clib_bitmap_count_set_bits (is_set_bitmap))
691 clib_time_init (&ct);
693 clib_warning ("%.4e clocks/get %.4e gets/call %.4e gets/sec",
694 (f64) tm->get_stats.n_clocks / (f64) tm->get_stats.n_vectors,
695 (f64) tm->get_stats.n_vectors / (f64) tm->get_stats.n_calls,
696 (f64) tm->get_stats.n_vectors / (f64) (tm->get_stats.n_clocks * ct.seconds_per_clock));
697 if (tm->set_stats.n_calls > 0)
698 clib_warning ("%.4e clocks/set %.4e sets/call %.4e sets/sec",
699 (f64) tm->set_stats.n_clocks / (f64) tm->set_stats.n_vectors,
700 (f64) tm->set_stats.n_vectors / (f64) tm->set_stats.n_calls,
701 (f64) tm->set_stats.n_vectors / (f64) (tm->set_stats.n_clocks * ct.seconds_per_clock));
702 if (tm->unset_stats.n_calls > 0)
703 clib_warning ("%.4e clocks/unset %.4e unsets/call %.4e unsets/sec",
704 (f64) tm->unset_stats.n_clocks / (f64) tm->unset_stats.n_vectors,
705 (f64) tm->unset_stats.n_vectors / (f64) tm->unset_stats.n_calls,
706 (f64) tm->unset_stats.n_vectors / (f64) (tm->unset_stats.n_clocks * ct.seconds_per_clock));
711 clib_error_report (error);
715 #endif /* CLIB_HAVE_VEC128 */
717 #ifndef CLIB_HAVE_VEC128
718 int test_vhash_main (unformat_input_t * input)
720 clib_error ("compiled without vector support");
726 int main (int argc, char * argv [])
731 unformat_init_command_line (&i, argv);
732 r = test_vhash_main (&i);