[GHC] #3630: Suggested algorithm to control upper bound of space "leaks"

[GHC]

#3630: Suggested algorithm to control upper bound of space "leaks"
---------------------------------+------------------------------------------
    Reporter:  shelbymoore3      |        Owner:                  
        Type:  proposal          |       Status:  new             
    Priority:  normal            |    Milestone:                  
   Component:  Compiler          |      Version:  6.10.4          
    Severity:  normal            |   Resolution:                  
    Keywords:                    |   Difficulty:  Unknown         
    Testcase:                    |           Os:  Unknown/Multiple
Architecture:  Unknown/Multiple  |  
---------------------------------+------------------------------------------
Comment (by shelbymoore3):

 Readers can continue clicking "next message" on the links I have provided
 to see all the discussion.  For example:

 http://www.haskell.org/pipermail/cvs-ghc/2009-November/050949.html

 In link above I offered the idea that the decision on which thunks to not
 update would probably be best determined not individually, but stochastic-
 ally on timer in groups by determining if the (space allocated per unit
 time / thunks updated per unit time) was excessive given the level of
 paging (fault) load last reported by the virtual memory manager, and if so
 then reverting those memo-izations.

 I understand that you said (at the mailing list), that we can not revert
 (discard the memo/normal form) without retaining the free variables, so I
 suggested at link above that we would retain these only temporarily in the
 GC nursery and make the decision on whether to revert, before these
 evaluated thunks are pushed out of the nursery.  There would be no need to
 retain the revert overhead until the paging fault load is approaching the
 level we need to start throttling space allocation rate.  We do not want
 to employ to binary (on/off) approach, but rather a rate reduction
 approach (so that gradually space intensive operations are not memo-ized,
 so that our annealing coverges, see http://www.haskell.org/pipermail
 /haskell-cafe/2009-November/068479.html).

 We are not trying to kill all space leaks (e.g. free variables), but
 rather gradually slow down the rate (velocity) of which we are creating
 additional space allocation as we gradually approach some intolerable
 measure of the paging fault load.  We know that paging fault load is
 orders-of-magnitude more costly performance-wise than CPU load.  With a
 high paging fault load, the program can be unusable.  So we do not need to
 worry about free variables retaining space allocation, as we are
 approaching this stochastically with global measure of the impact of
 additional space allocation (i.e. paging load).

 Hopefully the above achieves a trade-off in absolute speed, for tolerable
 speed in spite of what would have been crushing space leaks.  And
 hopefully there is no impact on absolute speed at all, until paging load
 has become a factor.

 Note even though I have also tried to suggest this area of work (and
 alternative approaches) for a master's thesis, I think perhaps the
 solution above is straight forward enough to proceed:

 http://www.haskell.org/pipermail/haskell-cafe/2009-November/068638.html

 Maybe I would be willing to experiment if I had a better understanding of
 the Haskell source code.  I suppose I could do that at some time in
 future, if no one jumps on this before then.  It might be a year or more
 from now.  I would prefer to see someone earn their masters on this,
 because I would get no compensation at all for working on this, and
 Haskell is not (yet) my area of specialization.  It is nice to leave some
 work for fresh students, since this seems to be in the theoretical realm
 (as much as in the practical realm).

 If a wiki is better, must I create one then post a link to it here?

 P.S. Simon apologies if I have overly impinged on your time or if I have
 made any gross error.  I am trying to help.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3630#comment:4>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler