Implement memcmp using SIMD intrinsics

This patch implements memcmp and use librte_hash as the first candidate to use rte_memcmp which is implemented using AVX/SSE intrinsics.

Tested with GCC(4.8.2) and Clang(3.4-1) compilers and both tests show better performance on Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz, Ubuntu 14.04 x86_64 shows when compared to memcmp.

Changes in v3:
Implement complete memcmp functionality. Implement functional and performance tests and add it to "make test" infrastructure code.

Changes in v2:
Modified code to support only upto 64 bytes as that's the max bytes used by hash for comparison.

Changes in v1:
Initial changes to support memcmp with support upto 128 bytes.

Signed-off-by Ravi Kerur <[email protected]>

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +0 -0

/librte_eal/common/include/arch/x86/rte_memcmp.h

+ * @param src_1
+ * Pointer to the first source of the data.
+ * @param src_2
+ * Pointer to the second source of the data.
+ * @param n
+ * Number of bytes to compare.
+ * @return

+ *   zero if src_1 equal src_2
+ *   -ve if src_1 less than src_2
+ *   +ve if src_1 greater than src_2

+ */

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +4 -0

+static inline int
+rte_memcmp(const void *src_1, const void *src,
+		size_t n) __attribute__((always_inline));
+

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +4 -0

+			return i;
+	return -1;
+}
+

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +8 -0

+static inline int
+rte_memcmp(const void *_src_1, const void *_src_2, size_t n)
+{
+	const uint8_t *src_1 = (const uint8_t *)_src_1;
+	const uint8_t *src_2 = (const uint8_t *)_src_2;
+	int ret = 0;
+
+	if (n < 16)

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +48 -0

+	if (n <= 48) {
+		ret = rte_cmp32(src_1, src_2);
+		if (unlikely(ret != 0))
+			return ret;
+
+		return rte_cmp16(src_1 - 16 + n, src_2 - 16 + n);
+	}
+
+	if (n <= 64) {
+		ret = rte_cmp32(src_1, src_2);
+		if (unlikely(ret != 0))
+			return ret;
+
+		ret = rte_cmp16(src_1 + 32, src_2 + 32);
+
+		if (unlikely(ret != 0))
+			return ret;
+
+		return rte_cmp16(src_1 - 16 + n, src_2 - 16 + n);
+	}
+
+	if (n <= 96) {
+		ret = rte_cmp64(src_1, src_2);
+		if (unlikely(ret != 0))
+			return ret;
+
+		ret = rte_cmp16(src_1 + 64, src_2 + 64);
+		if (unlikely(ret != 0))
+			return ret;
+
+		return rte_cmp16(src_1 - 16 + n, src_2 - 16 + n);
+	}
+
+	if (n <= 128) {
+		ret = rte_cmp64(src_1, src_2);
+		if (unlikely(ret != 0))
+			return ret;
+
+		ret = rte_cmp32(src_1 + 64, src_2 + 64);
+		if (unlikely(ret != 0))
+			return ret;
+
+		ret = rte_cmp16(src_1 + 96, src_2 + 96);
+		if (unlikely(ret != 0))
+			return ret;
+
+		return rte_cmp16(src_1 - 16 + n, src_2 - 16 + n);
+	}

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +20 -0

+{
+	int ret;
+
+	ret = rte_cmp16((const uint8_t *)src_1 + 0 * 16,
+			(const uint8_t *)src_2 + 0 * 16);
+
+	if (unlikely(ret != 0))
+		return ret;
+
+	ret = rte_cmp16((const uint8_t *)src_1 + 1 * 16,
+			(const uint8_t *)src_2 + 1 * 16);
+
+	if (unlikely(ret != 0))
+		return ret;
+
+	return rte_cmp16((const uint8_t *)src_1 + 2 * 16,
+			(const uint8_t *)src_2 + 2 * 16);
+}
+
+/**

Quoted 2 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +0 -0

/librte_eal/common/include/arch/x86/rte_memcmp.h

[...]

lib

Quoted 7 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +7 -0

+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/**
+ * Compare bytes between two locations. The locations must not overlap.
+ *

Parameter names should be kept consistent as they are in function body.

Quoted 15 lines

+ * @param src_1
+ * Pointer to the first source of the data.
+ * @param src_2
+ * Pointer to the second source of the data.
+ * @param n
+ * Number of bytes to compare.
+ * @return

+ *   zero if src_1 equal src_2
+ *   -ve if src_1 less than src_2
+ *   +ve if src_1 greater than src_2

+ */

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +4 -0

+static inline int
+rte_memcmp(const void *src_1, const void *src,
+             size_t n) __attribute__((always_inline));
+

lib

Quoted 10 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +10 -0

+/**
+ * Find the first different bit for comparison.
+ */
+static inline int
+rte_cmpffd (uint32_t x, uint32_t y)
+{
+     int i;
+     int pos = x ^ y;
+     for (i = 0; i < 32; i++)
+             if (pos & (1<<i))

Coding style check :-)
BTW, does the bsf instruction provide this check?

Quoted 4 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +4 -0

+                     return i;
+     return -1;
+}
+

[...]

lib

Quoted 6 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +6 -0

+/**
+ * Compare 48 bytes between two locations.
+ * Locations should not overlap.
+ */
+static inline int
+rte_cmp48(const void *src_1, const void *src_2)

Guess this is not used.

[...]

lib

Quoted 11 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +11 -0

+/**
+ * Compare 256 bytes between two locations.
+ * Locations should not overlap.
+ */
+static inline int
+rte_cmp256(const void *src_1, const void *src_2)
+{
+     int ret;
+
+     ret = rte_cmp64((const uint8_t *)src_1 + 0 * 64,
+                     (const uint8_t *)src_2 + 0 * 64);

Why not just use rte_cmp128?

[...]

Quoted 8 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +8 -0

+static inline int
+rte_memcmp(const void *_src_1, const void *_src_2, size_t n)
+{
+     const uint8_t *src_1 = (const uint8_t *)_src_1;
+     const uint8_t *src_2 = (const uint8_t *)_src_2;
+     int ret = 0;
+
+     if (n < 16)

lib

Quoted 10 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +10 -0

+             return rte_memcmp_regular(src_1, src_2, n);
+
+     if (n <= 32) {
+             ret = rte_cmp16(src_1, src_2);
+             if (unlikely(ret != 0))
+                     return ret;
+
+             return rte_cmp16(src_1 - 16 + n, src_2 - 16 + n);
+     }
+

Too many conditions here may harm the overall performance. It's a trade-off thing, all about balancing the overhead. Just make sure this is tuned based on actual test numbers.

Quoted 48 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +48 -0

+     if (n <= 48) {
+             ret = rte_cmp32(src_1, src_2);
+             if (unlikely(ret != 0))
+                     return ret;
+
+             return rte_cmp16(src_1 - 16 + n, src_2 - 16 + n);
+     }
+
+     if (n <= 64) {
+             ret = rte_cmp32(src_1, src_2);
+             if (unlikely(ret != 0))
+                     return ret;
+
+             ret = rte_cmp16(src_1 + 32, src_2 + 32);
+
+             if (unlikely(ret != 0))
+                     return ret;
+
+             return rte_cmp16(src_1 - 16 + n, src_2 - 16 + n);
+     }
+
+     if (n <= 96) {
+             ret = rte_cmp64(src_1, src_2);
+             if (unlikely(ret != 0))
+                     return ret;
+
+             ret = rte_cmp16(src_1 + 64, src_2 + 64);
+             if (unlikely(ret != 0))
+                     return ret;
+
+             return rte_cmp16(src_1 - 16 + n, src_2 - 16 + n);
+     }
+
+     if (n <= 128) {
+             ret = rte_cmp64(src_1, src_2);
+             if (unlikely(ret != 0))
+                     return ret;
+
+             ret = rte_cmp32(src_1 + 64, src_2 + 64);
+             if (unlikely(ret != 0))
+                     return ret;
+
+             ret = rte_cmp16(src_1 + 96, src_2 + 96);
+             if (unlikely(ret != 0))
+                     return ret;
+
+             return rte_cmp16(src_1 - 16 + n, src_2 - 16 + n);
+     }

[...]

lib

Quoted 6 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +6 -0

+/**
+ * Compare 48 bytes between two locations.
+ * Locations should not overlap.
+ */
+static inline int
+rte_cmp48(const void *src_1, const void *src_2)

Not used.

Quoted 20 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +20 -0

+{
+     int ret;
+
+     ret = rte_cmp16((const uint8_t *)src_1 + 0 * 16,
+                     (const uint8_t *)src_2 + 0 * 16);
+
+     if (unlikely(ret != 0))
+             return ret;
+
+     ret = rte_cmp16((const uint8_t *)src_1 + 1 * 16,
+                     (const uint8_t *)src_2 + 1 * 16);
+
+     if (unlikely(ret != 0))
+             return ret;
+
+     return rte_cmp16((const uint8_t *)src_1 + 2 * 16,
+                     (const uint8_t *)src_2 + 2 * 16);
+}
+
+/**

lib

Quoted 10 lines

lib renamed from lib/librte_eal/common/include/arch/x86/rte_memcmp.h +10 -0

+ * Compare 64 bytes between two locations.
+ * Locations should not overlap.
+ */
+static inline int
+rte_cmp64(const void *src_1, const void *src_2)
+{
+     int ret;
+
+     ret = rte_cmp16((const uint8_t *)src_1 + 0 * 16,
+                     (const uint8_t *)src_2 + 0 * 16);

Why not rte_cmp32? And use rte_cmp64 for rte_cmp128, and so on. That should make the code looks clearer.

It'd be great if you could format this patch into a patch set with several little ones. :-)
Also, the kernel checkpatch is very helpful.
Good coding style and patch organization make it easy for in-depth reviews.

Quoted 5 lines

It'd be great if you could format this patch into a patch set with several little ones. :-)
Also, the kernel checkpatch is very helpful.
Good coding style and patch organization make it easy for in-depth reviews.

Combination of scalar and vector (32/64/128) was done to get optimal performance numbers. If there is enough interest in this I can work on it and provide an updated patch set.

Quoted 1 line

Quoted 1 line

It'd be great if you could format this patch into a patch set with

several

Quoted 3 lines

Quoted 3 lines

little ones. :-)
Also, the kernel checkpatch is very helpful.
Good coding style and patch organization make it easy for in-depth

reviews.

Quoted 2 lines

Quoted 1 line

Combination of scalar and vector (32/64/128) was done to get optimal

performance numbers. If there is enough interest in this I can work on it and provide an updated patch set.

That'll be very helpful! Looking forward to your patch :) BTW, have you tested real example performance with your patch?

Background:
After preliminary discussion with John (Zhihong) and Tim from Intel it was decided that it would be beneficial to use AVX/SSE intrinsics for memcmp similar to memcpy that had been implemeneted. In addition, we decided to use librte_hash as a test candidate to test both functionality and performance.

Further discussions lead to complete functionality implementation of memory comparison and v3 code reflects that.

Test was conducted on Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz, Ubuntu 14.04, x86_64, 16GB DDR3 system.

Ravi Kerur (1):
Implement memcmp using Intel SIMD instrinsics.

Quoted 6 lines · Ravi Kerur

Background:
After preliminary discussion with John (Zhihong) and Tim from Intel it was decided that it would be beneficial to use AVX/SSE intrinsics for memcmp similar to memcpy that had been implemeneted. In addition, we decided to use librte_hash as a test candidate to test both functionality and performance.

Quoted 8 lines

Further discussions lead to complete functionality implementation of memory comparison and v3 code reflects that.

Test was conducted on Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz, Ubuntu 14.04, x86_64, 16GB DDR3 system.

Ravi Kerur (1):
Implement memcmp using Intel SIMD instrinsics.

As my previous mail got lost I am resending it.

In short you shouldn't
use sse2/avx2 for memcmp at all. In 95% of calls you find inequality in first 8 bytes so sse2 adds just unnecessary overhead versus checking these with.

190:   48 8b 4e 08             mov    0x8(%rsi),%rcx
194:   48 39 4f 08             cmp    %rcx,0x8(%rdi)
198:   75 f3                   jne    18d <memeq30+0xd>

Also as you have full memcmp does in your gcc optimize out if (memcmp(x,y))
like in mine?

So run also implementation below in your benchmark, my guess is it will be faster.

Quoted 2 lines · Ravi Kerur

Background:
After preliminary discussion with John (Zhihong) and Tim from Intel it

was

Quoted 2 lines

decided that it would be beneficial to use AVX/SSE intrinsics for memcmp similar to memcpy that had been implemeneted. In addition, we decided to

use

Quoted 1 line

librte_hash as a test candidate to test both functionality and

performance.

Quoted 2 lines

Further discussions lead to complete functionality implementation of

memory

Quoted 3 lines

comparison and v3 code reflects that.

Test was conducted on Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz, Ubuntu

14.04,

Quoted 4 lines

x86_64, 16GB DDR3 system.

Ravi Kerur (1):
Implement memcmp using Intel SIMD instrinsics.

As my previous mail got lost I am resending it.

In short you shouldn't
use sse2/avx2 for memcmp at all. In 95% of calls you find inequality in first 8 bytes so sse2 adds just unnecessary overhead versus checking these with.

190:   48 8b 4e 08             mov    0x8(%rsi),%rcx
194:   48 39 4f 08             cmp    %rcx,0x8(%rdi)
198:   75 f3                   jne    18d <memeq30+0xd>

Also as you have full memcmp does in your gcc optimize out if (memcmp(x,y))
like in mine?

So run also implementation below in your benchmark, my guess is it will be faster.

Original mail follows:

Hi,

I as glibc developer that wrote current strcmp code have some comments.

First is that gcc builtins for *cmp are garbage that produce rep cmpsb which is slower than byte-by-byte loop. So compile your test again with -fno-builtin-memcmp and your performance gain will probably disappear.

Then there is inlining. Its correct to do that for first 32 bytes and I plan to add header that does that check to improve performance. However not for bytes after 32'th. Thats very cold code, Only 5.6% calls reach 17th byte and 1.7% of calls read 33'th byte, so just do libcall to save size.

That also makes avx2 pointless, for most string funtions avx2 doesn't give you gains as xmm for first 64 bytes has better latency and while loop is faster its also relatively cold as its almost never reached.

For memcmp I posted on gcc list a sample implementation how it should do inlining. I found that gcc optimizes that better than expected and produces probably optimal header (see below and feel free to use it).

When you care about sign then its better to load first 8 bytes, convert them to big endian where can you compare directly. When you don't gcc managed to optimize away bswap so you check 8 bytes with three instructions below. Now I think that in header we shouldn't use sse at all.

 190:   48 8b 4e 08             mov    0x8(%rsi),%rcx
 194:   48 39 4f 08             cmp    %rcx,0x8(%rdi)
 198:   75 f3                   jne    18d <memeq30+0xd>

As I mentioned statistics on my computer memcmp has following:

calls 1430827
average n: 7.4 n <= 0: 0.1% n <= 4: 36.3% n <= 8: 78.4% n <=
16: 94.4% n <= 24: 97.3% n <= 32: 98.3% n <= 48: 98.6% n <= 64:
99.9%
s aligned to 4 bytes: 99.8% 8 bytes: 97.5% 16 bytes: 59.5%
average *s access cache latency 3.6 l <= 8: 92.0% l <= 16: 96.1%
l <= 32: 98.9% l <= 64: 99.4% l <= 128: 99.5%

s2 aligned to 4 bytes:  24.1%  8 bytes:  13.1% 16 bytes:   8.2%
s-s2 aligned to 4 bytes:  24.1%  8 bytes:  15.4% 16 bytes:  10.3%

average *s2 access cache latency 1.5 l <= 8: 98.0% l <= 16:
99.6% l <= 32: 99.9% l <= 64: 100.0% l <= 128: 100.0%
average capacity: 8.5 c <= 0: 0.0% c <= 4: 36.0% c <= 8: 78.3%
c <= 16: 91.8% c <= 24: 94.8% c <= 32: 95.7% c <= 48: 96.1% c <= 64:
99.9%

#include <string.h>
#include <stdint.h>

#undef memcmp
#define memcmp(x, y, n) (__builtin_constant_p (n) && n < 64 ?

__memcmp_inline (x, y, n) \
                         : memcmp (x, y, n))

#define LOAD8(x) (*((uint8_t *) (x)))
#define LOAD32(x) (*((uint32_t *) (x)))
#define LOAD64(x) (*((uint64_t *) (x)))

#define CHECK(tp, n)
#if __BYTE_ORDER == __LITTLE_ENDIAN

# define SWAP32(x) __builtin_bswap32 (LOAD32 (x))
# define SWAP64(x) __builtin_bswap64 (LOAD64 (x))
#else
# define SWAP32(x) LOAD32 (x)
# define SWAP64(x) LOAD64 (x)
#endif

#define __ARCH_64BIT 1

static __always_inline
int
check (uint64_t x, uint64_t y)
{
if (x == y)

    return 0;
  if (x > y)
    return 1;

return -1;
}

static __always_inline
int
check_nonzero (uint64_t x, uint64_t y)
{
if (x > y)

    return 1;

return -1;
}

static __always_inline
int
__memcmp_inline (void *x, void *y, size_t n)
{

#define CHECK1 if (LOAD8 (x + i) - LOAD8 (y + i)) \
    return check_nonzero (LOAD8 (x + i), LOAD8 (y + i)); i = i + 1;
#define CHECK4 if (i == 0 ? SWAP32 (x + i) - SWAP32 (y + i)\
                      : LOAD32 (x + i) - LOAD32 (y + i)) \
    return check_nonzero (SWAP32 (x + i), SWAP32 (y + i)); i = i + 4;
#define CHECK8 if (i == 0 ? SWAP64 (x + i) - SWAP64 (y + i)\
                      : LOAD64 (x + i) - LOAD64 (y + i)) \
    return check_nonzero (SWAP64 (x + i), SWAP64 (y + i)); i = i + 8;

#define CHECK1FINAL(o) return check (LOAD8 (x + i + o), LOAD8 (y + i + o)); #define CHECK4FINAL(o) return check (SWAP32 (x + i + o), SWAP32 (y + i + o));
#define CHECK8FINAL(o) return check (SWAP64 (x + i + o), SWAP64 (y + i + o));

#if __ARCH_64BIT == 0

# undef CHECK8
# undef CHECK8FINAL
# define CHECK8 CHECK4 CHECK4
# define CHECK8FINAL(o) CHECK4 CHECK4FINAL (o)
#endif

#define LOOP if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 } \
if (i + 8 < n) { CHECK8 }

  long i = 0;

  switch (n % 8)
    {
    case 0:
      if (n == 0)
        return 0;

      LOOP; CHECK8FINAL (0);
    case 1:
      LOOP CHECK1FINAL (0);
    case 2:
      if (n == 2)
        {
          CHECK1 CHECK1FINAL (0);
        }
      LOOP CHECK4FINAL (-2);
    case 3:
      if (n == 3)
        {
          CHECK1 CHECK1 CHECK1FINAL (0);
        }
      LOOP CHECK4FINAL (-1);
    case 4:
      LOOP CHECK4FINAL (0);
    case 5:
      if (n == 5)
        {
          CHECK4 CHECK1FINAL (0);
        }
#if __ARCH_64BIT
      LOOP CHECK8FINAL (-3);
#else
      LOOP CHECK4 CHECK1FINAL (0);
#endif
    case 6:
      if (n == 6)
        {
          CHECK4 CHECK4FINAL (-2);
        }
      LOOP CHECK8FINAL (-2);
    case 7:
      if (n == 7)
        {
          CHECK4 CHECK4FINAL (-1);
        }
      LOOP CHECK8FINAL (-1);
    }
}

int
memcmp1 (char *x, char *y)
{
return memcmp (x, y, 1);
}
int
memcmp10 (char *x, char *y)
{
return memcmp (x, y, 10);
}
int
memcmp20 (char *x, char *y)
{
return memcmp (x, y, 20);
}
int
memcmp30 (char *x, char *y)
{
return memcmp (x, y, 30);
}

int
memeq1 (char *x, char *y)
{
return memcmp (x, y, 1) != 0;
}
int
memeq10 (char *x, char *y)
{
return memcmp (x, y, 10) != 0;
}
int
memeq20 (char *x, char *y)
{
return memcmp (x, y, 20) != 0;
}
int
memeq30 (char *x, char *y)
{
return memcmp (x, y, 30) != 0;
}