Feature #638
Time limit: let user specify time limit for a computation
Description
Robbiano asked whether it would be possible to allow a user to specify a (CPU) time limit for a computation.
Discuss!
Related issues
History
#1
Updated by John Abbott over 9 years ago
Updated by - Category set to New Function
- Target version set to CoCoALib-1.0
- setting a time limit should be accessible from CoCoA-5
- should it be a general feature, or applicable to just some fns?
- a similar feature should be in CoCoALib (which is why this issue is in CoCoALib)
- what will CoCoALib do if the time limit is exceeded? (throw an exception?)
- how accurately should we observe the limit? (if limit is 100s, but we notice after 120s, is that OK? After 200s?)
- (again) general feature, or just for certain functions?
#2
Updated by John Abbott over 9 years ago
There is a built-in system "timer/alarm" mechanism which works via signals; I do not know much about this (incl. how portable it might be). In any case I believe that non-trivial reactions to signals have to be effected by polling (i.e. the program must explicitly check every so often whether the signal has been received).
Since explicit checking is needed we could simply do it directly (i.e. compare CpuTime() with a limit value, presumably stored in a global). I would not expect portability problems with this approach.
The accuracy of responding to a time limit depends on how often we poll (i.e. check whether we have exceeded the limit). However, we cannot check inside a GMP operation; so if coeffs become big, we may go considerably beyond the limit before we can poll.
Using time limits in a multithreaded environment looks to be "complicated".
#3
Updated by John Abbott over 9 years ago
I believe it would be simplest to start with time limits being allowed only for certain functions. Amongst other things, this makes it clear when we should stop checking, and (hopefully) limits which bits of source code need to make explicit checks.
It would be nice to have a uniform syntax for specifying time limits (assuming they are offered by several functions).
Would we want to impose any other sorts of limit? (would this even be technically feasible?)
NOTE let's ignore "other sorts of limit" until we have resolved the time limit issue. Anyway I cannot think of anything else we could reasonably limit.
#4
Updated by Anna Maria Bigatti over 9 years ago
Updated by John Abbott wrote:
I believe it would be simplest to start with time limits being allowed only for certain functions.
I agree: I think we should start from GBasis (the most likely function to take "too long") & Co.
I don't think we need it for many functions.
In CoCoA-4 we had a function called GBasisTimeout, checking the time after each reduction (even though a reduction could take a long time, so we could miss the timeout by quite a bit).
This way there's no need for a global variable.
It would be nice to have a uniform syntax for specifying time limits (assuming they are offered by several functions).
Now I think it could be useful (and possibly easier) to make a timeout function in CoCoA-5 for user defined functions with a time check at every line (+ inside CoCoALib functions with timeouts?)
Func2 := TimeOut(Func1, Sec)
Would that be too costly? should that be recursively set for all called functions? would that be possible?!? ..... should these lines be moved to "CoCoA-5 issues"? ;-)
#5
Updated by John Abbott over 9 years ago
- Status changed from New to In Progress
- % Done changed from 0 to 10
I agree that GBasis computation is the obvious candidate (are there any others?).
I am unclear about whether the time limit should be specified explicitly for each relevant call, or whether there should be the possibility to say that "all GBasis computations should be limited to X seconds".
Note that GBases may be computed indirectly in many different ways: IsIn, elim, LT(I), etc.
A disadvantage of specifying explicitly for each call is that we need to add lots of new fns, namely a new "time limit" fn for each existing fn which internally computes a GBasis.
NOTE if I recall correctly, GCD may sometimes compute a GBasis (with the current implementation); would we want this to be time-limited too?
#6
Updated by John Abbott over 9 years ago
I'm not sure about your TimeOut proposal. We should talk about details before making any decision. I'm inclined to think that it would be a lot of work (incl. significant changes to the interpreter) for a feature which is only rarely used.
#7
Updated by John Abbott over 8 years ago
My comment in note 2 about using the system "alarm" mechanism might fit in quite well with the CheckForInterrupt mechanism. There are certainly some common elements e.g. having to poll to see if an external event has occurred.
#8
Updated by John Abbott almost 7 years ago
- Related to Design #1086: New design for interrupt mechanism added
#9
Updated by John Abbott almost 7 years ago
- Status changed from In Progress to Resolved
- Assignee set to John Abbott
- % Done changed from 10 to 80
I have just checked in a first attempt at allowing users to impose time limits on computations in CoCoALib.
It uses the "system timer" to send a signal (SIGVTALRM) after a given number of CPU seconds; then CheckForInterrupt will detect the signal and throw a TimerInterruptReceived.
I have checked in the code with documentation and examples Not sure how to do tests.
Let me know if it works for you!
#10
Updated by John Abbott over 6 years ago
I have modified the structure of interrupt, and now have a new version of CpuTimeLimit which does not need BOOST.
It seems to be a drop-in replacement for the version which uses the system timer.
First tests are promising; hope to check in soon.
#11
Updated by John Abbott over 6 years ago
Checked in the new BOOST-free version.
Still have to update doc.
#12
Updated by John Abbott over 6 years ago
- Status changed from Resolved to Closed
- Target version changed from CoCoALib-1.0 to CoCoALib-0.99560
- % Done changed from 80 to 100
- Estimated time set to 26.26 h
#13
Updated by John Abbott almost 6 years ago
- Related to Slug #1181: CpuTime is costly! added