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

[Simon Peyton Jones]

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:omeragacan at gmail.com]
|  Sent: 21 February 2018 06:30
|  To: Simon Peyton Jones <simonpj at microsoft.com>
|  Cc: ghc-devs <ghc-devs at haskell.org>
|  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 <simonpj at microsoft.com>:
|  > 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:ghc-devs-bounces at haskell.org] On Behalf Of
|  > | Ömer Sinan Agacan
|  > | Sent: 20 February 2018 16:25
|  > | To: ghc-devs <ghc-devs at haskell.org>
|  > | 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
|  > | ghc-devs at haskell.org
|  > |
|  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