Speed up foldMap for sequences

[oisdk]

I noticed that foldMapWithIndex on sequences is significantly faster than foldMap in certain cases:

benchmarking 50000/getSum . foldMap Sum
time                 1.051 ms   (1.003 ms .. 1.093 ms)
                     0.988 R²   (0.983 R² .. 0.994 R²)
mean                 1.123 ms   (1.094 ms .. 1.154 ms)
std dev              110.7 μs   (93.16 μs .. 131.6 μs)
variance introduced by outliers: 72% (severely inflated)

benchmarking 50000/getSum . foldMapWithIndex (const Sum)
time                 435.5 μs   (433.0 μs .. 438.2 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 433.1 μs   (431.5 μs .. 435.4 μs)
std dev              6.490 μs   (4.910 μs .. 9.372 μs)

benchmarking 50000/foldl' (+) 0
time                 420.6 μs   (419.2 μs .. 422.8 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 429.2 μs   (425.4 μs .. 433.8 μs)
std dev              15.71 μs   (12.04 μs .. 19.77 μs)
variance introduced by outliers: 30% (moderately inflated)

Unfortunately, the core output is too large for me to really understand, but I think there's some specialisation not happening which does happen in the manually-specialised foldMapWithIndex.

When the definition for foldMap mimics foldMapWithIndex:

instance Foldable Seq where
    foldMap f' (Seq xs') = foldMapTreeE (lift_elem f') xs'
      where
        lift_elem :: (a -> m) -> (Elem a -> m)
#if __GLASGOW_HASKELL__ >= 708
        lift_elem g = coerce g
#else
        lift_elem g = \(Elem a) -> g a
#endif
        foldMapTreeE :: Monoid m => (Elem a -> m) -> FingerTree (Elem a) -> m
        foldMapTreeE _ EmptyT = mempty
        foldMapTreeE f (Single xs) = f xs
        foldMapTreeE f (Deep _ pr m sf) = 
            foldMapDigitE f pr <>
            foldMapTreeN (foldMapNodeE f) m <>
            foldMapDigitE f sf

        foldMapTreeN :: Monoid m => (Node a -> m) -> FingerTree (Node a) -> m
        foldMapTreeN _ EmptyT = mempty
        foldMapTreeN f (Single xs) = f xs
        foldMapTreeN f (Deep _ pr m sf) = 
            foldMapDigitN f pr <>
            foldMapTreeN (foldMapNodeN f) m <>
            foldMapDigitN f sf

        foldMapDigitE :: Monoid m => (Elem a -> m) -> Digit (Elem a) -> m
        foldMapDigitE f t = foldDigit (<>) f t

        foldMapDigitN :: Monoid m => (Node a -> m) -> Digit (Node a) -> m
        foldMapDigitN f t = foldDigit (<>) f t

        foldMapNodeE :: Monoid m => (Elem a -> m) -> Node (Elem a) -> m
        foldMapNodeE f t = foldNode (<>) f t

        foldMapNodeN :: Monoid m => (Node a -> m) -> Node (Node a) -> m
        foldMapNodeN f t = foldNode (<>) f t
#if __GLASGOW_HASKELL__
    {-# INLINABLE foldMap #-}
#endif

The speeds are more what you'd expect:

benchmarking 50000/getSum . foldMap Sum
time                 317.9 μs   (316.3 μs .. 319.2 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 318.2 μs   (316.8 μs .. 320.2 μs)
std dev              5.982 μs   (4.938 μs .. 7.338 μs)
variance introduced by outliers: 11% (moderately inflated)
             
benchmarking 50000/getSum . foldMapWithIndex (const Sum)
time                 431.7 μs   (428.6 μs .. 434.0 μs)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 443.1 μs   (436.4 μs .. 451.8 μs)
std dev              23.79 μs   (18.88 μs .. 33.82 μs)
variance introduced by outliers: 48% (moderately inflated)
             
benchmarking 50000/foldl' (+) 0
time                 409.0 μs   (405.5 μs .. 414.5 μs)
                     0.998 R²   (0.996 R² .. 1.000 R²)
mean                 418.6 μs   (415.3 μs .. 426.1 μs)
std dev              19.48 μs   (15.71 μs .. 27.21 μs)
variance introduced by outliers: 42% (moderately inflated)

Although I'm not entirely sure why.

[treeowl]

Utterly enormous and inscrutable Core is the norm for Data.Sequence, unfortunately. I'm totally open to pull requests, as always. You may also want to look into #113 while you're in the neighborhood. And it might also be worth checking on foldl and foldr.

Another thing to consider:

We might be able to win some by splitting up the Foldable class up into single-method classes to use internally. That way we won't have big dictionaries flying all over. I don't know how if at all that relates to the improvements you see with the above change.

[oisdk]

I think what's happening in my benchmarks is that the specialisations on Sum and (+) aren't firing, rather than the dictionaries. I'll take a look and see if it helps elsewhere, though.

While checking out foldl', it looks like I am getting some speedups (around 5-10%, it's hard to tell), but I think there's a bug in the strictness of foldl'? Here's the rule from Data.Foldable:

foldl' f z = foldl' f z . toList

But for a sequence:

foldl' (\_ e -> e) undefined (fromList [x]) === x

Whereas:

foldl' (\_ e -> e) undefined [x] === undefined

In fact:

foldl' (\_ e -> e) undefined (fromList [x,y,z]) === z

[treeowl]

Indeed there is a mismatch, but it's not our fault: the list version changed by mistake in base 4.8 or so. Should we change to match? Unclear. We should should certainly document.

[oisdk]

Oh ok, I didn't realise. Strict-in-the initial would have been what I expected, so when I saw:

foldl' f z (One a) = f z a

I assumed it was a bug.

Anyway, in my benchmarks that change doesn't actually have a huge impact on the resulting speed. However, what does have a big impact is writing out the first level of each fold for the finger tree, and similarly manually specialising the "first-level" fold for digits and nodes. For example:

instance Foldable FingerTree where
    foldr _ z EmptyT = z
    foldr f z (Single x) = x `f` z
    foldr f z (Deep _ pr m sf) =
        foldrDigit f (foldrTree (foldrNode f) (foldrDigit f z sf) m) pr
      where
        foldrTree :: (Node a -> b -> b) -> b -> FingerTree (Node a) -> b
        foldrTree _ z EmptyT = z
        foldrTree f z (Single x) = x `f` z
        foldrTree f z (Deep _ pr m sf) =
            foldrDigitN f (foldrTree (foldrNodeN f) (foldrDigitN f z sf) m) pr

        foldrDigit :: (a -> b -> b) -> b -> Digit a -> b
        foldrDigit f b t = foldr f b t

        foldrDigitN :: (Node a -> b -> b) -> b -> Digit (Node a) -> b
        foldrDigitN f b t = foldr f b t

        foldrNode :: (a -> b -> b) -> Node a -> b -> b
        foldrNode f t b = foldr f b t

        foldrNodeN :: (Node a -> b -> b) -> Node (Node a) -> b -> b
        foldrNodeN f t b = foldr f b t
    {-# INLINE foldr #-}

I'm about to dive into the core to see what's going on, but I suspect this lets the function given to foldr specialise to the a instead of being obscured by Elem a.

At this stage, I've written foldr, foldMap, and foldl' in this style for the fingertree, and benchmarked them with the following functions:

foldMapSum :: Seq.Seq Int -> Int
foldMapSum = getSum . foldMap Sum

foldlSum :: Seq.Seq Int -> Int
foldlSum = foldl' (+) 0

foldrSum :: Seq.Seq Int -> Int
foldrSum xs = foldr (\x k z -> k $! z+x) id xs 0

These are the results on random sequences of length 500000:

benchmarking 500000/foldrSum/old
time                 37.39 ms   (36.43 ms .. 38.31 ms)
                     0.998 R²   (0.998 R² .. 0.999 R²)
mean                 38.50 ms   (37.96 ms .. 39.48 ms)
std dev              1.442 ms   (673.9 μs .. 2.439 ms)
variance introduced by outliers: 12% (moderately inflated)
             
benchmarking 500000/foldrSum/new
time                 4.315 ms   (4.226 ms .. 4.396 ms)
                     0.997 R²   (0.996 R² .. 0.998 R²)
mean                 4.190 ms   (4.141 ms .. 4.250 ms)
std dev              165.3 μs   (143.4 μs .. 190.2 μs)
variance introduced by outliers: 20% (moderately inflated)
             
benchmarking 500000/foldMapSum/old
time                 12.69 ms   (11.61 ms .. 13.48 ms)
                     0.978 R²   (0.953 R² .. 0.995 R²)
mean                 12.85 ms   (12.54 ms .. 13.15 ms)
std dev              884.9 μs   (685.5 μs .. 1.291 ms)
variance introduced by outliers: 33% (moderately inflated)
             
benchmarking 500000/foldMapSum/new
time                 3.506 ms   (3.483 ms .. 3.526 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 3.621 ms   (3.592 ms .. 3.656 ms)
std dev              100.8 μs   (85.21 μs .. 130.8 μs)
variance introduced by outliers: 13% (moderately inflated)
             
benchmarking 500000/foldlSum/old
time                 4.209 ms   (4.177 ms .. 4.238 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 4.351 ms   (4.309 ms .. 4.412 ms)
std dev              143.6 μs   (110.3 μs .. 217.4 μs)
variance introduced by outliers: 16% (moderately inflated)
             
benchmarking 500000/foldlSum/new
time                 2.382 ms   (2.347 ms .. 2.415 ms)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 2.434 ms   (2.419 ms .. 2.452 ms)
std dev              58.13 μs   (48.23 μs .. 75.36 μs)
variance introduced by outliers: 11% (moderately inflated)

[treeowl]

Jeepers creepers! Those are some seriously impressive numbers! Make the code as clean as you can, but we definitely want those.

…

On Jan 23, 2018 11:12 AM, "Donnacha Oisín Kidney" ***@***.***> wrote: Oh ok, I didn't realise. Strict-in-the initial would have been what I expected, so when I saw: foldl' f z (One a) = f z a I assumed it was a bug. Anyway, in my benchmarks that change doesn't actually have a huge impact on the resulting code. However, what *does* have a big impact is writing out the first level of each fold for the finger tree, and similarly manually specialising the "first-level" fold for digits and nodes. For example: instance Foldable FingerTree where foldr _ z EmptyT = z foldr f z (Single x) = x `f` z foldr f z (Deep _ pr m sf) = foldrDigit f (foldrTree (foldrNode f) (foldrDigit f z sf) m) pr where foldrTree :: (Node a -> b -> b) -> b -> FingerTree (Node a) -> b foldrTree _ z EmptyT = z foldrTree f z (Single x) = x `f` z foldrTree f z (Deep _ pr m sf) = foldrDigitN f (foldrTree (foldrNodeN f) (foldrDigitN f z sf) m) pr foldrDigit :: (a -> b -> b) -> b -> Digit a -> b foldrDigit f b t = foldr f b t foldrDigitN :: (Node a -> b -> b) -> b -> Digit (Node a) -> b foldrDigitN f b t = foldr f b t foldrNode :: (a -> b -> b) -> Node a -> b -> b foldrNode f t b = foldr f b t foldrNodeN :: (Node a -> b -> b) -> Node (Node a) -> b -> b foldrNodeN f t b = foldr f b t {-# INLINE foldr #-} I'm about to dive into the core to see what's going on, but I suspect this lets the function given to foldr specialise to the a instead of being obscured by Elem a. At this stage, I've written foldr, foldMap, and foldl' in this style for the fingertree, and benchmarked them with the following functions: foldMapSum :: Seq.Seq Int -> Int foldMapSum = getSum . foldMap Sum foldlSum :: Seq.Seq Int -> Int foldlSum = foldl' (+) 0 foldrSum :: Seq.Seq Int -> Int foldrSum xs = foldr (\x k z -> k $! z+x) id xs 0 These are the results on random sequences of length 500000: benchmarking 500000/foldrSum/old time 37.39 ms (36.43 ms .. 38.31 ms) 0.998 R² (0.998 R² .. 0.999 R²) mean 38.50 ms (37.96 ms .. 39.48 ms) std dev 1.442 ms (673.9 μs .. 2.439 ms) variance introduced by outliers: 12% (moderately inflated) benchmarking 500000/foldrSum/new time 4.315 ms (4.226 ms .. 4.396 ms) 0.997 R² (0.996 R² .. 0.998 R²) mean 4.190 ms (4.141 ms .. 4.250 ms) std dev 165.3 μs (143.4 μs .. 190.2 μs) variance introduced by outliers: 20% (moderately inflated) benchmarking 500000/foldMapSum/old time 12.69 ms (11.61 ms .. 13.48 ms) 0.978 R² (0.953 R² .. 0.995 R²) mean 12.85 ms (12.54 ms .. 13.15 ms) std dev 884.9 μs (685.5 μs .. 1.291 ms) variance introduced by outliers: 33% (moderately inflated) benchmarking 500000/foldMapSum/new time 3.506 ms (3.483 ms .. 3.526 ms) 0.999 R² (0.999 R² .. 1.000 R²) mean 3.621 ms (3.592 ms .. 3.656 ms) std dev 100.8 μs (85.21 μs .. 130.8 μs) variance introduced by outliers: 13% (moderately inflated) benchmarking 500000/foldlSum/old time 4.209 ms (4.177 ms .. 4.238 ms) 0.999 R² (0.999 R² .. 1.000 R²) mean 4.351 ms (4.309 ms .. 4.412 ms) std dev 143.6 μs (110.3 μs .. 217.4 μs) variance introduced by outliers: 16% (moderately inflated) benchmarking 500000/foldlSum/new time 2.382 ms (2.347 ms .. 2.415 ms) 0.999 R² (0.998 R² .. 0.999 R²) mean 2.434 ms (2.419 ms .. 2.452 ms) std dev 58.13 μs (48.23 μs .. 75.36 μs) variance introduced by outliers: 11% (moderately inflated) — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#504 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_bcSHAje68QHnZx6-sOmEI2Ap4daks5tNgTSgaJpZM4RmnVE> .

[treeowl]

Closed in #510.