A (late)demand analysis and w/w question
Simon Peyton Jones
simonpj at microsoft.com
Wed Feb 21 09:45:34 UTC 2018
Correct. Another example might be
f 0 = []
f n = n : f (n1)
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: ghcdevs <ghcdevs 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

 20180221 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%2Fenus%2Fresearch%2Fpublication%2Ftheorypractice
 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%2Fenus%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 boxdemad stuff in the appendix is not implemented
 > in GHC)
 >
 > Simon
 >
 >
 >  Original Message
 >  From: ghcdevs [mailto:ghcdevsbounces at haskell.org] On Behalf Of
 >  Ömer Sinan Agacan
 >  Sent: 20 February 2018 16:25
 >  To: ghcdevs <ghcdevs 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
 >  _______________________________________________
 >  ghcdevs mailing list
 >  ghcdevs at haskell.org
 > 
 https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fmail
 >  .hask
 >  ell.org%2Fcgibin%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
More information about the ghcdevs
mailing list