Joachim Breitner | 1 Aug 12:38 2012

Non-updateable thunks

Hello,

I’m still working on issues of performance vs. sharing; I must assume
some of the people here on the list must have seen my "dup"-paper¹ as
referees.

I’m now wondering about a approach where the compiler (either
automatically or by user annotation; I’ll leave that question for later)
would mark some thunks as reentrant, i.e. simply skip the blackholing
and update frame pushing. A quick test showed that this should work
quite well, take the usual example:

        import System.Environment
        main = do
            a <- getArgs
            let n = length a
            print n
            let l = [n..30000000]
            print $ last l + last l

This obviously leaks memory:

        $ ./Test +RTS -t
        0
        60000000
        <<ghc: 2400054760 bytes, 4596 GCs, 169560494/935354240 avg/max
        bytes residency (11 samples), 2121M in use, 0.00 INIT (0.00
        elapsed), 0.63 MUT (0.63 elapsed), 4.28 GC (4.29 elapsed) :ghc>>

I then modified the the assembly (a crude but effective way of testing
(Continue reading)

Simon Marlow | 3 Aug 10:28 2012
Picon

Re: Non-updateable thunks

On 01/08/2012 11:38, Joachim Breitner wrote:
> Hello,
>
> I’m still working on issues of performance vs. sharing; I must assume
> some of the people here on the list must have seen my "dup"-paper¹ as
> referees.
>
> I’m now wondering about a approach where the compiler (either
> automatically or by user annotation; I’ll leave that question for later)
> would mark some thunks as reentrant, i.e. simply skip the blackholing
> and update frame pushing. A quick test showed that this should work
> quite well, take the usual example:
>
>          import System.Environment
>          main = do
>              a <- getArgs
>              let n = length a
>              print n
>              let l = [n..30000000]
>              print $ last l + last l
>
> This obviously leaks memory:
>
>          $ ./Test +RTS -t
>          0
>          60000000
>          <<ghc: 2400054760 bytes, 4596 GCs, 169560494/935354240 avg/max
>          bytes residency (11 samples), 2121M in use, 0.00 INIT (0.00
>          elapsed), 0.63 MUT (0.63 elapsed), 4.28 GC (4.29 elapsed) :ghc>>
>
(Continue reading)

Joachim Breitner | 3 Aug 11:29 2012

Re: Non-updateable thunks

Hi Simon,

Am Freitag, den 03.08.2012, 09:28 +0100 schrieb Simon Marlow:
> > My question is: Has anybody worked in that direction? And are there any
> > fundamental problems with the current RTS implementation and such
> > closures?
> 
> Long ago GHC used to have an "update analyser" which would detect some 
> thunks that would never be re-entered and omit the update frame on them. 
>   I wrote a paper about this many years ago, and there were other people 
> working on similar ideas, some using types (e.g. linear types) - google 
> for "update avoidance".  As I understand it you want to omit doing some 
> updates in order to avoid space leaks, which is slightly different.

Thanks for the pointers, I will have a look. Why was the update analyser
removed from GHC?

> The StgSyn abstract syntax has an UpdateFlag on each StgRhs which lets 
> you turn off the update, and I believe the code generator will respect 
> it although it isn't actually ever turned off at the moment.

Indeed that works: I added a stg2stg transformation phase that removes
the flag on some thunks (with hard-coded names for now :-)) and the
generated code works as expected. I’m now thinking how I can allow the
programmer to annotate thunks  as non-updateable, and how to carry that
information to the stg phase.

Greetings,
Joachim

(Continue reading)

Simon Marlow | 8 Aug 13:09 2012
Picon

Re: Non-updateable thunks

On 03/08/2012 10:29, Joachim Breitner wrote:
> Hi Simon,
>
> Am Freitag, den 03.08.2012, 09:28 +0100 schrieb Simon Marlow:
>>> My question is: Has anybody worked in that direction? And are there any
>>> fundamental problems with the current RTS implementation and such
>>> closures?
>>
>> Long ago GHC used to have an "update analyser" which would detect some
>> thunks that would never be re-entered and omit the update frame on them.
>>    I wrote a paper about this many years ago, and there were other people
>> working on similar ideas, some using types (e.g. linear types) - google
>> for "update avoidance".  As I understand it you want to omit doing some
>> updates in order to avoid space leaks, which is slightly different.
>
> Thanks for the pointers, I will have a look. Why was the update analyser
> removed from GHC?

It was expensive and had very little benefit - most thunks that were 
deemed non-updatable by the analysis were also strict, so update 
analysis did very little in the presence of strictness analysis.

Cheers,
	Simon
Simon Peyton-Jones | 14 Aug 16:01 2012
Picon

RE: Non-updateable thunks

The update analysis developed by Keith Wansbrough was very complicated, and although rather beautiful
(read his thesis and our papers), it didn't pay its way in terms of complexity.

Coincidentally, Ilya Sergey is here on an internship and is now working on a "cheap and cheerful" update
analysis that may get much of the benefit for much less cost. We'll see.

Simon

| -----Original Message-----
| From: glasgow-haskell-users-bounces <at> haskell.org [mailto:glasgow-
| haskell-users-bounces <at> haskell.org] On Behalf Of Joachim Breitner
| Sent: 01 August 2012 11:38
| To: glasgow-haskell-users
| Subject: Non-updateable thunks
| 
| Hello,
| 
| I’m still working on issues of performance vs. sharing; I must assume
| some of the people here on the list must have seen my "dup"-paper¹ as
| referees.
| 
| I’m now wondering about a approach where the compiler (either
| automatically or by user annotation; I’ll leave that question for
| later) would mark some thunks as reentrant, i.e. simply skip the
| blackholing and update frame pushing. A quick test showed that this
| should work quite well, take the usual example:
| 
|         import System.Environment
|         main = do
|             a <- getArgs
(Continue reading)


Gmane