[Haskell-cafe] Something like optimistic evaluation

[Daniil Elovkov]

Brent Yorgey wrote:
> 
> On Mon, Apr 28, 2008 at 6:09 PM, Daniil Elovkov 
> <daniil.elovkov at googlemail.com <mailto:daniil.elovkov at googlemail.com>> 
> wrote:
> 
>     Hello
> 
>     Somewhat on the topic of optimistic evaluation, I've just thought of
>     another way to evaluate thunks.
> 
>     When the program is about to block on some IO, what if we start a
>     thread to evaluate (any) unevaluated thunks. We'll have additional
>     system thread, but the blocked one will not actually consume any
>     processor time.
> 
>     This would take place only when the program is compiled as threaded
>     and run with -N k, k>1.
> 
>     The RTS knows at least about some operations that will block, those
>     which IO operations are implemented with. for example. It could
>     merely start a process of evaluating any (or something more clever)
>     outstanding thunks right before going into one of those operations
>     and stop it when it's back.
> 
>     Of course, it's not like optimistic evaluation because we don't
>     avoid creating thunks. But in a sense it's similar. It could also be
>     compared with incremental garbage collection :)
> 
>     Has something like that been done, discussed?
> 
> 
> This sounds like it could be helpful in certain circumstances, but in 
> many cases it could probably lead to unpredictable (and uncontrollable!) 
> memory usage.  I could imagine a situation where my program is running 
> along just fine, and then one day it takes a long time to do a read from 
> the network due to latency or whatever, and suddenly memory usage shoots 
> through the roof, due to evaluation of some infinite (or even just very 
> large) data structure. 
> 

Yes, well, optimistic evaluation itself, as I understand, already 
exploits some mechanisms for avoiding that kind of thing. For example it 
stops evaluating a thunk if it starts to take too long. In case of OE we 
have to care about time (and memory). In this 'behind IO' case we only 
have to care about memory usage.

There can be some rules, like have an upper bound of amount of memory 
taken by new thunks. Also, of course it would make sense to do a sort of 
'breadth first' evaluation.

After all, the research has already been done on OE, its trade-offs, 
what happens with infinite data structures, etc. This would be just a 
relatively minor tweak. And, in terms of real execution time it would be 
simply free, it seems.