Performance regression (~34%) in 8.2.1, poor register allocation(?) in an inner loop over an array
Testing GHC 8.0.1 against the RC 8.2.0.20170507
I've distilled a smallish test-case from a much larger case in my 'hashabler' library, and validated that the same modifications also make that regression disappear in the real case. It's probably possible to get this smaller but I don't know if I'll have time to work on it more for a while:
repro3.hs:
{-# LANGUAGE BangPatterns #-}
module Main(main) where
import Criterion.Main
import qualified Data.Primitive as P
import Data.Bits
import Data.Word
import Control.DeepSeq
main :: IO ()
main = do
defaultMain
[ env (newByteArr64 5) $ \ ~bs ->
bench "ByteArray 5" $ nf (hashTextSip 99) bs
, env (newByteArr64 8) $ \ ~bs ->
bench "ByteArray 8" $ nf (hashTextSip 99) bs
, env (newByteArr64 512) $ \ ~bs ->
bench "ByteArray 512" $ nf (hashTextSip 99) bs
, env (newByteArr64 1000000) $ \ ~bs ->
bench "ByteArray 1000000" $ nf (hashTextSip 99) bs
]
instance NFData P.ByteArray where rnf _ = ()
newByteArr64 n = P.newAlignedPinnedByteArray (8*n) 8 >>= P.unsafeFreezeByteArray
sipRound :: Word64 -> Word64 -> Word64 -> Word64 -> (Word64, Word64, Word64, Word64)
{-# INLINE sipRound #-}
sipRound v0 v1 v2 v3 = (v3 `xor` v0, v0 `xor` v1, v1 `xor` v2, v2 `xor` v3)
hashTextSip :: Word64 -> P.ByteArray -> Word64
{-# INLINE hashTextSip #-}
hashTextSip h = \ ba ->
let !lenWord16 = P.sizeofByteArray ba `unsafeShiftR` 1
!word16sRem = lenWord16 .&. 3
!word16sIx = lenWord16-word16sRem
!ixFinal = lenWord16-1
!word16sIxWd = word16sIx `unsafeShiftR` 2 -- `div` 4
hash4Word16sLoop hAcc@(!w0,!w1,!w2,!w3) !ix
| ix == word16sIxWd = hashRemainingWord16s hAcc word16sIx
| otherwise =
let w64Dirty = P.indexByteArray ba ix
w64 = clean4xWord16ChunkLE w64Dirty
in hash4Word16sLoop (sipRound (w0 `xor` w64) w1 w2 w3) (ix + 1)
-- NOTE: Removing this causes regression to disappear as well.
hashRemainingWord16s (!w0,!w1,!w2,!w3) !ix
| ix > ixFinal = w0
| otherwise =
let w16 = P.indexByteArray ba ix
in hashRemainingWord16s (sipRound (w0 `xor` (fromIntegral (w16 :: Word16))) w1 w2 w3) (ix+1)
in hash4Word16sLoop (h,1,2,3) 0
clean4xWord16ChunkLE :: Word64 -> Word64
{-# INLINE clean4xWord16ChunkLE #-}
clean4xWord16ChunkLE w64Dirty =
-- NOTE: no regression when just this (8.2 is faster)
-- (((byteSwap64 w64Dirty) `unsafeShiftR` 8) .&. 0x00FF00FF00FF00FF)
-- ...but this is a big regression:
(((byteSwap64 w64Dirty) `unsafeShiftR` 8) .&. 0x00FF00FF00FF00FF)
.|.
(((byteSwap64 w64Dirty) `unsafeShiftL` 8) .&. 0xFF00FF00FF00FF00)Here are the results of the benchmark above on my machine:
On GHC **8.0.1**:
benchmarking ByteArray 5
time 24.70 ns (24.00 ns .. 26.25 ns)
0.987 R² (0.967 R² .. 1.000 R²)
mean 24.44 ns (24.13 ns .. 25.80 ns)
std dev 1.859 ns (318.3 ps .. 4.227 ns)
variance introduced by outliers: 86% (severely inflated)
benchmarking ByteArray 8
time 32.66 ns (32.58 ns .. 32.76 ns)
1.000 R² (1.000 R² .. 1.000 R²)
mean 32.79 ns (32.64 ns .. 33.09 ns)
std dev 683.7 ps (365.4 ps .. 1.175 ns)
variance introduced by outliers: 31% (moderately inflated)
benchmarking ByteArray 512
time 1.428 μs (1.382 μs .. 1.522 μs)
0.986 R² (0.970 R² .. 1.000 R²)
mean 1.398 μs (1.384 μs .. 1.454 μs)
std dev 91.12 ns (4.475 ns .. 193.9 ns)
variance introduced by outliers: 76% (severely inflated)
benchmarking ByteArray 1000000
time 2.658 ms (2.653 ms .. 2.663 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 2.672 ms (2.665 ms .. 2.691 ms)
std dev 35.00 μs (10.88 μs .. 59.58 μs)
And on **GHC 8.2** RC:
benchmarking ByteArray 5
time 23.78 ns (23.68 ns .. 23.88 ns)
1.000 R² (1.000 R² .. 1.000 R²)
mean 23.83 ns (23.76 ns .. 23.95 ns)
std dev 298.8 ps (183.2 ps .. 482.5 ps)
variance introduced by outliers: 14% (moderately inflated)
benchmarking ByteArray 8
time 35.81 ns (35.44 ns .. 36.27 ns)
0.999 R² (0.998 R² .. 1.000 R²)
mean 35.56 ns (35.45 ns .. 35.94 ns)
std dev 596.8 ps (134.5 ps .. 1.184 ns)
variance introduced by outliers: 22% (moderately inflated)
benchmarking ByteArray 512
time 1.706 μs (1.698 μs .. 1.716 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 1.701 μs (1.698 μs .. 1.707 μs)
std dev 13.27 ns (5.825 ns .. 24.41 ns)
benchmarking ByteArray 1000000
time 3.322 ms (3.284 ms .. 3.377 ms)
0.999 R² (0.998 R² .. 1.000 R²)
mean 3.296 ms (3.287 ms .. 3.332 ms)
std dev 44.62 μs (20.55 μs .. 87.29 μs)
Looking at the core wasn't fruitful, but I think dumping the asm shows that this is a case of bad (or worse) register allocation. I've attached two screenshots showing the instructions added (in blue), when moving from the one-line clean4xWord16ChunkLE to the two-line version, for both 8.0 and 8.2 (there wasn't anything in the diff besides instances of this change).
It looks in the 8.2 version like we've decided we're out of registers and need to use the stack.
In my real code I'm seeing 35% regression on very long Text, as well as 21% regression on very long ByteString; the latter implementation is similarly structured to hashTextSip, but doesn't call clean4xWord16ChunkLE but does do a byteswap.
Trac metadata
| Trac field | Value |
|---|---|
| Version | 8.2.1-rc2 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | Compiler (NCG) |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture |