Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
Hi, Am Mittwoch, den 29.08.2012, 17:16 +0100 schrieb Thomas Schilling: Syntactically, I'd prefer something that looks more like a function. With a pragma it's difficult to see what expression it actually affects. For example, we already have the special functions lazy and inline. Since avoiding updates essentially turns lazy evaluation into call-by-name you could call it cbn. Perhaps that suggests a different use case, though, so nonstrict, unshared, or nonlazy might be more self-explanatory. thanks for the feedback. I only made it a pragma because it seemed to be simpler at first, but now the branch also supports GHC.Prim.noupdate (better name to be found before it reaches any official GHC branch, if that ever happens). I'd also like to point out that avoiding updates can dramatically improve the kind of speedups my tracing JIT can achieve. In particular, on some benchmarks, it can optimise idiomatic Haskell code to the same level as stream fusion. I can simulate that by avoiding *all* updates (i.e., use call-by-name), but that would break some programs badly. (Technically, that's all legal, but I'm pretty sure it breaks any tying-the-knot tricks.) If you can make use of my code in Lambdachine I’d be very happy to help fixing bus and to hear about your results (but from a first glance it seems that you are not using that part of GHC in your project, right?). Greetings, Joachim -- Dipl.-Math. Dipl.-Inform. Joachim Breitner Wissenschaftlicher Mitarbeiter http://pp.info.uni-karlsruhe.de/~breitner signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
On 30 August 2012 09:34, Joachim Breitner breit...@kit.edu wrote: but from a first glance it seems that you are not using that part of GHC in your project, right? No, I don't think I can make use of your work directly. Lambdachine uses GHC up until the CorePrep phase (the last phase before conversion to STG, I think). I'll probably need a dynamic tagging mechanism to keep track of what's potentially shared. Not sure what the overhead of that will be. / Thomas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
Hi, Am Dienstag, den 28.08.2012, 18:16 -0400 schrieb Carter Schonwald: On Tuesday, August 28, 2012, Yves Parès wrote: Monad? Simple strictness anotation is enough in that case: upd_noupd n = let l = myenum' 0 n h = head l in h `seq` last l + h darn, I though I changed my examples before posting to: upd_noupd n = let l = myenum' 0 n in last l + length l (head was a bad example because actually due to strictness analysis and worker/wrapper transformation, GHC would yield good code even without `seq`). In this case (which is actually the benchmarked case), reordering or strictness annotations do not help. Greetings and sorry for the confusion, Joachim -- Dipl.-Math. Dipl.-Inform. Joachim Breitner Wissenschaftlicher Mitarbeiter http://pp.info.uni-karlsruhe.de/~breitner signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
Hi,
upd_noupd n =
let l = myenum' 0 n
in last l + length l
This could be rewritten as
upd_noupd n =
let l n = myenum' 0 n
in last (l n) + length (l n)
Or a special form of let could be introduced to define locally-scoped macros:
upd_noupd n =
let# l = myenum' 0 n
in last l + length l
What's the strength of the {-# NOUPDATE #-} approach?
Regards,
Facundo
Date: Wed, 29 Aug 2012 10:20:21 +0200
From: Joachim Breitner breit...@kit.edu
Subject: Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-}
pragma
To: haskell-cafe@haskell.org
Message-ID: 1346228421.4271.9.camel@kirk
Content-Type: text/plain; charset=iso-8859-15
Hi,
Am Dienstag, den 28.08.2012, 18:16 -0400 schrieb Carter Schonwald:
On Tuesday, August 28, 2012, Yves Par?s wrote:
Monad? Simple strictness anotation is enough in that case:
upd_noupd n =
let l = myenum' 0 n
h = head l
in h `seq` last l + h
darn, I though I changed my examples before posting to:
upd_noupd n =
let l = myenum' 0 n
in last l + length l
(head was a bad example because actually due to strictness analysis
and worker/wrapper transformation, GHC would yield good code even
without `seq`).
In this case (which is actually the benchmarked case), reordering or
strictness annotations do not help.
Greetings and sorry for the confusion,
Joachim
--
Dipl.-Math. Dipl.-Inform. Joachim Breitner
Wissenschaftlicher Mitarbeiter
http://pp.info.uni-karlsruhe.de/~breitner
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
Hi Facundo,
Am Mittwoch, den 29.08.2012, 10:26 -0300 schrieb Facundo Domínguez:
upd_noupd n =
let l = myenum' 0 n
in last l + length l
This could be rewritten as
upd_noupd n =
let l n = myenum' 0 n
in last (l n) + length (l n)
Or a special form of let could be introduced to define locally-scoped macros:
upd_noupd n =
let# l = myenum' 0 n
in last l + length l
What's the strength of the {-# NOUPDATE #-} approach?
it does not require refactoring of the code. There is not always a
parameter handy that you can use to prevent sharing, and using () for
that sometimes fails due to the full-lazyness-transformation.
And a locally-scoped macros would not help in this case:
test g n = g (myenum' 0 n)
Now you still might want to prevent the long list to be stored, but here
it cannot be done just by inlining or macro expansion.
Greetings,
Joachim
--
Dipl.-Math. Dipl.-Inform. Joachim Breitner
Wissenschaftlicher Mitarbeiter
http://pp.info.uni-karlsruhe.de/~breitner
signature.asc
Description: This is a digitally signed message part
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
And of course the biggest reason for this change, is we want GHC to continue
to become smarter. Remember, Haskell is a high level language. The
original promise, is that the code should be algebraically optimizable by
the compiler itself. Yes, of course many Haskell coders have learned to
deal with the places where Haskell is all to close to the metal. But we
hope that this will not always be the case. The interesting part, may not
be that you can add the pragma yourself, but that in the future, you won't
have to change anything at all.
Tim
-- Původní zpráva --
Od: Joachim Breitner breit...@kit.edu
Datum: 29. 8. 2012
Předmět: Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
Hi Facundo,
Am Mittwoch, den 29.08.2012, 10:26 -0300 schrieb Facundo Domínguez:
upd_noupd n =
let l = myenum' 0 n
in last l + length l
This could be rewritten as
upd_noupd n =
let l n = myenum' 0 n
in last (l n) + length (l n)
Or a special form of let could be introduced to define locally-scoped
macros:
upd_noupd n =
let# l = myenum' 0 n
in last l + length l
What's the strength of the {-# NOUPDATE #-} approach?
it does not require refactoring of the code. There is not always a
parameter handy that you can use to prevent sharing, and using () for
that sometimes fails due to the full-lazyness-transformation.
And a locally-scoped macros would not help in this case:
test g n = g (myenum' 0 n)
Now you still might want to prevent the long list to be stored, but here
it cannot be done just by inlining or macro expansion.
Greetings,
Joachim
--
Dipl.-Math. Dipl.-Inform. Joachim Breitner
Wissenschaftlicher Mitarbeiter
http://pp.info.uni-karlsruhe.de/~breitner
(http://pp.info.uni-karlsruhe.de/%7Ebreitner)___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
On 29 August 2012 15:21, Joachim Breitner breit...@kit.edu wrote:
Hi Facundo,
Am Mittwoch, den 29.08.2012, 10:26 -0300 schrieb Facundo Domínguez:
upd_noupd n =
let l = myenum' 0 n
in last l + length l
This could be rewritten as
upd_noupd n =
let l n = myenum' 0 n
in last (l n) + length (l n)
Or a special form of let could be introduced to define locally-scoped
macros:
upd_noupd n =
let# l = myenum' 0 n
in last l + length l
What's the strength of the {-# NOUPDATE #-} approach?
it does not require refactoring of the code. There is not always a
parameter handy that you can use to prevent sharing, and using () for
that sometimes fails due to the full-lazyness-transformation.
And a locally-scoped macros would not help in this case:
test g n = g (myenum' 0 n)
Now you still might want to prevent the long list to be stored, but here
it cannot be done just by inlining or macro expansion.
Syntactically, I'd prefer something that looks more like a function. With
a pragma it's difficult to see what expression it actually affects. For
example, we already have the special functions lazy and inline. Since
avoiding updates essentially turns lazy evaluation into call-by-name you
could call it cbn. Perhaps that suggests a different use case, though, so
nonstrict, unshared, or nonlazy might be more self-explanatory.
I'd also like to point out that avoiding updates can dramatically improve
the kind of speedups my tracing JIT can achieve. In particular, on some
benchmarks, it can optimise idiomatic Haskell code to the same level as
stream fusion. I can simulate that by avoiding *all* updates (i.e., use
call-by-name), but that would break some programs badly. (Technically,
that's all legal, but I'm pretty sure it breaks any tying-the-knot
tricks.)
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
Dear GHC users,
I am experimenting with ways to /prevent/ sharing in Haskell, e.g. to
avoid space leaks or to speed up evaluation. A first attempt was to
duplicate closures on the heap to preserve the original one, see
http://arxiv.org/abs/1207.2017 for a detailed description and
information on the prototype implementation; no GHC patching required
for that.
Currently I am trying a different angle: Simply avoid generating the
code that will update a closure after its evaluation; hence the closure
stays a thunk and will happily re-evaluate the next time it is used.
Here is a classical example. Take this function (it is basically [f..t]
but with a fixed type and no risk of existing rules firing):
myenum :: Int - Int - [Int]
myenum f t = if f = t
then f : myenum (f + 1) t
else []
and this example where sharing hurts performance badly:
upd_upd n =
let l = myenum 0 n
in last l + head l
The problem is that during the evaluation of last l, the list is live
and needs to be kept in memory, although in this case, re-evaluating l
for head l would be cheaper. If n is 5000, then this takes 3845ms
on my machine, measured with criterion, and a considerable amount of
memory (3000MB).
So here is what you can do now: You can mark the value as
non-updateable. We change myenum to
myenum' :: Int - Int - [Int]
myenum' f t = if f = t then f : ({-# NOUPDATE #-} myenum' (f + 1) t)
else []
and use that:
upd_noupd n =
let l = myenum' 0 n
in last l + head l
The improvement is considerable: 531ms and not much memory used (18MB)
Actually, it should suffice to put the pragma in the definition of l
without touching myenum:
noupd_noupd n =
let l = {-# NOUPDATE #-} myenum 0 n
in last l + head l
but this does not work with -O due to other optimizations in GHC. (It
does work without optimization.)
The next step would be to think of conditions under which the compiler
could automatically add the pragma, e.g. when it sees that evaluation a
thunk is very cheap but will increase memory consumption considerable.
Also this does not have to be a pragma; it could just as well be a
function noupdate :: a - a that is treated specially by the compiler,
similar to the inline function.
If you want to play around this, feel free to fetch it from the unshare
branch of my ghc repository at http://git.nomeata.de/?p=ghc.git or
https://github.com/nomeata/ghc for the GitHub-lovers. Note that the
branch is repeatedly rebased against ghc master.
Greetings,
Joachim
--
Dipl.-Math. Dipl.-Inform. Joachim Breitner
Wissenschaftlicher Mitarbeiter
http://pp.info.uni-karlsruhe.de/~breitner
signature.asc
Description: This is a digitally signed message part
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A first glimps on the {-# NOUPDATE #-} pragma
Hey Joachim,
isn't this an example where the exact same issue could be solved via some
suitable use of a monad for ordering those two computations on l?
cheers
-Carter
On Tue, Aug 28, 2012 at 12:44 PM, Joachim Breitner breit...@kit.edu wrote:
Dear GHC users,
I am experimenting with ways to /prevent/ sharing in Haskell, e.g. to
avoid space leaks or to speed up evaluation. A first attempt was to
duplicate closures on the heap to preserve the original one, see
http://arxiv.org/abs/1207.2017 for a detailed description and
information on the prototype implementation; no GHC patching required
for that.
Currently I am trying a different angle: Simply avoid generating the
code that will update a closure after its evaluation; hence the closure
stays a thunk and will happily re-evaluate the next time it is used.
Here is a classical example. Take this function (it is basically [f..t]
but with a fixed type and no risk of existing rules firing):
myenum :: Int - Int - [Int]
myenum f t = if f = t
then f : myenum (f + 1) t
else []
and this example where sharing hurts performance badly:
upd_upd n =
let l = myenum 0 n
in last l + head l
The problem is that during the evaluation of last l, the list is live
and needs to be kept in memory, although in this case, re-evaluating l
for head l would be cheaper. If n is 5000, then this takes 3845ms
on my machine, measured with criterion, and a considerable amount of
memory (3000MB).
So here is what you can do now: You can mark the value as
non-updateable. We change myenum to
myenum' :: Int - Int - [Int]
myenum' f t = if f = t then f : ({-# NOUPDATE #-} myenum' (f + 1)
t) else []
and use that:
upd_noupd n =
let l = myenum' 0 n
in last l + head l
The improvement is considerable: 531ms and not much memory used (18MB)
Actually, it should suffice to put the pragma in the definition of l
without touching myenum:
noupd_noupd n =
let l = {-# NOUPDATE #-} myenum 0 n
in last l + head l
but this does not work with -O due to other optimizations in GHC. (It
does work without optimization.)
The next step would be to think of conditions under which the compiler
could automatically add the pragma, e.g. when it sees that evaluation a
thunk is very cheap but will increase memory consumption considerable.
Also this does not have to be a pragma; it could just as well be a
function noupdate :: a - a that is treated specially by the compiler,
similar to the inline function.
If you want to play around this, feel free to fetch it from the unshare
branch of my ghc repository at http://git.nomeata.de/?p=ghc.git or
https://github.com/nomeata/ghc for the GitHub-lovers. Note that the
branch is repeatedly rebased against ghc master.
Greetings,
Joachim
--
Dipl.-Math. Dipl.-Inform. Joachim Breitner
Wissenschaftlicher Mitarbeiter
http://pp.info.uni-karlsruhe.de/~breitner
___
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] A first glimps on the {-# NOUPDATE #-} pragma
You got me there. Excellent point
On Tuesday, August 28, 2012, Yves Parès wrote:
Monad? Simple strictness anotation is enough in that case:
upd_noupd n =
let l = myenum' 0 n
h = head l
in h `seq` last l + h
Le mardi 28 août 2012 22:39:09 UTC+2, Carter Schonwald a écrit :
Hey Joachim,
isn't this an example where the exact same issue could be solved via some
suitable use of a monad for ordering those two computations on l?
cheers
-Carter
On Tue, Aug 28, 2012 at 12:44 PM, Joachim Breitner brei...@kit.eduwrote:
Dear GHC users,
I am experimenting with ways to /prevent/ sharing in Haskell, e.g. to
avoid space leaks or to speed up evaluation. A first attempt was to
duplicate closures on the heap to preserve the original one, see
http://arxiv.org/abs/1207.2017 for a detailed description and
information on the prototype implementation; no GHC patching required
for that.
Currently I am trying a different angle: Simply avoid generating the
code that will update a closure after its evaluation; hence the closure
stays a thunk and will happily re-evaluate the next time it is used.
Here is a classical example. Take this function (it is basically [f..t]
but with a fixed type and no risk of existing rules firing):
myenum :: Int - Int - [Int]
myenum f t = if f = t
then f : myenum (f + 1) t
else []
and this example where sharing hurts performance badly:
upd_upd n =
let l = myenum 0 n
in last l + head l
The problem is that during the evaluation of last l, the list is live
and needs to be kept in memory, although in this case, re-evaluating l
for head l would be cheaper. If n is 5000, then this takes 3845ms
on my machine, measured with criterion, and a considerable amount of
memory (3000MB).
So here is what you can do now: You can mark the value as
non-updateable. We change myenum to
myenum' :: Int - Int - [Int]
myenum' f t = if f = t then f : ({-# NOUPDATE #-} myenum' (f +
1) t) else []
and use that:
upd_noupd n =
let l = myenum' 0 n
in last l + head l
The improvement is considerable: 531ms and not much memory used (18MB)
Actually, it should suffice to put the pragma in the definition of l
without touching myenum:
noupd_noupd n =
let l = {-# NOUPDATE #-} myenum 0 n
in last l + head l
but this does not work with -O due to other optimizations in GHC. (It
does work without optimization.)
The next step would be to think of conditions under which the compiler
could automatically add the pragma, e.g. when it sees that evaluation a
thunk is very cheap but will increase memory consumption considerable.
Also this does not have to be a pragma; it could just as well be a
function noupdate :: a - a that is treated specially by the compiler,
similar to the inline function.
If you want to play around this, feel free to fetch it from the unshare
branch of my ghc repository at
http://git.nomeata.de/?p=ghc.**githttp://git.nomeata.de/?p=ghc.gitor
https://github.com/nomeata/ghc for the GitHub-lovers. Note that the
branch is repeatedly rebased against ghc master.
Greetings,
Joachim
--
Dipl.-Math. Dipl.-Inform. Joachim Breitner
Wissenschaftlicher Mitarbeiter
http://pp.info.uni-karlsruhe.**de/~breitnerhttp://pp.info.uni-karlsruhe.de/%7Ebreitner
__**_
Haskell-Cafe mailing list
haskel...@haskell.org
http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
