Science & Code

• Felix August 2, 2008

  Actionscript optimization

  Code, General, Tutorial

  Since the introduction of actionscript and the beginning of game development with flash (and, more recently, with Flex oder similar tools) performance was always a big topic in the game developer community. A common source for benchmarks are the oddhammer actionscript performance tests which give a nice overview of actionscript behavior. Sadly, no benchmark is available for AS3.0; but there are enough resources out there dealing with the topic.

  However, the scope of this post is not an in-depth analysis of optimization tricks, but a broader view on the whole process. Of course I”m obligated to introduce this post with the probably most famous quote on this topic

  “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.”

  —Donald Knuth

  The principles I will present should not only hold true for actionscript but for mostly all other languages.

  Design first

  Optimization is not something you should do during coding, but afterwards. Your program should run error-free and fulfill all requirements and you should be sure that no further features must be implemented. An exception for this rule might be a severe performance drain that poses an obstacle for testing itself. However, if you encounter such a situation, chances are the problem lies not on the execution time but inside your algorithms!

  Algorithms next

  Before you roll up your sleeves and viciously butcher your code to shave of some milliseconds, think about the algorithms you are using. Do they suit the task? May there be an alternative, more fitting one? May there be hidden costs because of assumptions you made?

  I especially want to stress the last point. Hidden costs. Last year I participated in a programming exercise at the university. The task was to implement and visualize a R-tree in Java. We had a huge data file on our hands to test our implementation. At first, the visualization worked fine, but after some point we noticed a severe delay during redraws. The problem happened very suddenly, and both Michael and me could not think of any changes that may have increased the costs so dramatically — we were, of course, only thinking about changes made in the visualization, like turning on anti-aliasing etc. Finally, we managed to track down the source of the trouble. It was a simple loop:

  
  // Vector<Box> boxes;
  for( int i = 0; i < boxes.length; ++i ) {
  	Box currentBox = boxes.get( i );
  	// stuff
  }
  

  At first we used a for-each loop, but for some reason I can’t remember we needed a running index. So, naturally, we substituted the for-each loop with a simple index loop. Which was a really bad idea (and I am bit ashamed of that, but I was not used to the Java collections back then): the get(int index) method of the collection iterates through all elements until the given index is reached. It does not cache the latest requested element (thats what iterators are for), so our innocent looking loop just evolved from a linear time algorithm to a quadratic one. As it was used to traverse the huge dataset, the whole operation took ridiculously long.

  This example shows how a simple assumption can trash your whole performance. You will need an huge effort to track down these costs, so you should double-check them early and thoroughly!

  Also keep in mind that even if an algorithm has a good asymptotic upper bound it might be still slower for small instances. A good example for this is a comparison between Quicksort and a simpler sorting algorithm like Insertion sort. Although the asymptotic (average) performance of Quicksort is better, small instances (depending highly on the language you are using, this might be around a size of 100) are sorted faster by simpler algorithms. This is due to the higher costs of each step in the more complicated algorithm, which have to pay off first by reducing the amounts of steps.
  Which brings us to the next point: measuring your performance.

  Measure twice hundreds of times

  There are a huge number of factors involved in the resulting performance of your program, so theoretical considerations do not suffice. The only real way to test if a change in code results in a change in runtime (for better or worse) is profiling. Whether you do it yourself (by measuring some test case with a simple stopwatch program) or with a sophisticated tool depends entirely on the precision you want to achieve. The bottom line is: whenever you change your code, check whether it really improved the performance!
  A readable code is worth several milliseconds of execution time.

  Optimize bottlenecks

  If all of the above points have been checked, optimization may be the last option (and it should be!). But before jumping into your code and optimizing the hell out of it you should again return to the profiling step: most optimization tricks only cut the execution time by some milliseconds, making them useless in code which is not executed very frequently (an exception might be code which causes severe delays when executed, but the first step in such a case would be spreading the execution over several frames). In general: only performance bottlenecks should be optimized. Efforts to optimize each and every line of code is just a waste of time.

  Another important thing to keep in mind is the expiration date of the optimization your using. Some tricks might have worked in earlier versions of AS (or even worse: in earlier versions of the Flash Player!) but may be useless in the current.

  Runtime optimization

  A totally different approach is the usage of time/space trade-offs. The basic idea is to save once computated values and re-use them later on, hoping that some values are needed very often during execution. Doing so for a single method is also called memoization, for which Pet Tomato has written a lean and simple generic function. But even if memory is cheap and available in huge amounts, memoziation should be limited to cases where a significant improvement can be measured.

  Talking about all-purpose methods: the most common bottleneck in already optimized actionscript is object instantiation. So in order to reduce the associated overhead, instead of creating objects and destroying them afterwards, one can collect and recycle them. This technique is called ‘object pool’ and can be implemented in various ways, a good introduction can be found in this article at polygonal labs. However, beware of dangerous side-effects due to multiple references — object pool should not be used for classes which reference other objects in a complicated fashion. A good rule of thumb is: a good candidate for object pooling are classes which are primitive and widely used, i.e. points, matrices, etc.

  Conclusion

  Optimization is a very delicate and debatable topic. In general, programs should be optimized in a top-down fashion: the broad aspects — like algorithms — first; the fine ones — like single lines of code — last. Whatever technique you choose to employ, be sure not to trust your gut but only the hard facts — measured execution time.

   
   

1. Flash Links of the Day | JADBOX: Web Application Musings

   […] Science&Code: Actionscript optimization […]

   Pingback received August 5, 2008 @ 7:47 pm
2. Michael

   Don’t remind me of the story with the linked list and quadratic complexity. It is responsible for most of my nightmares whice contain an ‘O*’ in them…

   Comment written August 10, 2008 @ 9:36 pm