Timing out a pure evaluation of an expression I did not write myself

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

Timing out a pure evaluation of an expression I did not write myself

Ryan Reich
I want to time out a pure computation.  My experience, and that described in various previous questions here and elsewhere (the best of which is https://mail.haskell.org/pipermail/haskell-cafe/2011-February/088820.html), is that this doesn't always work: for instance,

>>> timeout 1 $ evaluate $ let x = 0 : x in last x

does not time out because, apparently, the fact that the expression evaluates in constant space (i.e. never allocates) means that it never yields to the timeout monitor thread that would kill it.

The solution that is described in the other iterations is to embed checkpoints in the expression that do allocate, giving the RTS a chance to switch contexts.  However, in my application, the expression is /arbitrary/ and I do not have the freedom to inject alterations into it.  (Don't argue this point, please.  The expression is arbitrary.)

How can I time out a tight loop like the above?  Clearly, it can be done, because I can, say, alt-tab over to another terminal and kill the process, which exploits the operating system's more aggressively pre-emptive scheduling.  Is there a solution using bound threads, say 'forkOS' instead of 'forkIO' in the implementation of 'timeout'?  Unix signals?  Some FFI-based workaround?  Etc.  Keep in mind that notwithstanding that comment, I don't actually want to kill the whole process, but just the one evaluation.

Thanks in advance,
Ryan Reich

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Daniel Díaz Casanueva
Hello Ryan.

Try evaluating the expression to normal form instead of weak head normal form in your expression. So:

>>> timeout 1 $ evaluate $ force $ let x = 0 : x in last x

The function `force` comes from the deepseq package. You can read the docs here: http://hackage.haskell.org/package/deepseq-1.4.4.0/docs/Control-DeepSeq.html

I hope that helps.

Best regards,
Daniel

Am So., 18. Nov. 2018 um 00:22 Uhr schrieb Ryan Reich <[hidden email]>:
I want to time out a pure computation.  My experience, and that described in various previous questions here and elsewhere (the best of which is https://mail.haskell.org/pipermail/haskell-cafe/2011-February/088820.html), is that this doesn't always work: for instance,

>>> timeout 1 $ evaluate $ let x = 0 : x in last x

does not time out because, apparently, the fact that the expression evaluates in constant space (i.e. never allocates) means that it never yields to the timeout monitor thread that would kill it.

The solution that is described in the other iterations is to embed checkpoints in the expression that do allocate, giving the RTS a chance to switch contexts.  However, in my application, the expression is /arbitrary/ and I do not have the freedom to inject alterations into it.  (Don't argue this point, please.  The expression is arbitrary.)

How can I time out a tight loop like the above?  Clearly, it can be done, because I can, say, alt-tab over to another terminal and kill the process, which exploits the operating system's more aggressively pre-emptive scheduling.  Is there a solution using bound threads, say 'forkOS' instead of 'forkIO' in the implementation of 'timeout'?  Unix signals?  Some FFI-based workaround?  Etc.  Keep in mind that notwithstanding that comment, I don't actually want to kill the whole process, but just the one evaluation.

Thanks in advance,
Ryan Reich
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Daniel Díaz Casanueva
Actually, after reading the question again, it seems like my response wasn't quite right. You are not actually building the list. In that case, I am as confused as you. :)

Sorry!

Am So., 18. Nov. 2018 um 01:51 Uhr schrieb Daniel Díaz Casanueva <[hidden email]>:
Hello Ryan.

Try evaluating the expression to normal form instead of weak head normal form in your expression. So:

>>> timeout 1 $ evaluate $ force $ let x = 0 : x in last x

The function `force` comes from the deepseq package. You can read the docs here: http://hackage.haskell.org/package/deepseq-1.4.4.0/docs/Control-DeepSeq.html

I hope that helps.

Best regards,
Daniel

Am So., 18. Nov. 2018 um 00:22 Uhr schrieb Ryan Reich <[hidden email]>:
I want to time out a pure computation.  My experience, and that described in various previous questions here and elsewhere (the best of which is https://mail.haskell.org/pipermail/haskell-cafe/2011-February/088820.html), is that this doesn't always work: for instance,

>>> timeout 1 $ evaluate $ let x = 0 : x in last x

does not time out because, apparently, the fact that the expression evaluates in constant space (i.e. never allocates) means that it never yields to the timeout monitor thread that would kill it.

The solution that is described in the other iterations is to embed checkpoints in the expression that do allocate, giving the RTS a chance to switch contexts.  However, in my application, the expression is /arbitrary/ and I do not have the freedom to inject alterations into it.  (Don't argue this point, please.  The expression is arbitrary.)

How can I time out a tight loop like the above?  Clearly, it can be done, because I can, say, alt-tab over to another terminal and kill the process, which exploits the operating system's more aggressively pre-emptive scheduling.  Is there a solution using bound threads, say 'forkOS' instead of 'forkIO' in the implementation of 'timeout'?  Unix signals?  Some FFI-based workaround?  Etc.  Keep in mind that notwithstanding that comment, I don't actually want to kill the whole process, but just the one evaluation.

Thanks in advance,
Ryan Reich
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Ryan Reich
I was just about to reply with an observation to that effect :)  The place that I'd want to put 'force' is actually inside the 'let' clause, which of course you can't do just by applying a function.  The expression as a whole is just an Integer.

On Sat, Nov 17, 2018 at 4:56 PM Daniel Díaz Casanueva <[hidden email]> wrote:
Actually, after reading the question again, it seems like my response wasn't quite right. You are not actually building the list. In that case, I am as confused as you. :)

Sorry!

Am So., 18. Nov. 2018 um 01:51 Uhr schrieb Daniel Díaz Casanueva <[hidden email]>:
Hello Ryan.

Try evaluating the expression to normal form instead of weak head normal form in your expression. So:

>>> timeout 1 $ evaluate $ force $ let x = 0 : x in last x

The function `force` comes from the deepseq package. You can read the docs here: http://hackage.haskell.org/package/deepseq-1.4.4.0/docs/Control-DeepSeq.html

I hope that helps.

Best regards,
Daniel

Am So., 18. Nov. 2018 um 00:22 Uhr schrieb Ryan Reich <[hidden email]>:
I want to time out a pure computation.  My experience, and that described in various previous questions here and elsewhere (the best of which is https://mail.haskell.org/pipermail/haskell-cafe/2011-February/088820.html), is that this doesn't always work: for instance,

>>> timeout 1 $ evaluate $ let x = 0 : x in last x

does not time out because, apparently, the fact that the expression evaluates in constant space (i.e. never allocates) means that it never yields to the timeout monitor thread that would kill it.

The solution that is described in the other iterations is to embed checkpoints in the expression that do allocate, giving the RTS a chance to switch contexts.  However, in my application, the expression is /arbitrary/ and I do not have the freedom to inject alterations into it.  (Don't argue this point, please.  The expression is arbitrary.)

How can I time out a tight loop like the above?  Clearly, it can be done, because I can, say, alt-tab over to another terminal and kill the process, which exploits the operating system's more aggressively pre-emptive scheduling.  Is there a solution using bound threads, say 'forkOS' instead of 'forkIO' in the implementation of 'timeout'?  Unix signals?  Some FFI-based workaround?  Etc.  Keep in mind that notwithstanding that comment, I don't actually want to kill the whole process, but just the one evaluation.

Thanks in advance,
Ryan Reich
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Arjen
In reply to this post by Ryan Reich
On Sat, 2018-11-17 at 15:21 -0800, Ryan Reich wrote:

> I want to time out a pure computation.  My experience, and that
> described in various previous questions here and elsewhere (the best
> of which is
> https://mail.haskell.org/pipermail/haskell-cafe/2011-February/088820.html
> ), is that this doesn't always work: for instance,
>
> >>> timeout 1 $ evaluate $ let x = 0 : x in last x
>
> does not time out because, apparently, the fact that the expression
> evaluates in constant space (i.e. never allocates) means that it
> never yields to the timeout monitor thread that would kill it.
>
> The solution that is described in the other iterations is to embed
> checkpoints in the expression that do allocate, giving the RTS a
> chance to switch contexts.  However, in my application, the
> expression is /arbitrary/ and I do not have the freedom to inject
> alterations into it.  (Don't argue this point, please.  The
> expression is arbitrary.)
>
> How can I time out a tight loop like the above?  Clearly, it can be
> done, because I can, say, alt-tab over to another terminal and kill
> the process, which exploits the operating system's more aggressively
> pre-emptive scheduling.  Is there a solution using bound threads, say
> 'forkOS' instead of 'forkIO' in the implementation of 'timeout'?
> Unix signals?  Some FFI-based workaround?  Etc.  Keep in mind that
> notwithstanding that comment, I don't actually want to kill the whole
> process, but just the one evaluation.
>
> Thanks in advance,
> Ryan Reich
>
If you are using GHC, the -fno-omit-yields compiler option might be of
help, which does not optimize out the allocation check that is also
used for interrupting threads.

See also:
https://stackoverflow.com/questions/34317730/haskell-timeout-diverging-computation

Are you using the threaded runtime (GHC option -threaded)?

hope this helps, Arjen

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Ryan Reich
In reply to this post by Ryan Reich
I suppose my question concerns the more general question of how to create OS-managed threads in GHC.  As I understand it, GHC's concurrency model only exposes its RTS-managed internal threads, which are distributed somehow to OS threads by the scheduler, and this is the source of my timeout problem, because the scheduler never runs.  Contrast this with plain Linux C, where we can do something with pthread_create to call a function in an OS-managed thread directly.  I would have expected there to be a corresponding operation in GHC Haskell ("bound threads" seem not to be it, as they are still scheduled by the RTS) but it does not appear that there is.  Is this because of the need to keep the runtime unified?  Because it seems strange that we are prevented from operating truly independent threads.

Ryan

On Sat, Nov 17, 2018 at 3:21 PM Ryan Reich <[hidden email]> wrote:
I want to time out a pure computation.  My experience, and that described in various previous questions here and elsewhere (the best of which is https://mail.haskell.org/pipermail/haskell-cafe/2011-February/088820.html), is that this doesn't always work: for instance,

>>> timeout 1 $ evaluate $ let x = 0 : x in last x

does not time out because, apparently, the fact that the expression evaluates in constant space (i.e. never allocates) means that it never yields to the timeout monitor thread that would kill it.

The solution that is described in the other iterations is to embed checkpoints in the expression that do allocate, giving the RTS a chance to switch contexts.  However, in my application, the expression is /arbitrary/ and I do not have the freedom to inject alterations into it.  (Don't argue this point, please.  The expression is arbitrary.)

How can I time out a tight loop like the above?  Clearly, it can be done, because I can, say, alt-tab over to another terminal and kill the process, which exploits the operating system's more aggressively pre-emptive scheduling.  Is there a solution using bound threads, say 'forkOS' instead of 'forkIO' in the implementation of 'timeout'?  Unix signals?  Some FFI-based workaround?  Etc.  Keep in mind that notwithstanding that comment, I don't actually want to kill the whole process, but just the one evaluation.

Thanks in advance,
Ryan Reich

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Viktor Dukhovni
On Mon, Nov 19, 2018 at 11:26:17AM -0800, Ryan Reich wrote:

> I suppose my question concerns the more general question of how to create
> OS-managed threads in GHC.  [...]
> I would have expected there to
> be a corresponding operation in GHC Haskell ("bound threads" seem not to be
> it, as they are still scheduled by the RTS) but it does not appear that
> there is.  Is this because of the need to keep the runtime unified?
> Because it seems strange that we are prevented from operating truly
> independent threads.

I was just reading:

    https://cs.nyu.edu/~mwalfish/classes/14fa/ref/boehm05threads.pdf

which may offer some insight.  The runtime needs to be able to
provide a consistent memory model to threads.  Just running something
in an OS thread that's managed by the RTS could make that difficult,
and it is not clear how that cooperates with garbage collection.

But to your point, when adding threads to your example, I find that
the infinite loop then runs concurrently in all the threads, and
the timeout never happens.  While:

    Replacing:   let x = 0:x in last x
    with:        let ! x = 0 + x in x

does make timeout work, so it is not entirely obvious which pure
computations can be timed out.

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Carter Schonwald
so one way to handle no allocation things playing nicely with the scheduler is to compile haskell code with -fno-omit-yields

this will generate code which has scheduler yields even in loops which dont allocate

cheers!
-Carter

On Mon, Nov 19, 2018 at 3:27 PM Viktor Dukhovni <[hidden email]> wrote:
On Mon, Nov 19, 2018 at 11:26:17AM -0800, Ryan Reich wrote:

> I suppose my question concerns the more general question of how to create
> OS-managed threads in GHC.  [...]
> I would have expected there to
> be a corresponding operation in GHC Haskell ("bound threads" seem not to be
> it, as they are still scheduled by the RTS) but it does not appear that
> there is.  Is this because of the need to keep the runtime unified?
> Because it seems strange that we are prevented from operating truly
> independent threads.

I was just reading:

    https://cs.nyu.edu/~mwalfish/classes/14fa/ref/boehm05threads.pdf

which may offer some insight.  The runtime needs to be able to
provide a consistent memory model to threads.  Just running something
in an OS thread that's managed by the RTS could make that difficult,
and it is not clear how that cooperates with garbage collection.

But to your point, when adding threads to your example, I find that
the infinite loop then runs concurrently in all the threads, and
the timeout never happens.  While:

    Replacing:   let x = 0:x in last x
    with:        let ! x = 0 + x in x

does make timeout work, so it is not entirely obvious which pure
computations can be timed out.

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Ryan Reich
Thanks for the suggestion, which Arjen made also.  Unfortunately, it does not appear to help.  See this simple program:

-- Loop.hs
import Control.Exception
import System.Timeout

main :: IO (Maybe Integer)
main = timeout 100000 $ evaluate $ last $ repeat 0
-- end

With either GHC invocation "stack exec ghc Loop[ -- -fno-omit-yields]", running ./Loop fails to terminate (it should do so in 0.1s).

Based only on the very terse description of that flag in the User's Guide, and its name, I think the problem is simply that GHC doesn't normally generate yields in that loop, so there's nothing not to omit.


On Mon, Nov 26, 2018 at 4:14 PM Carter Schonwald <[hidden email]> wrote:
so one way to handle no allocation things playing nicely with the scheduler is to compile haskell code with -fno-omit-yields

this will generate code which has scheduler yields even in loops which dont allocate

cheers!
-Carter

On Mon, Nov 19, 2018 at 3:27 PM Viktor Dukhovni <[hidden email]> wrote:
On Mon, Nov 19, 2018 at 11:26:17AM -0800, Ryan Reich wrote:

> I suppose my question concerns the more general question of how to create
> OS-managed threads in GHC.  [...]
> I would have expected there to
> be a corresponding operation in GHC Haskell ("bound threads" seem not to be
> it, as they are still scheduled by the RTS) but it does not appear that
> there is.  Is this because of the need to keep the runtime unified?
> Because it seems strange that we are prevented from operating truly
> independent threads.

I was just reading:

    https://cs.nyu.edu/~mwalfish/classes/14fa/ref/boehm05threads.pdf

which may offer some insight.  The runtime needs to be able to
provide a consistent memory model to threads.  Just running something
in an OS thread that's managed by the RTS could make that difficult,
and it is not clear how that cooperates with garbage collection.

But to your point, when adding threads to your example, I find that
the infinite loop then runs concurrently in all the threads, and
the timeout never happens.  While:

    Replacing:   let x = 0:x in last x
    with:        let ! x = 0 + x in x

does make timeout work, so it is not entirely obvious which pure
computations can be timed out.

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Viktor Dukhovni
On Wed, Nov 28, 2018 at 09:39:01AM -0800, Ryan Reich wrote:

> Thanks for the suggestion, which Arjen made also.  Unfortunately, it does
> not appear to help.  See this simple program:
>
> -- Loop.hs
> import Control.Exception
> import System.Timeout
>
> main :: IO (Maybe Integer)
> main = timeout 100000 $ evaluate $ last $ repeat 0
> -- end
>
> With either GHC invocation "stack exec ghc Loop[ -- -fno-omit-yields]",
> running ./Loop fails to terminate (it should do so in 0.1s).
>
> Based only on the very terse description of that flag in the User's Guide,
> and its name, I think the problem is simply that GHC doesn't normally
> *generate* yields in that loop, so there's nothing not to omit.

It times out for me with GHC 8.4.4 on FreeBSD 11.2, and "ghc -O -fno-omit-yields"
and does  not time out with "ghc -O":

    $ cat /tmp/foo.hs
    import Control.Exception
    import System.Timeout

    main :: IO (Maybe Integer)
    main = timeout 1000000 $ evaluate $ last $ repeat 0

    $ ghc -O -fno-omit-yields /tmp/foo.hs
    [1 of 1] Compiling Main             ( /tmp/foo.hs, /tmp/foo.o ) [Optimisation flags changed]
    Linking /tmp/foo ...

    $ time /tmp/foo

    real    0m1.033s
    user    0m1.025s
    sys     0m0.008s

    $ rm /tmp/foo
    $ ghc -O /tmp/foo.hs
    [1 of 1] Compiling Main             ( /tmp/foo.hs, /tmp/foo.o ) [Optimisation flags changed]
    Linking /tmp/foo ...

    $ time /tmp/foo
    ^C^C

    real    0m5.864s
    user    0m5.857s
    sys     0m0.000s

On MacOS X with GHC 7.10.3, it does not time out either way.  Perhaps
some versions of GHC don't make the timeout possible.

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Ryan Reich
I expected something like that. I'm all the way back in ghc-8.2.2, but I think what this really shows is that the flag is unreliable and version-dependent. Unfortunately there doesn't seem to be a precise specification of where yield points should appear, and therefore, where they might be not-omitted.

On Wed, Nov 28, 2018, 17:10 Viktor Dukhovni <[hidden email] wrote:
On Wed, Nov 28, 2018 at 09:39:01AM -0800, Ryan Reich wrote:

> Thanks for the suggestion, which Arjen made also.  Unfortunately, it does
> not appear to help.  See this simple program:
>
> -- Loop.hs
> import Control.Exception
> import System.Timeout
>
> main :: IO (Maybe Integer)
> main = timeout 100000 $ evaluate $ last $ repeat 0
> -- end
>
> With either GHC invocation "stack exec ghc Loop[ -- -fno-omit-yields]",
> running ./Loop fails to terminate (it should do so in 0.1s).
>
> Based only on the very terse description of that flag in the User's Guide,
> and its name, I think the problem is simply that GHC doesn't normally
> *generate* yields in that loop, so there's nothing not to omit.

It times out for me with GHC 8.4.4 on FreeBSD 11.2, and "ghc -O -fno-omit-yields"
and does  not time out with "ghc -O":

    $ cat /tmp/foo.hs
    import Control.Exception
    import System.Timeout

    main :: IO (Maybe Integer)
    main = timeout 1000000 $ evaluate $ last $ repeat 0

    $ ghc -O -fno-omit-yields /tmp/foo.hs
    [1 of 1] Compiling Main             ( /tmp/foo.hs, /tmp/foo.o ) [Optimisation flags changed]
    Linking /tmp/foo ...

    $ time /tmp/foo

    real    0m1.033s
    user    0m1.025s
    sys     0m0.008s

    $ rm /tmp/foo
    $ ghc -O /tmp/foo.hs
    [1 of 1] Compiling Main             ( /tmp/foo.hs, /tmp/foo.o ) [Optimisation flags changed]
    Linking /tmp/foo ...

    $ time /tmp/foo
    ^C^C

    real    0m5.864s
    user    0m5.857s
    sys     0m0.000s

On MacOS X with GHC 7.10.3, it does not time out either way.  Perhaps
some versions of GHC don't make the timeout possible.

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Erik Hesselink
Hi Ryan,

I'm not quite sure of your use case, but lambdabot/mueval do something like this I think. From a brief look at the source [1] it seems they compute in a separate thread, then in another thread, wait until the timeout then kill the computation thread. Would something like that work for you?

Erik


On Thu, 29 Nov 2018 at 03:41, Ryan Reich <[hidden email]> wrote:
I expected something like that. I'm all the way back in ghc-8.2.2, but I think what this really shows is that the flag is unreliable and version-dependent. Unfortunately there doesn't seem to be a precise specification of where yield points should appear, and therefore, where they might be not-omitted.

On Wed, Nov 28, 2018, 17:10 Viktor Dukhovni <[hidden email] wrote:
On Wed, Nov 28, 2018 at 09:39:01AM -0800, Ryan Reich wrote:

> Thanks for the suggestion, which Arjen made also.  Unfortunately, it does
> not appear to help.  See this simple program:
>
> -- Loop.hs
> import Control.Exception
> import System.Timeout
>
> main :: IO (Maybe Integer)
> main = timeout 100000 $ evaluate $ last $ repeat 0
> -- end
>
> With either GHC invocation "stack exec ghc Loop[ -- -fno-omit-yields]",
> running ./Loop fails to terminate (it should do so in 0.1s).
>
> Based only on the very terse description of that flag in the User's Guide,
> and its name, I think the problem is simply that GHC doesn't normally
> *generate* yields in that loop, so there's nothing not to omit.

It times out for me with GHC 8.4.4 on FreeBSD 11.2, and "ghc -O -fno-omit-yields"
and does  not time out with "ghc -O":

    $ cat /tmp/foo.hs
    import Control.Exception
    import System.Timeout

    main :: IO (Maybe Integer)
    main = timeout 1000000 $ evaluate $ last $ repeat 0

    $ ghc -O -fno-omit-yields /tmp/foo.hs
    [1 of 1] Compiling Main             ( /tmp/foo.hs, /tmp/foo.o ) [Optimisation flags changed]
    Linking /tmp/foo ...

    $ time /tmp/foo

    real    0m1.033s
    user    0m1.025s
    sys     0m0.008s

    $ rm /tmp/foo
    $ ghc -O /tmp/foo.hs
    [1 of 1] Compiling Main             ( /tmp/foo.hs, /tmp/foo.o ) [Optimisation flags changed]
    Linking /tmp/foo ...

    $ time /tmp/foo
    ^C^C

    real    0m5.864s
    user    0m5.857s
    sys     0m0.000s

On MacOS X with GHC 7.10.3, it does not time out either way.  Perhaps
some versions of GHC don't make the timeout possible.

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Carter Schonwald
Yeah that’s probably a better approach. 

On Thu, Nov 29, 2018 at 5:16 AM Erik Hesselink <[hidden email]> wrote:
Hi Ryan,

I'm not quite sure of your use case, but lambdabot/mueval do something like this I think. From a brief look at the source [1] it seems they compute in a separate thread, then in another thread, wait until the timeout then kill the computation thread. Would something like that work for you?

Erik


On Thu, 29 Nov 2018 at 03:41, Ryan Reich <[hidden email]> wrote:
I expected something like that. I'm all the way back in ghc-8.2.2, but I think what this really shows is that the flag is unreliable and version-dependent. Unfortunately there doesn't seem to be a precise specification of where yield points should appear, and therefore, where they might be not-omitted.

On Wed, Nov 28, 2018, 17:10 Viktor Dukhovni <[hidden email] wrote:
On Wed, Nov 28, 2018 at 09:39:01AM -0800, Ryan Reich wrote:

> Thanks for the suggestion, which Arjen made also.  Unfortunately, it does
> not appear to help.  See this simple program:
>
> -- Loop.hs
> import Control.Exception
> import System.Timeout
>
> main :: IO (Maybe Integer)
> main = timeout 100000 $ evaluate $ last $ repeat 0
> -- end
>
> With either GHC invocation "stack exec ghc Loop[ -- -fno-omit-yields]",
> running ./Loop fails to terminate (it should do so in 0.1s).
>
> Based only on the very terse description of that flag in the User's Guide,
> and its name, I think the problem is simply that GHC doesn't normally
> *generate* yields in that loop, so there's nothing not to omit.

It times out for me with GHC 8.4.4 on FreeBSD 11.2, and "ghc -O -fno-omit-yields"
and does  not time out with "ghc -O":

    $ cat /tmp/foo.hs
    import Control.Exception
    import System.Timeout

    main :: IO (Maybe Integer)
    main = timeout 1000000 $ evaluate $ last $ repeat 0

    $ ghc -O -fno-omit-yields /tmp/foo.hs
    [1 of 1] Compiling Main             ( /tmp/foo.hs, /tmp/foo.o ) [Optimisation flags changed]
    Linking /tmp/foo ...

    $ time /tmp/foo

    real    0m1.033s
    user    0m1.025s
    sys     0m0.008s

    $ rm /tmp/foo
    $ ghc -O /tmp/foo.hs
    [1 of 1] Compiling Main             ( /tmp/foo.hs, /tmp/foo.o ) [Optimisation flags changed]
    Linking /tmp/foo ...

    $ time /tmp/foo
    ^C^C

    real    0m5.864s
    user    0m5.857s
    sys     0m0.000s

On MacOS X with GHC 7.10.3, it does not time out either way.  Perhaps
some versions of GHC don't make the timeout possible.

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Ian Denhardt
In reply to this post by Erik Hesselink
That should have the same problem; the exceptions can't be delivered
until the target thread reaches a yield. 'timeout' uses the same
underlying mechanism.

Obvious worrisome question: is it possible to use this to DoS
lambdabot/mueval?

Quoting Erik Hesselink (2018-11-29 05:15:49)

>    Hi Ryan,
>    I'm not quite sure of your use case, but lambdabot/mueval do something
>    like this I think. From a brief look at the source [1] it seems they
>    compute in a separate thread, then in another thread, wait until the
>    timeout then kill the computation thread. Would something like that
>    work for you?
>    Erik
>    [1]
>    [1]https://github.com/gwern/mueval/blob/09b6a7aa5a25c4115442ea2e6ae0c2d
>    b557007f8/Mueval/Parallel.hs
>
>    On Thu, 29 Nov 2018 at 03:41, Ryan Reich <[2][hidden email]>
>    wrote:
>
>    I expected something like that. I'm all the way back in ghc-8.2.2, but
>    I think what this really shows is that the flag is unreliable and
>    version-dependent. Unfortunately there doesn't seem to be a precise
>    specification of where yield points should appear, and therefore, where
>    they might be not-omitted.
>
>    On Wed, Nov 28, 2018, 17:10 Viktor Dukhovni <[3][hidden email]
>    wrote:
>
>      On Wed, Nov 28, 2018 at 09:39:01AM -0800, Ryan Reich wrote:
>      > Thanks for the suggestion, which Arjen made also.�  Unfortunately,
>      it does
>      > not appear to help.�  See this simple program:
>      >
>      > -- Loop.hs
>      > import Control.Exception
>      > import System.Timeout
>      >
>      > main :: IO (Maybe Integer)
>      > main = timeout 100000 $ evaluate $ last $ repeat 0
>      > -- end
>      >
>      > With either GHC invocation "stack exec ghc Loop[ --
>      -fno-omit-yields]",
>      > running ./Loop fails to terminate (it should do so in 0.1s).
>      >
>      > Based only on the very terse description of that flag in the
>      User's Guide,
>      > and its name, I think the problem is simply that GHC doesn't
>      normally
>      > *generate* yields in that loop, so there's nothing not to omit.
>      It times out for me with GHC 8.4.4 on FreeBSD 11.2, and "ghc -O
>      -fno-omit-yields"
>      and does�  not time out with "ghc -O":
>      �  �  $ cat /tmp/foo.hs
>      �  �  import Control.Exception
>      �  �  import System.Timeout
>      �  �  main :: IO (Maybe Integer)
>      �  �  main = timeout 1000000 $ evaluate $ last $ repeat 0
>      �  �  $ ghc -O -fno-omit-yields /tmp/foo.hs
>      �  �  [1 of 1] Compiling Main�  �  �  �  �  �  � ( /tmp/foo.hs,
>      /tmp/foo.o ) [Optimisation flags changed]
>      �  �  Linking /tmp/foo ...
>      �  �  $ time /tmp/foo
>      �  �  real�  �  0m1.033s
>      �  �  user�  �  0m1.025s
>      �  �  sys�  �  � 0m0.008s
>      �  �  $ rm /tmp/foo
>      �  �  $ ghc -O /tmp/foo.hs
>      �  �  [1 of 1] Compiling Main�  �  �  �  �  �  � ( /tmp/foo.hs,
>      /tmp/foo.o ) [Optimisation flags changed]
>      �  �  Linking /tmp/foo ...
>      �  �  $ time /tmp/foo
>      �  �  ^C^C
>      �  �  real�  �  0m5.864s
>      �  �  user�  �  0m5.857s
>      �  �  sys�  �  � 0m0.000s
>      On MacOS X with GHC 7.10.3, it does not time out either way.�
>      Perhaps
>      some versions of GHC don't make the timeout possible.
>      --
>      �  �  �  �  Viktor.
>      _______________________________________________
>      Haskell-Cafe mailing list
>      To (un)subscribe, modify options or view archives go to:
>      [4]http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>      Only members subscribed via the mailman list are allowed to post.
>
>      _______________________________________________
>      Haskell-Cafe mailing list
>      To (un)subscribe, modify options or view archives go to:
>      [5]http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>      Only members subscribed via the mailman list are allowed to post.
>
> Verweise
>
>    1. https://github.com/gwern/mueval/blob/09b6a7aa5a25c4115442ea2e6ae0c2db557007f8/Mueval/Parallel.hs
>    2. mailto:[hidden email]
>    3. mailto:[hidden email]
>    4. http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>    5. http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Ryan Reich
In reply to this post by Erik Hesselink
I did actually construct a workaround where I compute in a separate (forked, via System.Posix) process to time it out, then recomputed in the main process to get the value. It's got a significant overhead but I'm not sure yet if that is a real issue.

Using just a separate rts thread is how the standard timeout works; if you mean that those guys use a separate OS thread that gets scheduled outside the rts, that would be perfect. I'm just faking that with the fork.

On Thu, Nov 29, 2018, 02:16 Erik Hesselink <[hidden email] wrote:
Hi Ryan,

I'm not quite sure of your use case, but lambdabot/mueval do something like this I think. From a brief look at the source [1] it seems they compute in a separate thread, then in another thread, wait until the timeout then kill the computation thread. Would something like that work for you?

Erik


On Thu, 29 Nov 2018 at 03:41, Ryan Reich <[hidden email]> wrote:
I expected something like that. I'm all the way back in ghc-8.2.2, but I think what this really shows is that the flag is unreliable and version-dependent. Unfortunately there doesn't seem to be a precise specification of where yield points should appear, and therefore, where they might be not-omitted.

On Wed, Nov 28, 2018, 17:10 Viktor Dukhovni <[hidden email] wrote:
On Wed, Nov 28, 2018 at 09:39:01AM -0800, Ryan Reich wrote:

> Thanks for the suggestion, which Arjen made also.  Unfortunately, it does
> not appear to help.  See this simple program:
>
> -- Loop.hs
> import Control.Exception
> import System.Timeout
>
> main :: IO (Maybe Integer)
> main = timeout 100000 $ evaluate $ last $ repeat 0
> -- end
>
> With either GHC invocation "stack exec ghc Loop[ -- -fno-omit-yields]",
> running ./Loop fails to terminate (it should do so in 0.1s).
>
> Based only on the very terse description of that flag in the User's Guide,
> and its name, I think the problem is simply that GHC doesn't normally
> *generate* yields in that loop, so there's nothing not to omit.

It times out for me with GHC 8.4.4 on FreeBSD 11.2, and "ghc -O -fno-omit-yields"
and does  not time out with "ghc -O":

    $ cat /tmp/foo.hs
    import Control.Exception
    import System.Timeout

    main :: IO (Maybe Integer)
    main = timeout 1000000 $ evaluate $ last $ repeat 0

    $ ghc -O -fno-omit-yields /tmp/foo.hs
    [1 of 1] Compiling Main             ( /tmp/foo.hs, /tmp/foo.o ) [Optimisation flags changed]
    Linking /tmp/foo ...

    $ time /tmp/foo

    real    0m1.033s
    user    0m1.025s
    sys     0m0.008s

    $ rm /tmp/foo
    $ ghc -O /tmp/foo.hs
    [1 of 1] Compiling Main             ( /tmp/foo.hs, /tmp/foo.o ) [Optimisation flags changed]
    Linking /tmp/foo ...

    $ time /tmp/foo
    ^C^C

    real    0m5.864s
    user    0m5.857s
    sys     0m0.000s

On MacOS X with GHC 7.10.3, it does not time out either way.  Perhaps
some versions of GHC don't make the timeout possible.

--
        Viktor.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Haskell - Haskell-Cafe mailing list
In reply to this post by Ryan Reich
Ryan Reich wrote:
> I expected something like that. I'm all the way back in ghc-8.2.2, but I
> think what this really shows is that the flag is unreliable and
> version-dependent.

The program terminates for me with ghc 8.0.2, 8.2.2, 8.4.3, and 8.6.1,
if compiled with -O -fno-omit-yields; of the versions that I have around
only version 7.8.4 supports -fno-omit-yields but produces a
non-terminating program. This is on x86-64.

I suspect that the real problem is that ghc's recompilation check does
not take -fno-omit-yields into account before version 8.4.1, so you have
to force a clean build for the flag to take effect.

Cheers,

Bertram
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Timing out a pure evaluation of an expression I did not write myself

Haskell - Haskell-Cafe mailing list
In reply to this post by Erik Hesselink
Erik Hesselink wrote:
> Hi Ryan,
>
> I'm not quite sure of your use case, but lambdabot/mueval do something like
> this I think. From a brief look at the source [1] it seems they compute in
> a separate thread, then in another thread, wait until the timeout then kill
> the computation thread. Would something like that work for you?

That is not the whole story; the above mechanism is subject to the same
problems as the original poster's program.

mueval actually comes with a wrapper program ("mueval", source:
"watchdog.hs") that invokes the actual interpreter ("mueval-core",
source: "main.hs") as a subprocess; both programs implement a timeout,
but the wrapper kills the interpreter if the internal timeout fails.

This machinery predates -fno-omit-yields. But it's still useful because
it also protects against blocking unsafe foreign calls and other
scenarios where the RTS can become completely unresponsive, as well
as potential holes in -fno-omit-yields.

Cheers,

Bertram
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.