Gabe Black has submitted this change. (
https://gem5-review.googlesource.com/c/public/gem5/+/26164 )
Change subject: base: Optimize and otherwise fix a couple of functions in
intmath.hh.
......................................................................
base: Optimize and otherwise fix a couple of functions in intmath.hh.
As described in the Jira issue, this replaces the implementation of
isPowerOf2() and power(). It also revamps floorLog2 so that there only
needs to be one implementation and no assumptions about how big certain
types are.
The way power() used to work was to raise a number n to an exponent e
by multiplying n times itself e times. As a warning in this function
explains, this can be quite slow for large e. A much more efficient
way to raise a number to an exponent is to square n over and over, and
to multiply in the current square if that bit of e is set.
n ^ 15 = (n^1) * (n^2) * (n^4) * (n^8)
n^8 = (n^4)^2
n^4 = (n^2)^2
n^2 = n^2
n^1 = n
So that takes 6 multiplications, n^2, (n^2)^2, (n^4)^2, and then each
multipy to compute the final result, instead of 14.
The difference is more pronounced for larger exponents, although you'd
quickly start to overflow a uint64_t.
Jira Issue: https://gem5.atlassian.net/browse/GEM5-140
Change-Id: I0ae05aeba1b5882d2a616613b1679e6206b4cbfe
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/26164
Reviewed-by: Daniel Carvalho <[email protected]>
Maintainer: Gabe Black <[email protected]>
Tested-by: kokoro <[email protected]>
---
M src/base/intmath.hh
M src/base/intmath.test.cc
2 files changed, 45 insertions(+), 79 deletions(-)
Approvals:
Daniel Carvalho: Looks good to me, approved
Gabe Black: Looks good to me, approved
kokoro: Regressions pass
diff --git a/src/base/intmath.hh b/src/base/intmath.hh
index c6ad329..3713ae6 100644
--- a/src/base/intmath.hh
+++ b/src/base/intmath.hh
@@ -30,6 +30,8 @@
#define __BASE_INTMATH_HH__
#include <cassert>
+#include <cstdint>
+#include <type_traits>
#include "base/logging.hh"
#include "base/types.hh"
@@ -37,97 +39,41 @@
inline uint64_t
power(uint32_t n, uint32_t e)
{
- if (e > 20)
- warn("Warning, power() function is quite slow for large
exponents\n");
-
- if (e == 0)
- return 1;
-
- uint64_t result = n;
- uint64_t old_result = 0;
- for (int x = 1; x < e; x++) {
- old_result = result;
- result *= n;
- if (old_result > result)
- warn("power() overflowed!\n");
+ uint64_t result = 1;
+ uint64_t component = n;
+ while (e) {
+ uint64_t last = result;
+ if (e & 0x1)
+ result *= component;
+ warn_if(result < last, "power() overflowed!");
+ e >>= 1;
+ component *= component;
}
return result;
}
-
-inline int
-floorLog2(unsigned x)
+template <class T>
+inline typename std::enable_if<std::is_integral<T>::value, int>::type
+floorLog2(T x)
{
assert(x > 0);
+ // A guaranteed unsigned version of x.
+ uint64_t ux = (typename std::make_unsigned<T>::type)x;
+
int y = 0;
+ constexpr auto ts = sizeof(T);
- if (x & 0xffff0000) { y += 16; x >>= 16; }
- if (x & 0x0000ff00) { y += 8; x >>= 8; }
- if (x & 0x000000f0) { y += 4; x >>= 4; }
- if (x & 0x0000000c) { y += 2; x >>= 2; }
- if (x & 0x00000002) { y += 1; }
+ if (ts >= 8 && (ux & ULL(0xffffffff00000000))) { y += 32; ux >>= 32; }
+ if (ts >= 4 && (ux & ULL(0x00000000ffff0000))) { y += 16; ux >>= 16; }
+ if (ts >= 2 && (ux & ULL(0x000000000000ff00))) { y += 8; ux >>= 8; }
+ if (ux & ULL(0x00000000000000f0)) { y += 4; ux >>= 4; }
+ if (ux & ULL(0x000000000000000c)) { y += 2; ux >>= 2; }
+ if (ux & ULL(0x0000000000000002)) { y += 1; }
return y;
}
-inline int
-floorLog2(unsigned long x)
-{
- assert(x > 0);
-
- int y = 0;
-
-#if defined(__LP64__)
- if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; }
-#endif
- if (x & 0xffff0000) { y += 16; x >>= 16; }
- if (x & 0x0000ff00) { y += 8; x >>= 8; }
- if (x & 0x000000f0) { y += 4; x >>= 4; }
- if (x & 0x0000000c) { y += 2; x >>= 2; }
- if (x & 0x00000002) { y += 1; }
-
- return y;
-}
-
-inline int
-floorLog2(unsigned long long x)
-{
- assert(x > 0);
-
- int y = 0;
-
- if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; }
- if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; }
- if (x & ULL(0x000000000000ff00)) { y += 8; x >>= 8; }
- if (x & ULL(0x00000000000000f0)) { y += 4; x >>= 4; }
- if (x & ULL(0x000000000000000c)) { y += 2; x >>= 2; }
- if (x & ULL(0x0000000000000002)) { y += 1; }
-
- return y;
-}
-
-inline int
-floorLog2(int x)
-{
- assert(x > 0);
- return floorLog2((unsigned)x);
-}
-
-inline int
-floorLog2(long x)
-{
- assert(x > 0);
- return floorLog2((unsigned long)x);
-}
-
-inline int
-floorLog2(long long x)
-{
- assert(x > 0);
- return floorLog2((unsigned long long)x);
-}
-
template <class T>
inline int
ceilLog2(const T& n)
@@ -143,7 +89,9 @@
inline bool
isPowerOf2(const T& n)
{
- return n != 0 && floorLog2(n) == ceilLog2(n);
+ // If n is non-zero, and subtracting one borrows all the way to the MSB
+ // and flips all bits, then this is a power of 2.
+ return n && !(n & (n - 1));
}
template <class T, class U>
diff --git a/src/base/intmath.test.cc b/src/base/intmath.test.cc
index f869ffe..5740bd4 100644
--- a/src/base/intmath.test.cc
+++ b/src/base/intmath.test.cc
@@ -58,6 +58,24 @@
EXPECT_EQ(16, floorLog2(65537));
EXPECT_EQ(20, floorLog2(1783592));
EXPECT_EQ(41, floorLog2(2821109907456));
+
+ // Test unsigned integers of various sizes.
+ EXPECT_EQ(0, floorLog2((uint8_t)1));
+ EXPECT_EQ(0, floorLog2((uint16_t)1));
+ EXPECT_EQ(0, floorLog2((uint32_t)1));
+ EXPECT_EQ(0, floorLog2((uint64_t)1));
+
+ // Test signed integers of various sizes.
+ EXPECT_EQ(0, floorLog2((int8_t)1));
+ EXPECT_EQ(0, floorLog2((int16_t)1));
+ EXPECT_EQ(0, floorLog2((int32_t)1));
+ EXPECT_EQ(0, floorLog2((int64_t)1));
+}
+
+TEST(IntmathDeathTest, floorLog2)
+{
+ // Verify a non-positive input triggers an assert.
+ EXPECT_DEATH_IF_SUPPORTED(floorLog2(0), "x > 0");
}
TEST(IntmathTest, ceilLog2)
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/26164
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: I0ae05aeba1b5882d2a616613b1679e6206b4cbfe
Gerrit-Change-Number: 26164
Gerrit-PatchSet: 4
Gerrit-Owner: Gabe Black <[email protected]>
Gerrit-Reviewer: Bobby R. Bruce <[email protected]>
Gerrit-Reviewer: Daniel Carvalho <[email protected]>
Gerrit-Reviewer: Gabe Black <[email protected]>
Gerrit-Reviewer: Jason Lowe-Power <[email protected]>
Gerrit-Reviewer: kokoro <[email protected]>
Gerrit-MessageType: merged
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
