Re: keepAlive# primop

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: keepAlive# primop

Ben Gamari-3

Ccing ghc-devs@ since this discussion is something of general interest
to the community.


Sylvain Henry <[hidden email]> writes:

> Simon, Ben,
>
> I've been reading and thinking about `readRW#` issues which are very
> related to issues we have with `keepAlive#` primop.
>
> To recap, the problem is that we want some transformations (that Simon
> has listed in [1]) to consider:
>
> ```
> case runRW# f of ...
>
> case keepAlive# k a of ...
> ```
>
> as if they were really:
>
> ```
> case f realWorld# of ...
>
> case a of ...
> ```
>
> BUT without breaking the semantics of runRW# and keepAlive#.
>
> I have been thinking about a solution that I have described on the wiki:
> https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables
>
> The idea is to keep a set of variable names in each Core case-expression
> that are kept alive during the evaluation of the scrutinee.
>
> I think it would work very nicely with your `newState#` primop described
> in [2], both for `runST` and for `unsafeDupablePerformIO` (details on
> the wiki).
>
> It requires a little more upfront work to adapt the code involving
> case-expressions. But it will force us to review all transformations to
> check if they are sound when keep-alive sets are not empty, which we
> would have to do anyway if we implemented another option. We could start
> by disabling transformations involving non-empty keep-alive sets and
> iterate to enable the sound ones.
>
> I would like your opinions on the approach. I may have totally missed
> something.
Thanks for writing this down!

Indeed it is an interesting idea. However, as expressed on IRC, I
wonder whether this problem rises to the level where it warrants an
adaptation to our Core representation. It feels a bit like the
tail is wagging the dog here, especially given how the "tail" here
merely exists to support FFI.

That being said, this is one of the few options which remain on the
table that doesn't require changes to user code. Moreover, the
applicability to runRW# is quite intriguing.

Another (admittedly, more ad-hoc) option that would avoid modifying Core
would be to teach the simplifier about the class of
"continuation-passing" primops (e.g. `keepAlive#` and `runRW#`), allowing it
to push case analyses into the continuation argument. That is,

    case keepAlive# x expr of pat -> rhs

            ~>

    keepAlive# x (case expr of pat -> rhs)

Of course, doing this is a bit tricky since one must rewrite the
application of keepAlive# to ensure that the resulting application is
well-typed. Admittedly, this doesn't help the runRW# case (although this
could presumably be accommodated by touch#'ing the final state token in
the runRW# desugaring emitted by CorePrep).

On the whole, I'm not a fan of this ad-hoc option. It increases the
complexity of the simplifier all to support a single operation. By
comparison, the Core extension looks somewhat appealing.

Cheers,

- Ben


[1] https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables

P.S. A minor note: the keepAlive# "pseudo-instruction" mentioned on the
Wiki [1] is precisely the touch# operation we have today.

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: keepAlive# primop

Sylvain Henry-2

Hi ghc-devs,

After a discussion today about `keepAlive#`, I think Option E [1] is even more appealing.

To recap the idea was to have keep-alive variable sets attached to case-expressions in Core. E.g. `case {k} x of ...`


1. One of the issue was the semantics of `keepAlive#`. `keepAlive#` is very intricate with evaluation. As Simon mentioned we want a semantics like:

 keepAlive# k x ==> x `seq` touch# k `seq` x

with potentially a special `seq` to deal with diverging `x`.

With `case {k} x of ...` we have this semantics. Even if we throw the case alternatives if `x` diverges, we don't throw the keep-alive set so we're good.


2. Simon wanted to push `keepAlive#` into case-expressions. With this approach we should only have to fix case-of-case to take keep-alive sets into account.

case {k} (case {k2} x of .. -> a; ... -> b) of
  C0 .. -> e1
  C1 .. -> e2

===>

case {k,k2} x of
   ... -> case {k} a of { C0 .. -> e1; C1 ... -> e2 }
   ... -> case {k} b of { C0 .. -> e1; C1 ... -> e2 }


3. Compared to other approaches: we don't have to use stack frames (good for performance) and we don't have to deal with a continuation (good for Core optimizations, hence perf).

4. Implementing this approach is quite straightforward even if it modifies Core. I did it last month in [2]. This patch doesn't fully work yet with `-O` because some transformation (related to join points IIRC) doesn't take keep-alive sets into account but it should be pretty easy to fix if we want to use this approach.


Given how hard it is to come up with a good design/implementation of other approaches, this one strikes me as probably the more principled we have and yet it is relatively easy to implement. What do you think?

Cheers,
Sylvain


[1] https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables

[2] https://gitlab.haskell.org/hsyl20/ghc/-/commits/hsyl20-keepalive



On 13/04/2020 19:51, Ben Gamari wrote:
Ccing ghc-devs@ since this discussion is something of general interest
to the community.


Sylvain Henry [hidden email] writes:

Simon, Ben,

I've been reading and thinking about `readRW#` issues which are very 
related to issues we have with `keepAlive#` primop.

To recap, the problem is that we want some transformations (that Simon 
has listed in [1]) to consider:

```
case runRW# f of ...

case keepAlive# k a of ...
```

as if they were really:

```
case f realWorld# of ...

case a of ...
```

BUT without breaking the semantics of runRW# and keepAlive#.

I have been thinking about a solution that I have described on the wiki: 
https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables

The idea is to keep a set of variable names in each Core case-expression 
that are kept alive during the evaluation of the scrutinee.

I think it would work very nicely with your `newState#` primop described 
in [2], both for `runST` and for `unsafeDupablePerformIO` (details on 
the wiki).

It requires a little more upfront work to adapt the code involving 
case-expressions. But it will force us to review all transformations to 
check if they are sound when keep-alive sets are not empty, which we 
would have to do anyway if we implemented another option. We could start 
by disabling transformations involving non-empty keep-alive sets and 
iterate to enable the sound ones.

I would like your opinions on the approach. I may have totally missed 
something.
Thanks for writing this down!

Indeed it is an interesting idea. However, as expressed on IRC, I
wonder whether this problem rises to the level where it warrants an
adaptation to our Core representation. It feels a bit like the
tail is wagging the dog here, especially given how the "tail" here
merely exists to support FFI.

That being said, this is one of the few options which remain on the
table that doesn't require changes to user code. Moreover, the
applicability to runRW# is quite intriguing.

Another (admittedly, more ad-hoc) option that would avoid modifying Core
would be to teach the simplifier about the class of
"continuation-passing" primops (e.g. `keepAlive#` and `runRW#`), allowing it
to push case analyses into the continuation argument. That is,

    case keepAlive# x expr of pat -> rhs

            ~>

    keepAlive# x (case expr of pat -> rhs)

Of course, doing this is a bit tricky since one must rewrite the
application of keepAlive# to ensure that the resulting application is
well-typed. Admittedly, this doesn't help the runRW# case (although this
could presumably be accommodated by touch#'ing the final state token in
the runRW# desugaring emitted by CorePrep).

On the whole, I'm not a fan of this ad-hoc option. It increases the
complexity of the simplifier all to support a single operation. By
comparison, the Core extension looks somewhat appealing.

Cheers,

- Ben


[1] https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables

P.S. A minor note: the keepAlive# "pseudo-instruction" mentioned on the
Wiki [1] is precisely the touch# operation we have today.

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: keepAlive# primop

GHC - devs mailing list

I’m pretty reluctant to change the Core Language to support one very dark corner use-case.  Then every Core consumer and producer must understand the semantics of this new field, and respect that semantics.

 

As I understand it, our definition

 

keepAlive# k x s = case nodiv x s of (# s1, r #) ->
                   case touch# k s1 of (# s2, _ #) ->
                   (# s2, r #)

 

does just what we want, except perhaps efficiency, without changing the language.  If that’s true, let’s convince ourselves that

  • The efficiency cannot be recovered
  • The loss of efficiency matters a lot

before taking more drastic steps.

 

For completeness,

               nodiv :: IO a -> IO a

behaves like the identity function except that (nodiv e) never says “guarantees to diverges”

 

Simon

 

From: Sylvain Henry <[hidden email]>
Sent: 26 May 2020 18:04
To: Ben Gamari <[hidden email]>; Simon Peyton Jones <[hidden email]>
Cc: GHC developers <[hidden email]>
Subject: Re: keepAlive# primop

 

Hi ghc-devs,

After a discussion today about `keepAlive#`, I think Option E [1] is even more appealing.

To recap the idea was to have keep-alive variable sets attached to case-expressions in Core. E.g. `case {k} x of ...`

 

1. One of the issue was the semantics of `keepAlive#`. `keepAlive#` is very intricate with evaluation. As Simon mentioned we want a semantics like:

 keepAlive# k x ==> x `seq` touch# k `seq` x

with potentially a special `seq` to deal with diverging `x`.

With `case {k} x of ...` we have this semantics. Even if we throw the case alternatives if `x` diverges, we don't throw the keep-alive set so we're good.

 

2. Simon wanted to push `keepAlive#` into case-expressions. With this approach we should only have to fix case-of-case to take keep-alive sets into account.

case {k} (case {k2} x of .. -> a; ... -> b) of
  C0 .. -> e1
  C1 .. -> e2
 
===>
 
case {k,k2} x of
   ... -> case {k} a of { C0 .. -> e1; C1 ... -> e2 }
   ... -> case {k} b of { C0 .. -> e1; C1 ... -> e2 }
 
 

3. Compared to other approaches: we don't have to use stack frames (good for performance) and we don't have to deal with a continuation (good for Core optimizations, hence perf).

4. Implementing this approach is quite straightforward even if it modifies Core. I did it last month in [2]. This patch doesn't fully work yet with `-O` because some transformation (related to join points IIRC) doesn't take keep-alive sets into account but it should be pretty easy to fix if we want to use this approach.

 

Given how hard it is to come up with a good design/implementation of other approaches, this one strikes me as probably the more principled we have and yet it is relatively easy to implement. What do you think?

Cheers,
Sylvain

 

[1] https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables

[2] https://gitlab.haskell.org/hsyl20/ghc/-/commits/hsyl20-keepalive

 

 

On 13/04/2020 19:51, Ben Gamari wrote:

 
Ccing ghc-devs@ since this discussion is something of general interest
to the community.
 
 
Sylvain Henry [hidden email] writes:
 
Simon, Ben,
 
I've been reading and thinking about `readRW#` issues which are very 
related to issues we have with `keepAlive#` primop.
 
To recap, the problem is that we want some transformations (that Simon 
has listed in [1]) to consider:
 
```
case runRW# f of ...
 
case keepAlive# k a of ...
```
 
as if they were really:
 
```
case f realWorld# of ...
 
case a of ...
```
 
BUT without breaking the semantics of runRW# and keepAlive#.
 
I have been thinking about a solution that I have described on the wiki: 
https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables
 
The idea is to keep a set of variable names in each Core case-expression 
that are kept alive during the evaluation of the scrutinee.
 
I think it would work very nicely with your `newState#` primop described 
in [2], both for `runST` and for `unsafeDupablePerformIO` (details on 
the wiki).
 
It requires a little more upfront work to adapt the code involving 
case-expressions. But it will force us to review all transformations to 
check if they are sound when keep-alive sets are not empty, which we 
would have to do anyway if we implemented another option. We could start 
by disabling transformations involving non-empty keep-alive sets and 
iterate to enable the sound ones.
 
I would like your opinions on the approach. I may have totally missed 
something.
 
Thanks for writing this down!
 
Indeed it is an interesting idea. However, as expressed on IRC, I
wonder whether this problem rises to the level where it warrants an
adaptation to our Core representation. It feels a bit like the
tail is wagging the dog here, especially given how the "tail" here
merely exists to support FFI.
 
That being said, this is one of the few options which remain on the
table that doesn't require changes to user code. Moreover, the
applicability to runRW# is quite intriguing.
 
Another (admittedly, more ad-hoc) option that would avoid modifying Core
would be to teach the simplifier about the class of
"continuation-passing" primops (e.g. `keepAlive#` and `runRW#`), allowing it
to push case analyses into the continuation argument. That is,
 
    case keepAlive# x expr of pat -> rhs
 
            ~>
 
    keepAlive# x (case expr of pat -> rhs)
 
Of course, doing this is a bit tricky since one must rewrite the
application of keepAlive# to ensure that the resulting application is
well-typed. Admittedly, this doesn't help the runRW# case (although this
could presumably be accommodated by touch#'ing the final state token in
the runRW# desugaring emitted by CorePrep).
 
On the whole, I'm not a fan of this ad-hoc option. It increases the
complexity of the simplifier all to support a single operation. By
comparison, the Core extension looks somewhat appealing.
 
Cheers,
 
- Ben
 
 
[1] https://gitlab.haskell.org/ghc/ghc/-/wikis/proposal/with-combinator#option-e-tag-core-case-expression-with-kept-alive-variables
 
P.S. A minor note: the keepAlive# "pseudo-instruction" mentioned on the
Wiki [1] is precisely the touch# operation we have today.

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs