[PPL-devel] [GIT] ppl/ppl(master): Bit_Row iterators reimplemented more efficiently.
Roberto Bagnara
bagnara at cs.unipr.it
Mon Apr 20 22:06:46 CEST 2009
Module: ppl/ppl
Branch: master
Commit: 0dbad6c0854d82ebeed8d0ab04bd915f3699a005
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0dbad6c0854d82ebeed8d0ab04bd915f3699a005
Author: Roberto Bagnara <bagnara at cs.unipr.it>
Date: Mon Apr 20 22:06:33 2009 +0200
Bit_Row iterators reimplemented more efficiently.
---
src/Bit_Row.cc | 77 +--------------------
src/Bit_Row.defs.hh | 6 --
src/Bit_Row.inlines.hh | 172 ++++++++++++++++++++++++++++++++++++++++++++---
3 files changed, 165 insertions(+), 90 deletions(-)
diff --git a/src/Bit_Row.cc b/src/Bit_Row.cc
index 4cece3a..1983f21 100644
--- a/src/Bit_Row.cc
+++ b/src/Bit_Row.cc
@@ -28,75 +28,6 @@ site: http://www.cs.unipr.it/ppl/ . */
namespace PPL = Parma_Polyhedra_Library;
-#if !PPL_HAVE_DECL_FFS || PPL_SIZEOF_MP_LIMB_T != PPL_SIZEOF_INT
-unsigned int
-PPL::Bit_Row::first_one(mp_limb_t w) {
- unsigned int r = 0;
- w = w & -w;
-#if PPL_SIZEOF_MP_LIMB_T == 8
- if ((w & 0xffffffff) == 0) {
- w >>= 32;
- r += 32;
- }
-#elif PPL_SIZEOF_MP_LIMB_T != 4
-#error "Size of mp_limb_t not supported by Bit_Row::first_one(mp_limb_t w)."
-#endif
- if ((w & 0xffff) == 0) {
- w >>= 16;
- r += 16;
- }
- if ((w & 0xff) == 0) {
- w >>= 8;
- r += 8;
- }
- if (w & 0xf0)
- r += 4;
- if (w & 0xcc)
- r += 2;
- if (w & 0xaa)
- r += 1;
- return r;
-}
-#endif // !PPL_HAVE_DECL_FFS || PPL_SIZEOF_MP_LIMB_T != PPL_SIZEOF_INT
-
-unsigned int
-PPL::Bit_Row::last_one(mp_limb_t w) {
- unsigned int r = 0;
-#if PPL_SIZEOF_MP_LIMB_T == 8
- if (w &
-#if PPL_SIZEOF_LONG == 8
- 0xffffffff00000000
-#else
- 0xffffffff00000000LL
-#endif
- ) {
- w >>= 32;
- r += 32;
- }
-#elif PPL_SIZEOF_MP_LIMB_T != 4
-#error "Size of mp_limb_t not supported by Bit_Row::last_one(mp_limb_t w)."
-#endif
- if (w & 0xffff0000) {
- w >>= 16;
- r += 16;
- }
- if (w & 0xff00) {
- w >>= 8;
- r += 8;
- }
- if (w & 0xf0) {
- w >>= 4;
- r += 4;
- }
- if (w & 0xc) {
- w >>= 2;
- r += 2;
- }
- if (w & 0x2)
- r += 1;
- return r;
-}
-
unsigned long
PPL::Bit_Row::first() const {
const mp_size_t vec_size = vec->_mp_size;
@@ -106,7 +37,7 @@ PPL::Bit_Row::first() const {
for (; li < vec_size; ++li, ++p) {
const mp_limb_t limb = *p;
if (limb != 0)
- return li*PPL_BITS_PER_GMP_LIMB + first_one(limb);
+ return li*PPL_BITS_PER_GMP_LIMB + Implementation::first_one(limb);
}
return ULONG_MAX;
}
@@ -136,7 +67,7 @@ PPL::Bit_Row::next(unsigned long position) const {
while (true) {
if (limb != 0)
- return li*PPL_BITS_PER_GMP_LIMB + first_one(limb);
+ return li*PPL_BITS_PER_GMP_LIMB + Implementation::first_one(limb);
++li;
if (li == vec_size)
break;
@@ -156,7 +87,7 @@ PPL::Bit_Row::last() const {
const mp_srcptr p = vec->_mp_d + li;
const mp_limb_t limb = *p;
assert(limb != 0);
- return li*PPL_BITS_PER_GMP_LIMB + last_one(limb);
+ return li*PPL_BITS_PER_GMP_LIMB + Implementation::last_one(limb);
}
unsigned long
@@ -189,7 +120,7 @@ PPL::Bit_Row::prev(unsigned long position) const {
while (true) {
if (limb != 0)
- return li*PPL_BITS_PER_GMP_LIMB + last_one(limb);
+ return li*PPL_BITS_PER_GMP_LIMB + Implementation::last_one(limb);
if (li == 0)
break;
--li;
diff --git a/src/Bit_Row.defs.hh b/src/Bit_Row.defs.hh
index ce278c9..ee1c98e 100644
--- a/src/Bit_Row.defs.hh
+++ b/src/Bit_Row.defs.hh
@@ -203,12 +203,6 @@ private:
Upon entry, \p vec must have allocated enough space to contain the result.
*/
void union_helper(const Bit_Row& x, const Bit_Row& y);
-
- //! Assuming \p w is nonzero, returns the index of the first set bit in \p w.
- static unsigned int first_one(mp_limb_t w);
-
- //! Assuming \p w is nonzero, returns the index of the last set bit in \p w.
- static unsigned int last_one(mp_limb_t w);
};
namespace std {
diff --git a/src/Bit_Row.inlines.hh b/src/Bit_Row.inlines.hh
index 5084a64..2ad8a19 100644
--- a/src/Bit_Row.inlines.hh
+++ b/src/Bit_Row.inlines.hh
@@ -91,8 +91,9 @@ Bit_Row::clear_from(const unsigned long k) {
inline unsigned long
Bit_Row::count_ones() const {
- assert(vec->_mp_size >= 0);
- return vec->_mp_size == 0 ? 0 : mpn_popcount(vec->_mp_d, vec->_mp_size);
+ mp_size_t x_size = vec->_mp_size;
+ assert(x_size >= 0);
+ return x_size == 0 ? 0 : mpn_popcount(vec->_mp_d, x_size);
}
inline bool
@@ -120,15 +121,6 @@ Bit_Row::total_memory_in_bytes() const {
return sizeof(*this) + external_memory_in_bytes();
}
-#if PPL_HAVE_DECL_FFS && PPL_SIZEOF_MP_LIMB_T == PPL_SIZEOF_INT
-
-inline unsigned int
-Bit_Row::first_one(mp_limb_t w) {
- return ffs(w)-1;
-}
-
-#endif
-
/*! \relates Bit_Row */
inline void
set_union(const Bit_Row& x, const Bit_Row& y, Bit_Row& z) {
@@ -160,6 +152,164 @@ set_difference(const Bit_Row& x, const Bit_Row& y, Bit_Row& z) {
mpz_and(z.vec, x.vec, complement_y.get_mpz_t());
}
+namespace Implementation {
+
+#if defined(__GNUC__)
+
+/*! \brief
+ Assuming \p u is nonzero, returns the index of the first set bit in \p u.
+*/
+inline unsigned int
+first_one(unsigned int u) {
+ assert(u != 0);
+ return __builtin_ctz(u);
+}
+
+/*! \brief
+ Assuming \p ul is nonzero, returns the index of the first set bit in
+ \p ul.
+*/
+inline unsigned int
+first_one(unsigned long ul) {
+ assert(ul != 0);
+ return __builtin_ctzl(ul);
+}
+
+/*! \brief
+ Assuming \p ull is nonzero, returns the index of the first set bit in
+ \p ull.
+*/
+inline unsigned int
+first_one(unsigned long long ull) {
+ assert(ull != 0);
+ return __builtin_ctzll(ull);
+}
+
+#elif PPL_HAVE_DECL_FFS && PPL_SIZEOF_MP_LIMB_T == PPL_SIZEOF_INT
+
+/*! \brief
+ Assuming \p w is nonzero, returns the index of the first set bit in \p w.
+*/
+inline unsigned int
+first_one(mp_limb_t w) {
+ return ffs(w)-1;
+}
+
+#else
+
+/*! \brief
+ Assuming \p w is nonzero, returns the index of the first set bit in \p w.
+*/
+inline unsigned int
+first_one(mp_limb_t w) {
+ unsigned int r = 0;
+ w = w & -w;
+#if PPL_SIZEOF_MP_LIMB_T == 8
+ if ((w & 0xffffffff) == 0) {
+ w >>= 32;
+ r += 32;
+ }
+#elif PPL_SIZEOF_MP_LIMB_T != 4
+#error "size of mp_limb_t not supported by first_one(mp_limb_t w)."
+#endif
+ if ((w & 0xffff) == 0) {
+ w >>= 16;
+ r += 16;
+ }
+ if ((w & 0xff) == 0) {
+ w >>= 8;
+ r += 8;
+ }
+ if (w & 0xf0)
+ r += 4;
+ if (w & 0xcc)
+ r += 2;
+ if (w & 0xaa)
+ r += 1;
+ return r;
+}
+#endif // !defined(__GNUC__)
+ // && (!PPL_HAVE_DECL_FFS || PPL_SIZEOF_MP_LIMB_T != PPL_SIZEOF_INT)
+
+#if defined(__GNUC__)
+
+/*! \brief
+ Assuming \p u is nonzero, returns the index of the last set bit in \p u.
+*/
+inline unsigned int
+last_one(unsigned int u) {
+ assert(u != 0);
+ return sizeof(unsigned int)*CHAR_BIT - 1 - __builtin_clz(u);
+}
+
+/*! \brief
+ Assuming \p ul is nonzero, returns the index of the last set bit in
+ \p ul.
+*/
+inline unsigned int
+last_one(unsigned long ul) {
+ assert(ul != 0);
+ return sizeof(unsigned long)*CHAR_BIT - 1 - __builtin_clzl(ul);
+}
+
+/*! \brief
+ Assuming \p ull is nonzero, returns the index of the last set bit in
+ \p ull.
+*/
+inline unsigned int
+last_one(unsigned long long ull) {
+ assert(ull != 0);
+ return sizeof(unsigned long long)*CHAR_BIT - 1 - __builtin_clzll(ull);
+}
+
+#else // !defined(__GNUC__)
+
+/*! \brief
+ Assuming \p w is nonzero, returns the index of the last set bit in \p w.
+*/
+inline unsigned int
+last_one(mp_limb_t w) {
+ assert(w != 0);
+ unsigned int r = 0;
+#if PPL_SIZEOF_MP_LIMB_T == 8
+ if (w &
+#if PPL_SIZEOF_LONG == 8
+ 0xffffffff00000000
+#else
+ 0xffffffff00000000LL
+#endif
+ ) {
+ w >>= 32;
+ r += 32;
+ }
+#elif PPL_SIZEOF_MP_LIMB_T != 4
+#error "size of mp_limb_t not supported by last_one(mp_limb_t w)."
+#endif
+ if (w & 0xffff0000) {
+ w >>= 16;
+ r += 16;
+ }
+ if (w & 0xff00) {
+ w >>= 8;
+ r += 8;
+ }
+ if (w & 0xf0) {
+ w >>= 4;
+ r += 4;
+ }
+ if (w & 0xc) {
+ w >>= 2;
+ r += 2;
+ }
+ if (w & 0x2)
+ r += 1;
+ return r;
+}
+
+#endif // !defined(__GNUC__)
+
+} // namespace Implementation
+
} // namespace Parma_Polyhedra_Library
More information about the PPL-devel
mailing list