src/vppinfra/test_qhash.c

/*
 * 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;

  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;

  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:
 */