Skip to content

Instantly share code, notes, and snippets.

@jrepp

jrepp/hash_mul_test.c

Last active March 2, 2022 14:50
Show Gist options
  • Save jrepp/2981eec90bba881696256605722e94d7 to your computer and use it in GitHub Desktop.
Save jrepp/2981eec90bba881696256605722e94d7 to your computer and use it in GitHub Desktop.
Download ZIP
Multiplicative hash test program that stacks a few algorithms against each other and shows their relative collisions and table distributions.
Raw
hash_mul_test.c
// This is a file that produces statistics for various integer multiplicative and mix functions to profile their performance
// for a representative problem (apriltag cluster hashing)
//
// the output of this program is a CSV of hash collisions and depth (including p90 depth)
// additional the full hash table distributions for each sample set is printed
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <math.h>
typedef uint32_t (*cluster_hash_func)(uint32_t x, uint32_t y);
struct cluster_hash_func_desc {
const char *name;
cluster_hash_func h;
};
struct cluster_hash {
cluster_hash_func h;
uint32_t *bins;
uint32_t nbins;
uint32_t items;
uint32_t collisions;
uint32_t maxbin;
};
struct distribution {
const char *name;
uint32_t size;
uint32_t clusters;
uint32_t nbins;
uint32_t values[0];
};
uint32_t u64hash_2(uint32_t x, uint32_t y) {
uint64_t v = ((uint64_t)x) << 32 | y;
return (2654435761 * v) >> 32;
}
uint32_t knuth_mul(uint32_t x, uint32_t y) {
uint64_t v = ((uint64_t)x) << 32 | y;
return (2654435769 * v) >> 32;
}
uint32_t mix(uint32_t x, uint32_t y) {
uint32_t v = (x * 4294967311) ^ (y * 4294967311);
return v;
}
uint32_t mix2(uint32_t x, uint32_t y) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
y = ((y >> 16) ^ y) * 0x45d9f3b;
y = ((y >> 16) ^ y) * 0x45d9f3b;
y = (y >> 16) ^ y;
return x ^ y;
}
void cluster_hash_init(struct cluster_hash *ht, uint32_t nbins) {
memset(ht, 0, sizeof(struct cluster_hash));
ht->bins = calloc(nbins, sizeof(ht->bins[0]));
ht->nbins = nbins;
}
void cluster_hash_deinit(struct cluster_hash *h) {
free(h->bins);
}
void hash_one_coord(struct cluster_hash *ht, uint32_t x, uint32_t y) {
uint32_t hvalue = ht->h(x, y);
uint32_t bin = hvalue % ht->nbins;
if (ht->bins[bin]) {
ht->collisions++;
}
ht->bins[bin]++;
ht->items++;
if (ht->maxbin < ht->bins[bin]) {
ht->maxbin = ht->bins[bin];
}
}
void process_image(struct cluster_hash *ht, uint32_t w, uint32_t h, uint32_t clusters) {
srandom(612341);
for (uint32_t c = 0; c < clusters; ++c) {
uint32_t x = rand() % w;
uint32_t y = rand() % h;
hash_one_coord(ht, x, y);
}
}
struct distribution* create_distribution(struct cluster_hash *ht) {
struct distribution *d = (struct distribution *)calloc(1,
sizeof(struct distribution) + ((ht->maxbin + 1) * sizeof(uint32_t)));
d->size = ht->maxbin + 1;
for (uint32_t i = 0; i < ht->nbins; ++i) {
d->values[ht->bins[i]]++;
}
return d;
}
void print_distribution(struct distribution *d) {
for (uint32_t i = 0; i < d->size; ++i) {
printf("%5u, ", d->values[i]);
}
}
float calc_p(float p, struct distribution *d, uint32_t sample_size) {
float pop = 0;
float target_pop = (float)(sample_size) * (p/100.0);
float thresh = 0;
for (uint32_t i = 0; i < d->size; ++i) {
if (pop + (float)d->values[i] < target_pop) {
pop += (float)d->values[i];
thresh = (float)i;
} else {
float left = target_pop - pop;
float delta = (pop + d->values[i]) - pop;
thresh += left / delta;
break;
}
}
return thresh;
}
int main() {
struct cluster_hash ht;
struct cluster_hash_func_desc funcs[] = {
{ "default", u64hash_2 },
{ "knuth_mul", knuth_mul },
{ "mix", mix },
{ "mix2", mix2 },
};
// w, h, clusters, nclustermap
uint32_t image_sizes[][4] = {
// nori-5-640.jpg: for single tag in image with default settings
// 240x320 on threshim 118 clusters, nclustermap 15360, orig 480x640
{ 640, 480, 118, 15360 }, // captured
{ 640, 480, 118 * 3, 15360 }, // 3x captured
{ 640, 480, 118, 15361 }, // prime nclustermap
{ 640, 480, 118, 256 }, // reduced nclustermap
{ 640, 480, 118, 257 }, // reduced prime nclustermap
{ 640, 480, 118 * 3, 256 }, // 3x clusters
{ 640, 480, 118 * 3, 257 }, // 3x clusters
// crash-april.pnm: multiple tags in noisy black image
// 1224x1024 on threshim 1435 clusters, nclustermap 250675
{ 2448, 2048, 1435, 250675 }, // captured
{ 2448, 2048, 1435 * 3, 250675 }, // 3x captured
{ 2448, 2048, 1435, 250681 }, // prime nclustermap
{ 2448, 2048, 1435, 1024 }, // reduced nclustermap
{ 2448, 2048, 1435, 1031 }, // reduced prime nclustermap
{ 2448, 2048, 1435 * 3, 1024 }, // 3x clusters, reduced
{ 2448, 2048, 1435 * 3, 1031 }, // 3x clusters, reduced prime
// nori-5-orig.jpg: same image at higher resolution (single tag
// 2016x1512 threshim 5932 clusters, nclustermap 609638
{ 4032, 3024, 5932, 609638 }, // captured
{ 4032, 3024, 5932 * 3, 609638 }, // 3x captured
{ 4032, 3024, 5932, 609641 }, // prime nclustermap
{ 4032, 3024, 5932, 2048 }, // reduced nclustermap
{ 4032, 3024, 5932, 2053 }, // reduced prime nclustermap
{ 4032, 3024, 5932 * 3, 2048 }, // 3x clusters, reduced nclustermap
{ 4032, 3024, 5932 * 3, 2053 }, // 3x clusters, reduced prime nclustermap
};
uint32_t nfuncs = sizeof(funcs)/sizeof(funcs[0]);
uint32_t ntests = sizeof(image_sizes)/sizeof(image_sizes[0]);
printf("---------------- cluster hashing ------------------------\n");
printf("w, h, clusters, nbins, hash, collisions, maxbin, p90\n");
struct distribution **distributions = (struct distribution **)calloc(
nfuncs * ntests, sizeof(struct distribution*));
uint32_t dist_i = 0;
for (uint32_t t = 0; t < ntests; ++t) {
uint32_t w = image_sizes[t][0],
h = image_sizes[t][1],
c = image_sizes[t][2],
n = image_sizes[t][3];
printf("%5u, %5u, %5u, %8u, ",
w,
h,
c,
n);
for (uint32_t f = 0; f < nfuncs; ++f) {
cluster_hash_init(&ht, n);
ht.h = funcs[f].h;
// threshim coords are /2
process_image(&ht, w / 2, h / 2, c);
struct distribution *d = create_distribution(&ht);
float p90 = calc_p(90.0, d, ht.nbins);
d->name = funcs[f].name;
d->clusters = c;
d->nbins = ht.nbins;
printf("%s, %5u, %3u, %3.3f, ",
funcs[f].name,
ht.collisions,
ht.maxbin,
p90);
distributions[dist_i++] = d;
cluster_hash_deinit(&ht);
}
printf("\n");
}
for (uint32_t i = 0; i < dist_i; ++i) {
struct distribution *d = distributions[i];
printf("%12s (c: %6u n: %6u): ", d->name, d->clusters, d->nbins);
print_distribution(d);
printf("\n");
free(d);
}
free(distributions);
return 0;
}
Raw
hash_mul_test.txt
---------------- cluster hashing ------------------------
w, h, clusters, nbins, hash, collisions, maxbin, p90
640, 480, 118, 15360, default, 0, 1, 0.907, knuth_mul, 0, 1, 0.907, mix, 1, 2, 0.907, mix2, 1, 2, 0.907,
640, 480, 354, 15360, default, 8, 2, 0.921, knuth_mul, 4, 2, 0.921, mix, 18, 3, 0.920, mix2, 4, 3, 0.921,
640, 480, 118, 15361, default, 1, 2, 0.907, knuth_mul, 0, 1, 0.907, mix, 1, 2, 0.907, mix2, 0, 1, 0.907,
640, 480, 118, 256, default, 28, 3, 0.991, knuth_mul, 23, 4, 0.890, mix, 22, 3, 0.903, mix2, 20, 3, 0.905,
640, 480, 118, 257, default, 21, 3, 0.914, knuth_mul, 25, 5, 0.886, mix, 29, 4, 0.959, mix2, 20, 3, 0.904,
640, 480, 354, 256, default, 168, 6, 2.650, knuth_mul, 165, 6, 2.669, mix, 158, 5, 2.576, mix2, 159, 6, 2.497,
640, 480, 354, 257, default, 159, 7, 2.475, knuth_mul, 165, 6, 2.630, mix, 180, 10, 2.721, mix2, 159, 5, 2.412,
2448, 2048, 1435, 250675, default, 3, 2, 0.905, knuth_mul, 7, 2, 0.905, mix, 70, 4, 0.905, mix2, 9, 4, 0.905,
2448, 2048, 4305, 250675, default, 41, 2, 0.916, knuth_mul, 51, 3, 0.916, mix, 611, 6, 0.913, mix2, 52, 6, 0.916,
2448, 2048, 1435, 250681, default, 6, 2, 0.905, knuth_mul, 6, 2, 0.905, mix, 70, 4, 0.905, mix2, 11, 4, 0.905,
2448, 2048, 1435, 1024, default, 667, 7, 2.591, knuth_mul, 665, 5, 2.651, mix, 665, 8, 2.592, mix2, 664, 7, 2.573,
2448, 2048, 1435, 1031, default, 654, 7, 2.521, knuth_mul, 657, 8, 2.635, mix, 657, 8, 2.594, mix2, 658, 6, 2.560,
2448, 2048, 4305, 1024, default, 3300, 12, 6.450, knuth_mul, 3299, 12, 6.539, mix, 3292, 11, 6.478, mix2, 3306, 12, 6.637,
2448, 2048, 4305, 1031, default, 3291, 13, 6.271, knuth_mul, 3291, 13, 6.460, mix, 3289, 13, 6.427, mix2, 3294, 12, 6.592,
4032, 3024, 5932, 609638, default, 38, 2, 0.909, knuth_mul, 51, 2, 0.909, mix, 672, 4, 0.908, mix2, 37, 3, 0.909,
4032, 3024, 17796, 609638, default, 345, 3, 0.927, knuth_mul, 371, 3, 0.926, mix, 5142, 10, 0.919, mix2, 338, 10, 0.927,
4032, 3024, 5932, 609641, default, 29, 2, 0.909, knuth_mul, 38, 2, 0.909, mix, 672, 4, 0.908, mix2, 37, 3, 0.909,
4032, 3024, 5932, 2048, default, 3992, 9, 4.698, knuth_mul, 3995, 10, 4.690, mix, 3998, 10, 4.738, mix2, 3994, 10, 4.682,
4032, 3024, 5932, 2053, default, 3997, 13, 4.721, knuth_mul, 3992, 9, 4.783, mix, 3991, 12, 4.757, mix2, 3998, 11, 4.712,
4032, 3024, 17796, 2048, default, 15748, 24, 12.058, knuth_mul, 15749, 23, 12.165, mix, 15749, 20, 12.040, mix2, 15748, 23, 12.047,
4032, 3024, 17796, 2053, default, 15743, 20, 12.224, knuth_mul, 15744, 20, 12.211, mix, 15743, 23, 12.297, mix2, 15743, 23, 11.938,
default (c: 118 n: 15360): 15242, 118,
knuth_mul (c: 118 n: 15360): 15242, 118,
mix (c: 118 n: 15360): 15243, 116, 1,
mix2 (c: 118 n: 15360): 15243, 116, 1,
default (c: 354 n: 15360): 15014, 338, 8,
knuth_mul (c: 354 n: 15360): 15010, 346, 4,
mix (c: 354 n: 15360): 15024, 319, 16, 1,
mix2 (c: 354 n: 15360): 15010, 347, 2, 1,
default (c: 118 n: 15361): 15244, 116, 1,
knuth_mul (c: 118 n: 15361): 15243, 118,
mix (c: 118 n: 15361): 15244, 116, 1,
mix2 (c: 118 n: 15361): 15243, 118,
default (c: 118 n: 256): 166, 65, 22, 3,
knuth_mul (c: 118 n: 256): 161, 78, 12, 4, 1,
mix (c: 118 n: 256): 160, 78, 14, 4,
mix2 (c: 118 n: 256): 158, 80, 16, 2,
default (c: 118 n: 257): 160, 78, 17, 2,
knuth_mul (c: 118 n: 257): 164, 76, 11, 5, 0, 1,
mix (c: 118 n: 257): 168, 66, 20, 0, 3,
mix2 (c: 118 n: 257): 159, 80, 16, 2,
default (c: 354 n: 256): 70, 85, 52, 36, 9, 3, 1,
knuth_mul (c: 354 n: 256): 67, 91, 53, 29, 11, 4, 1,
mix (c: 354 n: 256): 60, 96, 60, 25, 12, 3,
mix2 (c: 354 n: 256): 61, 92, 62, 31, 6, 3, 1,
default (c: 354 n: 257): 62, 93, 63, 28, 6, 4, 0, 1,
knuth_mul (c: 354 n: 257): 68, 90, 50, 37, 8, 3, 1,
mix (c: 354 n: 257): 83, 86, 45, 24, 9, 3, 2, 1, 2, 0, 2,
mix2 (c: 354 n: 257): 62, 87, 72, 25, 7, 4,
default (c: 1435 n: 250675): 249243, 1429, 3,
knuth_mul (c: 1435 n: 250675): 249247, 1421, 7,
mix (c: 1435 n: 250675): 249310, 1301, 60, 2, 2,
mix2 (c: 1435 n: 250675): 249249, 1419, 6, 0, 1,
default (c: 4305 n: 250675): 246411, 4223, 41,
knuth_mul (c: 4305 n: 250675): 246421, 4204, 49, 1,
mix (c: 4305 n: 250675): 246981, 3172, 452, 53, 16, 0, 1,
mix2 (c: 4305 n: 250675): 246422, 4206, 45, 1, 0, 0, 1,
default (c: 1435 n: 250681): 249252, 1423, 6,
knuth_mul (c: 1435 n: 250681): 249252, 1423, 6,
mix (c: 1435 n: 250681): 249316, 1301, 60, 2, 2,
mix2 (c: 1435 n: 250681): 249257, 1415, 8, 0, 1,
default (c: 1435 n: 1024): 256, 352, 235, 133, 28, 19, 0, 1,
knuth_mul (c: 1435 n: 1024): 254, 359, 237, 110, 48, 16,
mix (c: 1435 n: 1024): 254, 350, 246, 121, 39, 12, 1, 0, 1,
mix2 (c: 1435 n: 1024): 253, 355, 246, 118, 30, 19, 2, 1,
default (c: 1435 n: 1031): 250, 350, 268, 115, 41, 4, 1, 2,
knuth_mul (c: 1435 n: 1031): 253, 377, 228, 110, 48, 12, 2, 0, 1,
mix (c: 1435 n: 1031): 253, 371, 232, 121, 37, 15, 1, 0, 1,
mix2 (c: 1435 n: 1031): 254, 355, 264, 98, 46, 10, 4,
default (c: 4305 n: 1024): 19, 59, 116, 207, 206, 182, 102, 68, 36, 17, 5, 4, 3,
knuth_mul (c: 4305 n: 1024): 18, 66, 137, 189, 200, 158, 118, 66, 35, 20, 11, 4, 2,
mix (c: 4305 n: 1024): 11, 59, 151, 189, 203, 154, 124, 64, 36, 21, 6, 6,
mix2 (c: 4305 n: 1024): 25, 62, 143, 181, 200, 143, 116, 81, 41, 20, 5, 6, 1,
default (c: 4305 n: 1031): 17, 60, 134, 209, 184, 186, 120, 66, 22, 16, 8, 7, 1, 1,
knuth_mul (c: 4305 n: 1031): 17, 61, 128, 213, 200, 176, 103, 65, 33, 23, 9, 2, 0, 1,
mix (c: 4305 n: 1031): 15, 73, 143, 170, 203, 178, 116, 70, 37, 17, 5, 1, 1, 2,
mix2 (c: 4305 n: 1031): 20, 87, 130, 178, 192, 170, 113, 64, 36, 24, 12, 4, 1,
default (c: 5932 n: 609638): 603744, 5856, 38,
knuth_mul (c: 5932 n: 609638): 603757, 5830, 51,
mix (c: 5932 n: 609638): 604378, 4657, 539, 59, 5,
mix2 (c: 5932 n: 609638): 603743, 5859, 35, 1,
default (c: 17796 n: 609638): 592187, 17112, 333, 6,
knuth_mul (c: 17796 n: 609638): 592213, 17055, 369, 1,
mix (c: 17796 n: 609638): 596984, 8860, 2815, 730, 172, 52, 16, 5, 1, 1, 2,
mix2 (c: 17796 n: 609638): 592180, 17133, 319, 5, 0, 0, 0, 0, 0, 0, 1,
default (c: 5932 n: 609641): 603738, 5874, 29,
knuth_mul (c: 5932 n: 609641): 603747, 5856, 38,
mix (c: 5932 n: 609641): 604381, 4657, 539, 59, 5,
mix2 (c: 5932 n: 609641): 603746, 5859, 35, 1,
default (c: 5932 n: 2048): 108, 312, 489, 486, 317, 188, 86, 40, 18, 4,
knuth_mul (c: 5932 n: 2048): 111, 329, 486, 433, 351, 193, 82, 40, 17, 5, 1,
mix (c: 5932 n: 2048): 114, 328, 475, 442, 344, 190, 103, 37, 11, 3, 1,
mix2 (c: 5932 n: 2048): 110, 307, 484, 489, 327, 185, 93, 33, 15, 2, 3,
default (c: 5932 n: 2053): 118, 326, 486, 429, 359, 180, 100, 37, 14, 3, 0, 0, 0, 1,
knuth_mul (c: 5932 n: 2053): 113, 336, 477, 459, 317, 186, 112, 35, 12, 6,
mix (c: 5932 n: 2053): 112, 370, 449, 440, 329, 195, 86, 50, 15, 5, 1, 0, 1,
mix2 (c: 5932 n: 2053): 119, 325, 471, 480, 306, 206, 83, 44, 10, 6, 2, 1,
default (c: 17796 n: 2048): 0, 1, 12, 49, 81, 119, 210, 250, 290, 285, 244, 181, 116, 89, 59, 30, 10, 12, 7, 0, 2, 0, 0, 0, 1,
knuth_mul (c: 17796 n: 2048): 1, 1, 15, 39, 90, 145, 221, 251, 252, 263, 240, 175, 135, 92, 49, 38, 22, 4, 10, 3, 1, 0, 0, 1,
mix (c: 17796 n: 2048): 1, 3, 14, 33, 81, 147, 207, 224, 294, 287, 237, 194, 118, 80, 64, 39, 14, 3, 7, 0, 1,
mix2 (c: 17796 n: 2048): 0, 3, 11, 32, 87, 152, 205, 244, 287, 272, 228, 189, 129, 90, 52, 31, 16, 11, 5, 1, 2, 0, 0, 1,
default (c: 17796 n: 2053): 0, 4, 13, 37, 91, 135, 214, 267, 272, 261, 227, 191, 114, 97, 67, 29, 19, 11, 3, 0, 1,
knuth_mul (c: 17796 n: 2053): 1, 4, 15, 39, 82, 137, 243, 237, 272, 283, 208, 189, 120, 84, 60, 41, 19, 7, 6, 5, 1,
mix (c: 17796 n: 2053): 0, 8, 20, 41, 91, 168, 216, 229, 254, 263, 197, 200, 134, 90, 62, 39, 15, 9, 5, 6, 3, 2, 0, 1,
mix2 (c: 17796 n: 2053): 0, 1, 13, 45, 80, 128, 213, 268, 266, 301, 221, 186, 134, 79, 54, 27, 16, 11, 7, 1, 1, 0, 0, 1,
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment