timing/timeout (how to express that in Haskell)
What is the idiomatic way to say in (ghc) Haskell: "run this computation for at most x seconds" (e. g. it returns Boolean; imagine a primality test) so I want something :: Int -> a -> Maybe a with the guarantee that the result is Just x with x in whnf, or Nothing. I guess one answer is "that's not Haskell because that's not a function". Sure, but I think I need it anyways, so I would accept some IO .. in the types. Best regards, -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- ---- http://www.imn.htwk-leipzig.de/~waldmann/ -------
waldmann:
What is the idiomatic way to say in (ghc) Haskell: "run this computation for at most x seconds" (e. g. it returns Boolean; imagine a primality test) so I want something :: Int -> a -> Maybe a with the guarantee that the result is Just x with x in whnf, or Nothing. I guess one answer is "that's not Haskell because that's not a function". Sure, but I think I need it anyways, so I would accept some IO .. in the types.
This comes up occasionally, at least one solution is: watchdogIO :: Int -- milliseconds -> IO a -- expensive computation -> IO a -- cheap computation -> IO a watchdogIO millis expensive cheap = do mvar <- newEmptyMVar tid1 <- forkIO $ do x <- expensive x `seq` putMVar mvar (Just x) tid2 <- forkIO $ do threadDelay (millis * 1000) putMVar mvar Nothing res <- takeMVar mvar case res of Just x -> do info ("EXPENSIVE was used") killThread tid2 `catch` (\e -> warn (show e)) return x Nothing -> do info ("WATCHDOG after " ++ show millis ++ " milliseconds") killThread tid1 `catch` (\e -> warn (show e)) cheap Note that this does more than you want, but you get the idea. forkIO + killThread && threadDelay If you code up a nice example, perhaps you coudl put it on the wiki, under Idioms? -- Don
Donald Bruce Stewart wrote:
forkIO + killThread && threadDelay
OK that's nice and solves my problem. Thanks! Is the delay measured on the wall clock or on the user (per-process) clock? -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- ---- http://www.imn.htwk-leipzig.de/~waldmann/ -------
Donald Bruce Stewart wrote:
watchdogIO :: Int -- milliseconds -> IO a -- expensive computation -> IO a -- cheap computation -> IO a
I'm not satisfied by the given function completely. Suppose the wrappers for pure computations watchdog1 :: Int -> a -> IO (Maybe a) watchdog1 millis x = watchdogIO millis (return (Just x)) (return Nothing) watchdog2 :: Int -> a -> IO (Maybe a) watchdog2 millis x = watchdogIO millis (x `seq` return (Just x)) (return Nothing) and the (expensive) function grundy :: Integer -> Integer grundy n = mex [ grundy k | k <- [0..pred n] ] where mex xs = head [ k | k <- [0..] , not (elem k xs) ] Now *NG> Util.IO.Within.watchdog1 1000 (grundy 15) >>= print EXPENSIVE was used Just 15 (0.26 secs, 12677644 bytes) *NG> Util.IO.Within.watchdog1 1000 (grundy 20) >>= print EXPENSIVE was used Just 20 (8.35 secs, 395376708 bytes) So watchdog1 is'nt the right choice. Let's use watchdog2: *NG> Util.IO.Within.watchdog2 1000 (grundy 15) >>= print EXPENSIVE was used Just 15 (0.27 secs, 13075340 bytes) *NG> Util.IO.Within.watchdog2 1000 (grundy 20) >>= print WATCHDOG after 1000 milliseconds Nothing (1.08 secs, 49634204 bytes) Looks better, but: *NG> Util.IO.Within.watchdog2 1000 (map grundy [0..20]) >>= print EXPENSIVE was used Just [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] (16.81 secs, 790627600 bytes) So what we really need is a deepSeq once more. Regards, Mirko -- -- Mirko Rahn -- Tel +49-721 608 7504 -- --- http://liinwww.ira.uka.de/~rahn/ ---
rahn:
Donald Bruce Stewart wrote:
watchdogIO :: Int -- milliseconds -> IO a -- expensive computation -> IO a -- cheap computation -> IO a
I'm not satisfied by the given function completely. Suppose the wrappers for pure computations
watchdog1 :: Int -> a -> IO (Maybe a) watchdog1 millis x = watchdogIO millis (return (Just x)) (return Nothing)
watchdog2 :: Int -> a -> IO (Maybe a) watchdog2 millis x = watchdogIO millis (x `seq` return (Just x)) (return Nothing)
and the (expensive) function
grundy :: Integer -> Integer grundy n = mex [ grundy k | k <- [0..pred n] ] where mex xs = head [ k | k <- [0..] , not (elem k xs) ]
Now
*NG> Util.IO.Within.watchdog1 1000 (grundy 15) >>= print EXPENSIVE was used Just 15 (0.26 secs, 12677644 bytes) *NG> Util.IO.Within.watchdog1 1000 (grundy 20) >>= print EXPENSIVE was used Just 20 (8.35 secs, 395376708 bytes)
So watchdog1 is'nt the right choice. Let's use watchdog2:
*NG> Util.IO.Within.watchdog2 1000 (grundy 15) >>= print EXPENSIVE was used Just 15 (0.27 secs, 13075340 bytes) *NG> Util.IO.Within.watchdog2 1000 (grundy 20) >>= print WATCHDOG after 1000 milliseconds Nothing (1.08 secs, 49634204 bytes)
Looks better, but:
*NG> Util.IO.Within.watchdog2 1000 (map grundy [0..20]) >>= print EXPENSIVE was used Just [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] (16.81 secs, 790627600 bytes)
So what we really need is a deepSeq once more.
Yes, I think this came up once. We should be using deepSeq there. Note that this could was produced in the heat of last year's ICFP contest, so probably can be excused if it isn't fully tested :) -- Don
Donald Bruce Stewart wrote:
rahn:
Donald Bruce Stewart wrote:
watchdogIO :: Int -- milliseconds -> IO a -- expensive computation -> IO a -- cheap computation -> IO a
I'm not satisfied by the given function completely. Suppose the wrappers for pure computations
watchdog1 :: Int -> a -> IO (Maybe a) watchdog1 millis x = watchdogIO millis (return (Just x)) (return Nothing)
watchdog2 :: Int -> a -> IO (Maybe a) watchdog2 millis x = watchdogIO millis (x `seq` return (Just x)) (return Nothing)
and the (expensive) function
grundy :: Integer -> Integer grundy n = mex [ grundy k | k <- [0..pred n] ] where mex xs = head [ k | k <- [0..] , not (elem k xs) ]
Now
*NG> Util.IO.Within.watchdog1 1000 (grundy 15) >>= print EXPENSIVE was used Just 15 (0.26 secs, 12677644 bytes) *NG> Util.IO.Within.watchdog1 1000 (grundy 20) >>= print EXPENSIVE was used Just 20 (8.35 secs, 395376708 bytes)
So watchdog1 is'nt the right choice. Let's use watchdog2:
*NG> Util.IO.Within.watchdog2 1000 (grundy 15) >>= print EXPENSIVE was used Just 15 (0.27 secs, 13075340 bytes) *NG> Util.IO.Within.watchdog2 1000 (grundy 20) >>= print WATCHDOG after 1000 milliseconds Nothing (1.08 secs, 49634204 bytes)
Looks better, but:
*NG> Util.IO.Within.watchdog2 1000 (map grundy [0..20]) >>= print EXPENSIVE was used Just [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] (16.81 secs, 790627600 bytes)
So what we really need is a deepSeq once more.
Yes, I think this came up once. We should be using deepSeq there.
Note that this could was produced in the heat of last year's ICFP contest, so probably can be excused if it isn't fully tested :)
-- Don
Personally, I'm often surprised by the laziness introduced by Maybe. For instance, when I use Maybe to make a partial function total the following happens. The partial function is only evaluated when its result is needed, so the result is `strict' and evaluated to whnf. Unfortunately, wrapping the result in a Maybe results in the Maybe being evaluated to whnf and the total function returns a (Just <closure that does the real work>). What I usually want is, either Nothing when there is no result, or (Just <the result in whnf>) with the work already done using the partial function. It's just annoying that turning a partial function into a total one looses so much strictness, since it prevents strictness propagation. Of course, this is easily solved using a `strict' Maybe: data Perhaps a = Just' !a | Nothing' Are other people experiencing the same thing, or is it just an academic issue and can Haskell compilers optimize it? By the way, does anyone know a better name for "perhaps"? It sounds even more lazy than "maybe" to me. regards, Arjen
Arjen van Weelden wrote:
Personally, I'm often surprised by the laziness introduced by Maybe.
Yes. That's why I chose the return type Boolean in my original post, and I included the remark on "Just x with x in whnf". Mirko used a list, where whnf is not enough. PS: I am still curious: does threadDelay use the wall clock or the per-process clock (CPU time)? And regardless of the answer - how could one obtain the opposite behaviour? (I don't find this discussed in the visible docs. Or am I missing something?) Best regards, -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- ---- http://www.imn.htwk-leipzig.de/~waldmann/ -------
PS: I am still curious: does threadDelay use the wall clock or the per-process clock (CPU time)? And regardless of the answer - how could one obtain the opposite behaviour? (I don't find this discussed in the visible docs. Or am I missing something?)
I think it uses wall clock time. Proof: *NG> System.Time.getClockTime >>= print >> GHC.Conc.threadDelay (10^7)
System.Time.getClockTime >>= print Fri May 12 14:36:55 CEST 2006 Fri May 12 14:37:05 CEST 2006 (0.01 secs, 803092 bytes)
Delayed 10 secs without using CPU. BTW: Using the proposed watchdogIO-function I can observe the following behavior: *NG> Util.IO.Within.withinIO 10 ( GHC.Conc.threadDelay 10000 >> print "expensive" ) ( print "cheap" ) "expensive" "cheap" *NG> Util.IO.Within.withinIO 10 ( GHC.Conc.threadDelay 10000 >> print "expensive" ) ( print "cheap" ) "expensive" "cheap" *NG> Util.IO.Within.withinIO 10 ( GHC.Conc.threadDelay 10000 >> print "expensive" ) ( print "cheap" ) "expensive" "cheap" Uhhh, something's wrong here, *both* functions are executed... -- -- Mirko Rahn -- Tel +49-721 608 7504 -- --- http://liinwww.ira.uka.de/~rahn/ ---
Hello Mirko, Friday, May 12, 2006, 4:42:02 PM, you wrote:
PS: I am still curious: does threadDelay use the wall clock or the per-process clock (CPU time)?
I think it uses wall clock time. Proof:
And regardless of the answer - how could one obtain the opposite behaviour? (I don't find this discussed in the visible docs. Or am I missing something?)
use threadDelay in cycle, testing CPU time each time. the following code used by me to measure both wall and CPU time. but i should say that cpu time measurement sometimes gives negative results :) i think it may be because it returns time for CURRENT OS thread, but Haskell runtime sometimes creates new OS thread and continue execute Haskell code in this new created thread (at least under Windows) benchmark h str times action = do prev <- getCPUTime prev2 <- getClockTime action current <- getCPUTime current2 <- getClockTime let secs = fromIntegral (current-prev) / 1e12 secs2 = diffTimes current2 prev2 putStrLn$ str ++ ": " ++ showTime secs2 ++ " (user: " ++ showTime secs ++ ")" showTime secs = showFFloat (Just 3) secs " secs" diffTimes (TOD sa pa) (TOD sb pb) = i(sa - sb) + (i(pa-pb) / 1e12) i x = fromIntegral x -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
It's just annoying that turning a partial function into a total one looses so much strictness, since it prevents strictness propagation. Of course, this is easily solved using a `strict' Maybe: data Perhaps a = Just' !a | Nothing'
Are other people experiencing the same thing, or is it just an academic issue and can Haskell compilers optimize it?
I am using StrictMaybe.Maybe'. I haven't tried to quantify the effect of the optimization pragmas... Wolfram ================================================================== %include polycode.fmt \section{Strict Maybe Variant} \begin{code} module Data.Rel.Utils.StrictMaybe where import Control.Monad \end{code} \begin{code} data Maybe' a = Nothing' | Just' {fromJust' :: {-# UNPACK #-} ! a} deriving (Eq, Ord, Show, Read) \end{code} \begin{code} maybe' r f Nothing' = r maybe' r f (Just' x) = f x \end{code} \begin{code} instance Functor Maybe' where fmap f Nothing' = Nothing' fmap f (Just' x) = Just' (f x) {-# INLINE fmap #-} \end{code} \begin{code} instance Monad Maybe' where return = Just' Nothing' >>= f = Nothing' (Just' x) >>= f = f x {-# INLINE (>>=) #-} fail = const Nothing' \end{code} \begin{code} instance MonadPlus Maybe' where mzero = Nothing' Nothing' `mplus` m = m m@(Just' x) `mplus` _ = m \end{code}
participants (6)
-
Arjen van Weelden -
Bulat Ziganshin -
dons＠cse.unsw.edu.au -
Johannes Waldmann -
kahl＠cas.mcmaster.ca -
Mirko Rahn