Benchmarking: Data Structure Speed

Posted: December 21st, 2008 under ActionScript 3.0 Benchmarks.

Data structure trials focus on comparing speeds of variables, object types, classes, and the speed at which you can access and modify your data. The scope of testing every operation on every object is rather large, and in many ways unnecessary since you might not have an alternative. Instead, similar to the operation trials, there is specific focus on scenarios that present similar ways to create structures. Since most of these test concern different alternatives within flash it is no surprise that these trends were consistent across all computers.

Var usage, and effects of variable name length, 10,000,000 million computations per trial. Run the benchmarks: var usage, name length

  Var Usage Relative Speed Average Std. Dev.
Computer A Single Statement 0.1159 0.0075
Seperate Statements 0.1159 0.0075
Control 0.1159 0.0075

  Var Name Length Relative Speed Average Std. Dev.
Computer A One Letter 0.0350 0.0066
Five Letters 0.0370 0.0073
Fifteen Letters 0.0390 0.0075

Both of these tests included three references. I had read online that only using the var statement once (i.e. var i:int, a:Array, n:Number) would be faster than having three separate var statements, it turns out that is not at all the case. The var usage test is another test with scope issues so it makes a call to a local function to ensure that new variables are actually being created; the control for this test was a function that only declared one variable. Perhaps, a difference would be visible if you increased the number of references or the number of computations, but for all practical purposes there is no difference in cost. I believe this myth is perpetuated by programmers who either are not familiar with scope in Flash or are used to variable scope from other languages, if you declare a variable inside of a loop in ActionScript it exists in the scope of the function containing that loop.

Somewhat surprising, the length of variable names has no effect on speed in ActionScript 3.0. In most languages, it is true that longer names will incur a slight performance hit, which leads to a terrible practice of using one-letter variable names, which makes even the simplest code difficult to read. The reason why Flash is immune to this issue has to do with how Flash is compiled. There are a couple of Flash de-compilers that will take a .swf file and generate ActionScript from the byte code; there is an example of using one on gotoandlearn.com. When Flash compiles your ActionScript into byte code, it automatically renames your variables with shorter names, so make your names as long as you need them to be.

Instantiation time, 1,000,000 computations per trial. Run the benchmark instantiation time

  Variable Type Relative Speed Average Std. Dev.
Computer A Number 0.1229 0.0053
String 0.1251 0.0081
Array + 1,680% 2.2327 0.1769

In the previous tests all of the variables that were created where integer types, this benchmark is addressing the speed of creating different types. Also, because of issues with scope, this is another test that needs to call local functions so there is some additional overhead (based on the variable tests, 1,000,000 function calls takes roughly 0.0116 for Computer A). Rarely does the time to create a data type influence design, but given the results you might want to be more careful about using arrays. Across computers the difference in instantiation time for arrays ranged from +960% to 1,760%.

Array speed versus ByteArray speed, 10,000,000 computations per trial. Run the benchmarks: Array, ByteArray

  Array Relative Speed Average Std. Dev.
Computer A a[c] = b 0.5799 0.0307
b = a[c] 0.2214 0.0104
b = int(a[c]) 0.2237 0.0124

  ByteArray Relative Speed Average Std. Dev.
Computer A a[c] = b 0.5366 0.0488
b = a[c] 0.2771 0.0088
b = int(a[c]) 0.2730 0.0075

In both tests the arrays where composed of integers, and the variable b is an integer, so there should be no promotion issues. If you are unfamiliar with the difference between these two types, the top-level array is an object array, and the ByteArray stores data in bytes. The first interesting thing about these results was that casting a type to itself has essentially no cost, so never be afraid to cast objects coming out of an array if you are unsure. Second, I definitely expected the ByteArray to be faster across the board, when in reality it is about 30% slower on retrieving values (this was true on all computers). I would argue to just use which ever you are more comfortable with; personally I like the ByteArray for Booleans and integers because, while it is difficult to prove, I strongly believe that it uses less memory.

If versus Switch, 1,000,000 computations per trial. Run the benchmark: if vs. switch

  Function Relative Speed Average Std. Dev.
Computer A If 0.2993 0.0228
Switch 0.3035 0.0196
Control 0.1648 0.0077

This is another case of calling a local function, and this test needed an element of randomness (the control is a function generating one random number) so the overhead is considerable. The results seemed to be largely dependant on the number of comparisons either statement had to perform. Again, while I largely believed that a switch statement would be faster based on my knowledge of other languages, there appears to be little or no difference in ActionScript.

Class speed, 10,000,000 computations per trial. Run the benchmark: class speed

  Function Type Relative Speed Average Std. Dev.
Computer A Function + 318% 0.1357 0.0075
Getter Function + 318% 0.1421 0.0040
Direct Access 0.0440 0.0060

This test concerns the speed of accessing class data and confirms the widely held belief that accessing directly with the dot operator is faster than using a function. I used a custom vector class that I had written, both functions return the same number, which is the same class member directly accessed. I thought that a getter would be a more optimized function but there is enough overlap in the standard deviations to rule that possibility out. I would reiterate the same practices that have been ingrained into me since I started programming, if you are programming with multiple people direct access and public variables is frowned upon; furthermore, it can make bugs difficult to find and make your code more difficult to modify – but if you really need the speed use it. The increased time to use a method ranged from +150% to +585%.

The second traditional speed hierarchy of all languages is that it is faster to perform operations locally than it is to call a function in the same class, and it is even slower to call a function from a different class. I have a biased preference for code that is easy to maintain and read, it would be very tough for me to sacrifice class architecture for speed, but it is a trade off some people may want to consider – and we need to know the speed difference to make an informed decision. In general, the golden rule is to eliminate simple functions, I ran tests over Flash’s math class to determine just how complex something needed to be to merit the overhead of being a function. If you are unfamiliar with ?: syntax it is a ternary operator that is shorthand for an if else statement, if what is before the ‘?’ is true, return what is after the ‘?’, else return what is after the ‘:’.

Flash’s math class, 1,000,000 computations per trial. Run the benchmarks: floor, rounding, absolute value, ceiling.

  Operation Relative Speed Average Std. Dev.
Computer A Math.floor(Math.random()) + 2,771% (0.0919)* 0.0098
int(Math.random()) (0.0032)* 0.0121
Math.random() 0.1517 0.0071

  Operation Relative Speed Average Std. Dev.
Computer A Math.round(Math.random()) + 1,395% (0.1062)* 0.0105
int(Math.random() + 0.5) (0.0071)* 0.0124
Math.random() 0.1430 0.0051

  Operation Relative Speed Average Std. Dev.
Computer A Math.abs(Math.random()) + 670% (0.0639)* 0.0103
N < 0 ? N * -1 : N (0.0083)* 0.0063
Math.random() 0.1510 0.0135

  Operation Relative Speed Average Std. Dev.
Computer A Math.ceil(Math.random()) (0.0865)* 0.0101
N == int(N) ? N : int(N)+1 + 65% (0.1430)* 0.0096
Math.random() 0.1475 0.0080

* Since all of these tests included a call to Math.random() as a control, the speed of each control respective to the trial was subtracted from the results.

I cannot imagine anyone ever writing a function to perform a cast or a cast and an addition but that is essentially Math.floor() and Math.round(). Casts and adding are so fast that there speed is difficult to even measure, naturally, they are going to be faster than a function call. However, it really does not take much ActionScript to eclipse a flash function (which is primarily written in C++). Previously in the class speed test we learned that even an ActionScript class function call is in the 10,000,000 computations per trial family of operations, you would expect a Flash class function of the same complexity to be at least the same speed, if not faster. Again, these speeds where relatively the same across all computers

Lessons Learned:

  • Give your variables decent names, you are not increasing performance by using shorter names or abbreviations.
  • There is no real difference between naming your variables inline or with separate var statements.
  • Arrays do take a considerable amount of time to create.
  • There is no difference between an if statement and a switch statement, you should be more concerned with ranking your comparisons relative to their observed frequencies.
  • Arrays and ByteArrays have comparable speed, retrieving a value is almost twice as fast as setting a value.
  • Direct access of class members is three times as fast as accessing via a function.
  • Avoid using very simplistic functions, especially across classes.
  • Avoid repeatedly accessing a class member; store it once locally to perform all of your operations.

Again, most of these operations are fast, faster than graphics ever will be. Eliminating your simple functions, unnecessarily repeated external class function calls, and complex object initializations will save you CPU time. However, the volume of methods and initializations would have to be significant to make an appreciable change in performance. Efficient data structures should be designed and programmed from the beginning since it is often difficult or time consuming to change in later project phases. Changing the architecture of a project midstream usually takes so many man hours, for usually minimal results, that it would be prudent to look for other ways to improve performance first.

Continue to Graphics Speed

This post is part of a series:
Introduction
Methodology
Operation Speed
Data Structure Speed <-- You are here
Graphics Speed
Results

Bookmark this on Delicious

2 Comments »

  • Comment by Alan — June 21, 2009 @ 10:42 am

    1

    ‘Direct access of class members is three times as fast as accessing via a function.’

    Yes – for accessing one variable, but things get funny when you need to access multiple variables. I have done my own benchmarking and came to the same conclusions as yourself, but I got really, really weird things happening when I would access multiple properties on a class. Perhaps something to include in your tests:
    Class.a = [Sprite variable];
    Class.b = [Sprite variable];

    vs.

    Class.changeAB(a:Sprite,b:Sprite);


  • Pingback by ActionScript 3.0 Benchmark | Flash-Square — June 21, 2009 @ 6:12 pm

    2

    [...] Voici un article très complet trouvé sur le blog de Stephen Calendar, qui présente différentes techniques d’optimisation ActionScript 3.0. L’article est bien segmenté, couvre un grand nombre de pratiques, et les explications sont intéressantes. A lire ici! [...]


RSS feed for comments on this post. TrackBack URL

Leave a comment