Commits

Aleksey Khudyakov  committed 6f0027c

Unroll fold manually. GHC cannot specialize code enough

Also do not do extra work on 32-bit systems. And I'm not sure
that shifting by 32 is OK there.

  • Participants
  • Parent commits 520ef73

Comments (0)

Files changed (1)

File Statistics/Function.hs

 -- non-negative integer.  If the given value is already a power of
 -- two, it is returned unchanged.  If negative, zero is returned.
 nextHighestPowerOfTwo :: Int -> Int
-nextHighestPowerOfTwo n = 1 + foldl go (n-1) [1, 2, 4, 8, 16, 32]
-  where go m i = m .|. m `shiftR` i
+nextHighestPowerOfTwo n
+#if WORD_SIZE_IN_BITS == 64
+  = 1 + _i32
+#else
+  = 1 + i16
+#endif
+  where
+    i0   = n - 1
+    i1   = i0  .|. i0  `shiftR` 1
+    i2   = i1  .|. i1  `shiftR` 2
+    i4   = i2  .|. i2  `shiftR` 4
+    i8   = i4  .|. i4  `shiftR` 8
+    i16  = i8  .|. i8  `shiftR` 16
+    _i32 = i16 .|. i16 `shiftR` 32
+-- It could be implemented as
+--
+-- > nextHighestPowerOfTwo n = 1 + foldl' go (n-1) [1, 2, 4, 8, 16, 32]
+--     where go m i = m .|. m `shiftR` i
+--
+-- But GHC do not inline foldl (probably because it's recursive) and
+-- as result function walks list of boxed ints. Hand rolled version
+-- uses unboxed arithmetic.