2/21/2009

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.

9 comments:

Larry said...

Can you have more than one GreenThread running at the same time?

Larry said...

Nevermind, in looking at the code I can see clearly how it manages more than one thread. Great job!

chubbard said...

Just so there is no confusion you can have multiple GreenThread instances running. They will all share the single CPU that it will split the work across multiple instances. So it will slow down the other instances just by sharing the CPU. If you're algorithm needs it then it's there.

Greg Bird said...

Great work...
Just one thing, you mention recursive functions being a particular challenge - could you go into more details about what the issues are?

chubbard said...

@Greg. I started to write a response, but the comment got too big. I wrote a blog post that tries to discuss the issues, and propose a potential solution. Check it out here:

http://wrongnotes.blogspot.com/2010/03/greenthread-problems-with-recursive.html

Let me know your thoughts.

deti3000 said...

Thank you for this exceptional tool!

The only problem for my project is, that i need to start a new greenthread inside the run method of a greenthread. When the inner Greenthread has finished, return to the parent greenthread and run further. Any idea?
Thank you in advance!



override protected function run():Boolean {
if (i<1000){

//Calculating...
//Here i need to start another Greenthread! Is this possible?


i++;
return true;
} else {
return false;
}
}

des said...

Would you be able to provide an example of how you use the ProgressBar?

Thanks

work love said...

I has an application that receive data from the server (push) and save to a queue. The data is small but constant. Every 5 second, a process wake up to process and display (long process) the data. The problem is Flex constantly spend too much time receive and save the data to the queue and no time to update the display. I want the application to share the CPU (50-50) for display and receive data. Would greenthreads able to help in this situation? is there any other technique that can help? THANKS

Shaun Thomson said...

Hi

Just wondering if this works when using getDirectoryListing to load a listing of a large amount of files in a dir?

At the moment, my Flash UI hangs while loading the file data.

Thanks