Computation with time limit

Question

I'm trying to write a construct which allows me to run computations in a given time window. Something like:

def expensiveComputation(): Double = //... some intensive math

val result: Option[Double] = timeLimited( 45 ) { expensiveComputation() }

Here the timeLimited will run expensiveComputation with a timeout of 45 minutes. If it reaches the timeout it returns None, else it wrapped the result into Some.

I am looking for a solution which:

• Is pretty cheap in performance and memory;
• Will run the time-limited task in the current thread.

Any suggestion ?

EDIT

I understand my original problem has no solution. Say I can create a thread for the calculation (but I prefer not using a threadpool/executor/dispatcher). What's the fastest, safest and cleanest way to do it ?

Answer 1

Runs the given code block or throws an exception on timeout:

@throws(classOf[java.util.concurrent.TimeoutException])
def timedRun[F](timeout: Long)(f: => F): F = {

  import java.util.concurrent.{Callable, FutureTask, TimeUnit}

  val task = new FutureTask(new Callable[F]() {
    def call() = f
  })

  new Thread(task).start() 

  task.get(timeout, TimeUnit.MILLISECONDS)
}

Answer 2

Only an idea: I am not so familiar with akka futures. But perhaps its possible to stick the future executing thread to the current thread and use akka futures with timeouts?

Answer 3

To the best of my knowledge, either you yield (the computation calls to some scheduler) or you use a thread, which gets manipulated from the "outside".

Answer 4

If you want to run the task in the current thread and if there should be no other threads involved, you would have to check whether the time limit is over inside of expensiveComputation. For example, if expensiveComputation is a loop, you could check for the time after each iteration.

Answer 5

If you are ok for the code of expensiveComputation to check Thread.interrupted() frequently, pretty easy. But I suppose you are not.

I don't think there is any solution that will work for arbitrary expensiveComputation code. The question is what are you prepared to have as constraint on expensiveComputation.

You have the deprecated and quite unsafe Thead.stop(Throwable) too. If your code does not modify any object but those it created by itself, it might work.

Answer 6

I saw a pattern like this work well for time-limited tasks (Java code):

try {
    setTimeout(45*60*1000); // 45 min in ms
    while (not done) {
       checkTimeout();
       // do some stuff
       // if the stuff can take long, again:
       checkTimeout();
       // do some more stuff
    }
    return Some(result);
}
catch (TimeoutException ex) {
    return None;
}

The checkTimeout() function is cheap to call; you add it to code so that it is called reasonably often, but not too often. All it does is check current time against timer value set by setTimeout() plus the timeout value. If current time exceeds that value, checkTimeout() raises a TimeoutException.

I hope this logic can be reproduced in Scala, too.

Answer 7

For a generic solution (without having to go litter each of your expensiveComputations with checkTimeout() code) perhaps use Javassist. http://www.csg.is.titech.ac.jp/~chiba/javassist/
You can then insert various checkTimeout() methods dynamically.
Here is the intro text on their website:

Javassist (Java Programming Assistant) makes Java bytecode manipulation simple. It is a class library for editing bytecodes in Java; it enables Java programs to define a new class at runtime and to modify a class file when the JVM loads it. Unlike other similar bytecode editors, Javassist provides two levels of API: source level and bytecode level. If the users use the source-level API, they can edit a class file without knowledge of the specifications of the Java bytecode. The whole API is designed with only the vocabulary of the Java language. You can even specify inserted bytecode in the form of source text; Javassist compiles it on the fly. On the other hand, the bytecode-level API allows the users to directly edit a class file as other editors.

Aspect Oriented Programming: Javassist can be a good tool for adding new methods into a class and for inserting before/after/around advice at the both caller and callee sides.

Reflection: One of applications of Javassist is runtime reflection; Javassist enables Java programs to use a metaobject that controls method calls on base-level objects. No specialized compiler or virtual machine are needed.

Answer 8

In the currentThread?? Phhhew... Check after each step in computation Well if your "expensive computation" can be broken up into multiple steps or has iterative logic you could capture the time when you start and then check periodically between your steps. This is by no means a generic solution but will work.

For a more generic solution you might make use of aspects or annotation processing, that automatically litters your code with these checks. If the "check" tells you that your time is up return None.

Ill ponder a solution in java quickly below using annotations and an annotation processor...

public abstract Answer{}
public class Some extends Answer {public Answer(double answer){answer=answer}Double answer = null;}
public class None extends Answer {}


//This is the method before annotation processing
@TimeLimit(45)
public Answer CalculateQuestionToAnswerOf42() {
 double fairydust = Math.Pi * 1.618;
 double moonshadowdrops = (222.21) ^5;
 double thedevil == 222*3;
 return new Answer(fairydust + moonshadowdrops + thedevil);
}

//After annotation processing
public Answer calculateQuestionToAnswerOf42() {
 Date start = new Date() // added via annotation processing;
 double fairydust = Math.Pi * 1.618; 
 if(checkTimeout(start, 45)) return None; // added via annotation processing;
 double moonshadowdrops = (222.21) ^5;
 if(checkTimeout(start, 45)) return None; // added via annotation processing;
 double thedevil == 222*3;
 if(checkTimeout(start, 45)) return None; // added via annotation processing;
 return new Answer(fairydust + moonshadowdrops + thedevil);
}

Answer 9

If you're very seriously in need of this you could create a compiler plugin that inserts check blocks in loops and conditions. These check blocks can then check Thread.isInterrupted() and throw an Exception to escape.

You could possibly use an annotation, i.e. @interruptible, to mark the methods to enhance.