A (late-)demand analysis and w/w question

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

A (late-)demand analysis and w/w question

Ömer Sinan Ağacan
Hi,

I was recently looking at #6087. One of the cases that increased
allocations (see comment:27) is when we do worker/wrapper to pass an
`Int#` instead of `Int` when we need the boxed form in the function
body. This causes redundant allocations because we already have the
boxed version of the value but we passed it unboxed as a result of
worker/wrapper.

This raises the obvious (but maybe naive?) question of whether we could
improve the demand analysis and/or worker/wrapper to avoid unpacking
arguments when the argument is boxed again somewhere in the function
body.

Does this make sense? Has anyone tried this before?

Thanks,

Ömer
_______________________________________________
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: A (late-)demand analysis and w/w question

GHC - devs mailing list
It's called "reboxing" and is referred to in all the strictness analysis papers about GHC.  I don't know a reliable way to get rid of it; but I have it paged out at the moment.

Eg https://www.microsoft.com/en-us/research/publication/theory-practice-demand-analysis-haskell/
https://www.microsoft.com/en-us/research/publication/demand-analysis/ (the box-demad stuff in the appendix is not implemented in GHC)

Simon


| -----Original Message-----
| From: ghc-devs [mailto:[hidden email]] On Behalf Of Ömer
| Sinan Agacan
| Sent: 20 February 2018 16:25
| To: ghc-devs <[hidden email]>
| Subject: A (late-)demand analysis and w/w question
|
| Hi,
|
| I was recently looking at #6087. One of the cases that increased
| allocations (see comment:27) is when we do worker/wrapper to pass an
| `Int#` instead of `Int` when we need the boxed form in the function body.
| This causes redundant allocations because we already have the boxed
| version of the value but we passed it unboxed as a result of
| worker/wrapper.
|
| This raises the obvious (but maybe naive?) question of whether we could
| improve the demand analysis and/or worker/wrapper to avoid unpacking
| arguments when the argument is boxed again somewhere in the function
| body.
|
| Does this make sense? Has anyone tried this before?
|
| Thanks,
|
| Ömer
| _______________________________________________
| ghc-devs mailing list
| [hidden email]
| https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.hask
| ell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fghc-
| devs&data=04%7C01%7Csimonpj%40microsoft.com%7C6adfeaddd9964adcba3208d5787
| eb1b1%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636547407938408171%7CU
| nknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwi
| fQ%3D%3D%7C-
| 1&sdata=XQ7xTxQepBeyi%2FDSHMmyXD0H8xFkh%2FoawqiIJJCUBYk%3D&reserved=0
_______________________________________________
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: A (late-)demand analysis and w/w question

Ömer Sinan Ağacan
Thanks. I checked both papers, they mention that not all reboxing is
eliminated, but as far as I can see they don't give an example reboxing that's
not eliminated. It's not hard to come up with an example though. In this
function

    fac :: Int -> Int
    fac 0 = 1
    fac n = n * fac (n - 1)

before simplification the worker looks like this

    Rec {
    -- RHS size: {terms: 29, types: 10, coercions: 0, joins: 0/2}
    $wfac__s28Z
    $wfac__s28Z
      = \ ww_s28U ->
          let {
            w_s28R
            w_s28R = I# ww_s28U } in
          case let {
                 n_aU7
                 n_aU7 = w_s28R } in
               case check n_aU7 of {
                 False ->
                   case n_aU7 of { I# x_a27t ->
                   case fac_ (I# (-# x_a27t 1#)) of { I# y_a27x ->
                   I# (*# x_a27t y_a27x)
                   }
                   };
                 True -> n_aU7
               }
          of ww_s28X
          { I# ww_s28Y ->
          ww_s28Y
          }

`w_s28R` reboxes, but that's easily eliminated by the simplifier. In this
example:

    {-# NOINLINE check #-}
    check :: Int -> Bool
    check !n = True

    fac_ :: Int -> Int
    fac_ n = if check n then n else n * fac_ (n - 1)

even after simplifications we rebox the argument:

    Rec {
    -- RHS size: {terms: 17, types: 3, coercions: 0, joins: 0/0}
    $wfac_
    $wfac_
      = \ ww_s28U ->
          case check (I# ww_s28U) of {
            False ->
              case $wfac_ (-# ww_s28U 1#) of ww1_s28Y { __DEFAULT ->
              *# ww_s28U ww1_s28Y
              };
            True -> ww_s28U
          }
    end Rec }

This seems like a limitation of current demand analyser. I'm going to update
the ticket and put it on hold for now.

Ömer

2018-02-21 1:47 GMT+03:00 Simon Peyton Jones <[hidden email]>:

> It's called "reboxing" and is referred to in all the strictness analysis papers about GHC.  I don't know a reliable way to get rid of it; but I have it paged out at the moment.
>
> Eg https://www.microsoft.com/en-us/research/publication/theory-practice-demand-analysis-haskell/
> https://www.microsoft.com/en-us/research/publication/demand-analysis/ (the box-demad stuff in the appendix is not implemented in GHC)
>
> Simon
>
>
> | -----Original Message-----
> | From: ghc-devs [mailto:[hidden email]] On Behalf Of Ömer
> | Sinan Agacan
> | Sent: 20 February 2018 16:25
> | To: ghc-devs <[hidden email]>
> | Subject: A (late-)demand analysis and w/w question
> |
> | Hi,
> |
> | I was recently looking at #6087. One of the cases that increased
> | allocations (see comment:27) is when we do worker/wrapper to pass an
> | `Int#` instead of `Int` when we need the boxed form in the function body.
> | This causes redundant allocations because we already have the boxed
> | version of the value but we passed it unboxed as a result of
> | worker/wrapper.
> |
> | This raises the obvious (but maybe naive?) question of whether we could
> | improve the demand analysis and/or worker/wrapper to avoid unpacking
> | arguments when the argument is boxed again somewhere in the function
> | body.
> |
> | Does this make sense? Has anyone tried this before?
> |
> | Thanks,
> |
> | Ömer
> | _______________________________________________
> | ghc-devs mailing list
> | [hidden email]
> | https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail.hask
> | ell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fghc-
> | devs&data=04%7C01%7Csimonpj%40microsoft.com%7C6adfeaddd9964adcba3208d5787
> | eb1b1%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636547407938408171%7CU
> | nknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwi
> | fQ%3D%3D%7C-
> | 1&sdata=XQ7xTxQepBeyi%2FDSHMmyXD0H8xFkh%2FoawqiIJJCUBYk%3D&reserved=0
_______________________________________________
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: A (late-)demand analysis and w/w question

GHC - devs mailing list
Correct. Another example might be

f 0 = []
f n = n : f (n-1)

It's strict all right, but we need the boxed 'n' for the result.

"Boxity" analysis might try to figure out when the boxed version is needed, and pass that too. At one stage I had that but it seemed unprincipled.

Simo

|  -----Original Message-----
|  From: Ömer Sinan Ağacan [mailto:[hidden email]]
|  Sent: 21 February 2018 06:30
|  To: Simon Peyton Jones <[hidden email]>
|  Cc: ghc-devs <[hidden email]>
|  Subject: Re: A (late-)demand analysis and w/w question
|  
|  Thanks. I checked both papers, they mention that not all reboxing is
|  eliminated, but as far as I can see they don't give an example
|  reboxing that's not eliminated. It's not hard to come up with an
|  example though. In this function
|  
|      fac :: Int -> Int
|      fac 0 = 1
|      fac n = n * fac (n - 1)
|  
|  before simplification the worker looks like this
|  
|      Rec {
|      -- RHS size: {terms: 29, types: 10, coercions: 0, joins: 0/2}
|      $wfac__s28Z
|      $wfac__s28Z
|        = \ ww_s28U ->
|            let {
|              w_s28R
|              w_s28R = I# ww_s28U } in
|            case let {
|                   n_aU7
|                   n_aU7 = w_s28R } in
|                 case check n_aU7 of {
|                   False ->
|                     case n_aU7 of { I# x_a27t ->
|                     case fac_ (I# (-# x_a27t 1#)) of { I# y_a27x ->
|                     I# (*# x_a27t y_a27x)
|                     }
|                     };
|                   True -> n_aU7
|                 }
|            of ww_s28X
|            { I# ww_s28Y ->
|            ww_s28Y
|            }
|  
|  `w_s28R` reboxes, but that's easily eliminated by the simplifier. In
|  this
|  example:
|  
|      {-# NOINLINE check #-}
|      check :: Int -> Bool
|      check !n = True
|  
|      fac_ :: Int -> Int
|      fac_ n = if check n then n else n * fac_ (n - 1)
|  
|  even after simplifications we rebox the argument:
|  
|      Rec {
|      -- RHS size: {terms: 17, types: 3, coercions: 0, joins: 0/0}
|      $wfac_
|      $wfac_
|        = \ ww_s28U ->
|            case check (I# ww_s28U) of {
|              False ->
|                case $wfac_ (-# ww_s28U 1#) of ww1_s28Y { __DEFAULT ->
|                *# ww_s28U ww1_s28Y
|                };
|              True -> ww_s28U
|            }
|      end Rec }
|  
|  This seems like a limitation of current demand analyser. I'm going to
|  update the ticket and put it on hold for now.
|  
|  Ömer
|  
|  2018-02-21 1:47 GMT+03:00 Simon Peyton Jones <[hidden email]>:
|  > It's called "reboxing" and is referred to in all the strictness
|  analysis papers about GHC.  I don't know a reliable way to get rid of
|  it; but I have it paged out at the moment.
|  >
|  > Eg
|  >
|  https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.m
|  > icrosoft.com%2Fen-us%2Fresearch%2Fpublication%2Ftheory-practice-
|  demand
|  > -analysis-
|  haskell%2F&data=04%7C01%7Csimonpj%40microsoft.com%7C6ad8305c
|  >
|  795c4129a3f708d578f4b27d%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C
|  >
|  636547914720320997%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjo
|  > iV2luMzIiLCJBTiI6Ik1haWwifQ%3D%3D%7C-
|  1&sdata=LNLMS20hkf%2BP6yJSN3pH5Td
|  > AnZAU06Btx2RZKR8lBuo%3D&reserved=0
|  >
|  https://na01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.m
|  > icrosoft.com%2Fen-us%2Fresearch%2Fpublication%2Fdemand-
|  analysis%2F&dat
|  >
|  a=04%7C01%7Csimonpj%40microsoft.com%7C6ad8305c795c4129a3f708d578f4b27d
|  >
|  %7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636547914720320997%7CUnk
|  >
|  nown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWw
|  > ifQ%3D%3D%7C-
|  1&sdata=yTLi22Z3k1F%2F0CoqgOepxa6watIqpPMveAW%2B3vXLsNg%3
|  > D&reserved=0 (the box-demad stuff in the appendix is not implemented
|  > in GHC)
|  >
|  > Simon
|  >
|  >
|  > | -----Original Message-----
|  > | From: ghc-devs [mailto:[hidden email]] On Behalf Of
|  > | Ömer Sinan Agacan
|  > | Sent: 20 February 2018 16:25
|  > | To: ghc-devs <[hidden email]>
|  > | Subject: A (late-)demand analysis and w/w question
|  > |
|  > | Hi,
|  > |
|  > | I was recently looking at #6087. One of the cases that increased
|  > | allocations (see comment:27) is when we do worker/wrapper to pass
|  an
|  > | `Int#` instead of `Int` when we need the boxed form in the
|  function body.
|  > | This causes redundant allocations because we already have the
|  boxed
|  > | version of the value but we passed it unboxed as a result of
|  > | worker/wrapper.
|  > |
|  > | This raises the obvious (but maybe naive?) question of whether we
|  > | could improve the demand analysis and/or worker/wrapper to avoid
|  > | unpacking arguments when the argument is boxed again somewhere in
|  > | the function body.
|  > |
|  > | Does this make sense? Has anyone tried this before?
|  > |
|  > | Thanks,
|  > |
|  > | Ömer
|  > | _______________________________________________
|  > | ghc-devs mailing list
|  > | [hidden email]
|  > |
|  https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail
|  > | .hask
|  > | ell.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fghc-
|  > |
|  devs&data=04%7C01%7Csimonpj%40microsoft.com%7C6adfeaddd9964adcba3208
|  > | d5787
|  > |
|  eb1b1%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C63654740793840817
|  > | 1%7CU
|  > |
|  nknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1
|  > | haWwi
|  > | fQ%3D%3D%7C-
|  > |
|  1&sdata=XQ7xTxQepBeyi%2FDSHMmyXD0H8xFkh%2FoawqiIJJCUBYk%3D&reserved=
|  > | 0
_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs