Reading aligned memory using fast u32 access can lead to strict aliasing issues when paired with inlining

user_646947 0
Viewed 169

I've got a function which essentially produces a hash value over an arbitrary memory region. The input argument uses const void* type, as a way to say "this can be anything". So essentially : 

unsigned hash(const void* ptr, size_t size);

so far, so good.

The blob of bytes can be anything, and its start address can be anywhere. Meaning that sometimes, it's aligned on 32-bit boundaries, and sometimes it's not.

On some platforms (armv6 for example, or mips), reading from unaligned memory result in huge performance penalty. It's actually not possible to read 32-bit from unaligned memory directly, so the compiler tends to settle for a safer byte-by-byte recombination algorithm (the exact implementation details are hidden behind a memcpy()).

The safe access method is of course a lot slower than a direct 32-bit access, which is itself only possible when input data is properly aligned on 32-bit boundary. This leads to a design trying to separate the 2 cases : when input is unaligned, use the safe access code path, when input is aligned (effectively quite often) use the direct 32-bit access code path.

The difference in performance is huge, we are not talking of a few % here, this translates into a 5x performance increase, sometimes even more. So it's not just "nice", it actually makes the function competitive or not, useful or not.

This design has been working fine so far, in a decent number of scenarios.

Enter inlining.

Now, with the function implementation accessible at compilation time, a clever compiler can peel off all the indirection layers, and reduce the implementation to its essential elements. In the case where it can prove that the input is necessarily aligned, such as a struct with defined members, it can simplify the code, remove all the const void* indirections, and get down to the barebone implementation where the memory area is effectively read using a const u32* pointer.

And now strict-aliasing can kick in, as the input area is written using a struct S* ptr, and read using a different const u32* ptr, therefore allowing the compiler to consider these 2 operations as completely independent, eventually re-ordering them, leading to an incorrect outcome.

This is essentially the interpretation I received from a user. It may worth noting that I was unable to reproduce the issue, but strict-aliasing issues uncovered through inlining, this is a known topic. It is also known that strict aliasing can be difficult to reproduce due to tiny implementation details leading to different optimization choices depending on compiler version. I therefore consider the report as credible, but can't study it directly in absence of a reproduction case.

Anyway, now comes the question. How to handle this case correctly ? A "safe" solution is to always use the memcpy() path, but it craters the performance so much that it makes the function just no longer useful. Plus, it's obviously a terrible waste of energy. The easy escape is to not inline, though it leads to its own function call overhead (to be fair, not that large), and more importantly just "hides" the problem rather than solve it.

But I've yet to find a solution to it. I've been told that, no matter what kind of intermediate pointer is used, even if a const char* is part of the cast chain, this will not prevent the final const u32* read operation from violating strict aliasing (just repeating, I can't test it, because I can't reproduce the case). Described this way, this feels almost hopeless.

But I can't help but note that memcpy() can properly avoid such kind of re-ordering risk, even though its interface also uses const void*, and exact implementation vary a lot, but we can be certain that it's not just reading byte-by-byte const char*, as performance is excellent, and doesn't hesitate using vector code when faster. Also, memcpy() is a function which is definitely inlined a lot. So I guess there must be a solution to this problem.

strict-aliasing inline memory-access hash c
1 Answers

(unsigned) char is exempt from strict aliasing rules. No matter what, the following is safe and sane as long as sizeof(uint32_t) == 4:

unsigned hash(const void* ptr, size_t size) {
    const unsigned char* bytes = ptr;

    while (size >= 4) {
        uint32_t x;
        memcpy(&x, bytes, 4);
        bytes += 4;
        size -= 4;

        // Use x.
    }

    // Size leftover bytes.
}

Do note that the values of x will be dependent on the endianness of your machine. If you require cross-platform consistent hashes you will need to convert to your preferred endianness.

Note that if you force alignment you can make the compiler generate fast path code even with memcpy:

void* align(void* p, size_t n) {
    // n must be power of two.
    uintptr_t pi = (uintptr_t) p;
    return (unsigned char*) ((pi + (n - 1)) & -n);
}

inline uint32_t update_hash(uint32_t h, uint32_t x) {
    h += x;
    return h;
}

unsigned hash(const void* ptr, size_t size) {
    const unsigned char* bytes = (unsigned char*) ptr;
    const unsigned char* aligned_bytes = align((void*) bytes, 4);

    uint32_t h = 0;
    uint32_t x;
    if (bytes == aligned_bytes) {
        // Aligned fast path.
        while (size >= 4) {
            memcpy(&x, bytes, 4);
            h = update_hash(h, x);
            size -= 4;
            bytes += 4;
        }
    } else {
        // Slower unaligned path, copy to aligned buffer.
        while (size >= 4) {
            uint32_t buffer[32];
            size_t bufsize = size < 4*32 ? size / 4 : 32;
            memcpy(buffer, bytes, 4*bufsize);
            size -= 4*bufsize;

            for (int i = 0; i < bufsize; ++i) {
                h = update_hash(h, buffer[i]);
            }
        }
    }

    if (size) {
        // Assuming little endian.
        x = 0;
        memcpy(&x, bytes, size);
        h = update_hash(h, x);
    }

    return h;
}
user_5656350
Related