bihash_perf.c

#include <tscmarks.h>
#include <vppinfra/bihash_24_8.h>
#include <vppinfra/bihash_template.h>
#include <vppinfra/mem.h>

#include <vppinfra/bihash_template.c>

#define NUM_BUCKETS (1 << 24)
#define N_ELTS (100 * 1000 * 1000)
#define MEM_SIZE (16ULL << 30)

BVT (clib_bihash) test_table;

typedef union
{
  u16 words[24];
  u64 qwords[6];
  BVT (clib_bihash_kv) kv;
} foo_key_t;

static inline void
calc_key (foo_key_t *k, u32 x)
{
#ifdef BAD
  k->words[0] = x >> 16;
  k->words[1] = x & 0xffff;
  k->words[2] = x >> 16;
  k->words[3] = x & 0xffff;
#else
  u64 a = x >> 16;
  u64 b = x & 0xffff;
  k->qwords[0] = a | b << 16 | a << 32 | b << 48;
#endif

  k->qwords[1] = b | a << 16 | b << 32 | a << 48;
  k->qwords[2] = a | b << 16 | a << 32 | b << 48;
  //  k->qwords[3] = x;
  //  k->qwords[4] = x;
  //  k->qwords[5] = x;
}

void
key_add (u64 k, u64 v)
{
  foo_key_t fk;
  calc_key (&fk, k);
  fk.kv.value = v;
  BV (clib_bihash_add_del) (&test_table, &fk.kv, 1);
}

static inline uword
key_search (u64 k)
{
  foo_key_t fk;
  u64 hash;
  calc_key (&fk, k);
  hash = BV (clib_bihash_hash) (&fk.kv);
  BV (clib_bihash_search_inline_with_hash) (&test_table, hash, &fk.kv);
  return fk.kv.value;
}

#define CNT (8192)

int
main (int argc, char *argv[])
{
  int i;
  clib_mem_init (0, 8ULL << 20);

  clib_warning ("init");
  BV (clib_bihash_init) (&test_table, "test", NUM_BUCKETS, MEM_SIZE);

  for (i = 1; i <= N_ELTS; i++)
    {
      key_add (i, i * 10);
      if (i % 1000000 == 0)
        fformat (stderr, "\n%u elts\n%U\n", i, BV (format_bihash),
		 &test_table, 0);
    }

  clib_warning ("%U", BV (format_bihash), &test_table, 0);
  clib_warning ("rv %u", key_search (1024));

  while (1)
    {
      tsc_mark ("start");
      for (int i = 1; i < CNT; i++)
        {
          uword rv;
          rv = key_search (i);
          if (rv != i * 10)
            fformat (stderr, "i %u rv %u\n", i, rv);
        }
      tsc_mark ("end");
      tsc_print (1, CNT);
    }
}