2/19/2009

Actionscript and Concurrency (II of III)

Now that we understand more about how Flash works internally we can begin to talk about strategies to chop up our large running job into smaller pieces. We'll render the Mandelbrot set. It's a time consuming algorithm, and it's fun when your demos make pretty pictures too. Let's look at a simple implementation.


public function calculate( width : int, height : int ) : void {
_bitmap = new BitmapData( width, height, false, 0x020202 );

var realStep : Number = (_realMax - _realMin) / Number(_bitmap.width);
var imaginaryStep : Number = ( _imaginaryMax - _imaginaryMin ) / Number( _bitmap.height );

for( var screeny : int = 0; screeny < _bitmap.height; screeny++ ) {
for( var screenx : int = 0; screenx < _bitmap.width; screenx++ ) {
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) ) );
}
}
}
var evt : Event = new Event( Event.COMPLETE );
dispatchEvent( evt );
}


Click here to see it in action. Notice how there was a pause before it actually drew the Mandelbrot set. Maybe you got the pinwheel of death or not responding. That is what happens when you hold up the Event Queue.

At a high level this algorithm calculates whether or not a pixel at (screenx,screeny) is inside the Mandelbrot set (i.e. stays below 4). If it stays below 4 after maxIterations of the loop then it colors the pixel black. If not it's color is based on how many times the inner while loop ran before going past 4. It's not as important you understand what the algorithm is doing as so much the parts of the algorithm. The parts that make this a long job are the three loops inside.

Breaking Apart Algorithms


In order to split this job up and run across many frames we'll need to break up those top two loops. Before we jump into that let's talk in a little more general terms. Say we want to bust up a general purpose loop something like:


public function doLongWork( arg1 : String ) : void {
for( var i : int = 0; i < 1000000; i++ ) {
// do some work
}
}


callLater() Technique


We could use the UIComponent.callLater() method to trigger our loop that might look like the following:


public function doLongWork( arg1 : String, i : int, total : int ) : void {
// do work
if( i < total ) {
uicomponent.callLater( doLongWork, [ arg1, i + 1, total ] );
}
}


This is nice. We've removed the for loop and replaced it with what looks like a recursive call, but it's not. Actually what we're doing is doing a single iteration of the loop, and then scheduling the Event Queue to call us back later to do the next iteration of our loop. We do this until i == total, and that point we stop.

Timer Technique


Another way we could restructure our code is to us a timer. Here is another way to do this:


public function start() : void {
i = 0; total = 1000000;
var milliseconds = 1000 / Application.application.stage.frameRate;
_runner = new Timer( milliseconds );
_runner.addEventListener( TimerEvent.TIMER, doLongWork );
}

public function doLongWork() : void {
// do some work
i++;
if( i >= total ) {
_runner.stop();
_runner.removeEventListener( TimerEvent.TIMER, doLongWork );
}
}


A little more code, but this works too. Now we're scheduling a timer to call us at an interval of a single frame. That's the first line where we calculate in milliseconds the length of a single frame. Then we register our doLongWork method to get called back by the timer. We then remove the listener and stop the timer once i reaches total. Notice that in this method we have to move i and total into instance variables which means we have to initialize those in some sort of start method.

FRAME_ENTER Technique


The final option we could use is FRAME_ENTER event. That looks like this:


public function start() : void {
i = 0; total = 1000000;
Application.application.addEventListener( Event.FRAME_ENTER, doLongWork );
}

public function doLongWork( event : Event ) : void {
// do some work
i++;
if( i >= total ) {
Application.application.removeEventListener( Event.FRAME_ENTER, doLongWork );
}
}


This is nice because we don't have to fiddle with math in order to call us back at the frame rate. We just register a listener, when we're done we unregister our listener. Not as clean as callLater, but this works in both Flash and Flex. What's important to remember is that all of these techniques are equivalent. There is no discernible difference in performance between them.

Restructuring Our Demo


So now we can restructure our Mandelbrot algorithm to match one of these patterns. In our case we'll move screenx, screeny, _realStep, _imaginaryStep, and our BitmapData outside of our calculate() method, and put them inside calculateAsync(). Here's our Mandelbrot algorithm restructured:


public function calculateAsync( width : int, height : int ) : void {
_bitmap = new BitmapData( width, height, false, 0x020202 );
screenx = screeny = 0;
_realStep = (_realMax - _realMin) / Number(_bitmap.width);
_imaginaryStep = ( _imaginaryMax - _imaginaryMin ) / Number( _bitmap.height );
Application.application.addEventListener( Event.FRAME_ENTER, calculate );
}

private function calculate( event : Event ) : void {
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++;
} else {
Application.application.removeEventListener( Event.FRAME_ENTER, calculate );
}
}


Now if we ran this version of it you'd see it's 40x slower! Why is that? Well we're executing a single iteration every start of a frame (~40ms). If you timed the running of the calculate method. You'd see that it probably takes less than a millisecond to complete a single iteration. So we've just take a single iteration that ran in <1ms and now we're running it in 40ms! Yikes!

Remember when I said Flash is all about animation? Running jobs at the frame rate is great for animation, but horrible for general purpose concurrency. We need a better way. So our final part we'll discuss optimizing our technique and demonstrate a general purpose solution so that you don't have recreate the wheel when you need to run jobs for long periods of time. See you in the next installment.

1 comment:

Denis said...

Your Mandelbrot using Event.FRAME_ENTER doesn't run and leaves me on black screen with 0% loading. I've tried the link in Chrome and IE with players 10.3.x and 11.x. However if I leave it on the page, it very slowely progresses e.g. after 30 min I got to 3%, so not sure what's going on there.

In my Flex Builder using SDK 4.5.1 I can't find Event.FRAME_ENTER only a Event.ENTER_FRAME.