TimeConstrained

[mmatera]

In the path of rewrite TimeConstrained and related symbols, I was exploring some alternatives to provide a better and cross-platform compatible implementation.

Following https://www.geeksforgeeks.org/python-different-ways-to-kill-a-thread/ , and from some exchanges with @rocky, I considered three possibilities:

1. using flags
2. Using (multi) Process
3. Using Threads

In the current implementation, we have a combination of 1. and 3.: if a walltime is established by TimeConstrained,
the call to the evaluate(evaluation) is wrapped in a Thread object. If the walltime is reached, a the flag "timeout" is set to True in the evaluation object,
and then, the next call to evaluation is going to halt the evaluation.
The problem with this approach is that, if the timeout is reached during an evaluation which was delegated to sympy or another library, the thread continue working and consumig resources. An example of this patological case would be

TimeConstrained[Integrate[Sin[x]^10000, x],1.]
In this case, we give enough time to convert Integrate[Sin[x]^100000, x] into a sympy object and ask it to be evaluated. sympy does not check if the walltime is reached, so tries to evaluate the integral. Since the integral requires to build a very very large (sympy) expression, it takes a lot of time (and memory) to compute it.
When the walltime is reached, the thread continues and eventually could rise a SIGEV exception if the sympy implementation does not handle it (which is what happens if the Pyston or the win32 version of the library is used).

One possibility to overcome this issue was proposed in #354. Here, a trick using ctypes allows to inject an exception in the thread. The exception then stops the evaluation in sympy (or the library that is carring on the computation). This approach works for Pyston, but not in win32.

Another approach would be to move to the option 2., and put the evaluation inside a Process, which according to the documentation, works also in win32. An experiment in that direction is here:

mmatera#2

However, there is a trick: depending on the platform, the new process is created by "fork" the parent process (the default behaviour in Linux) or by "spawn" the new process (default in macOS and the unique possibility in win32). In the second case, Process needs to "pickle" its callable argument (which in our case is a lambda function). To make this work in win32 then implies to rewrite everything in a way that the evaluation object (and the associated definitions object) be pickled and passed to the process. Still, I have some doubts about what happens if the target evaluation is supposed to modify the definitions object. So, again, this approach does not work in win32. Notice also that the other reason to use the Process instead of the Thread backend was because Thread is affected by the Python GIL. However, in this case, we are not looking for paralelize code, but just to have some control about how long a piece of code is allowed to run.

As a conclusion, I guess that to have a better implementation, we should check walltimes using flags, and just wrap (with Process or Thread) the calls to external libraries.

Thoughts?

[rocky]

I considered three possibilities:

using flags
Using (multi) Process
Using Threads
In the current implementation, we have a combination of 1. and 3.

I looked at the article and all of the terminate flags in 1 use Threads. In other words, there are really only two kinds of implementations for TimedConstained, one that works off of threads and one that works off of processes. (There is also a mention of using sys.set_trace() but that wasn't intended for this and isn't really feasible and never used when a performant solution is desired.)

Within these, there are a number of variations on how they are used. The article mostly discusses ways with threads. But to be fair, that is because "threads" was the topic of discussion, not how to run a some Python code for a period of time. That article for example doesn't mention using timeout or alarm signals which works mostly on POSIX systems only.

As a general comment, in an implementation we should try to avoid polled waiting. In other words, avoid using some sort of "sleep" in the code.

Both threads and process implementations provide a timeout parameter in its objectjoin() method See here for doing this with threads, and here for the equivalent using processes. This is what should be used instead.

I am glad to see a discussion around how to implement TimeConstrained although it would have been better start this before the implementation, which was done in haste. I am not sure how the conclusion given follows, but I don't agree with it at the moment.

What is clear is that more thought and care needs done around the implementation of TimeConstrained.

[mmatera]

I looked at the article and all of the terminate flags in 1 use Threads. In other words, there are really only two kinds of implementations for TimedConstained, one that works off of threads and one that works off of processes. (There is also a mention of using sys.set_trace() but that wasn't intended for this and isn't really feasible and never used when a performant solution is desired.)

Within these, there are a number of variations on how they are used. The article mostly discusses ways with threads. But to be fair, that is because "threads" was the topic of discussion, not how to run a some Python code for a period of time. That article for example doesn't mention using timeout or alarm signals which works mostly on POSIX systems only.

OK, but if we can assume a POSIX system, the problem would be already solved using Threads.

As a general comment, in an implementation we should try to avoid polled waiting. In other words, avoid using some sort of "sleep" in the code.

OK, good to know it.

Both threads and process implementations provide a timeout parameter in its objectjoin() method See here for doing this with threads, and here for the equivalent using processes. This is what should be used instead.

I was aware of it. The problem is that in win32 I couldn't reach at that point...

I am glad to see a discussion around how to implement TimeConstrained although it would have been better start this before the implementation, which was done in haste. I am not sure how the conclusion given follows, but I don't agree with it at the moment.

I think it was a path we need to walk. The current implementation is not optimal but works well enough in Linux (and standard Python), and allows us to see what is needed for a better implementation. This discussion could not be even started without having it.

What is clear is that more thought and care needs done around the implementation of TimeConstrained.

[mmatera]

Here is a first cut of the last proposal

As a conclusion, I guess that to have a better implementation, we should check walltimes using flags, and just wrap (with Process or Thread) the calls to external libraries.

https://github.com/mmatera/mathics-core/pull/4/files

This passes all the tests in all the platforms, but at a cost: we need to detect bottlenecks in evaluations outside Mathics main loop and add code to convert it into external processes and control the wall time.

In any case, I still think that the option of using Thread would be optimal if it were a working implementation for all the supported platforms: for the behavior we are looking to implement for this symbol, GIL would not be a problem - because we are not looking for parallelism-
and as in threads, memory is shared, we could create the thread at the top level without having to introduce sparse changes in the code.