[ovs-dev] [PATCH 18/18] ofp-util: Optimize ofputil_version_bitmap_scanr

Simon Horman horms at verge.net.au
Fri Oct 26 02:36:06 UTC 2012


Make use of __builtin_clz if available which should optimize
ofputil_version_bitmap_scanr() by replacing a loop with
a single CLZ instruction when available.

I'm unsure if this approach is worth it or not.
But a similar approach could be taken to use ffs()
in bitmap_scan().

Signed-off-by: Simon Horman <horms at verge.net.au>
---
 configure.ac      |    1 +
 lib/ofp-util.c    |   19 -------------------
 lib/ofp-util.h    |   12 +++++++++++-
 lib/util.c        |   21 +++++++++++++++++++++
 lib/util.h        |    9 +++++++++
 m4/openvswitch.m4 |   16 ++++++++++++++++
 6 files changed, 58 insertions(+), 20 deletions(-)

diff --git a/configure.ac b/configure.ac
index 32940a5..7f9fffb 100644
--- a/configure.ac
+++ b/configure.ac
@@ -76,6 +76,7 @@ OVS_CHECK_GROFF
 OVS_CHECK_BRCOMPAT
 OVS_CHECK_GNU_MAKE
 OVS_CHECK_CACHE_TIME
+OVS_CHECK___BUILTIN_CLZ
 
 OVS_ENABLE_OPTION([-Wall])
 OVS_ENABLE_OPTION([-Wno-sign-compare])
diff --git a/lib/ofp-util.c b/lib/ofp-util.c
index 1639f9c..107661e 100644
--- a/lib/ofp-util.c
+++ b/lib/ofp-util.c
@@ -1077,25 +1077,6 @@ ofputil_version_bitmap_set_range1(size_t start, size_t end)
     return new;
 }
 
-/* Scans 'ovb'. Returns the bit offset of the highest-numbered bit set to 1,
- * or VERSION_BITMAP_W if all of the bits are set to 0. */
-size_t
-ofputil_version_bitmap_scanr(uint32_t bitmap)
-{
-    /* N.B: When using GCC 3.4 or newer this may be made
-     * faster using __builtin_clz()
-     */
-    size_t i = VERSION_BITMAP_W - 1;
-
-    do {
-        if (ofputil_version_bitmap_is_set(bitmap, i)) {
-            return i;
-        }
-    } while (i--);
-
-    return VERSION_BITMAP_W;
-}
-
 /* Find the number of bits in 'ovb' that are set to one. */
 size_t
 ofputil_version_bitmap_count_set(uint32_t bitmap)
diff --git a/lib/ofp-util.h b/lib/ofp-util.h
index 8dd1389..04501e6 100644
--- a/lib/ofp-util.h
+++ b/lib/ofp-util.h
@@ -130,9 +130,19 @@ ofputil_version_bitmap_is_set(uint32_t bitmap, size_t offset)
 }
 
 uint32_t ofputil_version_bitmap_set_range1(size_t start, size_t end);
-size_t ofputil_version_bitmap_scanr(uint32_t bitmap);
 size_t ofputil_version_bitmap_count_set(uint32_t bitmap);
 
+/* Scans 'ovb'. Returns the bit offset of the highest-numbered bit set to 1,
+ * or VERSION_BITMAP_W if all of the bits are set to 0. */
+static inline size_t
+ofputil_version_bitmap_scanr(uint32_t bitmap)
+{
+    if (!bitmap)
+        return VERSION_BITMAP_W;
+    BUILD_ASSERT(sizeof bitmap == sizeof(unsigned int));
+    return VERSION_BITMAP_W - 1 - clz(bitmap);
+}
+
 void ofputil_format_version_bitmap(struct ds *msg, uint32_t bitmap);
 void ofputil_format_version_bitmap_names(struct ds *msg, uint32_t bitmap);
 
diff --git a/lib/util.c b/lib/util.c
index c90d556..f25f66b 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -1149,3 +1149,24 @@ bitwise_get(const void *src, unsigned int src_len,
                  n_bits);
     return ntohll(value);
 }
+
+#ifndef HAVE___BUILTIN_CLZ
+#define UINT_BITS (sizeof(unsigned int) * 8)
+
+/* Returns the number of leading 0-bits in x
+ * x must be non-zero */
+int clz(unsigned int x)
+{
+    size_t i = UINT_BITS - 1;
+
+    assert(x);
+
+    do {
+        if (x & (1u << i)) {
+            return UINT_BITS - i - 1;
+        }
+    } while (i--);
+
+    return UINT_BITS;
+}
+#endif
diff --git a/lib/util.h b/lib/util.h
index a1f4bd7..91d4c1a 100644
--- a/lib/util.h
+++ b/lib/util.h
@@ -287,6 +287,15 @@ void bitwise_put(uint64_t value,
 uint64_t bitwise_get(const void *src, unsigned int src_len,
                      unsigned int src_ofs, unsigned int n_bits);
 
+#ifdef HAVE___BUILTIN_CLZ
+static inline int clz(unsigned int x)
+{
+    return __builtin_clz(x);
+}
+#else
+int clz(unsigned int x);
+#endif
+
 #ifdef  __cplusplus
 }
 #endif
diff --git a/m4/openvswitch.m4 b/m4/openvswitch.m4
index 7469011..ae761b5 100644
--- a/m4/openvswitch.m4
+++ b/m4/openvswitch.m4
@@ -193,6 +193,22 @@ AC_DEFUN([OVS_CHECK_MALLOC_HOOKS],
                 __free_hook in <malloc.h>.])
    fi])
 
+dnl Checks for __builtin_clz
+AC_DEFUN([OVS_CHECK___BUILTIN_CLZ],
+  [AC_CACHE_CHECK(
+    [whether __builtin_clz is provided],
+    [ovs_cv___builtin_clz],
+    [AC_COMPILE_IFELSE(
+      [AC_LANG_PROGRAM(
+         [],
+         [return __builtin_clz(1);])],
+      [ovs_cv___builtin_clz=yes],
+      [ovs_cv___builtin_clz=no])])
+   if test $ovs_cv___builtin_clz = yes; then
+     AC_DEFINE([HAVE___BUILTIN_CLZ], [1],
+               [Define to 1 if you have __builtin_clz])
+   fi])
+
 dnl Checks for valgrind/valgrind.h.
 AC_DEFUN([OVS_CHECK_VALGRIND],
   [AC_CHECK_HEADERS([valgrind/valgrind.h])])
-- 
1.7.10.4




More information about the dev mailing list