Parsing & Rendering Lots of Data in Flash Player

Introduction

When Flash Player 9 was released, one of the touted features was performance with the new ActionScript Virtual Machine.  At the time, I had put Flex 2 through a few of it’s paces, and felt that the new Flash Player had more than enough speed.  I figured I would never run into performance problems with ActionScript 3 since I never use any of the 3D engines for my work.  Then, on my recent project, I ran into 2 performance bottlenecks which caused the Flash Player to choke.

The first is parsing an ungodly amount of data.  I used to make fun of the people who’d bitch and moan on the Flex list about how putting 10,000 records into a Flex DataGrid didn’t perform so well.  My, and others, retort was why in the heck did you need to display that much data?  Surely there are better visual and more efficient ways of doing so.  Now, here I was in a similar situation.  Except, it really wasn’t that much data… it’s just that we off-loaded the creation of it from the server to the client.  In past projects, I’d get really verbose XML, or deeply nested AMF class objects.  The data was human readable (by a developer), and you could make sense of it immediately.  However, what I never cared to ask about was the cost that went into creating that format.  The cost in server resources.

On the product we’re creating, the application doesn’t necessarily ask for very complex objects from the server.  However, the server lead recognized that a lot of processing was needed to convert the data into something the client Flash app could use.  The decision was made to off-load the processing to the client machine instead.  This lessens the servers’ burden, ensures it scales better, and the Flash Player can handle it.  Or so the story went…

Leveraging Client Machines Processing Power

When I was at Microsoft MIX in 2008, one thing I kept hearing anyone and everyone in Microsoft associated with Silverlight saying was, “The client machine has a lot of un-tapped processing power.  We need to harness it.”  Two of the individuals got far off looks in their eyes, leading me to believe that they had some Director give a visionary presentation in some internal Microsoft venue, driving the mantra home.  My guess is this is a potential marketing angle for Silverlight: “Lessen your server’s burden by offloading processing of critical business tasks to the client machine”.  An assumption, but anyway, I’m living that “mantra” with Flash Player and it’s not as black and white as it sounds.  I’m still using a plugin, and while Just In Time compiled for some code, I don’t have access to 100% of the machine’s resources even using the direct and GPU rendering modes.  Safari, and Firefox on the Mac aren’t as nice as IE on the PC.

In short, my for loop that works for 600 nodes doesn’t work for 2000, and is even worse for 5000.

Parsing Over Frames

The commonly known solution since Flash Player 5 has been to utilize parsing over frames.  The theory goes that since code and visual rendering are on the same single-thread, if you reduce your usage of the code processing part by spreading it across frames, your GUI doesn’t lock up.  Ted Patrick had a post on this called the Elastic Racetrack.  It’s not that cut and dry, though, and Sean Christmann elaborated on the concept, which Ted later acknowledged.  What I haven’t seen is a good run down of what happens over time.  I’ve noticed that even if you do break your logic over frames, you still see a noticeable drop in rendering performance, even if you’re usage is a really small time slice.  This gets worse as your application grows in complexity.  For example, code that would run consistently between 20 and 40 milliseconds jumps to 200 to 300 when put into a reasonably sized Flex project.

Let’s first, however, show how you can parse lots of data.  In my current project, I’m getting simple Python objects via PyAMF.  I create ActionScript ValueObjects from them, both for strong typing, and for additional meaning my GUI needs.  I use the Factory pattern to do this.  Here’s an example function shortened:

public static function getDayEvents(object:Object):ArrayCollection
{
        var collection:ArrayCollection = new ArrayCollection();
        for(var cameraESN:String in object)
        {
                var cameraObject:Object = object[cameraESN];
                for(var eventID:String in cameraObject)
                {
                        var eventArray:Array		= cameraObject[eventID] as Array;
                        var dayEvent:DayEventVO 	= new DayEventVO();
                        dayEvent.cameraESN			= cameraESN;
                        dayEvent.eventID 			= parseInt(eventID);
                        dayEvent.startDate			= eventArray[0] as Date;
                        var endDate:Date			= eventArray[1] as Date;
                        dayEvent.endDate			= endDate;
                        dayEvent.originalStartDate	= new Date(dayEvent.startDate.valueOf());
                        dayEvent.originalEndDate	= new Date(dayEvent.endDate.valueOf());
                        var stillFrames:Array 		= eventArray[2] as Array;
                        dayEvent.stillFrames 		= stillFrames.concat();
                        dayEvent.stillFrames.sort(Array.NUMERIC);
                }
        }
        collection = extrapolateFromStillFrames(collection);
        collection.source.sortOn("startDate", Array.NUMERIC);
        return collection;
}

What this function does is take a raw Python object, and extract all the data I need into a linear ArrayCollection (pimp DataProvider for you Flasherz).  There are 2 performance problems with this function.  The first is the nested for in loop doesn’t scale into the thousands.  It’s barely noticeable, though.  The worst is the “extrapolateFromStillFrames” function.  That mofo does some serious (and horribly written *ahem*) math to calculate dates from video still frames.  In effect, you put in one ValueObject, and potentially get back five.

The Builder Pattern

As time went on, and the server started getting built, we started to get real-world data.  We had accumulated a lot of data, and I started seeing performance problems.  I tracked it down to this function.  I stared at it for a long while, amazed I had finally brought AS3 to it’s knee’s for something I thought was pretty simple.  So, I asked on Twitter if anyone knew what pattern to use parsing over frames and Branden Hall responded with the Builder pattern.  I took a quick look, and the concept seemed pretty simple.  Instead of doing a for loop followed by a hardcore function, I needed to break each parsing operation into its own function.  I made sure to only break out the ones that had proven performance issues (longer than 100 milliseconds in a isolated testing environment).  I’m all about re-factoring, but my Factory’s existing 20 methods work great and I wanted to ensure I could still use them.  In my years of doing this stuff, Factory parsing is always the weakest link.

I ignored the inheritance part of the pattern, and just created a DayEventBuiler.  It builds a single DayEventVO via 3 functions re-factored from my original Factory class.  I then re-factored some of the slower Factory functions into the DayEventBuilder.  I then created a DayEventDirector (Director) which is responsible for creating the DayEventBuilder (Builder), and using it to create a multitude of DayEventVO’s (Product).  This guy looks nothing like the Builder pattern in the above link, and I don’t need the abstraction part.  Instead, it calls those methods over time.  If anything takes longer than 10 milliseconds, I abort parsing the rest till the next frame.  Which leads me too…

Green Threads

…green threads.  First, some context.  “Threading” in general is a misnomer when applied to the Flash Player.  As of this writing, ActionScript 3 in Flash Player 10.0.22.87 is single-threaded with Shader’s capable of rendering in a separate thread.  What this means is that your ActionScript and the rendering of graphics runs on the same thread.  Networking, and other socket operations can run in a separate thread, as does a thread to watch your code and make sure it doesn’t time out.  Neither of those threads are accessible to you, though.  The only other option you have for true multi-threading in Flash Player is to utilize asynchronous Shaders.  Using the PixelBender toolkit, you can utilize a Shader to perform math operations on a separate thread.  I’ve tried and failed at converting my Factory parsing code to a series of pixels which PixelBender could convert for me.  So the only other option I had was green threads.

In short, a green thread is a fake thread.  Instead of utilizing multiple CPU’s or cores and distributing the workload amongst them, you emulate how threads work.  The main use for threads is to do GUI on one thread, and processor intensive or blocking operations on another thread.

Using green threads in ActionScript attempts to accomplish the same goal.  Instead of doing a deeply nested for loop with extra parsing functions at the end, you instead break that work up into a series of stand alone functions.  Those functions all do some work to build the completed DayEventVO, in this case, the Product portion of the Builder Pattern.  The Builder and Product portion are quite simple to write, but not so simple to test.  You need to ensure that each function is in fact fast enough to justify being a function.  If it’s slow, say over 100 milliseconds in an isolated testing environment, you need to break it up into multiple functions to remove the bottleneck.  Additionally, the functions themselves should scale.  Below is an example of a few functions from the Builder class I created to replace the above Factory function:

private var dayEvent:DayEventVO = new DayEventVO();

public function parseEventArray(eventID:uint, eventArray:Array, cameraESN:String):void
{
        dayEvent.cameraESN			= cameraESN;
        dayEvent.eventID 			= eventID;
        dayEvent.startDate			= eventArray[0] as Date;
        var endDate:Date			= eventArray[1] as Date;
        dayEvent.endDate			= endDate;
        dayEvent.originalStartDate	= new Date(dayEvent.startDate.valueOf());
        dayEvent.originalEndDate	= new Date(dayEvent.endDate.valueOf());
        var stillFrames:Array 		= eventArray[2] as Array;
        dayEvent.stillFrames 		= stillFrames.concat();
        dayEvent.stillFrames.sort(Array.NUMERIC);
}

Like a Command, the Builder function is only run once.  It’s purpose is to construct part of the DayEventVO member variable.  Notice I’ve offloaded some of the work of getting the parameters it needs to the Director, the class that instantiates the Builder and calls methods on it.  I could make it better by actually passing the raw AMF object I’m parsing, and let him handle the extraction of the parameters I need, but it was simple enough (sort of) to make the Director iterate through each one.  Here’s 2 more functions:

public function constructStillFrames():Boolean
{
        var constructedStillFrameDates:Array = DayEventsFactory.calculateStillFrameDates(dayEvent);
        if(constructedStillFrameDates)
        {
                dayEvent.stillFrameDates	= constructedStillFrameDates;
                return true;
        }
        else
        {
                return false;
        }
}

public function extrapolateFromStillFrames():Boolean
{
        if(dayEvents == null) dayEvents = new ArrayCollection();
        var stillLen:int = dayEvent.stillFrames.length;
        for(var stillIndex:uint = 0; stillIndex < stillLen; stillIndex++)
        {
                var stillObj:Object = dayEvent.stillFrameDates[stillIndex];
                var cloneEvent:DayEventVO = dayEvent.clone();
                if(stillIndex != 0)
                {
                        cloneEvent.startDate = new Date(stillObj.startDate.valueOf());
                }
                cloneEvent.endDate = new Date(stillObj.endDate.valueOf());
                cloneEvent.frameIndex = stillIndex;
                if(checkValidYear(cloneEvent) == false) return false;
                dayEvents.addItem(cloneEvent);
        }
        return true;
}

Both of the above functions do something extra; they return a true or false on whether they succeeded or not.  Even though our back-end is pretty solid, I still occasionally get older data.  What used to be an if-then statement in my Factory parsing functions is now a Boolean response from my Builder’s functions.  This indicates to the Director whether he should abort parsing this particular item, and move to the next one in case of a parsing failure.

Again, the point of the above is to ensure fast code & code that abstracts all the work so the Director only has to worry about keeping track of how much time has passed.

The Director is where the green threading happens.  Upon receiving the object, he starts parsing the first object.  If each function on the current Builder returns true, and the time hasn’t exceeded 10 milliseconds, he proceeds to the next.  If he’s done, and he has time left, he moves to the next object to parse.  If the time has exceeded 10 milliseconds, he merely waits a frame, and proceeds form where he left off.  It sounds simple, but it’s not.  You have to right a lot of state member variables to keep track of where you are in the process.  Here’s the main function where all the work happens, and it somewhat follows the Director design pattern.  He’ll store the current Builder he’s working with as a member variable, and constantly keep tabs on how much time has progressed.  This way, I do as much work as I can, but no more than I’m allowed:

private function processCurrentBuilderJob(totalTimeTaken:uint):void
{
        var startTime:uint;
        if(totalTimeTaken == 0)
        {
                startTime = getTimer();
        }
        else if(totalTimeTaken > PROCESS_TIMEOUT)
        {
                createBuilderSprite();
                builderSprite.addEventListener(Event.ENTER_FRAME, onProcessNextBuilderJob);
                return;
        }
        else
        {
                startTime = getTimer() - totalTimeTaken;
        }
        DayEventBuilder(currentBuilderJob.builder).parseEventArray(currentBuilderJob.eventID, currentBuilderJob.eventArray, currentBuilderJob.cameraESN)

        var result:Boolean = DayEventBuilder(currentBuilderJob.builder).constructStillFrames();
        if(result == false)
        {
                cleanAndPrepForNextBuilderJob(getTimer() - startTime);
                return;
        }

        result = DayEventBuilder(currentBuilderJob.builder).extrapolateFromStillFrames();
        if(result == false)
        {
                cleanAndPrepForNextBuilderJob(getTimer() - startTime);
                return;
        }

        lastStartTime = startTime;
        var elapsedTime:Number = getTimer() - startTime;
        doneWithCurrentBuilderJob(elapsedTime);
}

 The pro is my parsing went from locking up my GUI to just slowing it down a little.  The con is that my parsing time went from an 800 milliseconds for loop to a 2.3 seconds asynchronous green threading operation.  For the larger data sets it goes from a 1.5 seconds for loop, to an 5 seconds asynchronous green threading operation.  This varies on browsers and OS, but I like to use Safari on a Mac as my metric because that mofo is slow and gives me very little CPU compared to other browsers.  Version 3 is better than 2, but still.

The magic is merely using a getTimer() function call at the beginning of your function, and comparing it later on in the function after a Builder function call.  If it’s exceeded 10 milliseconds, you wait a frame.  That’s essentially how most green threads I’ve seen in Flash Player work.  A few people use 100 milliseconds as the common number, but I’m doing this in a few of my GUI classes as well that have complicated redraw, so use 10 in a constants file.  Here are some other blog posts discussing green threads in ActionScript: 

• Green Threading, Psuedo Threads, or AIR as a server?
• Threads in Actionscript 3
• Green Threads – Google Cached | Original

Rendering GUI and Conclusion

I’ve started using this technique in some of my more complicated GUI controls.  I have some graphs for example that utilize the same technique that Andrew Trice talks about in rendering large datasets.  The key, however, is aborting in the middle of the for loop if you take longer than stage.frameRate (or shorter if have other things going on).  So instead of just using setPixel, you actually draw as much as you can in 10 milliseconds for example, and then draw some more on your next iteration next frame.  This can go on for many frames, distributing the work across frames and not locking up your GUI.  For example, if you throw 9000 data points at a Flex Area Chart, she’ll lock up your GUI, AND cause performance issues thenceforth.  If, however, you draw it yourself using Andrew’s example, AND you take breaks between frame renderings, you’ll have no issues… other than a slow to draw chart.  A responsive GUI that is slow to draw is better than one that locks up your comp. 

The real solution is to get Flash Player 11 or 12 to have threads.  That, or for me to get a Charlie Gordon surgey to be smart enough to utilize PixelBender.