From 1cf9a165fc80b2f8109f85d5bd121e0c7c397e58 Mon Sep 17 00:00:00 2001
From: Damjan Marion <damarion@cisco.com>
Date: Wed, 23 May 2018 20:21:51 +0200
Subject: Vectorized bihash_{48,40,24,16}_8 key compare

bihash_48_8 case:
Scalar code: 6 clocks
SSE4.2 code: 3 clocks
AVX2 code: 2.27 clocks
AVX512 code: 1.5 clocks

Change-Id: I40700175835a1e7321276e47eadbf9771d3c5a68
Signed-off-by: Damjan Marion <damarion@cisco.com>
---
 src/vppinfra/bihash_16_8.h   |  6 ++++++
 src/vppinfra/bihash_24_8.h   | 12 +++++++++++-
 src/vppinfra/bihash_40_8.h   | 19 ++++++++++++++++++-
 src/vppinfra/bihash_48_8.h   | 18 +++++++++++++++++-
 src/vppinfra/vector_avx2.h   | 45 ++++++++++++++++++++++++--------------------
 src/vppinfra/vector_avx512.h |  7 ++++++-
 6 files changed, 83 insertions(+), 24 deletions(-)

diff --git a/src/vppinfra/bihash_16_8.h b/src/vppinfra/bihash_16_8.h
index 361665bee4b..dc820116cd9 100644
--- a/src/vppinfra/bihash_16_8.h
+++ b/src/vppinfra/bihash_16_8.h
@@ -67,7 +67,13 @@ format_bihash_kvp_16_8 (u8 * s, va_list * args)
 static inline int
 clib_bihash_key_compare_16_8 (u64 * a, u64 * b)
 {
+#if defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
+  u64x2 v;
+  v = u64x2_load_unaligned (a) ^ u64x2_load_unaligned (b);
+  return u64x2_is_all_zero (v);
+#else
   return ((a[0] ^ b[0]) | (a[1] ^ b[1])) == 0;
+#endif
 }
 
 #undef __included_bihash_template_h__
diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h
index 173168fe98e..0c57e35bc47 100644
--- a/src/vppinfra/bihash_24_8.h
+++ b/src/vppinfra/bihash_24_8.h
@@ -66,9 +66,19 @@ format_bihash_kvp_24_8 (u8 * s, va_list * args)
 }
 
 static inline int
-clib_bihash_key_compare_24_8 (const u64 * a, const u64 * b)
+clib_bihash_key_compare_24_8 (u64 * a, u64 * b)
 {
+#if defined (CLIB_HAVE_VEC512)
+  u64x8 v = u64x8_load_unaligned (a) ^ u64x8_load_unaligned (b);
+  return (u64x8_is_zero_mask (v) & 0x7) == 0;
+#elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
+  u64x2 v;
+  v = u64x2_load_unaligned (a) ^ u64x2_load_unaligned (b);
+  v |= u64x2_load_unaligned (a + 1) ^ u64x2_load_unaligned (b + 1);
+  return u64x2_is_all_zero (v);
+#else
   return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | (a[2] ^ b[2])) == 0;
+#endif
 }
 
 #undef __included_bihash_template_h__
diff --git a/src/vppinfra/bihash_40_8.h b/src/vppinfra/bihash_40_8.h
index 974a78d8cef..2e633fae27d 100644
--- a/src/vppinfra/bihash_40_8.h
+++ b/src/vppinfra/bihash_40_8.h
@@ -67,10 +67,27 @@ format_bihash_kvp_40_8 (u8 * s, va_list * args)
 }
 
 static inline int
-clib_bihash_key_compare_40_8 (const u64 * a, const u64 * b)
+clib_bihash_key_compare_40_8 (u64 * a, u64 * b)
 {
+#if defined (CLIB_HAVE_VEC512)
+  u64x8 v;
+  v = u64x8_load_unaligned (a) ^ u64x8_load_unaligned (b);
+  return (u64x8_is_zero_mask (v) & 0x1f) == 0;
+#elif defined (CLIB_HAVE_VEC256)
+  u64x4 v;
+  v = u64x4_load_unaligned (a) ^ u64x4_load_unaligned (b);
+  v |= u64x4_load_unaligned (a + 1) ^ u64x4_load_unaligned (b + 1);
+  return u64x4_is_all_zero (v);
+#elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
+  u64x2 v;
+  v = u64x2_load_unaligned (a) ^ u64x2_load_unaligned (b);
+  v |= u64x2_load_unaligned (a + 2) ^ u64x2_load_unaligned (b + 2);
+  v |= u64x2_load_unaligned (a + 3) ^ u64x2_load_unaligned (b + 3);
+  return u64x2_is_all_zero (v);
+#else
   return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | (a[2] ^ b[2]) | (a[3] ^ b[3])
 	  | (a[4] ^ b[4])) == 0;
+#endif
 }
 
 #undef __included_bihash_template_h__
diff --git a/src/vppinfra/bihash_48_8.h b/src/vppinfra/bihash_48_8.h
index 107bcace3ce..760ec0a4923 100644
--- a/src/vppinfra/bihash_48_8.h
+++ b/src/vppinfra/bihash_48_8.h
@@ -69,10 +69,26 @@ format_bihash_kvp_48_8 (u8 * s, va_list * args)
 }
 
 static inline int
-clib_bihash_key_compare_48_8 (const u64 * a, const u64 * b)
+clib_bihash_key_compare_48_8 (u64 * a, u64 * b)
 {
+#if defined (CLIB_HAVE_VEC512)
+  u64x8 v = u64x8_load_unaligned (a) ^ u64x8_load_unaligned (b);
+  return (u64x8_is_zero_mask (v) & 0x3f) == 0;
+#elif defined (CLIB_HAVE_VEC256)
+  u64x4 v;
+  v = u64x4_load_unaligned (a) ^ u64x4_load_unaligned (b);
+  v |= u64x4_load_unaligned (a + 2) ^ u64x4_load_unaligned (b + 2);
+  return u64x4_is_all_zero (v);
+#elif defined(CLIB_HAVE_VEC128) && defined(CLIB_HAVE_VEC128_UNALIGNED_LOAD_STORE)
+  u64x2 v;
+  v = u64x2_load_unaligned (a) ^ u64x2_load_unaligned (b);
+  v |= u64x2_load_unaligned (a + 2) ^ u64x2_load_unaligned (b + 2);
+  v |= u64x2_load_unaligned (a + 4) ^ u64x2_load_unaligned (b + 4);
+  return u64x2_is_all_zero (v);
+#else
   return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | (a[2] ^ b[2]) | (a[3] ^ b[3])
 	  | (a[4] ^ b[4]) | (a[5] ^ b[5])) == 0;
+#endif
 }
 
 #undef __included_bihash_template_h__
diff --git a/src/vppinfra/vector_avx2.h b/src/vppinfra/vector_avx2.h
index e2d5701c0e8..6dd110c52e3 100644
--- a/src/vppinfra/vector_avx2.h
+++ b/src/vppinfra/vector_avx2.h
@@ -64,29 +64,34 @@ u32x8_permute (u32x8 v, u32x8 idx)
   return (u32x8) _mm256_permutevar8x32_epi32 ((__m256i) v, (__m256i) idx);
 }
 
-always_inline u32x4
-u32x8_extract_lo (u32x8 v)
-{
-  return (u32x4) _mm256_extracti128_si256 ((__m256i) v, 0);
-}
+/* _extract_lo, _extract_hi */
+/* *INDENT-OFF* */
+#define _(t1,t2) \
+always_inline t1							\
+t2##_extract_lo (t2 v)							\
+{ return (t1) _mm256_extracti128_si256 ((__m256i) v, 0); }		\
+\
+always_inline t1							\
+t2##_extract_hi (t2 v)							\
+{ return (t1) _mm256_extracti128_si256 ((__m256i) v, 1); }		\
+\
+always_inline t2							\
+t2##_insert_lo (t2 v1, t1 v2)						\
+{ return (t2) _mm256_inserti128_si256 ((__m256i) v1, (__m128i) v2, 0); }\
+\
+always_inline t2							\
+t2##_insert_hi (t2 v1, t1 v2)						\
+{ return (t2) _mm256_inserti128_si256 ((__m256i) v1, (__m128i) v2, 1); }\
+
+_(u8x16, u8x32)
+_(u16x8, u16x16)
+_(u32x4, u32x8)
+_(u64x2, u64x4)
+#undef _
+/* *INDENT-ON* */
 
-always_inline u32x4
-u32x8_extract_hi (u32x8 v)
-{
-  return (u32x4) _mm256_extracti128_si256 ((__m256i) v, 1);
-}
 
-always_inline u32x8
-u32x8_insert_lo (u32x8 v1, u32x4 v2)
-{
-  return (u32x8) _mm256_inserti128_si256 ((__m256i) v1, (__m128i) v2, 0);
-}
 
-always_inline u32x8
-u32x8_insert_hi (u32x8 v1, u32x4 v2)
-{
-  return (u32x8) _mm256_inserti128_si256 ((__m256i) v1, (__m128i) v2, 1);
-}
 
 static_always_inline u32
 u8x32_msb_mask (u8x32 v)
diff --git a/src/vppinfra/vector_avx512.h b/src/vppinfra/vector_avx512.h
index 4aee8d1170a..f69c67e697c 100644
--- a/src/vppinfra/vector_avx512.h
+++ b/src/vppinfra/vector_avx512.h
@@ -28,7 +28,7 @@
   _(f,32,8,ps) _(f,64,4,pd)
 
 /* splat, load_unaligned, store_unaligned, is_all_zero, is_equal,
-   is_all_equal */
+   is_all_equal, is_zero_mask */
 #define _(t, s, c, i) \
 static_always_inline t##s##x##c						\
 t##s##x##c##_splat (t##s x)						\
@@ -53,6 +53,11 @@ t##s##x##c##_is_equal (t##s##x##c a, t##s##x##c b)			\
 static_always_inline int						\
 t##s##x##c##_is_all_equal (t##s##x##c v, t##s x)			\
 { return t##s##x##c##_is_equal (v, t##s##x##c##_splat (x)); }		\
+\
+static_always_inline u##c						\
+t##s##x##c##_is_zero_mask (t##s##x##c v)				\
+{ return _mm512_test_##i##_mask ((__m512i) v, (__m512i) v); }		\
+
 
 foreach_avx512_vec512i foreach_avx512_vec512u
 #undef _
-- 
cgit 1.2.3-korg