Limiting resources on a per-function basis?
jnewbern at nomaware.com
Sat Jan 3 04:37:50 EST 2004
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...
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
> > 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>
More information about the Haskell-Cafe