From f4cf31f5e1a952e8fb53e10160f167f29324c3b3 Mon Sep 17 00:00:00 2001 From: Gabe Black Date: Tue, 3 Mar 2020 17:41:44 -0800 Subject: [PATCH] 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 Maintainer: Gabe Black Tested-by: kokoro --- src/base/intmath.hh | 104 ++++++++++----------------------------- src/base/intmath.test.cc | 18 +++++++ 2 files changed, 44 insertions(+), 78 deletions(-) diff --git a/src/base/intmath.hh b/src/base/intmath.hh index c6ad329cc..3713ae624 100644 --- a/src/base/intmath.hh +++ b/src/base/intmath.hh @@ -30,6 +30,8 @@ #define __BASE_INTMATH_HH__ #include +#include +#include #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 +inline typename std::enable_if::value, int>::type +floorLog2(T x) { assert(x > 0); - int y = 0; - - 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 x) -{ - assert(x > 0); + // A guaranteed unsigned version of x. + uint64_t ux = (typename std::make_unsigned::type)x; int y = 0; + constexpr auto ts = sizeof(T); -#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; } + 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 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 inline int ceilLog2(const T& n) @@ -143,7 +89,9 @@ template 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 diff --git a/src/base/intmath.test.cc b/src/base/intmath.test.cc index f869ffe81..5740bd4b8 100644 --- a/src/base/intmath.test.cc +++ b/src/base/intmath.test.cc @@ -58,6 +58,24 @@ TEST(IntmathTest, floorLog2) 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) -- 2.30.2