Array Ordering in ActionScript 3

Update: I filed a bug about this issue.

coils This post starts out with a finite state machine, but it ends up talking about how iteration is implementing in ActionScript.

There I was – implementing a finite state machine. Each state had transitions, and the transitions are named and, additionally, processed in order. This is useful because you can order your transitions for consideration from most to least specific. Usually the last transition is unconditional.

Unfortunately, I began encountering issues with users who had the release player installed. Enemies would move erratically and transition between states inappropriately. Adding and removing log statements would sometimes make the problem go away, other times not. I suspected the VM or compiler.

As you may be aware the for and for each keywords in Flash are not guaranteed to iterate over keys or values in a consistent order. And of course, my loop for checking transitions looks like:

      	// Evaluate transitions in order until one goes.
      	for each(var t:ITransition in Transitions)
      		if(t.Evaluate(fsm) && fsm.SetCurrentState(t.GetTargetState()))

The icing on the cake is the hashtable implementation in Tamarin, which is used internally for storing object properties as well as (partially) for Arrays. Whenever you store a value by key, the key is converted to an atom, and the atom is used as the key for the hash table look up. Atoms are (basically) pointers, so the location in the hash table is based on the memory allocation pattern of your SWF (as well as the allocations of the player binary you are using). (See HashTable::find for the implementation behind this.)

In other words, the order of iteration will be random, but consistent for a given combination of player binary and SWF (and execution pattern). In my case, the iteration order was what you’d expect (order of addition to the Array) for debug player, and backwards for release player. A case of good luck turning bad, since it led me to believe that everything was working correctly in the debug player.

How does this relate to the log statements I mentioned earlier? Because iteration order is tied to memory allocations, it looked like a VM or compiler bug, since adding or removing code would change memory allocation patterns.

From this experience, I have two pieces of knowledge to share.

First, if you need to have both non-integer keys and values, but want to iterate in a specific order, you can’t use any of the built-in ActionScript classes. Instead, use a class like’s AssociativeArray, which subclasses flash.utils.Proxy to implement custom iteration logic.

Second, some parts of ActionScript do iterate in a consistent order:

  • “Dense” Arrays will iterate in order from first to last element. You can see the implementation for this in ArrayObject. “Dense” mode is heuristic but activated by having numeric indexes, especially starting at zero.
  • XML nodes. Children have a definite order based on the document and are iterated in this order.

The docs don’t describe this, to the best of my knowledge, which is why I post here. The best I can find is this from the online docs:

For example, you can use a loop to iterate through the properties of a generic object (object properties are not kept in any particular order, so properties may appear in a seemingly random order)

Is there any more information out there? I’d like to think I’m overlooking something!

Thanks to Steven Johnson of Adobe – his feedback was essential in the process of sorting this out. Creative Commons picture by davebluedevil.

Author: Ben Garney

See and @bengarney for details.

3 thoughts on “Array Ordering in ActionScript 3”

  1. In this case, I'm using a serialization system to fill the array, and it's easier to make (or borrow) an Array-compatible class that preserves the order than it is to change the serialization system.In a more general context, PHP lets you have ordered associative arrays, and it's quite useful – you often store results from a database indexed by primary key and ordered by the order your SQL query returned them, for instance. Maybe having a built-in way to do that in Flash would be helpful (even if the default Array doesn't).I wish they would document what WILL be in order and what won't, though. That's part of what cost me two days to fix this problem.

  2. Interesting observation about the atom ordering…but if a specific order is important to your code, why not push/unshift your transitions into a second (tightly-packed) array as they're initialized, then iterate over that one? Or maybe drop a marker variable onto your ITransition type and have the Transitions work as a linked list?

Comments are closed.