Re: Limiting resources on a per-function basis?

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 Nomaware, Inc.