On TimeConstrained[]

[aravindh-krishnamoorthy]

Nested TimeConstrained[] and RemainingTime[] are crucial for Rubi and other applications. In this thread, I propose to collect: (a) the requirements for these functions, (b) some initial design ideas, and (c) why the old implementation had to be removed. The impact of future multi-threading will also need to be considered. This will help me or others implement the feature better.

[rocky]

@aravindh-krishnamoorthy To be able to correct the problems with TimeConstrained[] it would be very helpful to have simple reproducible examples or test cases that can be run. This way, it is easy not only to demonstrate the problem but also to assess the goodness of solutions or that we've completely fixed the problem.

But even informally, what steps does one have to do to see the problem? My understanding is that you were going to add a mathics-core issue or feature, right?

[aravindh-krishnamoorthy]

Hello @rocky ! Based on a comment from @mmatera, I think there was a previous version of TimeConstrained[]. What were the deficiencies of this? What I'd like to do right now is to collect what "features" must be supported by that and related functions. Then, I want to think about what would be the best way to implement and test them.

[mmatera]

Indeed, it was a previous version with a homebrew implementation of TimeConstrained. That implementation failed to interrupt computations running in Sympy. The new version is based on the stopit package, but it seems to have some issues.

[rocky]

I am a bit lost at where things stand now. Independent of what happened in the past and how we go forward, would you summarize where things stand right now.

I'd like to get the tests in place that demonstrate what we are trying to fix put in before we start thinking about the fixes.

How does someone test what you have? Can we start doing CI testing of Mathics3-Rubi? How can a person see in quick, easy, and reliable way what the current issues are right now. Thanks.

[aravindh-krishnamoorthy]

A summary on the current state of TimeConstrained[] is as follows.

1. The current implementation is on https://github.com/Mathics3/mathics-core/tree/at-most-one-TimeConstrained
2. The implementation uses the stopit package with Thread (not signal) based functions, which are a (very) thin wrapper around threading.Timer.
3. stopit does not work well recursively. Hence, TimeConstrained[] can also not be called recursively. In 16de5ec a fix was proposed, where only the first TimeConstrained[] is honoured but any subsequent (nested) TimeConstrained[] is simply ignored and the function proceeds as if without any time constraints.

Depending on how we want to go with this:

1. We could git rid of the dependency on stopit and write the function using threading.Timer and support nested calls. This is because stopit is really a very thin wrapper and signal-based part is heavily OS dependent.
2. We can extend stopit (Thread part) to allow nested calls and implement support for nested TimeConstrained[] thus. But, this would take our implementation away from the "core" work of Mathics, as we now have to include and maintain stopit package in the Mathics3 umbrella.
3. Other ways I cannot think of right now (but suggestions are welcome).

So, to summarise the requirements (from my side):

1. Implement (ideally) platform independent timeout mechanism in TimeConstrained[] based on threading.Timer.
2. Support nested calls to TimeConstrained[].
3. Implement the closely related function TimeRemaining[].

Note: IMHO, the related function TimeRemaining[] is rather easy to implement once we get TimeConstrained[] right.

[mmatera]

IMHO, following the Open Source philosophy, it would make sense to propose a fix for stopit. Before using it, I had an implementation that partially worked on Linux, but failed in Windows. In any case, I plan to study the problem when I find time.

[rocky]

A summary on the current state of TimeConstrained[] is as follows.

1. The current implementation is on https://github.com/Mathics3/mathics-core/tree/at-most-one-TimeConstrained
2. The implementation uses the stopit package with Thread (not signal) based functions, which are a (very) thin wrapper around threading.Timer.
3. stopit does not work well recursively. Hence, TimeConstrained[] can also not be called recursively. In 16de5ec a fix was proposed, where only the first TimeConstrained[] is honoured but any subsequent (nested) TimeConstrained[] is simply ignored and the function proceeds as if without any time constraints.

Depending on how we want to go with this:

1. We could git rid of the dependency on stopit and write the function using threading.Timer and support nested calls. This is because stopit is really a very thin wrapper and signal-based part is heavily OS dependent.
2. We can extend stopit (Thread part) to allow nested calls and implement support for nested TimeConstrained[] thus. But, this would take our implementation away from the "core" work of Mathics, as we now have to include and maintain stopit package in the Mathics3 umbrella.
3. Other ways I cannot think of right now (but suggestions are welcome).

So, to summarise the requirements (from my side):

1. Implement (ideally) platform independent timeout mechanism in TimeConstrained[] based on threading.Timer.
2. Support nested calls to TimeConstrained[].
3. Implement the closely related function TimeRemaining[].

Note: IMHO, the related function TimeRemaining[] is rather easy to implement once we get TimeConstrained[] right.

Please put together a test case based on a Rubi code that can be used to measure the effectiveness of proposed solutions. Thanks.

[mmatera]

This was the implementation before stopit:

mathics-core/mathics/builtin/datentime.py

Line 1178 in b0b7efe

def eval_3(self, expr, t, failexpr, evaluation):

mathics-core/mathics/core/evaluation.py

Line 98 in b0b7efe

def run_with_timeout_and_stack(request, timeout, evaluation):

Another issue with it was that long sympy evaluations were not stopped with it.

[mmatera]

I think that the test case that @rocky ask for would be something like

>> TimeConstrained[TimeConstrained[Pause[2],5, "inner"],1,"outer"]
  = "outer"

and

>> TimeConstrained[TimeConstrained[Pause[2],1, "inner"],5,"outer"]
  = "inner"

With this PR glenfant/stopit#36, I get this behavior. Something that I could do is to include a subclass of ThreadTimeout inside Mathics-core that implements the changes in that PR.

[rocky]

@mmatera While I appreciate your guessing and trying to be helpful, I would also like to have real examples that occur using Rubi.

The Rubi code does not contain Pause[], so while it is possible this is equivalent to the behavior we want to address, it is also possible it does not.

We have already spent a lot of time on the TimeConstrained. Let's work smarter. In order to do that we need have some real tests in place first.

[rocky]

With this PR glenfant/stopit#36, I get this behavior. Something that I could do is to include a subclass of ThreadTimeout inside Mathics-core that implements the changes in that PR.

Please let's defer implementing the solutions until after we have a clear and more complete understanding of the problem that we are seeing in Rubi. I don't feel we have that just yet.

[mmatera]

@rocky, I have not been working on Ruby, but I have used this trick before on other kind of computations (for example, to decide if using exact diagonalization or numeric diagonalization in some problems in QM). Pause is a way to check a systematic behavior, but you can try something like Integrate[Sin[x]^10000,x]. In any case, solving the issue in stopit would solve our issue automatically.

[mmatera]

This is a real example from Ruby: from IntegrationUtilityFunctions.m: 2178,

TogetherSimplify[u_] :=
  TimeConstrained[
    With[{v=Together[Simplify[Together[u]]]},
    TimeConstrained[FixSimplify[v],$TimeLimit/3,v]],
  $TimeLimit,u]

This function tries to simplify an expression by first applying the Together rule, then applying Simplify rules, and then applying together again. It tries to do that inside the walltime defined by the variable $TimeLimit. As a part of the process, it tries to apply other rules, defined in FixSimplify. If it fails to apply these rules inside a third of the walltime given by $TimeLimit, it uses the result obtained by Together@Simplify@Together, and if it takes too much time, then returns the input as it was given.

[rocky]

Okay, we might be closer now to coming up with a real example.

However, TogetherSimplify[] is not run from a command prompt. So now the challenge is to provide a top-level Algebraic Integration example from Section 1 of Rubi that calls TogetherSimplify[] in a way that causes a problem.

We should also consider temporary alternatives for TogetherSimplify[].

I recall Integrate[Sin[x]^10000,x] mentioned before. But I don't see it logged as a Mathics3 issue, either open or closed. Was this ever raised as an issue?

If it hasn't, we should. Using the good practice of reporting minimal examples, I would appreciate it if we used the smallest number that reliably causes the problem, assuming it is not 10000.

[rocky]

Hmm. Can't TogetherSimplify[] be rewritten so it is not recursive but instead sequential using If[]?

[mmatera]

The idea behind this implementation is that if the simplification strategy takes more than a certain walltime, it cancels it, and uses another strategy. Of course, you can redefine TimeConstrained to just return the first argument, and then it would be the same as not establishing any walltime.

On the other hand, it seems that with small adjusts, stopit does the work. I will wait some time to see if I get some feedback from @glenfant. Otherwise, I think we can include the fork (just three Python modules).

[rocky]

The idea behind this implementation is that if the simplification strategy takes more than a certain walltime, it cancels it, and uses another strategy.

This sounds like it can be done as an iterative process.

On the other hand, it seems that with small adjusts, stopit does the work. I will wait some time to see if I get some feedback from @glenfant. Otherwise, I think we can include the fork (just three Python modules).

For this, I wouldn't change the Mathics3-core code, but instead, have this be something that the user decides to do. Install stopit from PyPI or some other forked version. A note can be made in both mathics-core and Mathics3-Rubi regarding some other version of stopit.

[mmatera]

Another interesting thing is that using the signal-based handler, it seems that stopit also works with emscripten. The only limitation is that only accepts integer number of seconds as the walltime.

[rocky]

Recently I looked at stopit, the code we have for TimeConstriant, what Python provides in the way of threading, timing, and signal handling.

In short, I think one can come up with reasonable support for TimeConstraint and TimeRemaining in Python that works across the platforms we support.

But it is more involved and subtle than any of the Python code I've seen so far.

It will take a bit of work to get right. And right now, we still don't have good, isolated cases. The current TimeConstraint test cases aren't robust.

It is a good idea to encapsulate a problem of time-constrained execution in a module such as stopit and that package is better than the homegrown solutions that we had in mathics core.

However stopit currently has a few issues in of itself. The public release of stopit was 7 years ago, and sadly the Python ecosystem has changed in a number of ways that force this code to change.

Testing uses the old JUnit-inspired unitest which is a little clunky and the directory organization structure is one that is no longer current practice. Nowadays tests pretty universally tests go in a test directory.

If it were just this and the older pre-Python 3.8 coding style, we could live with it. But the most serious problem with the current organization is the warning that using setuptools will be soon discontinued. (Thanks, Python!)

And then there is the stopit code itself. The good news is that currently, Python threading and signal handling mechanisms haven't changed.

For our purposes though, we could use some implementation changes to the stopit package.

Right now, the underlying model of stopit uses the basic mechanisms Python provides which is you specify a time interval from now. When multiple threads can occur (which is something we do want to eventually support in Orderless evaluation), and we have nested TimeConstraint, I think we need to include a wallclock time for expiration.

One advantage we get from wall-time recording is that if the implementation happens to include a SIGALRM (but not solely include, see below), then other events using the more precise deadline can cancel a too-grainy SIGALRM which might have been set as a failsafe measure.

Another advantage is that it can reduce the excess time obtained by attempting to measure time n as the sum of n 1/n time intervals.

stopit works inside a single thread. I think we can get more flexibility using multiple threads.

One of the workarounds for the fact that MS Windows does not support SIGALRM is to set up a time thread similar to what is done in Javascript. Here, there is a thread dedicated countdown timer (or better, a real-time deadline counter) and when the time runs out this thread cancels the expired threads.

Lastly, I'll mention that for systems that do support SIGALRM, that can be set in addition to using threads. If there is some sort of thread starvation caused by one thread, the independent mechanism can kick in and free things up.