July 15, 2011 0

iteration test with arrays and vectors

By in Action Script, Professional, Programming

Since FLash 10.x is out for a while now, I’m thinking about updating my code to support typed Vectors instead of Arrays. So I made a small benchmark to get an idea of the difference between the performance of an Array and a Vector.

The benchmark creates an array and vector containing int values (assigning the same random value to a certain index in both the Array and Vector). Then various test functions are called which calculate the sum of all values.

The Array and Vector are iterated in the following manners:

  • A normal for loop starting at index 0 and increasing the index and testing it with the length.
  • A normal for loop like the previous, but caching the length of the array in a local variable.
  • A normal for loop starting at the last index and decrease the index till it reaches 0.
  • A for-each-in statement

I also tried an iteration test with for-in statement, but that took so long it gave script timeout errors.

Next to functions expecting an Array parameter or Vector.parameter I also created functions expecting a * type. This because I have a library with support methods for Array which I would like to convert to be useable with Vectors. Since there is no general Vector type the general * type has to be used.

Below is the results using 10 million int values running it on a core i5 760 (not overclocked):

-1148916945, Vector: addVectorWithFor: 100ms
-1148916945, Vector: addVectorWithForCached: 59ms
-1148916945, Vector: addVectorWithForReverse: 57ms
-1148916945, Vector: addVectorWithForEach: 226ms
-1148916945, Vector: addGeneralWithFor: 676ms
-1148916945, Vector: addGeneralWithForCached: 527ms
-1148916945, Vector: addGeneralWithForReverse: 529ms
-1148916945, Vector: addGeneralWithForEach: 220ms
-1148916945, Array: addArrayWithFor: 535ms
-1148916945, Array: addArrayWithForCached: 479ms
-1148916945, Array: addArrayWithForReverse: 475ms
-1148916945, Array: addArrayWithForEach: 189ms
-1148916945, Array: addGeneralWithFor: 683ms
-1148916945, Array: addGeneralWithForCached: 506ms
-1148916945, Array: addGeneralWithForReverse: 484ms
-1148916945, Array: addGeneralWithForEach: 189ms
-- done

The value shown at the start is the calculated sum, to be sure all test functions are working correctly.

Looking at the results the following conclusions can be made:

  • The fastest way to iterate is using a Vector and normal for loop caching the length or using a reversed for loop.
  • The for-each-in statement is the fastest way to iterate an Array.
  • The for-each-in statement takes about the same time for every test and does not seem to depend on type (Arrays seem to be traversed a bit faster then Vectors).

To run the test yourself click here.

Extra note: as a small test I also created a version with debug information included; within the debug projector the normal for loops took longer to execute while the for-each-in statements didn’t show much difference in execution time.

Below is the source of the document class being used:

package  
{
  import flash.display.Sprite;
  import flash.events.Event;
  import flash.text.TextField;
  import flash.text.TextFormat;
  import flash.utils.getTimer;
 
  /**
   * Perform iteration tests on vector and array of int values.
   *
   * @ultraforce
   * J. Munnik
   * www.ultraforce.com
   * Copyright (c) 2011 by Ultra Force Development
   * 
   * version 1
   * - initial version
   * 
   */
  public class BracketOperatorTest extends Sprite
  {
    ///
    /// CONST
    ///
 
    /**
     * Number of values to fill array and vector with
     */
    public static const COUNT: int = 10000000;
 
    ///
    /// PRIVATE VARS
    ///
 
    /**
     * Text field for output.
     */
    private var m_log: TextField;
 
    /**
     * Contains test data
     */
    private var m_intVector: Vector.;
    private var m_intArray: Array;
 
    /**
     * Current test
     */
    private var m_testIndex:Number;
 
    ///
    /// PUBLIC METHODS
    ///
 
    /**
     * Constructor
     */
    public function BracketOperatorTest()
    {
      super();
      if (this.stage)
        this.onAddedToStage();
      else 
        this.addEventListener(Event.ADDED_TO_STAGE, onAddedToStage);
    }
 
    ///
    /// PRIVATE METHODS
    ///
 
    /**
     * Add textline(s) to log window.
     * 
     * @param	aText: text to log
     */
    private function log(aText: *): void
    {
      this.m_log.appendText(aText.toString());
      trace(aText);
    }
 
    /**
     * Create test data.
     */
    private function initTest(): void
    {
      // build test lists
      this.m_intVector = new Vector.(COUNT, true);
      this.m_intArray = new Array(COUNT);
      // fill with data
      for (var index: int = 0; index < COUNT; index++)
      {
        var value: int = Math.floor(Math.random() * COUNT);
        this.m_intArray[index] = value;
        this.m_intVector[index] = value;
      }
      // reset test index
      this.m_testIndex = 0;
    }
 
    /**
     * Run various tests on an array of int and a vector of int 
     * (same number of elements and same values at every index)
     * 
     * @return true if there is another test, false if there are no more tests
     */
    private function runTest(): Boolean
    {
      // perform tests
      var time: int = getTimer();
      // perform certain test and increase test index for next call
      switch(this.m_testIndex++)
      {
        case 0:
          this.log(this.addVectorWithFor(this.m_intVector));
          this.log(', Vector: addVectorWithFor: ' + (getTimer() - time) + 'ms\n');
          break;
        case 1:
          this.log(this.addVectorWithForCached(this.m_intVector));
          this.log(', Vector: addVectorWithForCached: ' + (getTimer() - time) + 'ms\n');
          break;
        case 2:
          this.log(this.addVectorWithForReverse(this.m_intVector));
          this.log(', Vector: addVectorWithForReverse: ' + (getTimer() - time) + 'ms\n');
          break;
        case 3:
          this.log(this.addVectorWithForEach(this.m_intVector));
          this.log(', Vector: addVectorWithForEach: ' + (getTimer() - time) + 'ms\n');
          break;
        case 4:
          this.log(this.addGeneralWithFor(this.m_intVector));
          this.log(', Vector: addGeneralWithFor: ' + (getTimer() - time) + 'ms\n');
          break;
        case 5:
          this.log(this.addGeneralWithForCached(this.m_intVector));
          this.log(', Vector: addGeneralWithForCached: ' + (getTimer() - time) + 'ms\n');
          break;
        case 6:
          this.log(this.addGeneralWithForReverse(this.m_intVector));
          this.log(', Vector: addGeneralWithForReverse: ' + (getTimer() - time) + 'ms\n');
          break;
        case 7:
          this.log(this.addGeneralWithForEach(this.m_intVector));
          this.log(', Vector: addGeneralWithForEach: ' + (getTimer() - time) + 'ms\n');
          break;
        case 8:
          this.log(this.addArrayWithFor(this.m_intArray));
          this.log(', Array: addArrayWithFor: ' + (getTimer() - time) + 'ms\n');
          break;
        case 9:
          this.log(this.addArrayWithForCached(this.m_intArray));
          this.log(', Array: addArrayWithForCached: ' + (getTimer() - time) + 'ms\n');
          break;
        case 10:
          this.log(this.addArrayWithForReverse(this.m_intArray));
          this.log(', Array: addArrayWithForReverse: ' + (getTimer() - time) + 'ms\n');
          break;
        case 11:
          this.log(this.addArrayWithForEach(this.m_intArray));
          this.log(', Array: addArrayWithForEach: ' + (getTimer() - time) + 'ms\n');
          break;
        case 12:
          this.log(this.addGeneralWithFor(this.m_intArray));
          this.log(', Array: addGeneralWithFor: ' + (getTimer() - time) + 'ms\n');
          break;
        case 13:
          this.log(this.addGeneralWithForCached(this.m_intArray));
          this.log(', Array: addGeneralWithForCached: ' + (getTimer() - time) + 'ms\n');
          break;
        case 14:
          this.log(this.addGeneralWithForReverse(this.m_intArray));
          this.log(', Array: addGeneralWithForReverse: ' + (getTimer() - time) + 'ms\n');
          break;
        case 15:
          this.log(this.addGeneralWithForEach(this.m_intArray));
          this.log(', Array: addGeneralWithForEach: ' + (getTimer() - time) + 'ms\n');
          break;
        default:
          this.log('-- done');
          // no more tests available
          return false;
      }
      // more tests available
      return true;
    }
 
    /**
     * Go trough array starting at index 0 to last value.
     * 
     * @param	anArray: array to go trough
     * 
     * @return sum of all int values
     */
    private function addArrayWithFor(anArray: Array): int
    {
      var result: int = 0;
      for (var index: int = 0; index < anArray.length; index++)
      {
        result += anArray[index];
      }
      return result
    }
 
    /**
     * Go trough array starting at index 0 to last value.
     * Cache the length of the list in a local variable.
     * 
     * @param	anArray: array to go trough
     * 
     * @return sum of all int values
     */
    private function addArrayWithForCached(anArray: Array): int
    {
      var result: int = 0;
      var count: int = anArray.length;
      for (var index: int = 0; index < count; index++)       {         result += anArray[index];       }       return result     }          /**      * Go trough array starting at last value and ending at first value (at index 0).      *       * @param	anArray: array to go trough      *       * @return sum of all int values      */     private function addArrayWithForReverse(anArray: Array): int     {       var result: int = 0;       for (var index: int = anArray.length - 1; index >= 0; index--)
      {
        result += anArray[index];
      }
      return result
    }
 
    /**
     * Go trough array starting using for each statement.
     * 
     * @param	anArray: array to go trough
     * 
     * @return sum of all int values
     */
    private function addArrayWithForEach(anArray: Array): int
    {
      var result: int = 0;
      for each(var value: int in anArray) result += value;
      return result
    }
 
    /**
     * Go trough a general value starting with the value at 
     * the first index and ending with the value at the last index. 
     * 
     * Assume the list has a length property and use the [] operator to 
     * access the values inside.
     * 
     * @param	anArray: general value to go trough
     * 
     * @return sum of all int values
     */
    private function addGeneralWithFor(anArray: *): int
    {
      var result: int = 0;
      for (var index: int = 0; index < anArray.length; index++)
      {
        result += anArray[index];
      }
      return result
    }
 
    /**
     * Go trough a general value starting with the value at 
     * the first index and ending with the value at the last index. 
     * 
     * Assume the list has a length property and use the [] operator to 
     * access the values inside.
     * 
     * Cache the length of the list in a local variable.
     * 
     * @param	anArray: general value to go trough
     * 
     * @return sum of all int values
     */
    private function addGeneralWithForCached(anArray: *): int
    {
      var result: int = 0;
      var count: int = anArray.length;
      for (var index: int = 0; index < count; index++)       {         result += anArray[index];       }       return result     }          /**      * Go trough a general value starting with the value at the last       * index and ending with the value at the first index.       *       * Assume the list has a length property and       * use the [] operator to access the values inside.      *       * @param	anArray: general value to go trough      *       * @return sum of all int values      */     private function addGeneralWithForReverse(anArray: *): int     {       var result: int = 0;       for (var index: int = anArray.length - 1; index >= 0; index--)
      {
        result += anArray[index];
      }
      return result
    }
 
    /**
     * Use for each statement on a general value.
     * 
     * @param	anArray: general value to go trough
     * 
     * @return sum of all int values
     */
    private function addGeneralWithForEach(anArray: *): int
    {
      var result: int = 0;
      for each(var value: int in anArray) result += value;
      return result
    }
 
    /**
     * Go trough a int vector starting with the value at the first 
     * index and ending with the value at the last index. 
     * 
     * @param	anArray: int vector to go trough
     * 
     * @return sum of all int values
     */
    private function addVectorWithFor(anArray: Vector.): int
    {
      var result: int = 0;
      for (var index: int = 0; index < anArray.length; index++)
      {
        result += anArray[index];
      }
      return result
    }
 
    /**
     * Go trough a int vector starting with the value at the first 
     * index and ending with the value at the last index. 
     * Cache the length of the list in a local variable.
     * 
     * @param	anArray: int vector to go trough
     * 
     * @return sum of all int values
     */
    private function addVectorWithForCached(anArray: Vector.): int
    {
      var result: int = 0;
      var count: int = anArray.length;
      for (var index: int = 0; index < count; index++)
      {
        result += anArray[index];
      }
      return result
    }
 
    /**
     * Go trough a int vector starting with the value at the last 
     * index and ending with the value at the first index. 
     * 
     * @param	anArray: int vector to go trough
     * 
     * @return sum of all int values
     */
    private function addVectorWithForReverse(anArray: Vector.): int
    {
      var result: int = 0;
      for (var index: int = anArray.length - 1; index >= 0; index--)
      {
        result += anArray[index];
      }
      return result
    }
 
    /**
     * Go trough a int vector using for each statement.
     * 
     * @param	anArray: int vector to go trough
     * 
     * @return sum of all int values
     */
    private function addVectorWithForEach(anArray: Vector.): int
    {
      var result: int = 0;
      for each(var value: int in anArray) result += value;
      return result
    }
 
    ///
    /// EVENTS
    ///
 
    /**
     * Instance is added to stage; run it.
     * 
     * @param	anEvent: event object (default is null)
     */
    private function onAddedToStage(anEvent: Event = null): void 
    {
      this.removeEventListener(Event.ADDED_TO_STAGE, onAddedToStage);
      this.m_log = new TextField();
      this.m_log.width = this.stage.stageWidth;
      this.m_log.height = this.stage.stageHeight;
      this.m_log.multiline = true;
      this.m_log.wordWrap = true;
      this.m_log.setTextFormat(
        this.m_log.defaultTextFormat = new TextFormat('_sans')
      );
      this.addChild(this.m_log);
      this.initTest();
      this.addEventListener(Event.ENTER_FRAME, onEnterFrame);
    }
 
    /**
     * Run a test. Stop listening to events if tests have finished.
     * 
     * @param	anEvent: event
     */
    private function onEnterFrame(anEvent: Event): void 
    {
      if (!this.runTest()) 
        this.removeEventListener(Event.ENTER_FRAME, onEnterFrame);
    }
  }
}

Tags: , , ,