Allowed inlining for traverseWithIndex (#623)
authorDonnacha Oisín Kidney <oisdk@users.noreply.github.com>
Fri, 12 Apr 2019 00:54:22 +0000 (01:54 +0100)
committerGitHub <noreply@github.com>
Fri, 12 Apr 2019 00:54:22 +0000 (01:54 +0100)
* Allowed inlining for traverseWithIndex

Switched NOINLINE to INLINE:
- Ideally this would be INLINABLE, but that can't have phase controls
- This is the next best, which gets the proper performance benefits and also the phase controles so the rewrite rules still fire properly

Because this was prompted by sequenceA.mapWithIndex being faster, a benchamrk of that operation has been added to compare.

* INLINABLE can have phase controls

As it turns out, INLINABLE *can* have phase controls.

Benchmarks so no real change:

benchmarking traverseWithIndex/State/10
time                 368.6 ns   (364.2 ns .. 372.2 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 366.6 ns   (363.2 ns .. 370.0 ns)
std dev              11.56 ns   (9.593 ns .. 14.54 ns)
variance introduced by outliers: 46% (moderately inflated)

benchmarking traverseWithIndex/State/100
time                 4.730 μs   (4.663 μs .. 4.796 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 4.702 μs   (4.660 μs .. 4.752 μs)
std dev              149.9 ns   (123.3 ns .. 192.9 ns)
variance introduced by outliers: 40% (moderately inflated)

benchmarking traverseWithIndex/State/1000
time                 65.15 μs   (64.31 μs .. 66.13 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 66.58 μs   (65.80 μs .. 67.65 μs)
std dev              3.082 μs   (2.343 μs .. 4.561 μs)
variance introduced by outliers: 50% (moderately inflated)

benchmarking sequenceA.mapWithIndex/State/10
time                 597.8 ns   (589.4 ns .. 606.8 ns)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 602.1 ns   (595.9 ns .. 610.4 ns)
std dev              23.84 ns   (17.59 ns .. 38.02 ns)
variance introduced by outliers: 56% (severely inflated)

benchmarking sequenceA.mapWithIndex/State/100
time                 5.915 μs   (5.854 μs .. 6.023 μs)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 6.006 μs   (5.939 μs .. 6.078 μs)
std dev              235.9 ns   (199.3 ns .. 285.5 ns)
variance introduced by outliers: 50% (moderately inflated)

benchmarking sequenceA.mapWithIndex/State/1000
time                 83.08 μs   (81.80 μs .. 84.81 μs)
                     0.998 R²   (0.998 R² .. 0.999 R²)
mean                 83.78 μs   (83.04 μs .. 84.50 μs)
std dev              2.604 μs   (2.277 μs .. 3.018 μs)
variance introduced by outliers: 30% (moderately inflated)

* put INLINABLE behind a macro

Data/Sequence/Internal.hs
benchmarks/Sequence.hs

index 55e0dd1..8a4dc90 100644 (file)
@@ -2975,7 +2975,12 @@ traverseWithIndex f' (Seq xs') = Seq <$> traverseWithIndexTreeE (\s (Elem a) ->
       !sPsab = sPsa + size b
 
 
-{-# NOINLINE [1] traverseWithIndex #-}
+#ifdef __GLASGOW_HASKELL__
+{-# INLINABLE [1] traverseWithIndex #-}
+#else
+{-# INLINE [1] traverseWithIndex #-}
+#endif
+
 #ifdef __GLASGOW_HASKELL__
 {-# RULES
 "travWithIndex/mapWithIndex" forall f g xs . traverseWithIndex f (mapWithIndex g xs) =
index c786b9e..27b802b 100644 (file)
@@ -90,6 +90,11 @@ main = do
          , bench "100" $ nf multiplyDown s100
          , bench "1000" $ nf multiplyDown s1000
          ]
+      , bgroup "sequenceA.mapWithIndex/State"
+         [ bench "10" $ nf multiplyDownMap s10
+         , bench "100" $ nf multiplyDownMap s100
+         , bench "1000" $ nf multiplyDownMap s1000
+         ]
       , bgroup "traverse/State"
          [ bench "10" $ nf multiplyUp s10
          , bench "100" $ nf multiplyUp s100
@@ -242,3 +247,10 @@ multiplyDown = flip evalState 0 . S.traverseWithIndex go where
     s <- get
     put (s - 1)
     return (s * i * x)
+
+multiplyDownMap :: S.Seq Int -> S.Seq Int
+multiplyDownMap = flip evalState 0 . sequenceA . S.mapWithIndex go where
+  go i x = do
+    s <- get
+    put (s - 1)
+    return (s * i * x)