Skip to content

Instantly share code, notes, and snippets.

@ayende ayende/ehash.c
Last active Nov 26, 2019

Embed
What would you like to do?
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <stdint.h>
#include <string.h>
#include <inttypes.h>
#include <stdbool.h>
#include "wyhash.h" // https://github.com/wangyi-fudan/wymlp/blob/master/wyhash.h
#define VALIDATE 0
#define HASH_BUCKET_PAGE_SIZE 8192
#define NUMBER_OF_HASH_BUCKET_PIECES 127
#define PIECE_BUCKET_BUFFER_SIZE 63
typedef struct hash_bucket_piece {
uint8_t overflowed: 1;
uint8_t bytes_used: 7;
uint8_t data[PIECE_BUCKET_BUFFER_SIZE];
} hash_bucket_piece_t;
static_assert(sizeof(hash_bucket_piece_t) == 64, "hash_bucket_piece_t is expected to be 64 bytes exactly");
typedef struct hash_bucket {
union {
struct {
uint64_t number_of_entries;
uint8_t depth;
bool seen;
};
uint8_t _padding[64];
};
hash_bucket_piece_t pieces[NUMBER_OF_HASH_BUCKET_PIECES];
} hash_bucket_t;
typedef struct hash_directory {
uint64_t number_of_entries;
uint32_t number_of_buckets;
uint32_t directory_pages;
uint8_t depth;
hash_bucket_t* buckets[0];
} hash_directory_t;
typedef struct hash_ctx {
void* (*allocate_page)(uint32_t n);
void (*release_page)(void* p);
hash_directory_t* dir;
} hash_ctx_t;
uint64_t hash(uint64_t x) {
x = (x ^ (x >> 30))* UINT64_C(0xbf58476d1ce4e5b9);
x = (x ^ (x >> 27))* UINT64_C(0x94d049bb133111eb);
x = x ^ (x >> 31);
return x;
}
void varint_decode(uint8_t** buf, uint64_t* val) {
uint64_t result = 0;
uint32_t shift = 0;
uint8_t* ptr = *buf;
uint8_t cur = 0;
do
{
cur = *ptr++;
result |= (uint64_t)(cur & 0x7f) << shift;
shift += 7;
} while (cur & 0x80);
*val = result;
*buf = ptr;
}
void varint_encode(uint64_t val, uint8_t** buf) {
uint8_t* ptr = *buf;
while (val >= 0x80) {
*ptr++ = ((uint8_t)val | 0x80);
val >>= 7;
}
*ptr++ = (uint8_t)(val);
*buf = ptr;
}
void print_bits(FILE* fd, uint64_t v, int depth)
{
uint8_t* b = (uint8_t*)&v;
uint8_t byte;
int i, j;
int bits = sizeof(uint64_t) * 8;
bool foundNonZero = false;
for (i = sizeof(uint64_t) - 1; i >= 0; i--)
{
for (j = 7; j >= 0; j--)
{
bits--;
byte = (b[i] >> j) & 1;
if (byte) {
foundNonZero = true;
}
if (!foundNonZero && bits > depth&& bits > 8)
continue;
fprintf(fd, "%u", byte);
if (bits == depth)
fprintf(fd, " ");
}
}
}
void print_hash_stats(hash_ctx_t* ctx) {
printf("Depth: %i - Entries: %I64u, Buckets: %i \n", ctx->dir->depth, ctx->dir->number_of_entries, ctx->dir->number_of_buckets);
for (size_t i = 0; i < ctx->dir->number_of_buckets; i++)
ctx->dir->buckets[i]->seen = false;
uint32_t min = 64, max = 0, total = 0,empties=0;
uint64_t sum = 0;
for (size_t i = 0; i < ctx->dir->number_of_buckets; i++)
{
hash_bucket_t* b = ctx->dir->buckets[i];
if (b->seen)
continue;
b->seen = false;
size_t total_used = 0;
for (size_t i = 0; i < NUMBER_OF_HASH_BUCKET_PIECES; i++) {
total_used += b->pieces[i].bytes_used;
if (b->pieces[i].bytes_used)
min = min < b->pieces[i].bytes_used ? min : b->pieces[i].bytes_used;
else
empties++;
max = max > b->pieces[i].bytes_used ? max : b->pieces[i].bytes_used;
sum += b->pieces[i].bytes_used;
total++;
}
//printf("%p - Depth: %i, Entries: %I64u, Size: %i\n", b, b->depth, b->number_of_entries, total_used);
}
printf("Total: %i, Min: %i, Max: %iu, Sum: %llu, Empties: %i, Avg: %f\n", total, min, max, sum, empties, sum / (float)total);
}
void print_bucket(FILE* fd, hash_bucket_t* b, uint32_t idx) {
size_t total_used = 0;
for (size_t i = 0; i < NUMBER_OF_HASH_BUCKET_PIECES; i++) {
total_used += b->pieces[i].bytes_used;
}
fprintf(fd, "\tbucket_%p [label=\"Depth: %i, Entries: %I64u, Size: %i, Index: %i\\l--------\\l", b, b->depth, b->number_of_entries, total_used, idx);
for (size_t i = 0; i < NUMBER_OF_HASH_BUCKET_PIECES; i++) {
hash_bucket_piece_t* p = &b->pieces[i];
uint8_t* buf = p->data;
uint8_t* end = p->data + p->bytes_used;
while (buf < end)
{
uint64_t k, v;
varint_decode(&buf, &k);
varint_decode(&buf, &v);
print_bits(fd, k, b->depth);
fprintf(fd, " \\| %4llu = %4llu\\l", k, v);
}
}
fprintf(fd, "\"]\n");
}
void print_dir_graphviz_to_file(FILE* fd, hash_ctx_t* ctx) {
fprintf(fd, "digraph hash {\n\tnode[shape = record ]; \n");
fprintf(fd, "\ttable [label=\"Depth: %i, Size: %i\\lPages: %i, Entries: %I64u\\l\"]\n", ctx->dir->depth, ctx->dir->number_of_buckets, ctx->dir->directory_pages, ctx->dir->number_of_entries);
fprintf(fd, "\tbuckets [label=\"");
for (size_t i = 0; i < ctx->dir->number_of_buckets; i++)
{
if (i != 0)
fprintf(fd, "|");
fprintf(fd, "<bucket_%i> %i - %p ", i, i, ctx->dir->buckets[i]);
ctx->dir->buckets[i]->seen = false;
}
fprintf(fd, "\"]\n");
for (size_t i = 0; i < ctx->dir->number_of_buckets; i++)
{
if (ctx->dir->buckets[i]->seen)
continue;
ctx->dir->buckets[i]->seen = true;
print_bucket(fd, ctx->dir->buckets[i], i);
}
for (size_t i = 0; i < ctx->dir->number_of_buckets; i++) {
fprintf(fd, "\tbuckets:bucket_%i -> bucket_%p;\n", i, ctx->dir->buckets[i]);
}
fprintf(fd, "\ttable->buckets;\n}\n");
}
void print_dir_graphviz(hash_ctx_t* ctx) {
print_dir_graphviz_to_file(stdout, ctx);
}
void write_dir_graphviz(hash_ctx_t* ctx, const char* prefix) {
static int counter = 0;
uint8_t buffer[256];
memset(buffer, 0, sizeof buffer);
counter++;
sprintf_s(buffer, sizeof buffer, "%s-%i.txt", prefix, counter);
FILE* f = NULL;
errno_t err = fopen_s(&f, buffer, "w");
if (err)
{
printf("Failed to open %s - %i", buffer, err);
return;
}
print_dir_graphviz_to_file(f, ctx);
if (f != 0)
fclose(f);
char* copy = _strdup(buffer);
memset(buffer, 0, sizeof buffer);
sprintf_s(buffer, sizeof buffer, "C:\\Users\\ayende\\Downloads\\graphviz-2.38\\release\\bin\\dot.exe -Tsvg %s > %s.svg", copy, copy);
system(buffer);
memset(buffer, 0, sizeof buffer);
sprintf_s(buffer, sizeof buffer, "%s.svg", copy);
system(buffer);
free(copy);
}
uint32_t hash_table_bucket_number(hash_ctx_t* ctx, uint64_t h) {
return h & (((uint64_t)1 << ctx->dir->depth) - 1);
}
size_t hash_table_get_directory_capacity(hash_ctx_t* ctx) {
return ((ctx->dir->directory_pages * HASH_BUCKET_PAGE_SIZE) - sizeof(hash_directory_t)) / sizeof(hash_bucket_t*);
}
hash_bucket_t* create_hash_bucket(hash_ctx_t* ctx) {
hash_bucket_t* b = ctx->allocate_page(1);
if (b == NULL)
return NULL;
memset(b, 0, sizeof(hash_bucket_t));
b->depth = ctx->dir->depth;
return b;
}
bool hash_table_get(hash_ctx_t* ctx, uint64_t key, uint64_t* value) {
uint32_t bucket_idx = hash_table_bucket_number(ctx, key);
hash_bucket_t* b = ctx->dir->buckets[bucket_idx];
uint32_t piece_idx = key % NUMBER_OF_HASH_BUCKET_PIECES;
for (size_t i = 0; i < NUMBER_OF_HASH_BUCKET_PIECES; i++)
{
hash_bucket_piece_t* p = &b->pieces[(piece_idx + i) % NUMBER_OF_HASH_BUCKET_PIECES];
uint8_t* buf = p->data;
uint8_t* end = p->data + p->bytes_used;
while (buf < end)
{
uint64_t k, v;
varint_decode(&buf, &k);
varint_decode(&buf, &v);
if (k == key) {
*value = v;
return true;
}
}
if (!p->overflowed)
break;
}
return false;
}
bool hash_table_piece_append_kv(hash_bucket_t* cur, uint64_t key, uint64_t value) {
uint32_t piece_idx = key % NUMBER_OF_HASH_BUCKET_PIECES;
uint8_t buffer[20];
uint8_t* write_buf = buffer;
varint_encode(key, &write_buf);
varint_encode(value, &write_buf);
uint8_t size = (uint8_t)(write_buf - buffer);
for (size_t i = 0; i < NUMBER_OF_HASH_BUCKET_PIECES; i++)
{
hash_bucket_piece_t* p = &cur->pieces[(piece_idx + i) % NUMBER_OF_HASH_BUCKET_PIECES];
if (size + p->bytes_used > PIECE_BUCKET_BUFFER_SIZE) {
p->overflowed = true;
continue;
}
memcpy(p->data + p->bytes_used, buffer, size);
p->bytes_used += size;
cur->number_of_entries++;
return true;
}
return false;
}
void validate_bucket(hash_ctx_t* ctx, hash_bucket_t* tmp) {
#if VALIDATE
uint64_t mask = ((uint64_t)1 << tmp->depth) - 1;
uint64_t first = 0;
bool has_first = false;
for (size_t i = 0; i < NUMBER_OF_HASH_BUCKET_PIECES; i++)
{
uint8_t* buf = tmp->pieces[i].data;
uint8_t* end = buf + tmp->pieces[i].bytes_used;
while (buf < end)
{
uint64_t k, v;
varint_decode(&buf, &k);
varint_decode(&buf, &v);
if (has_first == false)
{
first = k;
has_first = true;
}
if ((k & mask) != (first & mask)) {
write_dir_graphviz(ctx, "problem");
printf("Problem\n");
}
}
}
#endif
}
bool hash_table_put(hash_ctx_t* ctx, uint64_t key, uint64_t value) {
uint32_t bucket_idx = hash_table_bucket_number(ctx, key);
hash_bucket_t* b = ctx->dir->buckets[bucket_idx];
uint32_t piece_idx = key % NUMBER_OF_HASH_BUCKET_PIECES;
uint8_t tmp_buffer[20]; // each varint can take up to 10 bytes
uint8_t* buf_end = tmp_buffer;
varint_encode(key, &buf_end);
varint_encode(value, &buf_end);
ptrdiff_t encoded_size = buf_end - tmp_buffer;
for (size_t i = 0; i < NUMBER_OF_HASH_BUCKET_PIECES; i++)
{
hash_bucket_piece_t* p = &b->pieces[(piece_idx + i) % NUMBER_OF_HASH_BUCKET_PIECES];
uint8_t* buf = p->data;
uint8_t* end = p->data + p->bytes_used;
while (buf < end)
{
uint64_t k, v;
uint8_t* cur_buf_start = buf;
varint_decode(&buf, &k);
varint_decode(&buf, &v);
if (k == key) {
if (v == value)
return true; // nothing to do, value is already there
ptrdiff_t diff = buf - cur_buf_start;
if (diff == encoded_size) {
// new value fit exactly where the old one went, let's put it there
memcpy(cur_buf_start, tmp_buffer, encoded_size);
validate_bucket(ctx, b);
return true;
}
memmove(cur_buf_start, buf, end - buf);
p->bytes_used -= (uint8_t)diff;
b->number_of_entries--;
ctx->dir->number_of_entries--;
break; // found it, let's put this in
}
}
if (p->bytes_used + encoded_size <= PIECE_BUCKET_BUFFER_SIZE) {
memcpy(p->data + p->bytes_used, tmp_buffer, encoded_size);
p->bytes_used += (uint8_t)encoded_size;
b->number_of_entries++;
ctx->dir->number_of_entries++;
validate_bucket(ctx, b);
return true; // was able to update the value in the same piece, done
}
// if we are looking at an overflow page, move to the next one and try to find it there
if (!p->overflowed)
break;
}
// couldn't find it in the proper place, let's put it in overflow
for (size_t i = 0; i < NUMBER_OF_HASH_BUCKET_PIECES; i++)
{
hash_bucket_piece_t* p = &b->pieces[(piece_idx + i) % NUMBER_OF_HASH_BUCKET_PIECES];
if (p->bytes_used + encoded_size <= PIECE_BUCKET_BUFFER_SIZE) {
memcpy(p->data + p->bytes_used, tmp_buffer, encoded_size);
p->bytes_used += (uint8_t)encoded_size;
b->number_of_entries++;
ctx->dir->number_of_entries++;
validate_bucket(ctx, b);
return true; // was able to update the value in the same piece, done
}
p->overflowed = true;
}
// there is no room here, need to expand
if (ctx->dir->depth == b->depth) {
hash_directory_t* new_dir;
if (ctx->dir->number_of_buckets * 2 * sizeof(hash_bucket_t*) > hash_table_get_directory_capacity(ctx)) {
// have to increase the actual allocated memory here
new_dir = ctx->allocate_page(ctx->dir->directory_pages * 2);
if (new_dir == NULL)
return false;
size_t dir_size = ctx->dir->directory_pages * HASH_BUCKET_PAGE_SIZE;
memcpy(new_dir, ctx->dir, dir_size);
new_dir->directory_pages *= 2;
}
else {
new_dir = ctx->dir; // there is enough space to increase size without allocations
}
size_t buckets_size = ctx->dir->number_of_buckets * sizeof(hash_bucket_t*);
memcpy((uint8_t*)new_dir->buckets + buckets_size, (uint8_t*)ctx->dir->buckets, buckets_size);
new_dir->depth++;
new_dir->number_of_buckets *= 2;
if (new_dir != ctx->dir) {
ctx->release_page(ctx->dir);
ctx->dir = new_dir;
}
}
//write_dir_graphviz(ctx, "BEFORE");
hash_bucket_t* n = create_hash_bucket(ctx);
if (!n)
return false;
hash_bucket_t* tmp = ctx->allocate_page(1);
if (!tmp) {
ctx->release_page(n);
ctx->release_page(tmp);
// no need to release the ctx->dir we allocated, was wired
// properly to the table and will be freed with the whole table
return false;
}
memcpy(tmp, b, HASH_BUCKET_PAGE_SIZE);
memset(b, 0, sizeof(hash_bucket_t));
memset(n, 0, sizeof(hash_bucket_t));
n->depth = b->depth = tmp->depth + 1;
uint32_t bit = 1 << tmp->depth;
#if VALIDATE
uint64_t mask = (bit >> 1) - 1;
bool has_first = false;
uint64_t first_key = 0;
#endif
for (size_t i = 0; i < NUMBER_OF_HASH_BUCKET_PIECES; i++)
{
uint8_t* buf = tmp->pieces[i].data;
uint8_t* end = buf + tmp->pieces[i].bytes_used;
while (buf < end)
{
uint64_t k, v;
varint_decode(&buf, &k);
varint_decode(&buf, &v);
#if VALIDATE
if (!has_first) {
first_key = k;
has_first = true;
}
if ((first_key & mask) != (k & mask)) {
printf("mistmatch!: %I64u != %I64u\n", first_key, k);
}
#endif
hash_bucket_t* cur = k & bit ? n : b;
bool success = hash_table_piece_append_kv(cur, k, v);
#if VALIDATE
if (!success)
printf("Can't split a page properly? Impossible");
#endif
}
}
ctx->release_page(tmp);
for (size_t i = key & (bit - 1); i < ctx->dir->number_of_buckets; i += bit)
{
ctx->dir->buckets[i] = i & bit ? n : b;
}
// now can add the new value in...
{
hash_bucket_t* cur = key & bit ? n : b;
if (hash_table_piece_append_kv(cur, key, value)) {
ctx->dir->number_of_entries++;
}
else {
if (!hash_table_put(ctx, key, value)) {
#if VALIDATE
printf("Unable to recursively add? That really should never happen.");
#endif
return false;
}
}
}
validate_bucket(ctx, n);
validate_bucket(ctx, b);
return true;
}
bool hash_table_init(hash_ctx_t* ctx) {
ctx->dir = ctx->allocate_page(1);
if (ctx->dir == NULL)
return false;
memset(ctx->dir, 0, HASH_BUCKET_PAGE_SIZE);
ctx->dir->number_of_entries = 0;
ctx->dir->number_of_buckets = 2;
ctx->dir->directory_pages = 1;
ctx->dir->depth = 1;
ctx->dir->buckets[0] = create_hash_bucket(ctx);
ctx->dir->buckets[1] = create_hash_bucket(ctx);
if (!ctx->dir->buckets[0] || !ctx->dir->buckets[1]) {
ctx->release_page(ctx->dir->buckets[0]);
ctx->release_page(ctx->dir->buckets[1]);
ctx->release_page(ctx->dir);
return false;
}
return true;
}
int allocations = 0;
void* allocate_4k_page(uint32_t n) {
allocations++;
return _aligned_malloc(HASH_BUCKET_PAGE_SIZE * n, HASH_BUCKET_PAGE_SIZE);
}
void release_4k_page(void* p) {
if (!p)
return;
allocations--;
_aligned_free(p);
}
int main()
{
srand(19324);
uint32_t const size = 1024 * 1024;
uint64_t* keys = malloc(size * sizeof(uint64_t));
uint64_t* values = malloc(size * sizeof(uint64_t));
if (!keys || !values)
return -1;
for (size_t i = 0; i < size; i++)
{
keys[i] = wygrand();
values[i] = wygrand();
}
struct hash_ctx ctx = { allocate_4k_page, release_4k_page };
if (!hash_table_init(&ctx)) {
printf("Failed to init\n");
return -1;
}
uint64_t first_key = keys[0];
uint64_t first_value = values[0];
for (size_t i = 0; i < size; i++)
{
uint64_t v;
if (i == 184) {
printf("a - ");
}
if (!hash_table_put(&ctx, keys[i], values[i])) {
printf("Failed to put %i\n", i);
write_dir_graphviz(&ctx, "PUT-ERR");
return -1;
}
if (keys[i] == first_key)
first_value = values[i];
if (!hash_table_get(&ctx, first_key, &v) || v != first_value) {
printf("Failed to get 0 on %i\n", i);
write_dir_graphviz(&ctx, "PUT-ERR");
}
}
//write_dir_graphviz(&ctx, "FINAL");
for (size_t x = 0; x < size; x++)
{
uint64_t val;
if (!hash_table_get(&ctx, keys[x], &val)) {
printf("Failed to get %i\n", x);
write_dir_graphviz(&ctx, "GET-ERR");
return -1;
}
if (val != values[x]) {
printf("mismatch on %I32u - %I64u - %I64u, %I64u \n", x, keys[x], val, values[x]);
}
}
print_hash_stats(&ctx);
printf("%f MB\n", ((double)allocations * (double)HASH_BUCKET_PAGE_SIZE) / 1024.0 / 1024.0);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.