src/vppinfra/test_qhash.c - fdio/vpp - Gitiles

 /*
  * Copyright (c) 2015 Cisco and/or its affiliates.
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at:
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 #include <vppinfra/bitmap.h>
 #include <vppinfra/os.h>
 #include <vppinfra/qhash.h>
 #include <vppinfra/random.h>
 #include <vppinfra/time.h>

 typedef struct
 {
   u32 n_iter, seed, n_keys, n_hash_keys, verbose;

   u32 max_vector;

   uword *hash;

   uword *keys_in_hash_bitmap;

   u32 *qhash;

   uword *keys;

   uword *lookup_keys;
   uword *lookup_key_indices;
   u32 *lookup_results;

   u32 *get_multiple_results;

   clib_time_t time;

   f64 overflow_fraction, ave_elts;
   f64 get_time, hash_get_time;
   f64 set_time, set_count;
   f64 unset_time, unset_count;
   f64 hash_set_time, hash_unset_time;
 } test_qhash_main_t;

 clib_error_t *
 test_qhash_main (unformat_input_t * input)
 {
   clib_error_t *error = 0;
   test_qhash_main_t _tm, *tm = &_tm;
   uword i, iter;

   clib_memset (tm, 0, sizeof (tm[0]));
   tm->n_iter = 10;
   tm->seed = 1;
   tm->n_keys = 10;
   tm->max_vector = 1;

   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
     {
       if (unformat (input, "iter %d", &tm->n_iter))
 	;
       else if (unformat (input, "seed %d", &tm->seed))
 	;
       else if (unformat (input, "keys %d", &tm->n_keys))
 	;
       else if (unformat (input, "size %d", &tm->n_hash_keys))
 	;
       else if (unformat (input, "vector %d", &tm->max_vector))
 	;
       else if (unformat (input, "verbose"))
 	tm->verbose = 1;
       else
 	{
 	  error = clib_error_create ("unknown input `%U'\n",
 				     format_unformat_error, input);
 	  goto done;
 	}
     }

   if (!tm->seed)
     tm->seed = random_default_seed ();

   clib_time_init (&tm->time);

   clib_warning ("iter %d, seed %u, keys %d, max vector %d, ",
 		tm->n_iter, tm->seed, tm->n_keys, tm->max_vector);

   vec_resize (tm->keys, tm->n_keys);
   vec_resize (tm->get_multiple_results, tm->n_keys);
   for (i = 0; i < vec_len (tm->keys); i++)
     tm->keys[i] = random_uword (&tm->seed);

   if (!tm->n_hash_keys)
     tm->n_hash_keys = 2 * max_pow2 (tm->n_keys);
   tm->n_hash_keys = clib_max (tm->n_keys, tm->n_hash_keys);
   qhash_resize (tm->qhash, tm->n_hash_keys);

   {
     qhash_t *h = qhash_header (tm->qhash);
     int i;
     for (i = 0; i < ARRAY_LEN (h->hash_seeds); i++)
       h->hash_seeds[i] = random_uword (&tm->seed);
   }

   vec_resize (tm->lookup_keys, tm->max_vector);
   vec_resize (tm->lookup_key_indices, tm->max_vector);
   vec_resize (tm->lookup_results, tm->max_vector);

   for (iter = 0; iter < tm->n_iter; iter++)
     {
       uword *p, j, n, is_set;

       n = tm->max_vector;

       is_set = random_u32 (&tm->seed) & 1;
       is_set |= hash_elts (tm->hash) < (tm->n_keys / 4);
       if (hash_elts (tm->hash) > (3 * tm->n_keys) / 4)
 	is_set = 0;

       _vec_len (tm->lookup_keys) = n;
       _vec_len (tm->lookup_key_indices) = n;
       j = 0;
       while (j < n)
 	{
 	  i = random_u32 (&tm->seed) % vec_len (tm->keys);
 	  if (clib_bitmap_get (tm->keys_in_hash_bitmap, i) != is_set)
 	    {
 	      f64 t[2];
 	      tm->lookup_key_indices[j] = i;
 	      tm->lookup_keys[j] = tm->keys[i];
 	      t[0] = clib_time_now (&tm->time);
 	      if (is_set)
 		hash_set (tm->hash, tm->keys[i], i);
 	      else
 		hash_unset (tm->hash, tm->keys[i]);
 	      t[1] = clib_time_now (&tm->time);
 	      if (is_set)
 		tm->hash_set_time += t[1] - t[0];
 	      else
 		tm->hash_unset_time += t[1] - t[0];
 	      tm->keys_in_hash_bitmap
 		= clib_bitmap_set (tm->keys_in_hash_bitmap, i, is_set);
 	      j++;
 	    }
 	}

       {
 	f64 t[2];

 	if (is_set)
 	  {
 	    t[0] = clib_time_now (&tm->time);
 	    qhash_set_multiple (tm->qhash,
 				tm->lookup_keys,
 				vec_len (tm->lookup_keys),
 				tm->lookup_results);
 	    t[1] = clib_time_now (&tm->time);
 	    tm->set_time += t[1] - t[0];
 	    tm->set_count += vec_len (tm->lookup_keys);
 	    for (i = 0; i < vec_len (tm->lookup_keys); i++)
 	      {
 		uword r = tm->lookup_results[i];
 		*vec_elt_at_index (tm->qhash, r) = tm->lookup_key_indices[i];
 	      }
 	  }
 	else
 	  {
 	    t[0] = clib_time_now (&tm->time);
 	    qhash_unset_multiple (tm->qhash,
 				  tm->lookup_keys,
 				  vec_len (tm->lookup_keys),
 				  tm->lookup_results);
 	    t[1] = clib_time_now (&tm->time);
 	    tm->unset_time += t[1] - t[0];
 	    tm->unset_count += vec_len (tm->lookup_keys);

 	    for (i = 0; i < vec_len (tm->lookup_keys); i++)
 	      {
 		uword r = tm->lookup_results[i];
 		*vec_elt_at_index (tm->qhash, r) = ~0;
 	      }
 	  }
       }

       if (qhash_elts (tm->qhash) != hash_elts (tm->hash))
 	os_panic ();

       {
 	qhash_t *h;
 	uword i, k, l, count;

 	h = qhash_header (tm->qhash);

 	for (i = k = 0; k < vec_len (h->hash_key_valid_bitmap); k++)
 	  i += count_set_bits (h->hash_key_valid_bitmap[k]);
 	k = hash_elts (h->overflow_hash);
 	l = qhash_elts (tm->qhash);
 	if (i + k != l)
 	  os_panic ();

 	count = hash_elts (h->overflow_hash);
 	for (i = 0; i < (1 << h->log2_hash_size); i++)
 	  count += tm->qhash[i] != ~0;
 	if (count != qhash_elts (tm->qhash))
 	  os_panic ();

 	{
 	  u32 *tmp = 0;

 	  /* *INDENT-OFF* */
 	  hash_foreach (k, l, h->overflow_hash, ({
 	    j = qhash_hash_mix (h, k) / QHASH_KEYS_PER_BUCKET;
 	    vec_validate (tmp, j);
 	    tmp[j] += 1;
 	  }));
 	  /* *INDENT-ON* */

 	  for (k = 0; k < vec_len (tmp); k++)
 	    {
 	      if (k >= vec_len (h->overflow_counts))
 		os_panic ();
 	      if (h->overflow_counts[k] != tmp[k])
 		os_panic ();
 	    }
 	  for (; k < vec_len (h->overflow_counts); k++)
 	    if (h->overflow_counts[k] != 0)
 	      os_panic ();

 	  vec_free (tmp);
 	}
       }

       {
 	f64 t[2];

 	t[0] = clib_time_now (&tm->time);
 	qhash_get_multiple (tm->qhash, tm->keys, vec_len (tm->keys),
 			    tm->get_multiple_results);
 	t[1] = clib_time_now (&tm->time);
 	tm->get_time += t[1] - t[0];

 	for (i = 0; i < vec_len (tm->keys); i++)
 	  {
 	    u32 r;

 	    t[0] = clib_time_now (&tm->time);
 	    p = hash_get (tm->hash, tm->keys[i]);
 	    t[1] = clib_time_now (&tm->time);
 	    tm->hash_get_time += t[1] - t[0];

 	    r = qhash_get (tm->qhash, tm->keys[i]);
 	    if (p)
 	      {
 		if (p[0] != i)
 		  os_panic ();
 		if (*vec_elt_at_index (tm->qhash, r) != i)
 		  os_panic ();
 	      }
 	    else
 	      {
 		if (r != ~0)
 		  os_panic ();
 	      }
 	    if (r != tm->get_multiple_results[i])
 	      os_panic ();
 	  }
       }

       tm->overflow_fraction +=
 	((f64) qhash_n_overflow (tm->qhash) / qhash_elts (tm->qhash));
       tm->ave_elts += qhash_elts (tm->qhash);
     }

   fformat (stderr, "%d iter %.6e overflow, %.4f ave. elts\n",
 	   tm->n_iter,
 	   tm->overflow_fraction / tm->n_iter, tm->ave_elts / tm->n_iter);

   tm->get_time /= tm->n_iter * vec_len (tm->keys);
   tm->hash_get_time /= tm->n_iter * vec_len (tm->keys);

   tm->set_time /= tm->set_count;
   tm->unset_time /= tm->unset_count;
   tm->hash_set_time /= tm->set_count;
   tm->hash_unset_time /= tm->unset_count;

   fformat (stderr,
 	   "get/set/unset clocks %.2e %.2e %.2e clib %.2e %.2e %.2e ratio %.2f %.2f %.2f\n",
 	   tm->get_time * tm->time.clocks_per_second,
 	   tm->set_time * tm->time.clocks_per_second,
 	   tm->unset_time * tm->time.clocks_per_second,
 	   tm->hash_get_time * tm->time.clocks_per_second,
 	   tm->hash_set_time * tm->time.clocks_per_second,
 	   tm->hash_unset_time * tm->time.clocks_per_second,
 	   tm->hash_get_time / tm->get_time, tm->hash_set_time / tm->set_time,
 	   tm->hash_unset_time / tm->unset_time);


 done:
   return error;
 }

 #ifdef CLIB_UNIX
 int
 main (int argc, char *argv[])
 {
   unformat_input_t i;
   clib_error_t *error;

   clib_mem_init (0, 64ULL << 20);

   unformat_init_command_line (&i, argv);
   error = test_qhash_main (&i);
   unformat_free (&i);
   if (error)
     {
       clib_error_report (error);
       return 1;
     }
   else
     return 0;
 }
 #endif /* CLIB_UNIX */

 /*
  * fd.io coding-style-patch-verification: ON
  *
  * Local Variables:
  * eval: (c-set-style "gnu")
  * End:
  */
	/*
	* Copyright (c) 2015 Cisco and/or its affiliates.
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at:
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	#include <vppinfra/bitmap.h>
	#include <vppinfra/os.h>
	#include <vppinfra/qhash.h>
	#include <vppinfra/random.h>
	#include <vppinfra/time.h>

	typedef struct
	{
	u32 n_iter, seed, n_keys, n_hash_keys, verbose;

	u32 max_vector;

	uword *hash;

	uword *keys_in_hash_bitmap;

	u32 *qhash;

	uword *keys;

	uword *lookup_keys;
	uword *lookup_key_indices;
	u32 *lookup_results;

	u32 *get_multiple_results;

	clib_time_t time;

	f64 overflow_fraction, ave_elts;
	f64 get_time, hash_get_time;
	f64 set_time, set_count;
	f64 unset_time, unset_count;
	f64 hash_set_time, hash_unset_time;
	} test_qhash_main_t;

	clib_error_t *
	test_qhash_main (unformat_input_t * input)
	{
	clib_error_t *error = 0;
	test_qhash_main_t _tm, *tm = &_tm;
	uword i, iter;

	clib_memset (tm, 0, sizeof (tm[0]));
	tm->n_iter = 10;
	tm->seed = 1;
	tm->n_keys = 10;
	tm->max_vector = 1;

	while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
	{
	if (unformat (input, "iter %d", &tm->n_iter))
	;
	else if (unformat (input, "seed %d", &tm->seed))
	;
	else if (unformat (input, "keys %d", &tm->n_keys))
	;
	else if (unformat (input, "size %d", &tm->n_hash_keys))
	;
	else if (unformat (input, "vector %d", &tm->max_vector))
	;
	else if (unformat (input, "verbose"))
	tm->verbose = 1;
	else
	{
	error = clib_error_create ("unknown input `%U'\n",
	format_unformat_error, input);
	goto done;
	}
	}

	if (!tm->seed)
	tm->seed = random_default_seed ();

	clib_time_init (&tm->time);

	clib_warning ("iter %d, seed %u, keys %d, max vector %d, ",
	tm->n_iter, tm->seed, tm->n_keys, tm->max_vector);

	vec_resize (tm->keys, tm->n_keys);
	vec_resize (tm->get_multiple_results, tm->n_keys);
	for (i = 0; i < vec_len (tm->keys); i++)
	tm->keys[i] = random_uword (&tm->seed);

	if (!tm->n_hash_keys)
	tm->n_hash_keys = 2 * max_pow2 (tm->n_keys);
	tm->n_hash_keys = clib_max (tm->n_keys, tm->n_hash_keys);
	qhash_resize (tm->qhash, tm->n_hash_keys);

	{
	qhash_t *h = qhash_header (tm->qhash);
	int i;
	for (i = 0; i < ARRAY_LEN (h->hash_seeds); i++)
	h->hash_seeds[i] = random_uword (&tm->seed);
	}

	vec_resize (tm->lookup_keys, tm->max_vector);
	vec_resize (tm->lookup_key_indices, tm->max_vector);
	vec_resize (tm->lookup_results, tm->max_vector);

	for (iter = 0; iter < tm->n_iter; iter++)
	{
	uword *p, j, n, is_set;

	n = tm->max_vector;

	is_set = random_u32 (&tm->seed) & 1;
	is_set \|= hash_elts (tm->hash) < (tm->n_keys / 4);
	if (hash_elts (tm->hash) > (3 * tm->n_keys) / 4)
	is_set = 0;

	_vec_len (tm->lookup_keys) = n;
	_vec_len (tm->lookup_key_indices) = n;
	j = 0;
	while (j < n)
	{
	i = random_u32 (&tm->seed) % vec_len (tm->keys);
	if (clib_bitmap_get (tm->keys_in_hash_bitmap, i) != is_set)
	{
	f64 t[2];
	tm->lookup_key_indices[j] = i;
	tm->lookup_keys[j] = tm->keys[i];
	t[0] = clib_time_now (&tm->time);
	if (is_set)
	hash_set (tm->hash, tm->keys[i], i);
	else
	hash_unset (tm->hash, tm->keys[i]);
	t[1] = clib_time_now (&tm->time);
	if (is_set)
	tm->hash_set_time += t[1] - t[0];
	else
	tm->hash_unset_time += t[1] - t[0];
	tm->keys_in_hash_bitmap
	= clib_bitmap_set (tm->keys_in_hash_bitmap, i, is_set);
	j++;
	}
	}

	{
	f64 t[2];

	if (is_set)
	{
	t[0] = clib_time_now (&tm->time);
	qhash_set_multiple (tm->qhash,
	tm->lookup_keys,
	vec_len (tm->lookup_keys),
	tm->lookup_results);
	t[1] = clib_time_now (&tm->time);
	tm->set_time += t[1] - t[0];
	tm->set_count += vec_len (tm->lookup_keys);
	for (i = 0; i < vec_len (tm->lookup_keys); i++)
	{
	uword r = tm->lookup_results[i];
	*vec_elt_at_index (tm->qhash, r) = tm->lookup_key_indices[i];
	}
	}
	else
	{
	t[0] = clib_time_now (&tm->time);
	qhash_unset_multiple (tm->qhash,
	tm->lookup_keys,
	vec_len (tm->lookup_keys),
	tm->lookup_results);
	t[1] = clib_time_now (&tm->time);
	tm->unset_time += t[1] - t[0];
	tm->unset_count += vec_len (tm->lookup_keys);

	for (i = 0; i < vec_len (tm->lookup_keys); i++)
	{
	uword r = tm->lookup_results[i];
	*vec_elt_at_index (tm->qhash, r) = ~0;
	}
	}
	}

	if (qhash_elts (tm->qhash) != hash_elts (tm->hash))
	os_panic ();

	{
	qhash_t *h;
	uword i, k, l, count;

	h = qhash_header (tm->qhash);

	for (i = k = 0; k < vec_len (h->hash_key_valid_bitmap); k++)
	i += count_set_bits (h->hash_key_valid_bitmap[k]);
	k = hash_elts (h->overflow_hash);
	l = qhash_elts (tm->qhash);
	if (i + k != l)
	os_panic ();

	count = hash_elts (h->overflow_hash);
	for (i = 0; i < (1 << h->log2_hash_size); i++)
	count += tm->qhash[i] != ~0;
	if (count != qhash_elts (tm->qhash))
	os_panic ();

	{
	u32 *tmp = 0;

	/* INDENT-OFF */
	hash_foreach (k, l, h->overflow_hash, ({
	j = qhash_hash_mix (h, k) / QHASH_KEYS_PER_BUCKET;
	vec_validate (tmp, j);
	tmp[j] += 1;
	}));
	/* INDENT-ON */

	for (k = 0; k < vec_len (tmp); k++)
	{
	if (k >= vec_len (h->overflow_counts))
	os_panic ();
	if (h->overflow_counts[k] != tmp[k])
	os_panic ();
	}
	for (; k < vec_len (h->overflow_counts); k++)
	if (h->overflow_counts[k] != 0)
	os_panic ();

	vec_free (tmp);
	}
	}

	{
	f64 t[2];

	t[0] = clib_time_now (&tm->time);
	qhash_get_multiple (tm->qhash, tm->keys, vec_len (tm->keys),
	tm->get_multiple_results);
	t[1] = clib_time_now (&tm->time);
	tm->get_time += t[1] - t[0];

	for (i = 0; i < vec_len (tm->keys); i++)
	{
	u32 r;

	t[0] = clib_time_now (&tm->time);
	p = hash_get (tm->hash, tm->keys[i]);
	t[1] = clib_time_now (&tm->time);
	tm->hash_get_time += t[1] - t[0];

	r = qhash_get (tm->qhash, tm->keys[i]);
	if (p)
	{
	if (p[0] != i)
	os_panic ();
	if (*vec_elt_at_index (tm->qhash, r) != i)
	os_panic ();
	}
	else
	{
	if (r != ~0)
	os_panic ();
	}
	if (r != tm->get_multiple_results[i])
	os_panic ();
	}
	}

	tm->overflow_fraction +=
	((f64) qhash_n_overflow (tm->qhash) / qhash_elts (tm->qhash));
	tm->ave_elts += qhash_elts (tm->qhash);
	}

	fformat (stderr, "%d iter %.6e overflow, %.4f ave. elts\n",
	tm->n_iter,
	tm->overflow_fraction / tm->n_iter, tm->ave_elts / tm->n_iter);

	tm->get_time /= tm->n_iter * vec_len (tm->keys);
	tm->hash_get_time /= tm->n_iter * vec_len (tm->keys);

	tm->set_time /= tm->set_count;
	tm->unset_time /= tm->unset_count;
	tm->hash_set_time /= tm->set_count;
	tm->hash_unset_time /= tm->unset_count;

	fformat (stderr,
	"get/set/unset clocks %.2e %.2e %.2e clib %.2e %.2e %.2e ratio %.2f %.2f %.2f\n",
	tm->get_time * tm->time.clocks_per_second,
	tm->set_time * tm->time.clocks_per_second,
	tm->unset_time * tm->time.clocks_per_second,
	tm->hash_get_time * tm->time.clocks_per_second,
	tm->hash_set_time * tm->time.clocks_per_second,
	tm->hash_unset_time * tm->time.clocks_per_second,
	tm->hash_get_time / tm->get_time, tm->hash_set_time / tm->set_time,
	tm->hash_unset_time / tm->unset_time);


	done:
	return error;
	}

	#ifdef CLIB_UNIX
	int
	main (int argc, char *argv[])
	{
	unformat_input_t i;
	clib_error_t *error;

	clib_mem_init (0, 64ULL << 20);

	unformat_init_command_line (&i, argv);
	error = test_qhash_main (&i);
	unformat_free (&i);
	if (error)
	{
	clib_error_report (error);
	return 1;
	}
	else
	return 0;
	}
	#endif /* CLIB_UNIX */

	/*
	* fd.io coding-style-patch-verification: ON
	*
	* Local Variables:
	* eval: (c-set-style "gnu")
	* End:
	*/