bench.c

// https://old.reddit.com/r/C_Programming/comments/1iljkn2
// https://github.com/jamesnolanverran/dmap
#include "dmap.c"
#include <string.h>

#define KEYLEN  8
#define RUNS    10
#define KEYS    1000000

static void encode(char *key, int x)
{
    memset(key, '0', KEYLEN);
    char *end = key + KEYLEN;
    do *--end = '0' + x%10;
    while (x /= 10);
}

#ifndef BASELINE

int main(void)
{
    for (int n = 0; n < RUNS; n++) {
        int *m = 0;
        dmap_init(m, 0, ALLOC_MALLOC);
        for (int i = 0; i < KEYS; i++) {
            char key[KEYLEN];
            encode(key, i);
            dmap_insert(m, &key, i);
        }
        dmap_free(m);
    }
}


#else  // hash trie

#define new(a, t)   (t *)alloc(a, sizeof(t))
typedef struct { char *beg, *end; } Arena;
static void *alloc(Arena *a, int size) { return memset(a->end -= size, 0, size); }

typedef struct Map Map;
struct Map {
    Map *child[4];
    char key[KEYLEN];
    int  value;
};

static uint64_t hash(char *s)
{
    #if 1
    uint64_t h = 0x100;
    for (int i = 0; i < KEYLEN; i++) {
        h ^= s[i] & 255;
        h *= 1111111111111111111;
    }
    return h;
    #else
    u64 r[2];
    MurmurHash3_x64_128(s, KEYLEN, 0x9747b28c, r);
    return *r;
    #endif
}

static int *upsert(Map **m, char *key, Arena *a)
{
    for (uint64_t h = hash(key); *m; h <<= 2) {
        if (!memcmp(key, (*m)->key, KEYLEN)) {
            return &(*m)->value;
        }
        m = &(*m)->child[h>>62];
    }
    *m = new(a, Map);
    memcpy((*m)->key, key, KEYLEN);
    return &(*m)->value;
}

int main(void)
{
    int   cap = 1<<30;
    char *mem = malloc(cap);
    for (int n = 0; n < RUNS; n++) {
        Arena a = {mem, mem+cap};
        Map  *m = 0;
        for (int i = 0; i < KEYS; i++) {
            char key[KEYLEN];
            encode(key, i);
            upsert(&m, key, &a);
        }
    }
}

#endif