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 <ho...@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
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
