Inconsistent performance of simple loops with NCG
Summary
The NCG generates code for simple loops that performs very differently depending on where exactly the loop inlines.
Steps to reproduce
Compile the following code:
{-# language BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}
import Criterion
import Criterion.Main
import Data.Primitive
import GHC.Exts (RealWorld)
import Control.Monad.Primitive
main :: IO ()
main = do
let sz = 100000
arr <- newPrimArray sz
defaultMain
[ bench "first" (whnfIO (incrementHighToLowCase arr))
, bench "second" (whnfIO (incrementHighToLowCase arr))
, bench "third" (whnfIO (incrementHighToLowCase arr))
, bench "fourth" (whnfIO (incrementHighToLowCase arr))
, bench "fifth" (whnfIO (incrementHighToLowCase arr))
, bench "sixth" (whnfIO (incrementHighToLowCase arr))
]
incrementHighToLowCase :: MutablePrimArray RealWorld Int -> IO ()
incrementHighToLowCase m = modify' (+1) m
modify' :: (Prim a, PrimMonad m)
=> (a -> a)
-> MutablePrimArray (PrimState m) a
-> m ()
modify' f marr = do
let go !ix = case ix of
(-1) -> return ()
_ -> do
x <- readPrimArray marr ix
let !y = f x
writePrimArray marr ix y
go (ix - 1)
!sz <- getSizeofMutablePrimArray marr
go (sz - 1)There are three different flavors I've explored. One is to compile the code as is with the NCG (Variant A). One is to compile the code as in with -fllvm to use the LLVM backend (Variant B). The third is to compile the code with the NCG after explicitly marking incrementHighToLowCase as NOINLINE (Variant C). For a ligther dependency footprint, it is possible to use gauge instead of criterion. The results are the same.
Expected behavior
I expect for all six benchmarks to have the same performance. Instead, I get this:
benchmarking first
time 90.90 μs (90.39 μs .. 91.53 μs)
1.000 R² (0.999 R² .. 1.000 R²)
mean 90.66 μs (90.36 μs .. 91.09 μs)
std dev 1.187 μs (916.3 ns .. 1.689 μs)
benchmarking second
time 83.24 μs (82.96 μs .. 83.58 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 83.30 μs (83.10 μs .. 83.55 μs)
std dev 725.9 ns (580.6 ns .. 956.9 ns)
benchmarking third
time 56.02 μs (55.82 μs .. 56.25 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 56.15 μs (56.00 μs .. 56.37 μs)
std dev 604.7 ns (514.3 ns .. 761.8 ns)
benchmarking fourth
time 87.08 μs (86.40 μs .. 87.75 μs)
1.000 R² (0.999 R² .. 1.000 R²)
mean 86.85 μs (86.38 μs .. 87.37 μs)
std dev 1.666 μs (1.395 μs .. 2.062 μs)
variance introduced by outliers: 14% (moderately inflated)
benchmarking fifth
time 94.35 μs (93.96 μs .. 94.81 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 94.28 μs (94.00 μs .. 94.65 μs)
std dev 1.001 μs (803.7 ns .. 1.299 μs)
benchmarking sixth
time 55.48 μs (55.36 μs .. 55.65 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 55.57 μs (55.46 μs .. 55.72 μs)
std dev 404.1 ns (337.9 ns .. 502.8 ns)Strangely, benchmarks third and sixth are much faster than the others, but this only happens in Variant A. The other two variants show very consistent performance of the function. Variant B gives durations that hover within a percentage point of 44.47 μs, and Variant C gives durations that hover within a percentage point of 83.07 μs.
With -ddump-simple, I've been able to confirm that (without a NOINLINE pragma) the loop gets inlined into six different places in the benchmarking code, once into each individual benchmark. What I don't understand is why the NCG handles this so inconsistently while LLVM is fine with it.
This whole issue may not seem like a big deal, but I ran into this by encountering some benchmark results that seemed wrong. That is, the implementation of an algorithm that was supposed to be faster ended up being slower. By simply reordering the benchmarks, I was able to observe very different behavior. Suddenly, the implementation was previously slower became faster. It took me a while to realize that the NCG was compiling simple loops differently depending on which cons cell of the _ : _ : _ : _ : _ : _ : [] they showed up in. I almost made some erroneous conclusions about the implementations I was comparing, but I happened to switch around the order of the benchmarks and realized that the conclusions I had previously reached were wrong.
Environment
- GHC version used: 8.6.4
Optional:
- Operating System: Ubuntu
- System Architecture: x86-64