Limiting resources on a per-function basis?

[Jeff Newbern]

Alastair,

Thanks for your input.  I am mainly interested in this functionality to
enhance my unit tests.  I want to be able to run test cases with limits
on time, heap, stack, etc. and fail the test if it exceeds the limits.
I think for this application it is acceptable for limit to introduce
a strictness requirement on the output of the function-under-test.
I don't see any way around it, really.

I am not sure how to address the issue of shared results, though.
But since my main motivation is to enforce an upper-bound on resource
usage, it is not critical that I solve this issue unless I want to apply
tight bounds to an amortized algorithm.  It would be nice to be able to
do that, but it isn't my immediate concern.

Here is my proof-of-concept version of limit that implements a timeout:

> -- we use this as our dynamic exception type
> data TimeOut = TimeOut deriving Typeable;
>
> -- this function waits a specified number of microseconds before
> -- throwing a TimeOut exception to the specified thread
> timer :: Int -> ThreadId -> IO ()
> timer delay id = do threadDelay delay
>                     throwDynTo id TimeOut
> 		 
> -- convert a regular function into a function with a timeout,
> -- by forking a separate thread to wait the specified amount of time
> -- and then send a TimeOut exception back to the computing thread.
> -- if the computing thread has finished, it will kill the timer thread
> -- before it has a chance to raise the exception.
> limit :: (DeepSeq b) => Int -> (a -> b) -> (a -> IO (Maybe b))
> limit lim fn = (\x -> do id     <- myThreadId
>                          tid    <- forkIO $ timer lim id
>                          result <- return $!! (fn x)
>                          killThread tid
>                          return $ Just result
>                       `catchDyn` handleTimeout)
>   where handleTimeout :: TimeOut -> IO (Maybe b)
>         handleTimeout _ = return Nothing

I would like to find a cleaner way to do this, and one that imposes
fewer restrictions on the function-under-test.  Also, I think
implementing limits for heap and stack allocation will require a
different strategy, and will undoubtedly be more difficult.
I will have to become more familiar with the GHC RTS, I think...

Thanks again,
Jeff Newbern

On Sat, 2004-01-03 at 02:33, Alastair Reid wrote:
> > I would really like to be able to set resource limits on a per-function
> > basis.  I am envisioning something like:
> >
> > limit :: l -> (a -> b) -> (a -> Maybe b)
> > limit lim fn = ...
> >
> > which would convert a function so that it returns Nothing if a limit
> > (on stack, heap, time, etc.) is exceeded during evaluation of that
> > function.  Is there any hope of being able to do this within the
> > existing GHC libraries?
> 
> This is tricky in a lazy language for two reasons:
> 
> 1) Suppose the function returns '(42,37)', what do you want
>    the limit to be applied to?
> 
>    a) Computing the whole result.
>    b) Computing '(42,?)' (i.e., not evaluating the 2nd field)
>    c) Computing '(?,37)' (i.e., not evaluating the 1st field)
>    d) Computing '(?,?)' (i.e., not evaluating either field)
> 
> 2) Suppose the value being evaluated depends on a shared
>    result, should you include that cost in the result?
> 
>    For example, if you have:
> 
>      primes :: [Int]
>      primes = ... 
> 
>      getPrime :: Int -> Int
>      getPrime n = primes !! n
> 
>    should all calls to 'limit 10 getPrime 100' return the same
>    result even though the first call is vastly more expensive
>    than the subsequent calls.
> 
> There are also some semantic issues like retaining referential
>  transparency but the details depend a bit on the answers to the
>  above questions.
> 
> Some of the semantic issues can be addressed using non-deterministic 
> exceptions.  (For the most part, this involves putting 'limit' in the IO 
> monad.)
> 
> > If not, is it even possible to determine after-the-fact how much
> > stack or heap space a function evaluation required?
> 
> GHC's profiling tools can give information of this sort.
> I don't think there's a way to access this information at
> runtime but it should be possible to implement and might
> even be straightforward?
> 
> --
> Alastair Reid     www.haskell-consulting.com
-- 
Jeff Newbern <jnewbern at nomaware.com>
Nomaware, Inc.