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

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 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

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.

Answer 4

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 5

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 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.