/* Here is that cuckoo hash function converted to C */
/* Dann Corbit did the quick & dirty C conversion. */
/* */
/* K-ary cuckoo hashing (c) 2002-2003 by Peter Sanders */
/* this is a simple implementation for the purposes */
/* of measuring the performance of cuckoo hashing in abstract */
/* terms (number of probes per insert, storage efficiency) */
/* usage: compile using g++ or another ISO C++ compiler */
/* a.out <K<n<r<repeat<s eed for rng*/
/* there is also a constant tMax that defines the maximum number */
/* of trials for an insertion */
/* allocates space for n elements in K subtables, and repeats */
/* the follwing measurements repeat time: */
/* - find a hash function by filling full lookup tables */
/* with pseudo-random numbers. */
/* - insert elements i=0..n-1 into the table until this fails */
/* for the first time. (The cost of these insertions is not */
/* measured.) */
/* Every n/r successfully inserted elements, the follwing */
/* measurement is repeated n/r times: */
/* * a random element i2 is deleted */
/* * the hash table entries for i2 are filled with new random values
*/
/* * i2 is reinserted. */
/* Note that this is equivalent to removing a random element */
/* inserting a new element that */
/* has never been in the table before. */
/* The output is a table that gives */
/* - x the number of elements in the table at each measuremnt interval
*/
/* - the average number of probes for an insertion during the
measruements */
/* for the given number of inserted elements */
/* - K */
/* - n */
/* - repeat */
/* - seed */
#define DEBUGLEVEL 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include "util.h"
#include "mt-real.c"
#define split 1
const int tMax = 10000; /* max number of random walk trials */
int K; /* number of probes */
int n; /* number of elements */
int m; /* number of elements per table */
int **hash; /* K times n array */
int **table; /* K times m array */
double limit(double x, double bound)
{
if (x bound) {
return bound;
} else if (x < -bound) {
return -bound;
} else
return x;
}
double cpuTime()
{
return clock() * 1e-6;
}
/* generate random int in 0..x-1 */
int rand0K(int x)
{
return (int) (genrand() * x);
}
/* insert element i into table */
/* return value: */
/* -1 failure */
/* otherwise number of hash function evaluation */
int insert(int i)
{
int forbidden = -1;
int j = rand0K(K);
int t;
for (t = 1; t <= tMax; t++) {
int p = hash[j][i];
int newI = table[j][p];
table[j][p] = i; /* play the cuckoo */
if (newI == -1)
return t; /* done */
forbidden = j;
i = newI; /* find new home for cuckoo victim */
j = rand0K(K - 1);
if (j == forbidden)
j = K - 1;
}
return tMax + 1; /* insertion failed */
}
/* delete element i from the table */
void delete(int i)
{
int j;
for (j = 0; j < K; j++) {
int p = hash[j][i];
if (table[j][p] == i) {
table[j][p] = -1;
return;
}
}
}
int main(int argc, char **argv)
{
int i,
j;
int r;
int step;
int repeat;
int seed;
double *sumT;
int *cf;
int rep;
assert(argc == 6);
K = atoi(argv[1]); /* number of probes */
n = atoi(argv[2]); /* number of elements */
r = atoi(argv[3]); /* number of measured densities */
repeat = atoi(argv[4]); /* how often to start from scratch */
seed = atoi(argv[5]);
m = (int) (n / K + 0.5);
step = n / r;
sgenrand(seed);
puts("# x tAvg(x) K N repeat seed");
/* allocate hash function and table */
/* and an empty table */
hash = calloc(K, sizeof(int *));
table = calloc(K, sizeof(int *));
for (j = 0; j < K; j++) {
hash[j] = calloc(n, sizeof(int));
table[j] = calloc(m, sizeof(int));
}
/* initialize statistics */
/* sumT[i] is the average time for size i*step */
sumT = calloc(r + 1, sizeof(double)) ;
cf = calloc(r + 1, sizeof(int));
for (i = 0; i < r; i++) {
sumT[i] = 0;
cf[i] = 0;
}
/* main loop */
for (rep = 0; rep < repeat; rep++) {
/* init hash function and empty table */
for (j = 0; j < K; j++) {
for (i = 0; i < n; i++) {
hash[j][i] = rand0K(m);
}
for (i = 0; i < m; i++) {
table[j][i] = -1;
}
}
/* fill table and keep measuring from time to time */
for (i = 0; i < n; i++) {
if (insert(i) tMax)
break; /* table is full */
/* measure in detail here */
if (((i + 1) % step) == 0) {
int i1;
for (i1 = 0; i1 < step; i1++) {
int t;
/* delete & reinsert a random element */
int i2 = rand0K(i);
delete(i2);
for (j = 0; j < K; j++)
hash[j][i2] = rand0K(m);
t = insert(i2);
cf[i / step] += (t tMax);
/* cout << t << endl; */
sumT[i / step] += t;
}
}
}
}
for (rep = 0; rep < r; rep++) {
printf("%d %f %d %d %d %d %d\n",
rep * step + step,
sumT[rep] / step / repeat,
K,
n,
repeat,
seed,
cf[rep]);
}
return 0;
}
/*
mt-real.c follows:
*/
/* A C-program for MT19937B: Real number version */
/* genrand() generate one pseudorandom number with double precision
*/
/* which is uniformly distributed on [0,1]-interval for each call.
*/
/* sgenrand(seed) set initial values to the working area of 624
words.*/
/* sgenrand(seed) must be called once before calling genrand()
*/
/* (seed is any integer except 0).
*/
/*
LICENCE CONDITIONS:
Matsumoto and Nishimura consent to GNU General
Public Licence
NOTE:
When you use it in your program, please let Matsumoto
<ma******@math. keio.ac.jpknow it.
Because of a machine-trouble, Matsumoto lost emails
which arrived during May 28-29.
*/
#include<stdio. h>
/* Period parameters */
#define N 624
#define M 397
#define MATRIX_A 0x9908b0df /* constant vector a */
#define UPPER_MASK 0x80000000 /* most significant w-r bits */
#define LOWER_MASK 0x7fffffff /* least significant r bits */
/* for tempering */
#define TEMPERING_MASK_ B 0x9d2c5680
#define TEMPERING_MASK_ C 0xefc60000
#define TEMPERING_SHIFT _U(y) (y >11)
#define TEMPERING_SHIFT _S(y) (y << 7)
#define TEMPERING_SHIFT _T(y) (y << 15)
#define TEMPERING_SHIFT _L(y) (y >18)
static unsigned long ptgfsr[N]; /* set initial seeds: N = 624 words */
void
sgenrand(unsign ed long seed) /* seed should not be 0 */
{
int k;
/* setting initial seeds to ptgfsr[N] using */
/* the generator Line 25 of Table 1 in */
/* [KNUTH 1981, The Art of Computer Programming */
/* Vol. 2 (2nd Ed.), pp102] */
ptgfsr[0]= seed & 0xffffffff;
for (k=1; k<N; k++)
ptgfsr[k] = (69069 * ptgfsr[k-1]) & 0xffffffff;
}
double
genrand()
{
unsigned long y;
static int k = 1;
static unsigned long mag01[2]={0x0, MATRIX_A};
/* mag01[x] = x * MATRIX_A for x=0,1 */
if(k == N){ /* generate N words at one time */
int kk;
for (kk=0;kk<N-M;kk++) {
y = (ptgfsr[kk]&UPPER_MASK)|(p tgfsr[kk+1]&LOWER_MASK) ;
ptgfsr[kk] = ptgfsr[kk+M] ^ (y >1) ^ mag01[y & 0x1];
}
for (;kk<N-1;kk++) {
y = (ptgfsr[kk]&UPPER_MASK)|(p tgfsr[kk+1]&LOWER_MASK) ;
ptgfsr[kk] = ptgfsr[kk+(M-N)] ^ (y >1) ^ mag01[y & 0x1];
}
y = (ptgfsr[N-1]&UPPER_MASK)|(p tgfsr[0]&LOWER_MASK) ;
ptgfsr[N-1] = ptgfsr[M-1] ^ (y >1) ^ mag01[y & 0x1];
k = 0;
}
y = ptgfsr[k++];
y ^= TEMPERING_SHIFT _U(y);
y ^= TEMPERING_SHIFT _S(y) & TEMPERING_MASK_ B;
y ^= TEMPERING_SHIFT _T(y) & TEMPERING_MASK_ C;
y &= 0xffffffff; /* you may delete this line if word size = 32 */
y ^= TEMPERING_SHIFT _L(y);
return ( (double)y / (unsigned long)0xffffffff );
}
/*
util.h follows:
*/
/*
// this files contains all the application independent little
// functions and macros used for the optimizer.
// In particular Peters debug macros and Dags stuff
// from dbasic.h cdefs, random,...
//////////////// stuff originally from
debug.h ///////////////////////////////
// (c) 1997 Peter Sanders
// some little utilities for debugging adapted
// to the paros conventions
*/
#ifndef UTIL
#define UTIL
#ifndef Max
#define Max(x,y) ((x)>=(y)?(x):( y))
#endif
#ifndef Min
#define Min(x,y) ((x)<=(y)?(x):( y))
#endif
#ifndef Abs
#define Abs(x) ((x) < 0 ? -(x) : (x))
#endif
#ifndef PI
#define PI 3.1415926535
#endif
#endif
