gistfile1.c

include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <math.h>

#include "stinger_utils/timer.h"

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
  int64_t b=  -1, j = 0;
  while(j < num_buckets) {
    b = j;
    key = key * 2862933555777941757ULL + 1;
    j = (b + 1) * ((double)(1LL << 31) / (double)((key >> 33) + 1));
  }
  return b;
}

uint64_t
mix(int64_t n) {
  n = (~n) + (n << 21); // n = (n << 21) - n - 1;
  n = n ^ (n >> 24);
  n = (n + (n << 3)) + (n << 8); // n * 265
  n = n ^ (n >> 14);
  n = (n + (n << 2)) + (n << 4); // n * 21
  n = n ^ (n >> 28);
  n = n + (n << 31);
  return n;
}

int main(int argc, char *argv[])
{
  if(argc < 3) {
    printf("expects bin count parameter, iterations parameter\n");
    exit(-1);
  }

  int64_t bins = atoi(argv[1]);
  int64_t iters = atoi(argv[2]);


  int64_t sum_g = 0;

  // warm up
  for(int64_t i = 0; i < iters; i++) {
    sum_g += JumpConsistentHash(i, bins);
  }

  sum_g = 0;

  tic();
  for(int64_t i = 0; i < iters; i++) {
    sum_g += JumpConsistentHash(i, bins);
  }
  double time_g = toc();

  double avg_g = sum_g;
  avg_g /= iters;
  double sum_2_g = 0;

  for(int64_t i = 0; i < iters; i++) {
    sum_2_g += pow(avg_g - JumpConsistentHash(i, bins), 2);
  }

  printf("google hash %g %ld %g\n", time_g, sum_g, sum_2_g);

  int64_t sum_b = 0;

  tic();
  for(int64_t i = 0; i < iters; i++) {
    sum_b += mix(i) % bins;
  }
  double time_b = toc();

  double avg_b = sum_b;
  avg_b /= iters;
  double sum_2_b = 0;

  for(int64_t i = 0; i < iters; i++) {
    sum_2_b += pow(avg_b - JumpConsistentHash(i, bins), 2);
  }

  printf("bob jenkins hash %g %ld %g\n", time_b, sum_b, sum_2_b);
  printf("google is %gx faster\n", time_b / time_g);
  printf("bob is %gx faster\n", time_g / time_b);
}