Xxhash: Add NEON support

[Cyan4973]

Original request by @42Bastian : https://github.com/Cyan4973/xxHash/pull/72

Inspired from the AVX2 discussion, I suggest following code for ARM targets:
Function:
FORCE_INLINE U32 XXH32_endian_align(const void* input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align)

`if (len>=16) {
const BYTE* const limit = bEnd - 16;
const uint32_t initial[4] = {
PRIME32_1 + PRIME32_2,
PRIME32_2,
0,
-PRIME32_1
};
U32 v1;
U32 v2;
U32 v3;
U32 v4;
uint32x4_t vseed = vdupq_n_u32 (seed); // v(0,1,2,3) = seed
uint32x4_t prime1 = vdupq_n_u32(PRIME32_1); // prime1(0,1,2,3) = prime1
uint32x4_t prime2 = vdupq_n_u32(PRIME32_2); // prime2(0,1,2,3) = prime2
uint32x4_t v = vld1q_u32 (initial); // read initial into vector
uint32x4_t input;
uint32x4_t tmp;
v += vseed;
do {
input = vld1q_u32((uint32_t )p);
p += 16;
/ round */
v = vmlaq_u32 (v, input, prime2); // seed += input * PRIME32_2;
tmp = vshrq_n_u32 (v, 19); // XXH_rotl32(seed, 13);
v = vsliq_n_u32 (tmp, v, 13);
v = vmulq_u32 (v, prime1); // seed *= PRIME32_1;
} while (p<=limit);

v1 = vgetq_lane_u32(v,0);
v2 = vgetq_lane_u32(v,1);
v3 = vgetq_lane_u32(v,2);
v4 = vgetq_lane_u32(v,3);

h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
} else {
h32 = seed + PRIME32_5;
}`

On a ZYNQ (Cortex-A9) it nearly doubles speed.

[easyaspi314]

I can confirm the double speed.

LG G3 (Snapdragon 801/Krait 400, Cortex-A15 compatible)

(in Termux, on device)

$ clang-7 -v
clang version 7.0.0 (tags/RELEASE_700/final)
Target: arm--linux-android
... not important
$ make CC=clang-7 CFLAGS="-Ofast -march=armv7ve -mtune=native"

(Without the -march=armv7ve -mtune=native, clang will stupidly try to build for ARMv5TE.)

Without the patch:

$ ./xxhsum -b xxhash.c
./xxhsum 0.6.5 (32-bits little endian)
XXH32:              68220 it/s (  2312.4 MB/s)
XXH32 unaligned:    68356 it/s (  2317.0 MB/s)
XXH64:              24983 it/s (   846.8 MB/s)
XXH64 unaligned:    22392 it/s (   759.0 MB/s)

With the patch:

$ ./xxhsum -b xxhash.c
./xxhsum 0.6.5 (32-bits little endian)
XXH32:              120759 it/s (  4093.3 MB/s)
XXH32 unaligned:    121570 it/s (  4120.8 MB/s)
XXH64:               24838 it/s (   841.9 MB/s)
XXH64 unaligned:     22391 it/s (   759.0 MB/s)

[easyaspi314]

So I was experimenting and I think I got a thing that works portably, and that is using GCC/Clang's vector extensions.

The cool thing about the vector extensions is that they gracefully degrade if needed. So, even on, say, ARMv4t which lacks any form of SSE entirely, GCC will just use an array.

The other cool thing is that they can be treated like integers or arrays (except they don't decay to pointers or implicitly convert), and, as long as we treat them like arrays, we can use the conditional below:

#if XXH_GCC_VERSION >= 400
    typedef uint32_t U32x4 __attribute__((vector_size(16)));
#else 
    typedef uint32_t U32x4[4];
#endif 

The code looks like this:

    if (len>=16) {
        const BYTE* const limit = bEnd - 15;
        U32x4 v = {
            seed + PRIME32_1 + PRIME32_2,
            seed + PRIME32_2,
            seed + 0,
            seed - PRIME32_1
        };
        const U32x4 r = {1, 7, 12, 18};
        int i;
        do {
            const U32x4 inp = {
                XXH_get32bits(p),
                XXH_get32bits(p + 4),
                XXH_get32bits(p + 8),
                XXH_get32bits(p + 12)
            };

            for (i = 0; i < 4; i++) {
                v[i] = XXH32_round(v[i], inp[i]);
            }
            p += 16;
        } while (p < limit);
        /*  */
        for (i = 0; i < 4; i++) {
            v[i] = XXH_rotl32(v[i], r[i]);
        }
        /* Add them all together */
        h32 = v[0] + v[1] + v[2] + v[3];
    }

Don't worry about the loops, they are automatically vectorized.

It doesn't get past 4000 like the raw NEON instructions, but it gets to 3700 which is still a lot better, and it is pretty readable.

$ ./xxhsum -b xxhash.c
./xxhsum 0.6.5 (32-bits little endian)
XXH32:              68220 it/s (  3738.0 MB/s)
XXH32 unaligned:    68356 it/s (  3738.4 MB/s)

Edit: It is safe to let the compiler inline it.

[easyaspi314]

It also seems to have no negative effect on, say, x86_64, which already seems to vectorize it well (except when you disabled it in the Makefile). I get the exact same results as the original on my wimpy 2009 MacBook with a 2.13 GHz Core 2 Duo (penryn), both with sse4 enabled and disabled.

[Cyan4973]

All this looks good,
I'm opened to a PR along these lines.

Note that vectorization is actually detrimental for XXH32 on Intel cpus,
but the situation can be entirely different for ARM cpus.

[42Bastian]

I would keep both versions. Vectorization seems to work pretty well with clang-7. But there are a lot of old GCCs around which might fail on this.

[easyaspi314]

Huh. Well that's strange. GCC 8.2 can't seem to vectorize it properly on ARM unless I use the int-style operations, which then causes more issues.

I guess this isn't as simple as it seems. :thinking:

[Cyan4973]

Is there still a case about making a NEON optimized version of legacy XXH32 ?
I don't remember if XXH32a was created because of an absence of significant outcome with XXH32 proper.

[easyaspi314]

On ARMv7, NEON is definitely beneficial for both XXH32 and XXH64, however, aarch64 doesn't see as much of a difference.

[Cyan4973]

I've been testing this code on aarch64, and it seems to improve performance by ~15%.
While it's not as dramatic as the x2 performance improvement measured on ARM v7, it's still a nice improvement.

_edit_ : erf, nope, the performance difference came from the large fluctuations associated with thermal throttling and energy savings. When measurements are repeated enough, it seems the NEON code doesn't bring any benefit on this aarch64 platform, an outcome which feels similar to @easyaspi314 experience.

It seems this patch would be useful for ARMv7 + NEON, a combination which is not guaranteed, and complexify detection by predefined macros.