Actionscript and Concurrency (III of III)

In the previous article we covered techniques for breaking up our long running job, but the performance was 40x slower than if we just ran our algorithm straight out. The problem is our algorithm spends very little time doing work, and a lot of time waiting for the next frame. Actionscript's performance is really quite high. We need to increase the time spent running our algorithm and minimize the time we spend doing nothing. We can do that by doing many iterations per frame instead of just one. Using getTimer() we measure how much time we spent looping and back off right before the next frame. Let's look at the code:

public function start() : void {
    Application.application.addEventListener( Event.FRAME_ENTER, onCycle );
}

private function onCycle( event : Event ) : void {
   var cycle : Boolean = true;
   var start : Number = getTimer();
   var milliseconds = 1000 / Application.application.stage.frameRate - DELTA;
   while( cycle && (getTimer() - start) < milliseconds ) {
       cycle = doLongWork();
   }

   if( cycle == false ) {
       Application.application.removeEventListener( Event.FRAME_ENTER, doLongWork );
   }
}
    
public function doLongWork() : Boolean {
    // do some work
    i++;
    return i < total;
}

Now we broken up our algorithm into an extra method. First the start() method which we're already seen. The new method is the onCycle which calculates how long a frame is in milliseconds. The loop continues until either the doLongWork method returns false, or we run out of time. Notice the DELTA constant is some constant that keeps us from eating up the entire frame. We need to give a little breathing room for Flash to drain the queue. Notice how our doLongWork method is just the code pertaining to our job. This makes it's easier to build a general purpose solution that we can reuse.

Green Threads

We can't use true OS threads in Actionscript, but any language can emulate threads. This technique is often called Green Threads. Lots of languages have used this in the past. Threads in Ruby are still green, and early versions of Java were green as well. Now Actionscript can too. I should pause and give credit to Drew Cummins who implemented a version of this for Flash player 10. I've rewritten this to remove the dependency of Flash 10, and changed some of the API so event dispatch is more natural, added easy progress events, and optional progress tracking. Let's see how our Mandelbrot algorithm changes when we use this.

In order to use GreenThreads create a subclass of GreenThread, override run method, and optionally override initialize method to add code that runs at the start. Here is an example:

public class Mandelbrot extends GreenThread {
 private var _bitmap : BitmapData;
 private var _maxIteration : uint = 100;
 private var _realMin : Number = -2.0;
 private var _realMax : Number = 1.0;
 private var _imaginaryMin : Number = -1.0;
 private var _imaginaryMax : Number = 1.0;
 private var _shader : Shader;
 
 private var _realStep : Number;
 private var _imaginaryStep : Number;
 private var screenx : int = 0;
 private var screeny : int = 0;

 override protected function initialize( ) : void {
  _bitmap = new BitmapData( width, height, false, 0x020202 );
  screenx = screeny = 0;
  _realStep = (_realMax - _realMin) / Number(_bitmap.width);
  _imaginaryStep = ( _imaginaryMax - _imaginaryMin ) / Number( _bitmap.height );
 }

 override protected function run():Boolean {
  if( screenx > _bitmap.width ) {
   screenx = 0;
   screeny++;
  }
  if( screeny < _bitmap.height ) {
   var x : Number = screenx * _realStep + _realMin;
   var y : Number = screeny * _imaginaryStep + _imaginaryMin;
   var x0 : Number = x;
   var y0 : Number = y;
   var iteration : int = 0;
   while( x * x + y * y <= (2 * 2) && iteration < _maxIteration ) {
    var xtemp : Number = x * x - y * y + x0;
    y = 2 * x * y + y0;
    x = xtemp;
    iteration = iteration + 1;
   }
   
   if( iteration == _maxIteration ) {
    _bitmap.setPixel( screenx, screeny, 0x000000 );
   } else {
    _bitmap.setPixel( screenx, screeny, shader.lookup( Number(iteration) / Number(maxIteration) ) );
   }
   screenx++;
   return true;
  } else {
   return false;
  }
 }
}

The run() method is the body our of loop. The intialize() method is called once after the user calls the start() method. After that run() method is called repeatedly until it returns false. It's perfectly acceptable to call start() more than once to kick off the thread again after it's finished. That means you can calculate the Mandelbrot set from different zoom levels without needing to recreate new instances. The initialize() method will be called every time start() is called. Check out the results here.

You can also add optional progress tracking by setting maximum, and progress members. This will automatically dispatch ProgressEvents so that your instance can be a source to a ProgressBar. It makes tracking your job easy. GreenThread also subclasses EventDispatcher so you can dispatch events from within the run method.

By in large we've solved the performance problems or we've gotten very close. What's holding us back is the resolution of getTimer(). Since we only have precision of millisecond we really can't run the risk of going smaller than 1 millisecond for our DELTA. That costs us a few iterations on our run() method which can make a difference over 1000 cycles. We could be a full second behind Actionscript that just ran the job straight through. There are a few things we can do to squeeze a little more performance out of GreenThreads.

Frame rate governs everything we do, and by default Flex applications run at 24 frames/s, but really most Flex applications don't do that much animation so if we dropped the frame rate in half to 12 frames/s we would be able to run for longer periods uninterrupted. The fewer interruptions we have, the faster we'll go.

GreenThreads also allows you to configure how much of the frame's time you dedicate to running your thread. By default it's set at 0.99 that roughly leaves 1 ms to update the UI. Under some experimentation this has proven to work quite well without creating lots of timeouts, but if you want to tweak it just provide a new value in the start method like so:

public function go() : void {
   start( 0.5 );
}

If the delta is less than 1 then it means a percentage of the length of a frame. If it's >=1 then it means the number of milliseconds to subtract from the length of a frame. Some more thought needs to go into this so that as you run your application on different machines with different CPUs so the pause is appropriate for the CPU. In the future it might need to be dynamically adjusted as the algorithm runs.

Thread Statistics

GreenThreads supports runtime statistics for tracking your job. To turn on thread statistics pass true to the GreenThread constructor. Thread statistics collects total time the job took, number of timeouts, min and max iteration times, average time a single iteration took, how many cycles it took, etc. There is a fair amount of information that can be gathered to help tune your thread. You can access that information by doing the following:

public class SomeJob extends GreenThread {

   public function SomeJob() {
      super( true );   // turn on debug statisitics

      addEventListener( Event.COMPLETE, function( event : Event ) : void {
         trace( statistics.print() );
      });
   }
}

Conclusion

There are some drawbacks to doing concurrency this way. One is algorithm have to be cooperative, and stop processing in the middle to let Flash do its thing. That means your algorithm normally have to be rewritten to conform with this approach. That can be particularly difficult for recursive algorithms. There needs to be more research done into how you might fix this with the callLater() technique. The biggest draw back is that we cannot take advantage of multi-processors. For all the code you write Flash runs on a single OS thread. This is a serious disadvantage for us going forward because as Actionscript developers we cannot access boosts in hardware performance as cores are added.

It's been a lot of information but hopefully you now understand the theory behind concurrency in Actionscript, and you have a new library that helps you optimize your code. You can access the source code here, and download the GreenThread's library here. I look forward to hearing about what sorts of long running jobs you create.

Full source code of the Mandelbrot set is here.

Download GreenThread's library here.