[ovs-dev] [PATCH 2/2] lib/hash: Use CRC32 for hashing.

[Jarno Rajahalme]

On Jun 12, 2014, at 1:31 PM, Ben Pfaff <blp at nicira.com> wrote:

> On Wed, Jun 04, 2014 at 04:32:21PM -0700, Jarno Rajahalme wrote:
>> Use CRC32 intrinsics for hash computations when building for
>> X86_64 with SSE4_2.
>> 
>> Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
> 
> Did you consider using __builtin_constant_p() to inline the hash
> computation only when the number of words is a constant?  (On MSVC,
> which doesn't have __builtin_constant_p(), you could default to always
> inlining or never inlining, since this is not a correctness issue.)

You mean like this:

diff --git a/lib/hash.c b/lib/hash.c
index 29be9c5..71cd74c 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -59,3 +59,15 @@ hash_double(double x, uint32_t basis)
     memcpy(value, &x, sizeof value);
     return hash_3words(value[0], value[1], basis);
 }
+
+uint32_t
+hash_words__(const uint32_t p[], size_t n_words, uint32_t basis)
+{
+    return hash_words_inline(p, n_words, basis);
+}
+
+uint32_t
+hash_words64__(const uint64_t p[], size_t n_words, uint64_t basis)
+{
+    return hash_words64_inline(p, n_words, basis);
+}
diff --git a/lib/hash.h b/lib/hash.h
index 2535449..f8bbada 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -101,7 +101,7 @@ static inline uint32_t hash_finish(uint32_t hash, uint32_t final)
  * This is inlined for the compiler to have access to the 'n_words', which
  * in many cases is a constant. */
 static inline uint32_t
-hash_words(const uint32_t p[], size_t n_words, uint32_t basis)
+hash_words_inline(const uint32_t p[], size_t n_words, uint32_t basis)
 {
     uint32_t hash;
     size_t i;
@@ -114,10 +114,10 @@ hash_words(const uint32_t p[], size_t n_words, uint32_t basis)
 }
 
 static inline uint32_t
-hash_words64(const uint64_t p[], size_t n_words, uint64_t basis)
+hash_words64_inline(const uint64_t p[], size_t n_words, uint64_t basis)
 {
-    return hash_words((uint32_t *)p, n_words * 2,
-                      (uint32_t)basis ^ basis >> 32);
+    return hash_words_inline((uint32_t *)p, n_words * 2,
+                             (uint32_t)basis ^ basis >> 32);
 }
 
 static inline uint32_t hash_pointer(const void *p, uint32_t basis)
@@ -171,7 +171,7 @@ static inline uint32_t hash_finish(uint64_t hash, uint64_t final)
  * This is inlined for the compiler to have access to the 'n_words', which
  * in many cases is a constant. */
 static inline uint32_t
-hash_words(const uint32_t p_[], size_t n_words, uint32_t basis)
+hash_words_inline(const uint32_t p_[], size_t n_words, uint32_t basis)
 {
     const uint64_t *p = (const void *)p_;
     uint64_t hash1 = basis;
@@ -213,7 +213,7 @@ hash_words(const uint32_t p_[], size_t n_words, uint32_t basis)
 /* A simpler version for 64-bit data.
  * 'n_words' is the count of 64-bit words, basis is 64 bits. */
 static inline uint32_t
-hash_words64(const uint64_t p[], size_t n_words, uint64_t basis)
+hash_words64_inline(const uint64_t p[], size_t n_words, uint64_t basis)
 {
     uint64_t hash1 = (uint32_t)basis;
     uint64_t hash2 = basis >> 32;
@@ -262,6 +262,47 @@ static inline uint32_t hash_pointer(const void *p, uint32_t basis)
 }
 #endif
 
+uint32_t hash_words__(const uint32_t p[], size_t n_words, uint32_t basis);
+uint32_t hash_words64__(const uint64_t p[], size_t n_words, uint64_t basis);
+
+/* Inline the larger hash functions only when 'n_words' is known to be
+ * compile-time constant. */
+#if __GNUC__ >= 4
+static inline uint32_t
+hash_words(const uint32_t p[], size_t n_words, uint32_t basis)
+{
+    if (__builtin_constant_p(n_words)) {
+        return hash_words_inline(p, n_words, basis);
+    } else {
+        return hash_words__(p, n_words, basis);
+    }
+}
+
+static inline uint32_t
+hash_words64(const uint64_t p[], size_t n_words, uint64_t basis)
+{
+    if (__builtin_constant_p(n_words)) {
+        return hash_words64_inline(p, n_words, basis);
+    } else {
+        return hash_words64__(p, n_words, basis);
+    }
+}
+
+#else
+
+static inline uint32_t
+hash_words(const uint32_t p[], size_t n_words, uint32_t basis)
+{
+    return hash_words__(p, n_words, basis);
+}
+
+static inline uint32_t
+hash_words64(const uint64_t p[], size_t n_words, uint64_t basis)
+{
+    return hash_words64__(p, n_words, basis);
+}
+#endif
+
 static inline uint32_t hash_string(const char *s, uint32_t basis)
 {
     return hash_bytes(s, strlen(s), basis);


  Jarno