diff options
| author | Sylvain Henry <sylvain@haskus.fr> | 2019-08-06 19:35:16 +0200 |
|---|---|---|
| committer | Marge Bot <ben+marge-bot@smart-cactus.org> | 2019-08-18 05:16:40 -0400 |
| commit | ac73c1b13a4fef725f643e6985cdcb6f6fc1bef5 (patch) | |
| tree | 8d566feba1d2b5e964a06895a7d90b59e6a749ee | |
| parent | 47e162374051ed3e874ed7916cc811df288cbd95 (diff) | |
| download | haskell-ac73c1b13a4fef725f643e6985cdcb6f6fc1bef5.tar.gz | |
Faster exactLog2
Make `exactLog2` faster (use `countLeadingZeros` and Int32 bit-ops).
On my Core i7-9700k Criterion reports ~50% speedup (from 16 to 8ns).
| -rw-r--r-- | compiler/utils/Util.hs | 22 |
1 files changed, 8 insertions, 14 deletions
diff --git a/compiler/utils/Util.hs b/compiler/utils/Util.hs index dba5a4495f..ecbef752f1 100644 --- a/compiler/utils/Util.hs +++ b/compiler/utils/Util.hs @@ -1123,22 +1123,16 @@ toArgs str ----------------------------------------------------------------------------- -- Integers --- This algorithm for determining the $\log_2$ of exact powers of 2 comes --- from GCC. It requires bit manipulation primitives, and we use GHC --- extensions. Tough. - +-- | Determine the $\log_2$ of exact powers of 2 exactLog2 :: Integer -> Maybe Integer exactLog2 x - = if (x <= 0 || x >= 2147483648) then - Nothing - else - if (x .&. (-x)) /= x then - Nothing - else - Just (pow2 x) - where - pow2 x | x == 1 = 0 - | otherwise = 1 + pow2 (x `shiftR` 1) + | x <= 0 = Nothing + | x > fromIntegral (maxBound :: Int32) = Nothing + | x' .&. (-x') /= x' = Nothing + | otherwise = Just (fromIntegral c) + where + x' = fromIntegral x :: Int32 + c = countTrailingZeros x' {- -- ----------------------------------------------------------------------------- |