Using BitmapData for Array manipulation in AS3

UPDATE: The test app has been updated to include two more tests: one for a hash table based approach, and one that uses a ByteArray approach. Looks like the ByteArray approach is the fastest, followed by the hash table, followed by the bitmap method. They’re all pretty close when you’re working with 10k or 100k records, but once you get into a million or more items then the ByteArray approach pulls ahead. Thanks to Alex Bustin for sharing his code for the ByteArray test.

Recently I was thinking about how to do some complex Array manipulation, and how to do it fast. I needed to take a large source Array and filter it two different ways, producing two new filtered arrays, each of which is made up of a subset of the values in the source array. Then I wanted to know which values of the first filtered array were unique to that array (did not appear in filtered array #2) and vice versa. I came up with a technique that uses the bitmap manipulation of the Flash player to accomplish these goals.

An example of the problem:
Let’s say I have a source array that looks like this:

Source Array
Item 1
Item 2
Item 3
Item 4
Item 5

Then I filter that array to produce a new array, Filtered Array #1, that contains some but not all of the items. I do the same thing again, except this time using a different filter that produces Filtered Array #2. Now my data looks like this:

Source Array Filtered Array #1 Filtered Array #2
Item 1 Item 2 Item 1
Item 2 Item 3 Item 2
Item 3 Item 5 Item 3
Item 4 Item 4
Item 5

I want to know the unique values in Filtered Array #1 that do not appear in #2 (Item 5) and the unique values in Filtered Array #2 that do not appear in #1 (Item 1, Item 4). An added bonus would be some extra stuff like being able to know the union of both arrays (items that appear in either array 1 or 2) or the intersection (items that only appear in both filtered arrays).

The slow-ass way
So the first thing that comes to mind when trying to solve this is that you can simply do a for loop over the source array and check if each item appears in Filtered Array #1 and Filtered Array #2. This means you have one full loop over every item in the data set, and then you need to do a check for whether the item exists in each of the filtered arrays. The most basic way would be something like this:

var unique1:Array = [];
var unique2:Array = [];
for(var i:int=0; i

So that's the easiest way and it certainly works. I'm sure there are countless ways to do this in a more optimized way, like not looping over the source array but instead looping over the first filtered array, somehow marking all the items in the second filtered array if they were found in the first filtered array, then looping over the remaining items in the second filtered array. I'm sure someone will tell me that I should use a binary tree search since I know the source index, or that I should use a hashtable to lookup the existence of items faster. I bet all those different approaches would beat this simple example speed-wise, but I was still worried no matter how optimized an approach like this can get, it would still suck. (Side note: If you have an alternative approach that will handle many items with really fast performance, especially if you have an AS3 implementation, I'd love to hear about it.) So anyway, I decided I wanted to try something different.

Using bitmaps
Check this out. Say you have a source array of 10,000 items. Then you filter that down to a filtered array that might have a subset of about 4,000 of those items. The relationship of the items in the filtered array to the source array can be drawn using a bitmap like this:

This image is a 100 pixel by 100 pixel square, and each pixel within that square represents whether or not the item in the source array appears in the filtered array. So if the pixel at 0,0 is black that means that the first item in the source array is also in the filtered array. If a pixel is red, that means that that item does not appear in the filtered array.

Why did I choose to make a square image? I originally just did a single line 1px high. But Flash has a bitmap limitation of a max width or height of 2,880 pixels. So a single line means that you would be limited to arrays with only 2,880 items, and that's not the kind of problem I was trying to solve. The performance need arose from having to do this with a shitload of items. So if we use a square instead (easy to calculate the dimensions, just take the square root of the # of items), then we have a theoretical maximum number of items of 2,880 x 2,880 = about 8.3 million. I'm not going to try to filter more than 8 million items client-side, so I'm ok with that limitation.

OK, cool. Now we do the same thing for the second filtered array. Below is the generated image of both filtered arrays side by side. The red image represents Filtered Array #1 and the green represents Filtered Array #2:

But how do you create these images in an optimized way? Since the arrays are already being filtered, that means I'm using Array.filter() with a callback function to decide whether or not the item passes the filter test. This filter function is going to be run on every item in the array. So I use that function to also do my bitmap drawing. And check this out, the callback for a filterFunction tells you the index of the item in the array! So that gives you all the information you need to draw these images. You know that the function will get called one time for each item, and it tells you the index. So just do a simple BitmapData.setPixelAt() and once your filtering is complete your image has been generated. Dope.

So now we start with the real bitmap magic. We're going to use the compare() method of the BitmapData class to generate a third image that represents a pixel by pixel comparison of these two images. To use the compare() method you call it on one BitmapData and pass in a second BitmapData. The function will return a new BitmapData object that contains pixel comparisons. If the pixel in bitmap 1 is the same as the pixel in bitmap 2 then the new comparison bitmap will have a transparent pixel (0x00000000). If they are not the same, then it will return the "difference pixel", which contains the difference between each channel (RGB). So what happens when we run compare() on these two images? We get a new image something like this:

There are only a few possible pixel values now, and each unique pixel value tells us something special. So by looping over the pixels we can know whether the item occurs in both arrays, one array or the other, or neither array. And just like that, we got our answer.

Try out the demo application I created here. And you can view the full source here. Be forgiving, the source code is dirty as hell... no comments, no nothin'... I basically just cranked this out and decided to put it out there without taking the time to clean it up because a) I think it's a pretty cool approach and b) it's dinner time and I'm hungry.

So what about some benchmarks? I've put together a little demo app that you can play with to try out this method. It lets you run two algorithms, one that is a very simple for loop that loops over each item and calls array1.indexOf(item) and array2.indexOf(item) to see if the item is present in both filtered arrays. Then you can also run the bitmap test that I've described. Here are the results that I had on my machine when running both techniques on various numbers of items:

# of items For loop text Bitmap test
10 items 4 ms 4 ms
100 items 4 ms 4 ms
1,000 items 19 ms 7 ms
10,000 items 1300 ms 32 ms
100,000 items timeout 350 ms
1 million items timeout 3700 ms

These aren't meant to be scientific results. There are some pretty big factors that might influence speed. For the tests I have a filter function that just chooses at random (with 50% probability) which items to include in the two filtered arrays. If you change the number of items in either array the speeds will fluctuate. But the basic idea is that doing a for loop and checking for an item using indexOf fails miserably when you start getting over the tens of thousands of items. The bitmap method works even on a million records, albeit slowly at 3-4 seconds, but at least it works without timing out or crashing the browser.

And like I said before, I'm sure there are other algorithms that would be faster than looping over every item in the full array and checking using indexOf. If you have some implementations that solve the same problem but with better performance, please let me know in the comments.

So what?
I don't really know if I'm going to actually use this technique anywhere, but I might. I'm also thinking about performing other calculations on large datasets using similar methods. Essentially if you have two or more datasets, you can use this graphical technique to perform all kinda of other calculations. I'm only using the compare() function to test for a few very distinct possibilities, but you could imagine doing something much more detailed, like performing calculations based on the aggregate color difference of multiple array images. The bitmap manipulation in Flash is so damn fast, that it opens a whole new door if you try to think about using those methods for number crunching and not just pretty graphics.

P.S. I know it's been a long time since I did a blog post with code. I think this one geeks out to a pretty extreme level, so for anyone reading who was getting fed up with my non-technical ramblings, I hope this makes up for it.


Code samples from Adobe Flex 3.0 For Dummies

The compiled list of code samples from our Flex for Dummies book have been posted on the dedicated Flex for Dummies page of my blog. Each chapter (other than chapters 1, 4, 19, and 20) contains source code samples, and you can browse through them all online or download the code to run in Flex Builder yourself. We’ve double and triple checked everything to make sure it’s all error-free.

Download the code here.

screenshot071.jpgYou’ll see that each chapter contains two links, one to view the source code online and one to download a zip file. If you view the code online you can browse through each of the code listings for the chapter right in your web browser (and cut and paste to try running the sample yourself in Flex Builder). If you download the zip file you can get all the source files on your computer and load them right into Flex Builder yourself. Each chapter was created as a separate Flex project, so you can just create a new project for whichever chapter you like and copy over the files that are in the zip.

We’re still pulling together the last of the samples, so the code for chapters 2, 8, and 12 is on its way. We hope to have those chapters posted by the end of the week. My sincere apologies for not having the code samples online immediately when the book shipped. Wrapping up the creation and production of a book like this was a whirlwind of activity, and we certainly slipped a little in getting the code online.


Flex spotted on TV

I came across a video of a segment that aired on Fox Business News about HotPads.com, which is an online housing search website (rentals, sales, etc). As I was watching the clip I noticed that beautiful little preloader we’ve all come to know and love 🙂 HotPads uses a custom map engine they developed in Flex (after porting an older Flash app).

Here’s the screenshot that caught my eye:

You can watch the full video here:

And if you haven’t checked out hotpads before, it’s pretty dope. In addition to seeing rental listings on a map, they let you see some cool heatmaps of various things like foreclosure rates, income and age levels, etc. And it’s Flex, so show some love people.

Disclaimer or whatever: The guys who founded and run hotpads are friends of mine, I even did some work for them back a few years ago. I’ve got a little investment in the company that will one day either make me rich or hopefully at least buy me a six pack of beer.


Description of my Flash on the Beach session: Decompiling Flex and Flash

speakerbadge_200_120_e.gifI’ve just posted the title and description of the session I’ll be giving at Flash on the Beach, which is happening September 28-Oct 1 in Brighton, England. My session is titled: Decompiling Flex and Flash. Here’s the full description (which you can also find on the FOTB site):

In this session we’ll learn how to decompile ActionScript 3 SWF files and peek inside other people’s code. Decompiling a SWF is often seen as an evil tactic that should be punishable by death, but regardless of your moral opinion, every SWF you create can be decompiled into often beautifully readable source code. If you’ve produced something cool, chances are someone has decompiled it (hell, chances are I’ve decompiled it myself).

In this session you’ll learn what you get when you decompile a SWF and what you don’t. We’ll cover how far you can get piecing a decompiled application back together and I’ll share a few real-world stories of how decompiling has proven invaluable in my development career.

This session will focus on ripping apart some large-scale Flex applications and diving into the source (we’ll see if I can get sued by the end of the session). I’ll cover some Flex-specifics that are important when you decompile a Flex app (Flex framework classes, generated MXML code, data binding code, etc). But decompiling AS3 SWFs is just as applicable for SWFs produced in Flash Authoring as well, so there should be plenty of information for everyone.

And for all the paranoid folks out there, in addition to decompiling code, I’ll also cover a few techniques to protect your source code to make it harder for people to steal.

I hope to see some of you in England!


Some flexcoders stats

I’ve recently compiled a fairly complete database of all the messages ever sent to the flexcoders mailing list. I’ll be posting the sqlite database file that you can load into your own AIR applications to start playing with this data. But before anything else I thought I’d post a few fun tidbits:

Top 10 Posters

Poster # Messages # unique threads
Alex Harui 3259 2172
Matt Chotin 2793 2153
Tracy Spratt 2522 1886
Tom Chiverton 2368 1559
Manish Jethani 1296 1004
Gordon Smith 1371 978
JesterXL 1216 702
Abdul Qabiz 833 614
Michael Scmalle 904 513
Tim Hoff 798 470

Longest Threads

Subject # Messages # unique posters
Splitting FlexCoders into smaller, focused groups 130 28
Will Microsoft’s Silverlight Player Kill our beloved Flex? 127 48
Flex 1.5 price 102 36

[DISCLAIMER: I have not verified this data at all. For all I know I fucked something up in the scraping process and it’s all whack. Who knows.]

Method for gathering data
I wrote an AIR application that scrapes the mail archive site for a specific group. This pulled all the messages that are available on the flexcoders archive of mail archive. (to get this listing I did a search that encompasses the entire date range I wanted to get paged results for all the messages). Unfortunately I can only get pages of 10 messages at a time from the mail archive. And there are over 96,000 messages in the flexcoders archive. And I didn’t want to hammer the site to total death and wanted to respect the request to not request more than one page a second that’s in the mail archive FAQ. So how long does downloading 96,579 messages take if you download 10 at a time once a second? About 3 hours more or less.

Oh, and it turns out that the HTML in the mail archive pages isn’t valid XHTML, so parsing it can be a bit of a bitch. So I managed to get about 20,000 messages in when I ran into a parsing error that halted the whole process. After about 3 different tries I finally got all the way through.

[DISCLAIMER 2: The mail archive site lists something like 96,000 messages for flexcoders, but the yahoo group seems to have quite a bit more, more like 116,000. Why the 22k difference? I don’t know. Something’s whack, but I’m guessing that what I got is not the full 100% complete version of the messages. But hey, it’s the best I got right now.]

Why the hell?

We recently had a long discussion on flexcoders about whether or not the list should be split into multiple smaller lists. Notice the longest thread of all time in all of flexcoders history? Yeah, it’s that thread. So we debated back and forth and everyone seemed to have their own opinion. There were some assertions made about the stats of the list in terms fo # of people posting and losing previous subscribers. So I decided to get a database of all messages so I could try to figure some of that stuff out. So gathering the data was step 1. Now step 2 is using the data to try to figure out if people are in fact dropping off the list, and whatever other interesting tidbits I can glean out of it. I figure it’s a good way to play with some data visualization techniques.

What’s next with the data?
I’m going to post the sqlite DB file for anyone to download. The complete DB file is 90 megs. I’m also thinking about removing the “excerpt” column (which contains the first part of the complete message) because I assume that will drop the size considerably. I’m going to figure out whether I just want to post the 90 meg thing on my website or if I want to try to offload that somewhere, although I imagine there are only a few people who wpould be interested in downloading this thing anyway 😛

I’m also going to play with doing some visualizations of this data now that I have it in an AIR app. I’ll probably just take screenshots of what I come up with, seeing as to actually run this stuff you’d have to download a frickin 90 meg air file, which seems a little excessive. Or maybe I’ll give people a 90 meg AIR app, fuck it right?

I hope to post the sqlite database file over the weekend. Then as I have time I might start playing with the data and posting my results.


Proposal for a job at Adobe (that I never sent)

This is a document that I wrote back in October 2007. I forgot about it until just now. My original idea was to define my “dream job” within Adobe, explain exactly what I wanted to do, and tell them why they should hire me. For a variety of reasons I never sent this document. This was during a period in my life when I was considering a few different options for my “career”. I was doing the Flex consulting thing and billing my time hourly (which is pretty sweet). I was talking to Universal Mind about making the shift to a full time employee, and during that decision I considered what other full-time options I had.

When I first started this whole Flex blogging thing my original goal was to get a job at Adobe. No joke, I basically started blogging thinking “I’m going to blog, get good, show people I can do good shit, then ask for my dream job at Adobe.” The Adobe SF office is a 5 minute drive or 15 minute bike ride from my house in San Francisco, and I figured it would rock to work there doing something Flex related. Then my eyes were opened to the world of Flex consulting (the money, the women…) 🙂 But I always had a desire to go work for Adobe. So when I was considering full-time options, I obviously thought of boarding the mothership. So I wrote up a job proposal that describes the kind of job that I wanted. Yes, this is completely arrogant and egotistical. There were no job postings that I liked, so I decided to make one up. This was basically my way of saying: “You guys should want to hire me, but your job openings suck, so not only should you hire me, you should also make this sweet position just for me.”

I never sent this. In the end I decided that the position I was offered at Universal Mind was too good to pass up, and I was being ridiculous for even thinking anything otherwise (which I still believe). But I just read over this proposal again and I think that a lot of the ideas I bring up are still good ones. I would love to see this kind of experimental position created. So without further ado, here’s the job proposal I wrote. This is the main part of the document, I only took out the last page or so that talked about my relevant experience. If you can take this and get Adobe to create this job for you, go for it. I think this job would be sweet and it would benefit the Flex community and the Flex product as a whole.


I am interested in a position within Adobe that would allow me to create experimental user interfaces and data visualization prototypes using Flex. The purpose of this proposal is to clearly explain the ideal position I have in mind, why such a position would benefit Adobe, and why I would be right for the job.

Job description
I propose an experimental software developer position to explore alternative and inspiring user interfaces created with Flex, focusing on alternative input methods and advanced data visualization techniques. Work would be heavily focused on Actionscript 3 and, more specifically, utilizing the Flex framework. It is important to emphasize the experimental nature of this work. This work is meant to move AS3 and Flex onto the cutting edge of research and development in user interfaces. The end goal of such work would be to inspire and teach the Flex developer community by publishing the open-source research results and blogging explanatory tutorials.

Reasons for being within Adobe
An important question that should be discussed is the benefit of bringing experimental community-focused development in-house in Adobe. I am already involved in open-source Flex projects externally, and I have done a fair amount of experimental work using AS3 and Flex that has been published on my blog. Regardless of where I am employed, I plan on continuing this type of work. However, being within Adobe will provide some serious advantages to all parties involved.

Experimental projects benefit three distinct stakeholders: me personally, the Flex developer community, and Adobe. However, nearly all the experimental work that I do is done outside of paid working hours, forcing me to decide between work that gets me paid and work that gets me excited (which can often overlap, but seldom do completely). A traditional employer does not have the resources to allow me to work on experimental projects that may or may not have a commercial use. But even if an experimental project is completely useless in the commercial software space, it still benefits me (through personal growth and education), the Flex community (through published source code and inspiration), and Adobe (by generating buzz and interest in the technology). Adobe is the only commercial organization that benefits financially from work that might have no commercial purpose.

While Adobe benefits from projects with no commercial viability, Adobe would also be in a position to benefit from possible commercial success of research projects. All projects would be reviewed by Adobe, which would allow the company to decide if a research project has interesting commercial possibilities. If so, a project could continue as an internal product development effort. If Adobe decides it does not want to pursue a project internally then the project still benefits the Flex community when it is released open-source.

Research Projects
The decision to take on research projects would take multiple factors into account: awesomeness, pragmatic feasibility within a limited timeframe, potential benefit to the developer community, and potential commercial application within Adobe. The first and most important factor is the wow factor of each project. I plan on making experiments that blow people away and show off the strengths of Flash Player. Flex/Flash Player allows us to make interfaces and data visualization prototypes unlike anything ever seen on the web (or on the desktop for that matter). I want to make things that amaze people.

Projects will also need to have short timeframes, at least in terms of creating something impressive that can be shared with the community. Future development of experimental projects might continue after the initial project timeline, either within Adobe or in the developer community, but each project would have an initial exploration phase of no longer than a few months. I’ve found that setting such time constraints leads to more focused development and more impressive results.

A major goal of all projects would be to benefit the developer community through the release of source code. Each project would include blog posts and technical articles explaining how the project was developed. This will encourage the developer community to use the source code in other projects, and will also provide inspiration that will lead to the development of even more impressive projects within the community. I have considerable experience blogging about custom Flex component development and AS3 experiments. I understand the importance of useful resources with well-written source code and explanations. As a developer, I think the most important resource for learning advanced techniques is the wealth of information found in blogs. I know that personally I’ve probably learned more from Ely Greenfield’s code than from any other single source (not to mention the amount of inspiration his examples provide). But now you’ve got Ely off architecting instead of writing code. It’s my personal opinion that Adobe should get back into technically-focused blogging, as opposed to the non-technical evangelism that seems to be the current priority.

The final consideration, which is purposefully listed last, is the commercial possibility within Adobe. A research project may have serious commercial possibilities, and given further development might turn into an official Adobe product. This seems all the more likely given Adobe’s movement into software services that are based on Flex (Buzzword, CoCoMo, Pacifica, Photoshop Express, Premier Express). It’s important to note that I would hope potential research projects would be brainstormed with possible commercial viability as an afterthought. Personally, I believe the most inspirational work is done without first considering the commercial possibilities.

BRAINSTORMING: possible directions for research
Be aware that the list of potential research projects below is an off-the-top-of-my-head list. The number of awesome possibilities that show off Flex/AS3 is nearly infinite. I have provided a list of current research interests, but the intent of this document is not to propose specific projects, but instead articulate why this type of experimental developer position is important.

There are various open-source projects for eye tracking using normal web cameras. This software could theoretically communicate to a Flash/Flex application using a local socket connection. This could allow Flex applications to receive data about where the user is looking within the interface. The possible uses of such data are amazing. We could make a Flex analytics app that would let developers visually analyze how users are interacting with their software. We could track not only mouse click interactions and mouse movement, but now also the actual eye movements. Companies that develop Flex applications would love the ability to accurately track their user’s focus. And with video we could track where people are looking as the video plays, which could be commercially valuable for online advertising companies to run studies, especially now that video-overlay advertisements are becoming popular. Imagine a heatmap that plays live over a video indicating the hotspots that most people view.

I’ve been experimenting with some home-brew multi-touch hardware and an early AS3 api that allows me to incorporate a multi-touch interface in a Flex application. Multi-touch is currently a hot topic because of the iPhone and the Microsoft Surface. In terms of availability to developers, the Flash options for working with multi-touch are the most advanced and powerful. The AS3 API needs a lot of work to be ready for mass use and the hardware is still in its infancy, but the demos that we could build would blow people away.

Alternative menu systems
I’m interested in exploring alternatives to traditional menu systems within Flex applications. I’ve had great success implementing a radial menu in Flex in my TileUI prototype application, I would like to explore menus that size their items based on past usage, three dimensional menu systems, powerful shortcut-key navigation with Flex, and zooming menu interfaces.

3D interfaces
I have implemented a 3D interface for an experimental project called TileUI. This project used many available open-source AS3 libraries (most importantly PaperVision 3D and Actionscript Physics Engine). The result is an impressive prototype that shows off the amazing visual capabilities of the Flash Player. I would like to take the concept of 3D interface design more generally, and explore alternative 3D possibilities that would really demonstrate how we can create experiences far beyond traditional user interfaces.


I’m sponsoring 360|Flex

360flex_sanjose_badge200.gifI’m an official sponsor of the 360|Flex conference! I think I am the first and only “just a normal guy” (not a company or independent contractor) to be a sponsor. I’m not looking for clients, I’m not looking for work… I’m just a dude who likes the conference. I like it so much that I was really sad about not being able to speak at the next 360|Flex in San Jose in August. So since I can’t be there, I figured out how to get my face in front of y’all anyway 🙂 I’m sponsoring the official 360|Flex shirt that all attendees will get and all you suckas have to wear my silly face on your sleeve.

screenshot057.jpgCheck out all the sponsor logos on the 360|Flex site (screenshot on the right). You see that dumbass-looking face with the thumbs? That’s me!

Why the hell?
I owe a lot to 360|Flex. At the first one in San Jose back in March 2007 I made a ton of contacts that have helped me professionally. I happened to sit next to Tom Link and Brett Cortese from Universal Mind in the back of some session and we started talking. Now I’m a full-time employee with Universal Mind doing sweet Flex work. I got some of my work shown off in the keynote of that conference too, and people started hearing my name and wondering who I was.

Then at the second 360|Flex I did my first-ever conference presentation (on custom Flex component development). Suddenly I was somehow an authoritative Flex developer, and the main reason I actually spoke at that conference was because Tom Ortega asked me to in one of our local Flex user group meetings (in addition to planning 360|Flex, Tom also runs SilVaFug). I made a lot of friends at that conference and felt like I really became a part of the Flex community. And then I had a blast at the last 360|Flex in Atlanta, where I spoke again.

I make damn good money as a Flex developer, and I owe a lot of that to the fame and connections I made at the 360|Flex conferences. So this is my little way of paying some of that back. So thank you Tom and John for all your hard work!