Skip to content

Instantly share code, notes, and snippets.

@robmccoll
Last active October 24, 2016 19:41
Show Gist options
  • Save robmccoll/38f03971df66ca15e030 to your computer and use it in GitHub Desktop.
Save robmccoll/38f03971df66ca15e030 to your computer and use it in GitHub Desktop.
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment