hashtest.c

#include <assert.h>
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

typedef double lua_Number;
#define LUA_INT32 int32_t
#define cast(t, exp)	((t)(exp))
#define lua_number2int(i,n)	((i)=(int)(n))

#ifdef USE_LUA_HASH
/* Lua 5.2.4 hash function */
/* https://github.com/lua/lua/blob/v5.2.3/llimits.h#L232-L234 */
union luai_Cast { double l_d; LUA_INT32 l_p[2]; };
#define luai_hashnum(i,n)  \
  { volatile union luai_Cast u; u.l_d = (n) + 1.0;  /* avoid -0 */ \
    (i) = u.l_p[0]; (i) += u.l_p[1]; }  /* add double bits for his hash */
#else
/* Factorio hash function */
/* https://github.com/Rseding91/Factorio-Lua/blob/aa2e1f/src/llimits.h#L255-L257 */
#define luai_hashnum(i,n) { int e;  \
  n = frexp(n, &e) * (lua_Number)(INT_MAX - DBL_MAX_EXP);  \
  if (isinf(n)) i = INT_MAX; else lua_number2int(i, n); i += e; }
#endif

#define hashmod(t,n)	((n) % (((t)-1)|1))

/* Get the bucket index for a number */
static int hashnum (int tableBits, lua_Number n) {
  int i;
  luai_hashnum(i, n);
  if (i < 0) {
    if (cast(unsigned int, i) == 0u - i)  /* use unsigned to avoid overflows */
      i = 0;  /* handle INT_MIN */
    i = -i;  /* must be a positive value */
  }
  return hashmod(1 << tableBits, i);
}

int main (int argc, char *argv[]) {
    printf("bits  in-pos  max    avg  it-ops\n");
    for (int bits = 1; bits <= 30; bits++) {
        int start = 1024;
        size_t tableSize = 1 << bits;
        int max = tableSize + start;

        int *table = (int *)calloc(tableSize, sizeof *table);

        for (int n = start; n < max; n++) {
            int i = hashnum(bits, n);
            assert(i < tableSize);
            table[i]++;
        }

        int bucketMax = 0;
        int occupiedBuckets = 0;
        long itOps = 0;
        for (int i = 0; i < tableSize; i++) {
            int n = table[i];
            if (n > bucketMax) bucketMax = table[i];
            if (n > 0) occupiedBuckets++;
            itOps += (n * (n + 1)) / 2;
        }
        printf("%4d %6.1f%% %4d %6.1f %7.2f\n",
            bits,
            occupiedBuckets * 100.0 / (double) tableSize,
            bucketMax,
            tableSize / (double) occupiedBuckets,
            itOps / (double) tableSize);
        free(table);
    }
    return 0;
}