CoCoA » CoCoALib

In the current CVS version, intervals between genuine checks can be as long as 1000000 calls.

Quick reminder: issue #1181 arose because calling CpuTime can be quite costly, so it should not be called too often; as a consequence, I changed the impl of CpuTimeLimit so that a genuine check is made only every so often (and the frequency of the full checks is determined heuristically based on past computation speed).

In the problem reported in issue #1376 this interval was far too long, and a supposedly time-limited computation was effectively not time limited. The critical feature in that case was the calls to the check function did not occur a very regular intervals: i.e. the reductions inside a GB computation can require times which vary considerably.

A naive code change, limiting the longest interval to 512, produced satisfactory results. In my one test, allowing a limit of 1024 was less satisfactory, since the timeout was actually triggered after 38s when a limit of 30s had been requested.

• (A) let the creator of the CpuTimeLimit object specify a maximum interval between genuine timeout checks (via an optional(?) extra arg).
• (B) impose a (global) lower maximum.

Approach (A) does put some extra onus on the programmer. I think there should be a reasonable default which works well even when the timeout-check function is called somewhat irregularly, but is not too costly.

Approach (B) is definitely KISS; my main doubt is that it might be too costly if checks are frequently made in a fast loop. e.g. one could imagine a loop which can be very fast for certain inputs, but also much slower for other inputs; it would be a shame to penalize the fast case unnecessarily.

Here are the results of an extreme speed test for option (B) in the previous comment.

The simplistic test program is:

    long l = 0;
    const int mask = (1<<25)-1;    
    CpuTimeLimit CheckForTimeout(1.0);
    for (long i=0; i < 2000000000L; ++i)
    {
      if ((i&mask)==0) cout << i << endl;
      CheckForTimeout("loop");
      l += i;
    }

Of course, one would normally expect CpuTimeLimit to be used with loops where each iteration is significantly more costly. This is intended to be an extreme case. The use of mask is just so that I can easily roughly how far the loop went before the timeout occurred.

Results:
without CheckForTimeout: 1.23s for whole loop (about 60*2^25 iters)

  Limit       NumIters
   256          7*2^25
   512         10*2^25
  1024         13*2^25
  4096         16*2^25
  8192         16*2^25
 16384         17*2^25
 65536         17*2^25
262144         17*2^25

Conclusion: little further gain beyond a limit of 4096, and still less beyond 16384; however, there is a significant penalty at 256, and still a penalty at 512.

Now I'm thinking it may be simpler to use an approach like this:
measure actual CpuTime difference over the last interval;
compare this time with the time remaining;
if interval time is much smaller than time remaining then increase number of steps in an interval;
if interval time "close" to time remaining then reduce number of steps in an interval.

• if user says iterations take nearly constant time then "close to" means perhaps "greater than 1/2 time remaining"
• if user says iterations may take highly variable amounts of time then "close" means perhaps "greater than 1/100 time remaining"

I hope to do some experiments later today.