Iterating arbitrary memory and possible alignment issues

Question

I'm implementing a simple hash map in C, and I thus implemented a generic and simple hash function which has the following implementation:

static inline int64_t hash(void_t *key, size_t ksize)
{
    int64_t hash = 0;
    char_t *key_str = key;

    for (size_t i = 0; i < ksize; i++)
    {
        char_t c = key_str[i];
        hash = 31 * hash + c;
    }

    return hash;
}

I wondered if it'd be better to implement it like:

static inline int64_t hash_x64(void_t *key, size_t ksize)
{
    int64_t hash = 0;

    size_t remain_ksize = ksize;
    size_t i = 0;

    while (remain_ksize >= sizeof(int64_t)) 
    {
        int64_t *val = key + i;
        hash = 31 * hash + *val;

        remain_ksize -= sizeof(int64_t);
        i += sizeof(int64_t);
    }

    char_t *key_str = key;

    for (; i < remain_ksize; i++)
    {
        char_t c = key_str[i];
        hash = 31 * hash + c;
    }

    return hash;
}

Does this violate any alignment / aliasing rules? Is this code considered safe on x64 architectures? Would it execute faster on x64, or does the compiler already optimize the hash function for the underlying architecture?

[No, it is not safe](https://stackoverflow.com/questions/46790550/c-undefined-behavior-strict-aliasing-rule-or-incorrect-alignment) — Antti Haapala -- Слава Україні, Mar 20 '18 at 19:56

score 1 · Accepted Answer · answered Mar 20 '18 at 17:32

1

There's no guarantee that the buffer passed in is properly aligned on a 64-bit boundary. So the latter code runs the risk of crashing due to unaligned memory assess. There may also be a strict aliasing issue depending on what was passed in.

You're better off reading a single byte at a time. It avoids both issues, and any difference in performance is likely marginal.

answered Mar 20 '18 at 17:32

dbush

205,898
23
218
273

Let's say my key is 67 bytes long, I could iterate on the first 64 bytes as `int64_t` and then iterate the remaining 3 bytes. Could this still rise issues? – Jazzwave06 Mar 20 '18 at 17:34
@sturcotte06 Yes, because there's no guarantee the key starts on a 64-bit boundary. – dbush Mar 20 '18 at 17:35
Ok thank you very much. Also, would GCC with aggressive optimizations turned on, optimize this to prevent that registers are filled with only 1 byte at a time? – Jazzwave06 Mar 20 '18 at 17:36
@sturcotte06 Not sure, but unless you have a very specific reason to optimize at that level, it's not worth worrying about. – dbush Mar 20 '18 at 17:38
I have absolutely no reason to optimize this, as those maps are mainly used to replace XMacros generated maps (i.e static construction of the library). I was only wondering if there were optimizations I was not aware of that I could re-use in more performance-critical sections. – Jazzwave06 Mar 20 '18 at 17:42

Iterating arbitrary memory and possible alignment issues

1 Answers1