Consider design change in light of GHC join point work

[treeowl]

The join points paper suggests that it may now be possible to avoid the need for Skip altogether. It would be worth checking if that's actually the case. If so, it might be possible to simplify the implementation considerably. Furthermore, I seem to recall that the presence of skips (which allow vectors of the same length to be represented by streams of different lengths) prevents one or more optimizations. I vaguely remember trying to do something a bit clever with replicate and finding it impossible because of skips, but I don't remember any details.

[cartazio]

... filter can't fuse without skips can it?

…

On Tue, Feb 21, 2017 at 2:49 PM David Feuer ***@***.***> wrote: The join points paper <https://www.microsoft.com/en-us/research/publication/compiling-without-continuations/> suggests that it may now be possible to avoid the need for Skip altogether. It would be worth checking if that's actually the case. If so, it might be possible to simplify the implementation considerably. Furthermore, I seem to recall that the presence of skips (which allow vectors of the same length to be represented by streams of different lengths) prevents one or more optimizations. I vaguely remember trying to do something a bit clever with replicate and finding it impossible because of skips, but I don't remember any details. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#156>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAAQwtSu6MWDlo1qGWdrgLswl4Muet-aks5rez-1gaJpZM4MHx21> .

[treeowl]

I believe the join point paper claims the new approach would allow it to do so, yes. Whether that is actually the case as implemented, I don't know. On Feb 23, 2017 6:02 AM, "Carter Tazio Schonwald" <notifications@github.com> wrote:

…

... filter can't fuse without skips can it? On Tue, Feb 21, 2017 at 2:49 PM David Feuer ***@***.***> wrote: > The join points paper > <https://www.microsoft.com/en-us/research/publication/compiling-without- continuations/> > suggests that it may now be possible to avoid the need for Skip > altogether. It would be worth checking if that's actually the case. If so, > it might be possible to simplify the implementation considerably. > Furthermore, I seem to recall that the presence of skips (which allow > vectors of the same length to be represented by streams of different > lengths) prevents one or more optimizations. I vaguely remember trying to > do something a bit clever with replicate and finding it impossible > because of skips, but I don't remember any details. > > — > You are receiving this because you are subscribed to this thread. > Reply to this email directly, view it on GitHub > <#156>, or mute the thread > <https://github.com/notifications/unsubscribe-auth/ AAAQwtSu6MWDlo1qGWdrgLswl4Muet-aks5rez-1gaJpZM4MHx21> > . > — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#156 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_d0j-U5DDGe2FmQYYxi0Dk9RF-_Vks5rfWdHgaJpZM4MHx21> .

[dolio]

The paper says the new join point handling makes it so that recursive stepper functions are no longer a problem. So Skip is no longer needed.

However, making this change would break (fusion-wise) the functions that require Skip on every compiler version that doesn't have the new join point handling. I assume that's everything before 8.2, or at best 8.0. So I'm not sure such a change can be justified for quite some time.

[cartazio]

And we still need to measure impact on compile time/ code side / performance for vector. That would change how loop breakers etc are chosen sometimes right?

…

On Fri, Feb 24, 2017 at 12:50 AM dolio ***@***.***> wrote: The paper says the new join point handling makes it so that recursive stepper functions are no longer a problem. So Skip is no longer needed. However, making this change would break (fusion-wise) the functions that require Skip on every compiler version that doesn't have the new join point handling. I assume that's everything before 8.2, or at best 8.0. So I'm not sure such a change can be justified for quite some time. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#156 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAAQwr2jc6OW3lYepHs9qySRvlRAcjpGks5rfm-lgaJpZM4MHx21> .

[dolio]

The one way I can think of to accelerate this kind of thing is to decouple the fusion from vectors. Have modules that provide plain vectors, and other modules that somehow add in fusion. Then give a choice of which fusion framework to use.

However, I'm not very sure how to accomplish something like this. The most obvious thing to say is, "this is where you want ML modules," because fusion is sort of a thing that transforms one implementation of an API into another. But backpack is probably more of a limiting factor than the join point stuff. Perhaps a newtype could work:

newtype Fused v a = F (v a)

Where you use Fused Vector a if you want fusion to happen for your choice of Vector.

Anyhow, this is a research project on top of a research project. :)

[cartazio]

@treeowl whats the best way to explore the join point cleanup in your mind?

[GeorgeCo]

Any thoughts on this recently? From the paper it sound very interesting:

Result: simpler code, less of it, and faster to execute. It’s a straight win

Would it be worthwhile to do a small prototype to see e.g. how much it improves runtime and/or compiler performance? Perhaps some of the zip or zipWith functions ? I picked those based on the following from the paper, but I'm not sure if it applies to zip for vectors:

Now the stepper function can say to update the state and call again, obviating the need for a loop of its own. This makes
filter fusible, but it complicates everything else! Everything gets three cases instead of two, leading to more code and more runtime tests; and functions like zip that consume two lists become more complicated and less efficient.

[lehins]

It is interesting, but it is also an enormous amount of work. @GeorgeCo You feel like working on this and submitting a PR with a prototype? If I were to work on this I would start with implementing and verifying performance of filter, because that is exactly what we need Skip for.

We already have a plan for putting all the streaming functionality that uses Stream and Step types into a separate package #355 So if this approach with relying on join points proves itself as feasible replacement for newer ghc we could then have two stream packages: one for older ghc with Skip and another package for newer ghc versions that doesn't have to rely on Skip for performance.

[noughtmare]

I've just done a quick scan over the code. Now I'm stuck and it seems to me like it is impossible to remove Skip for monadic streams. Take for example the drop function. I've removed the Step constructor and replaced its usage by a recursive call:

drop :: Monad m => Int -> Stream m a -> Stream m a
{-# INLINE_FUSED drop #-}
drop n (Stream step t) = Stream step' (t, Just n)
  where
    {-# INLINE_INNER step' #-}
    step' (s, Just i) | i > 0 = do
                                  r <- step s
                                  case r of
                                     Yield _ s' -> step' (s', Just (i-1))
                                     Done       -> return Done

    step' (s, _) = liftM (\r ->
                     case r of
                       Yield x s' -> Yield x (s', Nothing)
                       Done       -> Done
                   ) (step s)

But here the step' (s', Just (i - 1)) recursive call is not guaranteed to be a tail call (that depends on what the Monad m is), so GHC can't mark step' as a join point in general (if I understand it correctly).

Or is there another way to write this so that it can use a join point?

[cartazio]

This is a very cool observation, would having a flavor of monads that guarantee they respect tail calls, in a way ghc understands, solve that? I’ve hit a similar technical issue in some of my own prjects over time, though with different motivations. I’ll ask around

…

On Mon, Sep 26, 2022 at 11:07 AM Jaro Reinders ***@***.***> wrote: I've just done a quick scan over the code. It seems to me like it is impossible to remove Skip for monadic streams. Take for example the drop function. I've removed the Step constructor and replaced its usage by a recursive call: drop :: Monad m => Int -> Stream m a -> Stream m a {-# INLINE_FUSED drop #-}drop n (Stream step t) = Stream step' (t, Just n) where {-# INLINE_INNER step' #-} step' (s, Just i) | i > 0 = do r <- step s case r of Yield _ s' -> step' (s', Just (i-1)) Done -> return Done step' (s, _) = liftM (\r -> case r of Yield x s' -> Yield x (s', Nothing) Done -> Done ) (step s) But here the step' (s', Just (i - 1)) recursive call is not guaranteed to be a tail call (that depends on what the Monad m is), so GHC can't mark step' as a join point in general (if I understand it correctly). — Reply to this email directly, view it on GitHub <#156 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAABBQXHQZAQDOBSHR2XCUTWAG33LANCNFSM4DA7DW2Q> . You are receiving this because you commented.Message ID: ***@***.***>

[noughtmare]

would having a flavor of monads that
guarantee they respect tail calls, in a way ghc understands, solve that?

That's exactly what I was thinking!

I wonder what that looks like. I know somebody asked SPJ once after one of his talks if join points could be made explicit in the surface language and SPJ considered the possibility but didn't see an immediate use case.

I also think this is related to Alexis King's "Effects for Less" talk which mentions that it is really important that the monadic bind operator gets inlined.

Perhaps if we use her Eff monad instead of arbitrary monads in the streams then we would not have this issue.

[GeorgeCo]

It might be worthwhile to draw SPJ and the other author of the paper into this conversation.

[noughtmare]

ping @simonpj @pdownen @lukemaurer (I couldn't find Zena Ariola's github account if she even has one)

[simonpj]

Now I'm stuck and it seems to me like it is impossible to remove Skip for monadic streams. T

We are taking about fusion here, correct? That's only going to happen if you inine the function (in this case drop at the call site, else there is nothing to fuse with. And once you inline, you likely have fixed the monad.

I rather doubt that you'll achieve fusion for an arbitrary monad.

A good way to move this converation on would be to provide a concrete example of

• a program where you think fusion should take place
• the fused program that you think GHC should be able to reach by program transformations.

Being concrete aids comprehension, and saves misinderstandings.

[noughtmare]

Oh, that sounds right. Now I feel silly for missing that.

To be much more concrete. Take for example the Quickhull benchmark. Before my changes it takes 55.7 ms and after removing Skip it takes 72.2 ms. Looking at the core reveals a bunch of bindings like the following which I think are to blame for this discrepancy. These are not present in the core dumps from before my changes.

letrec {
  $s$wstep'_sebJ :: Int# -> Int# ->
    Id (Step (Int, Int, Maybe (Double, Double)) ((Double, Double), Double))
  $s$wstep'_sebJ
    = \ (sc_sebF :: Int#) (sc1_sebE :: Int#) ->
        case >=# sc1_sebE ww_sdOU of {
          __DEFAULT ->
            case indexDoubleArray# ww2_sdP0 (+# ww1_sdOY sc1_sebE) of wild2_a6SW { __DEFAULT ->
            case indexDoubleArray# ww4_sdP7 (+# ww3_sdP5 sc1_sebE) of wild1_Xe { __DEFAULT ->
            case >=# sc_sebF ww7_sdOz of {
              __DEFAULT ->
                case indexDoubleArray# ipv3_adv1 sc_sebF of wild3_Xh { __DEFAULT ->
                case >## wild3_Xh 0.0## of {
                  __DEFAULT -> $s$wstep'_sebJ (+# sc_sebF 1#) (+# sc1_sebE 1#); -- <<< recursive call here
                  1# ->
                    (Yield
                       ((D# wild2_a6SW, D# wild1_Xe), D# wild3_Xh)
                       (I# (+# sc1_sebE 1#), I# (+# sc_sebF 1#), Nothing))
                    `cast` <Co:15>
                }};
              1# -> Done `cast` <Co:15>
            }}};
          1# -> Done `cast` <Co:15>
        }; } in

Here are the full pre and post dumps of all the benchmarks:
bench-dumps.zip

And the particular benchmarks that got noticeably worse are: listrank, awshcc, hybcc, quickhull, findIndexR, findIndexR_manual. Especially awshcc got more than 3x slower and hybcc about 2x slower.