Fusion isn't reliable

[kvanbere]

When investigating fusion triggering in my own library I tried the following line:

recieve ep2 >-> PBS.map (+1) >-> PBS.map (+1) >-> P.print

Using -ddump-rule-firings nothing for-related ever fired.

On the other hand, this seemed to fire many for-related rules:

recieve ep2 >-> P.map (BS.append "foo") >-> P.map (BS.append "bar") >-> P.print

This fired rules correctly too:

recieve ep2 >-> P.map (BS.map succ) >-> P.map (BS.map succ) >-> P.print

I don't think map from Pipes.ByteString is firing rules correctly at all ...

[kvanbere]

It's awkward because PBS.map is defined as;

-- | Apply a transformation to each 'Word8' in the stream
map :: Monad m => (Word8 -> Word8) -> Pipe ByteString ByteString m r
map f = P.map (BS.map f)
{-# INLINABLE map #-}

.. which is exactly the same as one above which works.

[kvanbere]

recieve ep2 >-> PBS.map (+1) >-> PBS.map (+1) >-> P.print:

[1 of 1] Compiling Main             ( Cloud.hs, Cloud.o )
Rule fired: unpack
Rule fired: unpack
Rule fired: unpack
Rule fired: unpack
Rule fired: foldr/nil
Rule fired: foldr/nil
Rule fired: foldr/nil
Rule fired: unpack
Rule fired: Class op fail
Rule fired: unpack
Rule fired: Class op fail
Rule fired: unpack
Rule fired: p >-> send'
Rule fired: Class op $p1MonadIO
Rule fired: Class op liftIO
Rule fired: Class op return
Rule fired: Class op >>=
Rule fired: Class op fromInteger
Rule fired: Class op +
Rule fired: Class op fromInteger
Rule fired: Class op +
Rule fired: p >-> print
Rule fired: Class op $p1MonadIO
Rule fired: Class op liftIO
Rule fired: Class op >>
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: _bind (Respond b  k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: Class op >>=
Rule fired: Class op return
Rule fired: SPEC Pipes.Core.+>> [GHC.Types.IO]
Rule fired: SPEC Pipes.Core.>>~ [GHC.Types.IO]
Rule fired: SPEC Pipes.Core.+>> [GHC.Types.IO]
Rule fired: SPEC Pipes.Core.+>> [GHC.Types.IO]
Rule fired: Class op return
Rule fired: Class op >>=
Rule fired: SPEC Pipes.Core.>>~ [GHC.Types.IO]
Rule fired: SPEC Pipes.Core.+>> [GHC.Types.IO]
Rule fired: SPEC Pipes.Core.>>~ [GHC.Types.IO]
Rule fired: Class op return
Rule fired: Class op >>=
Rule fired: _bind (Respond b  k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: _bind (Request a' k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: _bind (Respond b  k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: Class op $p1MonadIO
Rule fired: Class op liftIO
Rule fired: _bind (Respond b  k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: _bind (M          m) f
Rule fired: Class op return
Rule fired: Class op >>=
Rule fired: _bind (Pure    r   ) f
Rule fired: SPEC Pipes.Core.runEffect [GHC.Types.IO]
Rule fired: SPEC Pipes.ByteString.fromLazy [GHC.Types.IO]
Rule fired: SPEC Pipes.Core.runEffect [GHC.Types.IO]
Rule fired: integerToWord
Rule fired: narrow8Word#
Rule fired: _bind (Respond b  k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: _bind (Request a' k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: integerToWord
Rule fired: narrow8Word#
Rule fired: _bind (Respond b  k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: _bind (Request a' k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: Class op show
Rule fired: Class op liftIO
Rule fired: Class op liftIO
Rule fired: _bind (M          m) f
Rule fired: Class op return
Rule fired: Class op >>=
Rule fired: _bind (Pure    r   ) f
Rule fired: SPEC Pipes.Courier.recieve [GHC.Types.IO]
Rule fired: SPEC Pipes.Core.+>> [GHC.Types.IO]
Rule fired: SPEC Pipes.Core.+>> [GHC.Types.IO]
Rule fired: unpack-list
Rule fired: unpack-list
Rule fired: unpack-list
Rule fired: unpack-list
Rule fired: unpack-list
Rule fired: unpack-list
Rule fired: unpack-list
Linking Cloud ...

recieve ep2 >-> P.map (BS.map succ) >-> P.map (BS.map succ) >-> P.print:

[1 of 1] Compiling Main             ( Cloud.hs, Cloud.o )
Rule fired: unpack
Rule fired: unpack
Rule fired: unpack
Rule fired: unpack
Rule fired: foldr/nil
Rule fired: foldr/nil
Rule fired: foldr/nil
Rule fired: unpack
Rule fired: Class op fail
Rule fired: unpack
Rule fired: Class op fail
Rule fired: unpack
Rule fired: p >-> send'
Rule fired: Class op $p1MonadIO
Rule fired: Class op liftIO
Rule fired: Class op return
Rule fired: Class op >>=
Rule fired: Class op succ
Rule fired: p >-> map f
Rule fired: Class op succ
Rule fired: p >-> map f
Rule fired: for (for p f) g
Rule fired: for (yield x) f
Rule fired: p >-> print
Rule fired: Class op $p1MonadIO
Rule fired: Class op liftIO
Rule fired: for (for p f) g
Rule fired: Class op >>
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: Class op >>=
Rule fired: for (yield x) f
Rule fired: _bind (Respond b  k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: Class op >>=
Rule fired: Class op return
Rule fired: Class op $p1MonadIO
Rule fired: Class op liftIO
Rule fired: _bind (Respond b  k) f
Rule fired: _bind (Pure    r   ) f
Rule fired: _bind (M          m) f
Rule fired: Class op return
Rule fired: Class op >>=
Rule fired: _bind (Pure    r   ) f
Rule fired: SPEC Pipes.Core.runEffect [GHC.Types.IO]
Rule fired: SPEC Pipes.ByteString.fromLazy [GHC.Types.IO]
Rule fired: SPEC Pipes.Core.runEffect [GHC.Types.IO]
Rule fired: Class op show
Rule fired: Class op liftIO
Rule fired: Class op liftIO
Rule fired: _bind (M          m) f
Rule fired: Class op return
Rule fired: Class op >>=
Rule fired: _bind (Pure    r   ) f
Rule fired: SPEC Pipes.Courier.recieve [GHC.Types.IO]
Rule fired: unpack-list
Rule fired: unpack-list
Rule fired: unpack-list
Rule fired: unpack-list
Rule fired: unpack-list
Rule fired: unpack-list
Rule fired: unpack-list
Linking Cloud ...

[Gabriella439]

I found the problem. The difference between Pipes.Prelude.map and Pipes.ByteString.map is that the former one has this rewrite rule:

p >-> Pipes.Prelude.map f = for p (\a -> yield (f a))

... but I forgot to add the equivalent rewrite rule for Pipes.ByteString.map. In fact, a lot of the pipes-bytestring methods are missing these rewrite rules, so I will add them in the next release.

If you read the post closely, you'll see that defining things in terms of for cat does not suffice to completely trigger for loop fusion. You also need the rules like the above that translate (>->) to for.

Note that I cannot define a rewrite rule for all of them like this:

p >-> for cat f = for p f

This rule does not hold in general: it is only true if f never awaits. This is why I have to provide a separate rewrite rule for each of these functions.

[Gabriella439]

Oops, I wasn't paying attention very closely and didn't realize that Pipes.ByteString.map was defined in terms of Pipes.Prelude.map so what I previously said is not correct at all.

My first guess from looking at the rewrite rules was that (>->) was inlining too early (because of all the (+>>) and (>>~) specializations which is how (>->) is implemented internally). However, adding INLINE or NOINLINE pragmas didn't fix the problem, with or without phase control.

I also tried adding INLINE to Pipes.ByteString.map, with or without phase control. This didn't fix things either.

Usually my trick for optimizing things is a combination of benchmarks and careful study of selected rule firing examples. I try to find a pattern for what pragmas get rewrite rules to fire consistently across a wide range of examples and then use the benchmarks to prove that my pattern works.

I suspect what we will need here is some sort of phase control for either rules or inlining order but I'm not sure what the exact pattern will be yet. If you are new to this, a good place to begin is the article on phase control here and also the article on rewrite rules here.

In the short term, pipes-bytestring probably needs a benchmark suite anyway, so that's a useful thing we can do no matter what.

[kvanbere]

Some phase control would probably help the warnings GHC spits out for rewrite rules, too.

[Gabriella439]

I just wanted to let you know that I will be a little busy for the next few days working to polish pipes-text, but I will come back to this when I'm done.