Re: [Haskell-cafe] GHC magic optimization ?

[Neil Brown]

Emmanuel CHANTREAU wrote:

I will take an example:

f x y= x+y

The program ask the user to enter two numbers and print the sum. If the
user enter 1 2 f 1 2=3 is stored and a gargage collector is used to
remove this dandling expression later ?
If the user enter again 1 2, ghc search in dandling results to
try to find the result without computing it again ?
  

Hi,

I think what you're asking is how Haskell knows at run-time for which 
expressions it can re-use the results.  The answer is: it doesn't, it 
works it out at compile-time.  So if you have:


f x y = x + y

And at some point in your program you call f 1 2, and later on from a 
totally separate function you call f 1 2, the function will be evaluated 
twice (assuming 1 and 2 weren't known constants at compile-time).  But 
let's say you have:


g x y = f x y * f x y

Now the compiler (i.e. at compile-time) can do some magic.  It can spot 
the common expression and know the result of f x y must be the same both 
times, so it can convert to:


g x y = let z = f x y in z * z

Now, the Haskell run-time will evaluate f x y once, store the result in 
z, and use it twice.  That's how it can use commonalities in your code 
and avoid multiple evaluations of the same function call, which I 
*think* was your question.


Thanks,

Neil.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Luke Palmer]

On Fri, Dec 4, 2009 at 3:36 AM, Neil Brown nc...@kent.ac.uk wrote:
 But let's say you have:

 g x y = f x y * f x y

 Now the compiler (i.e. at compile-time) can do some magic.  It can spot the
 common expression and know the result of f x y must be the same both times,
 so it can convert to:

 g x y = let z = f x y in z * z

GHC does *not* do this by default, quite intentionally, even when
optimizations are enabled.  The reason is because it can cause major
changes in the space complexity of a program.  Eg.

x = sum [1..10^6] + product [1..10^6]
x' = let l = [1..10^6] in sum l + product l

x runs in constant space, but x' keeps the whole list in memory.  The
CSE here has actually wasted both time and space, since it is harder
to save [1..10^6] than to recompute it!  (Memory vs. arithmetic ops)

So GHC leaves it to the user to specify sharing.  If you want an
expression shared, let bind it and reuse.

Luke
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Joachim Breitner]

Hi,

Am Freitag, den 04.12.2009, 10:36 + schrieb Neil Brown:
 But let's say you have:
 
 g x y = f x y * f x y
 
 Now the compiler (i.e. at compile-time) can do some magic.  It can
 spot the common expression and know the result of f x y must be the
 same both times, so it can convert to:
 
 g x y = let z = f x y in z * z
 
 Now, the Haskell run-time will evaluate f x y once, store the result
 in z, and use it twice.  That's how it can use commonalities in your
 code and avoid multiple evaluations of the same function call, which I
 *think* was your question. 

Note that although the compiler _could_ do this transformation, it does
not actually do it because of some unwanted subtleties:
http://www.haskell.org/haskellwiki/GHC:FAQ#Does_GHC_do_common_subexpression_elimination.3F

(I was a bit disappointed when I found out about this, after first
hearing how much great optimization a haskell compiler _could_ do, but
that’s reality.)

Greetings,
Joachim

-- 
Joachim nomeata Breitner
  mail: m...@joachim-breitner.de | ICQ# 74513189 | GPG-Key: 4743206C
  JID: nome...@joachim-breitner.de | http://www.joachim-breitner.de/
  Debian Developer: nome...@debian.org


signature.asc
Description: Dies ist ein digital signierter Nachrichtenteil
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Mark Lentczner]

On Dec 4, 2009, at 2:43 AM, Luke Palmer wrote:

 So GHC leaves it to the user to specify sharing.  If you want an
 expression shared, let bind it and reuse.

Does GHC treat where and let the same in this regard? Or in code, are these 
treated the same?

 x'' = sum l + product l where l = [1..10^6]

 x' = let l = [1..10^6] in sum l + product l


I couldn't tell if the report implies that or not.

- Mark




Mark Lentczner
http://www.ozonehouse.com/mark/
m...@glyphic.com



___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Luke Palmer]

On Fri, Dec 4, 2009 at 9:44 AM, Mark Lentczner ma...@glyphic.com wrote:

 On Dec 4, 2009, at 2:43 AM, Luke Palmer wrote:

 So GHC leaves it to the user to specify sharing.  If you want an
 expression shared, let bind it and reuse.

 Does GHC treat where and let the same in this regard? Or in code, are these 
 treated the same?

where is just sugar for let.


 x'' = sum l + product l where l = [1..10^6]

 x' = let l = [1..10^6] in sum l + product l


 I couldn't tell if the report implies that or not.

        - Mark




 Mark Lentczner
 http://www.ozonehouse.com/mark/
 m...@glyphic.com



 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Matt Morrow]

Although, in Luke's example,

 x = sum [1..10^6] + product [1..10^6]
 x' = let l = [1..10^6] in sum l + product l

We can do much much better, if we're sufficiently smart.

-- Define:
bar m n = foo (enumFromTo m n)
foo xs  = sum xs + prod xs

-- We're given:
sum = foldl (+) 0
product = foldl (*) 1
foldl f z xs =
  case xs of
[] - []
x:xs - foldl f (f z x) xs
enumFromTo m n =
  case m  n of
True - []
False - m : enumFromTo (m+1) n

-- The fused loop becomes:
foo xs = go0 0 1 xs
  where go0 a b xs =
  case xs of
[] - a+b
x:xs - go0 (a+x) (b*x) xs

-- Now inline foo in bar:
bar m n = go2 0 1 m n
  where go2 = go0 a b (go1 m n)
go0 a b xs =
  case xs of
[] - a+b
x:xs - go0 (a+x) (b*x) xs
go1 m n =
  case m  n of
True - []
False - m : go1 (m+1) n

-- considering go2
go2 = go0 a b (go1 m n)

== case (go1 m n) of
  [] - a+b
   x:xs - go0 (a+x) (b*x) xs

== case (case m  n of
   True - []
   False - m : go1 (m+1) n) of
  [] - a+b
  x:xs - go0 (a+x) (b*x) xs

== case m  n of
  True - case [] of
[] - a+b
x:xs - go0 (a+x) (b*x) xs

  False - case (m : go1 (m+1) n) of
 [] - a+b
 x:xs - go0 (a+x) (b*x) xs

== case m  n of
  True - a+b
  False - go0 (a+m) (b*m) (go1 (m+1) n)

-- So,
go2 = case m  n of
True - a+b
False - go0 (a+m) (b*m) (go1 (m+1) n)

-- And by the original def of go2
go2 = go0 a b (go1 m n)

-- We get
go2 = case m  n of
True - a+b
False - go2 (a+m) (b*m) (m+1) n

-- go0 and go1 and now dead in bar
bar m n = go2 0 1 m n
  where go2 = case m  n of
True - a+b
False - go2 (a+m) (b*m) (m+1) n

-- (furthermore, if (+) here is for Int/Double etc,
-- we can reduce go2 further to operate on machine
-- ints/doubles and be a register-only non-allocating loop)

-- So now finally returning to our original code:
 x = sum [1..10^6] + product [1..10^6]
 x' = let l = [1..10^6] in sum l + product l

-- We get:
x' = bar 1 (10^6)

And the intermediate list never exists at all.

Matt




On 12/4/09, Luke Palmer lrpal...@gmail.com wrote:
 On Fri, Dec 4, 2009 at 3:36 AM, Neil Brown nc...@kent.ac.uk wrote:
 But let's say you have:

 g x y = f x y * f x y

 Now the compiler (i.e. at compile-time) can do some magic.  It can spot
 the
 common expression and know the result of f x y must be the same both
 times,
 so it can convert to:

 g x y = let z = f x y in z * z

 GHC does *not* do this by default, quite intentionally, even when
 optimizations are enabled.  The reason is because it can cause major
 changes in the space complexity of a program.  Eg.

 x = sum [1..10^6] + product [1..10^6]
 x' = let l = [1..10^6] in sum l + product l

 x runs in constant space, but x' keeps the whole list in memory.  The
 CSE here has actually wasted both time and space, since it is harder
 to save [1..10^6] than to recompute it!  (Memory vs. arithmetic ops)

 So GHC leaves it to the user to specify sharing.  If you want an
 expression shared, let bind it and reuse.

 Luke
 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[George Pollard]

2009/12/4 Evan Laforge qdun...@gmail.com:
 The interesting thing is CAFs, which at the top level will never be
 out of scope and hence live forever.

Untrue! CAFs can be garbage collected as well. See:

http://www.haskell.org/pipermail/glasgow-haskell-users/2005-September/009051.html
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Matt Morrow]

Fixing my errors:

 x = sum [1..10^6] + product [1..10^6]
 x' = let l = [1..10^6] in sum l + product l

-- Define:
bar m n = foo (enumFromTo m n)
foo xs  = sum xs + prod xs

-- We're given:
sum = foldl (+) 0
product = foldl (*) 1
foldl f z xs =
  case xs of
[] - []
x:xs - foldl f (f z x) xs
enumFromTo m n =
  case n  m of
True - []
False - m : enumFromTo (m+1) n

-- The fused loop becomes:
foo xs = go0 0 1 xs
  where go0 a b xs =
  case xs of
[] - a+b
x:xs - go0 (a+x) (b*x) xs

-- Now inline foo in bar:
bar m n = go2 0 1 m n
  where go2 a b m n = go0 a b (go1 m n)
go0 a b xs =
  case xs of
[] - a+b
x:xs - go0 (a+x) (b*x) xs
go1 m n =
  case m  n of
True - []
False - m : go1 (m+1) n

-- considering go2
go2 a b m n = go0 a b (go1 m n)

== case (go1 m n) of
  [] - a+b
   x:xs - go0 (a+x) (b*x) xs

== case (case n  m of
   True - []
   False - m : go1 (m+1) n) of
  [] - a+b
  x:xs - go0 (a+x) (b*x) xs

== case n  m of
  True - case [] of
[] - a+b
x:xs - go0 (a+x) (b*x) xs

  False - case (m : go1 (m+1) n) of
 [] - a+b
 x:xs - go0 (a+x) (b*x) xs

== case n  m of
  True - a+b
  False - go0 (a+m) (b*m) (go1 (m+1) n)

-- So,
go2 a b m n =
  case n  m of
True - a+b
False - go0 (a+m) (b*m) (go1 (m+1) n)

-- And by the original def of go2
go2 a b m n = go0 a b (go1 m n)

-- We get
go2 a b m n =
  case m  n of
True - a+b
False - go2 (a+m) (b*m) (m+1) n

-- go0 and go1 and now dead in bar
bar m n = go2 0 1 m n
  where go2 a b m n =
  case n  m of
True - a+b
False - go2 (a+m) (b*m) (m+1) n

-- (furthermore, if (+) here is for Int/Double etc,
-- we can reduce go2 further to operate on machine
-- ints/doubles and be a register-only non-allocating loop)

-- So now finally returning to our original code:
 x = sum [1..10^6] + product [1..10^6]
 x' = let l = [1..10^6] in sum l + product l

-- We get:
x' = bar 1 (10^6)

Matt






On 12/4/09, Matt Morrow moonpa...@gmail.com wrote:
 Although, in Luke's example,

 x = sum [1..10^6] + product [1..10^6]
 x' = let l = [1..10^6] in sum l + product l

 We can do much much better, if we're sufficiently smart.

 -- Define:
 bar m n = foo (enumFromTo m n)
 foo xs  = sum xs + prod xs

 -- We're given:
 sum = foldl (+) 0
 product = foldl (*) 1
 foldl f z xs =
   case xs of
 [] - []
 x:xs - foldl f (f z x) xs
 enumFromTo m n =
   case m  n of
 True - []
 False - m : enumFromTo (m+1) n

 -- The fused loop becomes:
 foo xs = go0 0 1 xs
   where go0 a b xs =
   case xs of
 [] - a+b
 x:xs - go0 (a+x) (b*x) xs

 -- Now inline foo in bar:
 bar m n = go2 0 1 m n
   where go2 = go0 a b (go1 m n)
 go0 a b xs =
   case xs of
 [] - a+b
 x:xs - go0 (a+x) (b*x) xs
 go1 m n =
   case m  n of
 True - []
 False - m : go1 (m+1) n

 -- considering go2
 go2 = go0 a b (go1 m n)

 == case (go1 m n) of
   [] - a+b
x:xs - go0 (a+x) (b*x) xs

 == case (case m  n of
True - []
False - m : go1 (m+1) n) of
   [] - a+b
   x:xs - go0 (a+x) (b*x) xs

 == case m  n of
   True - case [] of
 [] - a+b
 x:xs - go0 (a+x) (b*x) xs

   False - case (m : go1 (m+1) n) of
  [] - a+b
  x:xs - go0 (a+x) (b*x) xs

 == case m  n of
   True - a+b
   False - go0 (a+m) (b*m) (go1 (m+1) n)

 -- So,
 go2 = case m  n of
 True - a+b
 False - go0 (a+m) (b*m) (go1 (m+1) n)

 -- And by the original def of go2
 go2 = go0 a b (go1 m n)

 -- We get
 go2 = case m  n of
 True - a+b
 False - go2 (a+m) (b*m) (m+1) n

 -- go0 and go1 and now dead in bar
 bar m n = go2 0 1 m n
   where go2 = case m  n of
 True - a+b
 False - go2 (a+m) (b*m) (m+1) n

 -- (furthermore, if (+) here is for Int/Double etc,
 -- we can reduce go2 further to operate on machine
 -- ints/doubles and be a register-only non-allocating loop)

 -- So now finally returning to our original code:
 x = sum [1..10^6] + product [1..10^6]
 x' = let l = [1..10^6] in sum l + product l

 -- We get:
 x' = bar 1 (10^6)

 And the intermediate list never exists at all.

 Matt




 On 12/4/09, Luke Palmer lrpal...@gmail.com wrote:
 On Fri, Dec 4, 2009 at 3:36 AM, Neil Brown nc...@kent.ac.uk wrote:
 But let's say you have:

 g x y = f x y * f x y

 Now the compiler (i.e. at compile-time) can do some magic.  It can spot
 the
 common expression and know the result of f x y must be the same both
 times,
 so it can convert to:

 g x y = let z = f x y in z * z

 GHC 

Re: [Haskell-cafe] GHC magic optimization ?

[wren ng thornton]

Luke Palmer wrote:

On Fri, Dec 4, 2009 at 9:44 AM, Mark Lentczner ma...@glyphic.com wrote:

On Dec 4, 2009, at 2:43 AM, Luke Palmer wrote:


So GHC leaves it to the user to specify sharing.  If you want an
expression shared, let bind it and reuse.

Does GHC treat where and let the same in this regard? Or in code, are these 
treated the same?


where is just sugar for let.


Well, they have different scoping properties because they're in 
different syntactic classes in the parser (let is an expression whereas 
where is a modifier on statements), but other than that yes they're the 
same.


--
Live well,
~wren
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Haskell-cafe] GHC magic optimization ?

[Emmanuel CHANTREAU]

Hello

One thing is magic for me: how GHC can know what function results to
remember and what results can be forgotten ?

Is it just a stupid buffer algorithm or is there some mathematics
truths behind this ?

I'm very happy about Haskell, it's so great to put some smart ideas in
a computer.

thanks

-- 
Emmanuel Chantréau
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Henning Thielemann]

On Thu, 3 Dec 2009, Emmanuel CHANTREAU wrote:


Hello

One thing is magic for me: how GHC can know what function results to
remember and what results can be forgotten ?

Is it just a stupid buffer algorithm or is there some mathematics
truths behind this ?


Although it is not required by the Haskell 98 report, the 'let' expression 
usually stores variable values (sharing) and top-level constants are also 
stored. I wonder how much of currently existing Haskell code would still 
work, if this would be changed, since this behavior is essential for 
memory usage and speed.

 If you want to cache function results, see:
  http://www.haskell.org/haskellwiki/Memoization
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Eugene Kirpichov]

Hi.

There is actually no magic at all going on. Haskell has a reasonably
well-defined evaluation model; you can approximate it, at least not
taking IO into account, with lazy graph reduction (look that up on
google). Probably that is the mathematical truth you're looking for.

Actually, if Haskell had any magic, it would be bad, because magic
can't be reliable (if you can't describe it, you can't rely on it) and
your magically-efficient program would suddenly and unexplainably
break at random changes in the source or in the compiler version.

I remember being slightly shocked when I discovered that even in
Prolog no magic is going on and it has a well-defined evaluation
model, too (before that, when I only heard of Prolog but hadn't read
anything serious about it, I thought that it is a bunch of unthinkable
theorem proving wizardry).


2009/12/3 Emmanuel CHANTREAU echant+hask...@maretmanu.org:
 Hello

 One thing is magic for me: how GHC can know what function results to
 remember and what results can be forgotten ?

 Is it just a stupid buffer algorithm or is there some mathematics
 truths behind this ?

 I'm very happy about Haskell, it's so great to put some smart ideas in
 a computer.

 thanks

 --
 Emmanuel Chantréau
 ___
 Haskell-Cafe mailing list
 Haskell-Cafe@haskell.org
 http://www.haskell.org/mailman/listinfo/haskell-cafe




-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Miguel Mitrofanov]

Does this really mean that you want to know how the garbage collector works?

Emmanuel CHANTREAU wrote:

Hello

One thing is magic for me: how GHC can know what function results to
remember and what results can be forgotten ?

Is it just a stupid buffer algorithm or is there some mathematics
truths behind this ?

I'm very happy about Haskell, it's so great to put some smart ideas in
a computer.

thanks


___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Emmanuel CHANTREAU]

Hello

First, thank you for all answers.


Le Thu, 03 Dec 2009 18:58:33 +0300,
Miguel Mitrofanov miguelim...@yandex.ru a écrit :

 Does this really mean that you want to know how the garbage collector
 works?

Well, I try to understand your question...

I will take an example:

f x y= x+y

The program ask the user to enter two numbers and print the sum. If the
user enter 1 2 f 1 2=3 is stored and a gargage collector is used to
remove this dandling expression later ?
If the user enter again 1 2, ghc search in dandling results to
try to find the result without computing it again ?

For Eugene:
I use magic to mean beautiful and difficult to understand. I believe
in magic: I believe everything can be understood with time.

-- 
Emmanuel Chantréau
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Evan Laforge]

 I will take an example:

 f x y= x+y

 The program ask the user to enter two numbers and print the sum. If the
 user enter 1 2 f 1 2=3 is stored and a gargage collector is used to
 remove this dandling expression later ?
 If the user enter again 1 2, ghc search in dandling results to
 try to find the result without computing it again ?

If you do 'let x = f 1 2' then 'x' will be computed once it's
demanded, and at that point the thunk will be overwritten with a
number.  Further references just return the number.  But when 'x' is
out of scope it gets GCed.  So it depends if you keep 'x' in scope,
just like strict languages.

The interesting thing is CAFs, which at the top level will never be
out of scope and hence live forever.  However, it's my vague
understanding that due to optimizations, a non-global looking CAF can
wind up at the top level.

For example, given these:

expensive arg = trace exp arg
f args key = Map.lookup key fm
  where
  fm = Map.fromList (expensive args)
main = let g = f [('a', 1), ('b', 2)] in print (g 'a', g 'c')

g args = (v, args)
where v = expensive 42
main = print (g 12, g 90)

'trace' implies that expensive is only called once in both cases, but
I have to pass -O2, otherwise it gets called twice.  That implies
inner definitions with no free variables are only promoted (I believe
it's called let floating?) with -O2.

I think the 'f' example is impressive.  The GHC optimizer is pretty neat!

http://www.haskell.org/haskellwiki/Constant_applicative_form
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] GHC magic optimization ?

[Miguel Mitrofanov]

I will take an example:

f x y= x+y

The program ask the user to enter two numbers and print the sum. If  
the
user enter 1 2 f 1 2=3 is stored and a gargage collector is used  
to

remove this dandling expression later ?


It's not stored in any way.


If the user enter again 1 2, ghc search in dandling results to
try to find the result without computing it again ?


No, it wouldn't. It would calculate it another time.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe