This post is the continuation of the basic knowledge article Why we need a collection framework in ActionScript and introduces you to the benefits of collections more from a technical perspective.

Note to the performance tests in this article

This article contains a number of performance test results. The tests have been executed using a small testing harness which can be found at the sibirjak google code page. The column header of the tables showing those results use the following abbreviations. The measured time is displayed in milliseconds.

Definitions and overview

Definitions

First of all a small definition of the term collection used in this article. A data container is meant any data structure that holds a number of distinctive objects in order to return at a later time. The built-in data containers in Flash are Array, Vector, Object and Dictionary. A collection is then furthermore a data container …

• with a generalised API that fully abstracts from the actual implementation
• and a high degree of reusablility (not narrowed to a special operation purpose).

Collections do not try to replace the built-in containers but aim to extend those with functionality and common algorithms. Many programming languages carry a collections framework in its core libraries. In ActionScript we unfortunately need to implement collections individually. This situation has brought us already a lot of approaches to establish an ActionScript collections framework.

Common reasons to use collections

Besides the availability of a convenient API, collections are preferred to add specific functionality, to gain reliability or to increase the performance of certain operations. Especially the latter might be confusing at the first glance. Indeed, all built-in containers have their specific implementation and therefore distinctive benefits and disadvantages.

This article shows how the choice of an appropiate collection may improve the runtime performance of ActionScript applications by providing interesting examples and performance test results. The article starts with a description of situations where we typically use containers to collect data and what the different requirements to such containers are. The second part examines the built-in Array and Dictionary and how they can fit the indentified requirements. The third (and last) part discusses several collections and common approaches to implement them.

Aspects of using data containers

Software applications may need to collect data for various reasons. Each of those reasons implies a preferred way how elements are stored, retrieved or removed from the data container. Different problem situations may be solved best using an adequate container or vice versa, there is no multipurpose container that fits all kinds of requirements. This chapter shows a random list of situations where we typically use data containers.

Embedded inventory

The most obvious use case of collecting data is to make up a (hard coded) inventory which serves as a data base in the class or even in the entire application. The data in the inventory should have a stable order and provide at least fast sequential access (from the first to the last item).

1
2
3
4
5
6
7
8

Proxy

A proxy is an internal representation (or a cache) of data stored elsewhere, e.g. on a remote server. The proxy should use the same ordering as the orginal repository. Since data between client and server is exchanged and identified using an object ID, we like to address (find, add, remove) items in the proxy by using IDs.

1
2
3
4
5
6
7

Relations between objects

One-to-many relations can be expressed using a link table. The table do not need to have an order but should allow fast look up a relation by a given object.

1
2
3
4
5
6

Wrapper

Encapsulated components often store data in its own fashion by adding specific information to the given data objects using composition. To enable the user to operate the component with the orginal data, the component hosts an internal look-up table which maps objects to its wrappers.

1
2
3
4

Grouping objects

To return a group of objects from a method (or to pass to) we use a container. In the most of the cases the order of items returned is important.

1
2
3
4
5
6

Temporary containers

Often we set up local containers temporarily to find duplicates, to count instances, to store items matching a certain criterion or to prepare a data structure before further processing it. Sometimes a plain array does the work, sometimes a look-up container such as Object or Dictionary. In a number of cases we need a combination of both to preserve the original order while achieving fast look-up.

1
2
3
4
5
6
7
8
9
10
11
12

More specific software problems

A queue is an ordered container where we want to add at end and to remove at start. In a stack we add and remove always “at end”. A searchable index maintains a sort order, and items shall be addressed instantly by instance. And so on.

1
2
3
4
5
6
7
8
9

Binding data to user interfaces

Data driven user interface controls (List, SelectBox, DataGrid) often shall be updated automatically if the assigned data source changed. The data container then needs to dispatch change notifications.

Summary

The illustrated situations above show different and often mutually exclusive requirements to the desired data structure solution:

• The kind of order of the items (no order necessary, order by insertion, sort order).
• Sequential (for-loop, iterator) or random access (index, key, item by instance) to the items.
• High performance of adding and removing in front (or in between or at end) of a sequence of items.
• High performance of finding an element.
• Fast access to the lowest or highest element in a collection.
• Permission of multiple instances of an element (or not).
• Mapping of items by preserving a particular order of the entries.
• Enabling data binding by dispatching change notifications.

In the most of the situations we especially count only on a specific feature of a data container. This leads to the question if there are containers that fit the particular requirements better than others. The next chapter discusses how the Flash built-in data containers Array, Object and Dictionary might be used (or not) to solve common data handling problems.

Array and Dictionary – Features and Weaknesses

The Array

The Array is apparently the fastest possibility of storing elements sequentially. However, adding to (or removing from) an array requires the array to internally shift the position of all succeeding items by the number of elements added. This shifting is the more expensive the more the insertion occurred in front of the array and the longer the array is. Michael Baczynski (polygonal.de) has visulalised this behaviour in its linked list example.

Another consideration (and common trap) is the time required to find (or remove) an element within an array. Since the array is not a look-up container, the array needs to test each item for equality which is the more expensive the more longer the array is.

The table below shows the runtime of adding or removing at start or at end as well as the performance of the look-up operations has and remove.

Array tests source code

Keeping an array sorted

In many cases a container that maintains a sort order is desired. Such a container stores and returns its items always based on a sort critlerion. Applications could be a phone book, a high score list, a performant searchable index or a priority queue. A simple implementation would be to sort an array after each insertion operation. However, this approach does not scale as the following table shows.

Array tests source code

Another consideration regarding the sorted array. The built-in sort method does not preserve the formerly order of equal items. If it is important to sort equal items in the order they were inserted, the Array.sort() method cannot be used.

1
2
3
4
5

The Dictionary

The Dictionary is a look-up container where elements can be accessed instantly using a unique key. The Dictionary maintains no order of items and does not provide information about the number of elements contained. Operations based on keys perform in nearly constant time. Finding (or removing) of items is significantly slower than done with an array.

Dictionary tests source code

Another consideration of the Dictionary is its missing type safety. While everything is going well with complex keys, a primitive key is stored by its string representation rather than its original value as the following code example shows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

The missing type safety may cause serious errors or at least confusion. For example the algorithm to test if two arrays contain the same elements would not work reliably with an unmodified Dictionary. This algorithm populates a map with the number of occurrences of each element contained by both given arrays.

Dictionary used as a set

As shown, Array and Dictionary are basically slow in finding or removing items. Nevertheless, it is possible to assign the actual item (which we want to access instantly) in the key property of a Dictionary entry. All items then have to be unique.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

The features of such a set are the same as of the Dictionary: No order, no size information, no type safety … but a striking performance in locating objects .

Summary

The Flash containers are sufficiently for the most operations. Nevertheless, there are certain situations where performance, functionality and reliability leave something to be desired.

Performance

Adding or removing items in front of an array is a comparatively slow process. Thus, using an array as a queue is not the optimal solution, and a linked list performs much better (as we will see later in this article).

Finding items in an array or in a Dictionary instance requires linear time (the more elements the more time). As shown in the snippets above, we often want to find an item instantly. Fast item look-up can be achieved by using a Dictionary as a set.

Keeping an Array instance sorted calling its built-in sort after each insertion operation is a serious performance leak.

Functionality

The Dictionary does not reveal how many items it contains. Calculating such a size value can be done only with a loop over the entire contents which requires linear time.

The Dictionary does not provide any order of items. Fast key or item look-up (when used as a set) while maintaining a particular order is natively not possible. To anyhow obtain an ordered or sorted map (or set) we need to combine the Dictionary with an additional container that stores the item order.

Neither Array nor Dictionary support data binding. It is possible to wrap both containers to control all insertion or removal operations and dispatch reliable change notifications.

Reliability

The Array sort method is not stable which may cause confusion or even problems.

The Dictionary stores a primitive key always in its string representation. Different keys that have the same string representation are considered as identical (1 = “1″, true = “true”). Algorithms that rely on the Dictionary may fail if not considered.

Common collections and their implementation

Array wrapper (ArrayList)

An array wrapper is the most often encountered collection implementation. The most famous array wrapper is the Flex ArrayCollection. There are many reasons to create an ArrayList.

One goal is to control the way how items are added or removed. For example, it is possible to only permit inseration and removal at the end of an array which results then in a stack realisation.
Another goal is the simplification of the Array interface. For example arrayList.addAt(10, item) is fare more intuitive than array.splice(10, 0, item). By the way, who knows the difference between slice and splice without have an eye at the docs?
Often the array wrapper offers additional methods that easify the array handling (count, removeAll, lastIndexOf). The ArrayList might implement a stable sort that is used instead of the not stable built-in array sort.

1
2
3
4
5
6

Basic array wrapper implementation in ActionScript
AS3Commons ArrayList usage example

Performance

The basic array wrapper has nearly the same runtime as an unwrapped array.

Basic array wrapper tests source code
Array tests source code

Linked list

A linked list is the most important alternative to an array to achieve a succession of elements. The list is made up of mutually linking nodes where a single node is a plain data object holding a reference to its successor, predecessor and the actual data added.

Adding or removing of items costs always the same (constant) time because only the links between two or three nodes have to be updated. However, the linked list does not support index access (addAt, getAt, removeAt). Finding elements in a linked list is as expensive as in an array (has, remove).

A linked list is the preferred solution to realise a queue interface. Several data structures utilise a linked list (rather than an array) to maintain element succession.

Basic linked list implementation in ActionScript
AS3Commons LinkedList usage example
Linked list at Wikipedia

Performance

As the table shows, the average performance of insertion or removal operations of a linked list is significantly better than of an array.

Basic linked list tests source code
Array tests source code

Map

The (basic) map is an unordered container enabling fast key look-ups. A typical map implementation uses an array to host the values and a hashing function to calculate from a given key the index position where the value should be added (or can be found). This is actually not trivial, and fortunately we have in ActionScript the Dictionary that hides all the implementation details and can be used to create a map collection.

The map extends the Dictionary to add an instant size information and to fix the problem of type unsafety (shown in the Dictionary example above). String typed keys are separately stored in an Object instance which lets decide if a given primitive key really exists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Basic map implementation in ActionScript
AS3Commons Map usage example

Performance

The performance of the basic map is comparable to that of the Dictionary.

Basic map tests source code
Dictionary tests source code

Set

The set is in fact a map where only the keys are from interest. The set implementatin follows the same principles as the of the map: An Object is used to store the string typed keys, an instant size informatin is available.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Basic set implementation in ActionScript
AS3Commons Set usage example

Performance

The look-up operations has and remove operate in nearly constant time.

Basic set tests source code
Array tests source code

Sorted array

To get an array to keep a certain sort order it is the most performant solution to add items using the binary search algorithm. The search returns the index position where a given item should be added. Finding an element within the sorted array also uses a binary search.

AS3Commons SortedList implementation
AS3Commons SortedList usage example
Binary search algorithm at Wikipedia

Performance

The AS3Commons SortedList is an application of a sorted array and used here in the performance tests. Adding items to an array using the binary search algorithm (as the SortedList does) is significantly faster than adding items combined with a subsequent sort.

Adding items to a sorted array is slower than appending items to an unsorted array. Finding or removing elements is faster done with a sorted array.

AS3Commons SortedList tests source code
Array tests source code

Binary search tree

A binary search tree is the composite counterpart to a sorted array. The tree is made up of nodes where a single node is a plain data object holding a reference to its parent node, its left and right child and the actual data added. The value of the left child is always lesser, the value of the right child always greater than the value of a parent node.

Finding an element in a tree starts with the root node and continues with the left child node if the given value is lesser and with the right node if the given value is greater than the value of the parent node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

A binary search tree is used (like a sorted array) to achieve a persistant sort order in that finding of elements is comparable fast. The tree might be used as a priority queue where items are stored and returned depending on a given priority. The tree also may be used in combination with other structures to realise a sorted collection such as a sorted map or a sorted set.

The weakness of a binary search tree is its addiction to degenerate. In the worst case the tree consists of only left nodes or only right nodes. Finding elements in a degenerated tree may cost linear time since each node has to be compared. There are several tree implementations that deal with the problem. A treap is one of them.

AS3Commons Treap implementation
AS3Commons Treap usage example
Binary search tree at Wikipedia

Performance

The performance test uses the AS3Commons Treap and SortedList collections. It reveals, the binary search tree is not actually faster than a sorted array. However the sorted array suffers from the bad performance of (adding and) removing items in front of an array in general where the tree operations take the same time at all positions.

AS3Commons Treap tests source code
AS3Commons SortedList tests source code

Ordered map

A basic map does not have any succession order but this order may be realised by combining a map with a linked list where the map internally links a given key with a linked list node.

Basic ordered map implementation in ActionScript
AS3Commons LinkedMap usage example

Performance

For order related operations, the ordered map requires about the addition of time of a basic map and a linked list. For example removing at start takes 39ms which is the time needed to remove at start from a linked list (2ms) plus the time needed to remove a key from the map (37ms).

Basic ordered map tests source code
Basic map tests source code
Basic linked list tests source code

Ordered set

A basic set does not have any succession order but this order may be realised by combining a set with a linked list where the set internally links a given item with a linked list node.

Basic ordered set implementation in ActionScript
AS3Commons LinkedSet usage example

Performance

For order related operations, the ordered set requires about the addition of time of a basic set and a linked list. For example removing at start takes 39ms which is the time needed to remove at start from a linked list (1ms) plus the time needed to remove an item from the set (37ms).

While the Array slows down, finding or removing of items is done as fast it can be with an ordered set.

Basic ordered set tests source code
Basic set tests source code
Basic linked list tests source code
Array tests source code

Sorted map

A basic map does not have any succession order. A sort order may be realised by combining a map with a binary search tree where the map internally links a given key with a tree node.

AS3Commons SortedMap implementation
AS3Commons SortedMap usage example

Performance

The performance test uses the AS3Commons SortedMap, Map and Treap implementations. For order related operations, the sorted map requires about the addition of time of a basic map and a treap.

AS3Commons SortedMap tests source code
AS3Commons Map tests source code
AS3Commons Treap tests source code

Sorted set

A basic set does not have any succession order. A sort order may be realised by combining a set with a binary search tree where the set internally links a given item with a tree node.

The difference between a sorted set and a binary search tree is the performance of item based operations. While the tree needs to find a related node within its structure, the sorted set uses an internal Dictionary to instantly access this node.

AS3Commons SortedSet implementation
AS3Commons SortedSet usage example

Performance

The performance test uses the AS3Commons SortedSet, Set, Treap and SortedList implementations. For item based operations the set is significantly faster than the treap. For all other operations, the sorted set requires about the addition of time of a basic set and a treap.

Item based look-up operations (has, remove) are faster in a sorted set than in a sorted array. Removing of items from the sorted array has to take in account the time to shift the internal array indices. Here the sorted set has a far better average performance.

AS3Commons SortedSet tests source code
AS3Commons Set tests source code
AS3Commons Treap tests source code
AS3Commons SortedList tests source code

Summary

There is more than just arrays

Array and Dictionary are not the only possibilities to realise data containers in ActionScript. Choosing an alternative to Array and Dictionary is often valuable for the reasons of performance, functionality and reliability.

This article has shown several examples where the the built-in containers do not suffice and what implementations can better solve specific problems. An array wrapper might be used to control the array access and to add functionality, the linked list has a better performance of insertion and removal operations than an array, sorted list or binary search tree are very fast containers to maintain a persistent sort order, a custom map can fix an unsatisfying behaviour of the Dictionary and add introspection, the different set implementations provide fast access by instance, the ordered map saves the insertion order while elements containted by a sorted map are kept in a sort order.

Decide reasonable

All introduced collections have specific benefits and disadvantages. It depends on the special software problem what data container fits the best. Usually we need only a small and specific subset of the entire functionality of a data container. It is worthy to spend some time to analyse the problem and depending on that to choose an appropriate container. The following list suggest a few questions that may be asked.

• Is any succession of elements required?
  • Could a sorted structure be more performant?
• Is random access required (index, key, item by instance)?
  • Yes: What access type could be the best?
  • No: Are there lot of reads and writes in between a sequential container?
• Are duplicates permitted?

AS3Commons collaboration project

While in other languages the use of collections is highly popular, it isn’t in ActionScript. The reason might be a missing standard library. However, the algorithms used to implement collections are general, and the different ActionScript solutions we can find in the web are pretty similiar. Leads to the question, why we still do not have a unified collections framework in ActionScript

The AS3Commons project is a (yes, again another!) community approach to create a repository of reusable ActionScript components. I have contributed to the collections library there. If you have any feedback, you are welcome. Thank you.

AS3Commons collaboration project
AS3Commons Collections homepage