AlecMcE.com

Introduction

Invalidation is a pattern employed to solve problems where updating a model’s data may happen multiple times per frame, but updating the view’s rendering should happen only once. When dependencies exist between multiple models this can get complicated and potentially messy. This article looks at a solution to this mess by unifying invalidation logic into a single manager class.

The purpose of this discussion is not to offer a new class for people to take and use in their libraries so much, though you are welcome, if you should want to. Rather it is to discus a problem and my solution. Hopefully some people will learn something from reading it, and hopefully I will learn something by getting feedback about it!

The Invalidation Pattern

Consider the following simple implementation for drawing a coloured circle:

public class Circle extends Sprite
{

	private var _color:uint;
	private var _radius:Number;

	public function get color():Number { return _color; }
	public function set color(value:Number):void
	{
		_color = value;
		resolve();
	}

	public function get radius():Number { return _radius; }
	public function set radius(value:Number):void
	{
		_radius = value;
		resolve();
	}

	private function resolve():void
	{
		graphics.clear();
		graphics.beginFill(_color);
		graphics.drawCircle(0, 0, _radius);
		graphics.endFill();
	}

}

The problem here is that if in one frame I changed both the radius and the color, the resolve() function would be called twice. Though not a problem in this case, it could be if the resolve() function involved a lot of complex logic.

The invalidation pattern resolves it this way:

public class Circle extends Sprite
{

	private var _color:uint;
	private var _radius:Number;

	public function get color():Number { return _color; }
	public function set color(value:Number):void
	{
		_color = value;
		invalidate();
	}

	public function get radius():Number { return _radius; }
	public function set radius(value:Number):void
	{
		_radius = value;
		invalidate();
	}

	public function invalidate():void
	{
		... at some future point of my choosing, trigger resolve() ...
	} 

	public function resolve():void
	{
		graphics.clear();
		graphics.beginFill(_color);
		graphics.drawCircle(0, 0, _radius);
		graphics.endFill();
	}

}

Often in AS3, the invalidate() function looks like this:

public function invalidate():void
{
	addEventListener(Event.ENTER_FRAME, onEnterFrame);
}

private function onEnterFrame(event:Event):void
{
	removeEventListener(Event.ENTER_FRAME, onEnterFrame);
	resolve();
}

It is a good pattern that solves the problem of multiple resolve() calls. The actual mechanism contained inside invalidate() which causes resolve() to be called once at a convenient point is unimportant. For this sort of structure, this simple implementation does the job.

Where The Invalidation Pattern Becomes Complicated

Imagine that you have two classes: a line, and a circle, the intersection of which defines two circular segments. In fact, don’t imagine: look at this:

Both the line and circle implementations consist of two points which, on moving, invalidate the their equations. On resolve() the equations are resolved. The segments depend upon the the line and circle; when the line or circle is invalidated, they should be invalidated also.

A mechanism for the segments to know when their definiens (that which defines them) are resolved is required, suggesting that each element conforms to a common interface:

public interface Invalidates
{

	function invalidate():void;

	function get invalidated():Signal;

	function resolve():void;

}

and an implementation along these lines:

public class Line implements Invalidates
{

	private var _ax:Number;
	private var _ay:Number;
	private var _bx:Number;
	private var _by:Number;

	private var _invalidated:Signal;

	public function Line()
	{
		_invalidated = new Signal(Invalidates);
	}

	public function get ax():Number { return _ax; }
	public function set ax(value:Number):void
	{
		_ax = value;
		invalidate();
	}

	... missing a few uninteresting methods ...

	public function invalidate():void
	{
		_invalidated.dispatch(this);
	}

	public function resolve():void
	{
		... resolve the line ...
	}

}

public class Segment implements Invalidates
{
	private var _line:Line;
	private var _circle:Circle;

	... missing the constructor ...

	public function get line():Line { return _line; }
	public function set line(value:Line):void
	{
		_line = line;
		_line.invalidated.add(onInvalidated);
	}

	... missing a few uninteresting methods ...

	private function onInvalidated(definien:Invalidates):void
	{
		invalidate();
	}

	public function resolve():void
	{
		_line.resolve();
		_circle.resolve();

		... the rest of the resolution ...
	}
}

The problem here is the same problem that led us to consider the Invalidation Pattern in the first place: namely, that the Line’s resolve() method is going to get called a lot. Sure, we can pack the methods with lots if calls like:

private function invalidate():void
{
	if (_isInvalidated)
		return;

	_isInvalidated = true;
	invalidate();
}

public function resolve():void
{
	if (!_isInvalidated)
		return;

	_isInvaldiated = false;
	_line.resolve();
	_circle.resolve();

	... the rest of the resolution ...
}

However, it starts to feel like the classes are consumed with handling the invalidation management, rather than with what should be their single responsibility of properly modelling the geometrical entities for which they are named.

An important feature of this implemenation is that it guarantees that the Line’s and Circle’s resolve() methods are called before the sgement resolves. If B depends on A, then A must resolve before B resolves. This is a key feature of the Invalidation Manager, below.

Managing Invalidation

The current as3geometry library attempts to solve the problem of invalidation using the InvalidationManager.as class.

The Invalidation Manager handles classes that satisfy the Invalidates.as interface. Invalidates objects can be registered to the InvalidationManager, and dependencies can be established. As this happens, objects are categorized into tiers.

Initially, since every object is independent of each other when registered, newly registered elements are considered in tier 0. However, if a dependency is established such that B depends on A, B is put into the tier above A, so if A is in tier 0, B is in tier 1. If then C depends on B, since B is already in tier 1, C goes into tier 2.

The utility of the tiers comes from the fact that all objects in tier 0 are independent of each other and may be resolved in any order. Tiers are resolve in ascending order, ensuring that any object that is depended upon is resolved before any object which depends on it.

The problem with this approach comes when, for example, A depends on B depends on C already so they have the following tiers:

Then, if I have another object D already in tier 3, and define that B depends on D, I must move B to tier 4 and therefore also move C to tier 5.

Circularity presents an interesting problem within this system. If A depends on B depends on C, and then I define that C depends on A, the tier system breaks down. Currently attempting to create a circular reference will fail and an error will be thrown.

In order to keep the InvalidationManager clean, it does not actually handle when it resolves, but instead dispatches a signal when it has elements that require resolution. In the as3geometry implementation the AS3GeometryContext.as wraps the InvalidationManager and hooks it to the player events to so that when invalidation occurs it is resolved in good time.

The Invalidates classes, other than telling the contxt what it has a relationship to and what it does not, no longer contains any code that tries to manage other objects’ invalidations:

public class Line implements Invalidates
{

	private var _ax:Number;
	private var _ay:Number;
	private var _bx:Number;
	private var _by:Number;

	private var _context:InvalidationManagerContext;
	private var _invalidated:Signal;

	public function Line(context:InvalidationManagerContext)
	{
		_invalidated = new Signal(Invalidates);

		// elements that don't depend on other classes  like this don't really need the
		// context stored, but I store it here for consistency, and in case the structure
		// changes
		_context = context;
		context.register(this);
	}

	public function get ax():Number { return _ax; }
	public function set ax(value:Number):void
	{
		_ax = value;
		invalidate();
	}

	... missing a few uninteresting methods ...

	public function invalidate():void
	{
		_invalidated.dispatch(this);
	}

	public function resolve():void
	{
		... resolve the line ...
	}

}

public class Segment implements Invalidates
{
	private var _line:Line;
	private var _circle:Circle;

	private var _context:InvalidationManagerContext;
	private var _invalidated:Signal;

	public function Segment(context:InvalidationManagerContext)
	{
		_invalidated = new Signal(Invalidates);

		_context = context;
		_context.register(this);
	}

	public function get line():Line { return _line; }
	public function set line(value:Line):void
	{
		_line = line;
		_context.addDependency(_line, this);
	}

	... missing a few uninteresting methods ...

	private function onInvalidated(definien:Invalidates):void
	{
		invalidate();
	}

	public function resolve():void
	{
		... just resolve here! this is the big win ...
	}
}

Conclusion

A benefit to this approach is that Invalidates classes need very little boiler-plate code. The author of an Invalidates class need know only that changes should call invalidate() and that all resolution logic happens in resolve(). Responsibilities are extremely well separated.

The as3geometry implementation wraps the InvalidationManager into an AS3GeometryContext.as class that has a little more logic than the InvalidationManager, which does not have a mechanism for actually triggering the mass resolution. While the InvalidationManager handles the internal logic set-out above, the AS3GeometryContext handles hooking up the InvalidationManager to the player events.

There is a downside, of course. Currently in as3geometry, the constructor of every class contains a reference to the AS3GeometryContext, and every class stores a reference to it. It is not clear to me that this approach is avoidable, unless the manager is defined as a singleton. There are lots of good reasons why singletons are bad, not least because I might have good reason to have two parallel geometric contexts in one application.

Introduction

I was recently looking at an implementation of Conway’s Game Of Life, and was struck by the way in which the developer had constructed his grid. The Game of Life requires that you construct a two-dimensional array, but Flash does not support 2D arrays natively, so work arounds have to be found. There are slow workarounds, fast workarounds, and very fast workarounds. Of course, for very fast workarounds, we use Vector and target the Flash Player 10.

An example of Conway’s Game Of Life can be found below.

I should point out at the start that in these I am using for (var x:int = 0; x < 100; x++) loops. Using while (x--) or even while(--x > -1) may well be quicker, but here I am trying to highlight the relative speeds of the data structures that are being looped around, not the loops themselves.

Slow

public function generate():void
{
	grid = [];
	for (var x:int = 0; x < 100; x++)
	{
		grid[x] = [];
		for (var y:int = 0; y < 100; y++)
		{
			grid[x][y] = Math.random() < 0.5;
		}
	}
}

public function retrieve(x:int, y:int):Boolean
{
	return grid[x][y];
}

This is the slowest good method around. It's undoubtedly good, in that it is readable and concise. It's not so good in terms of speed though, because of the double Array reference that is required to get to the relevant reference. Array lookups are slow, and should be avoided in performance-critical areas.

Fast

public function generate():void
{
	grid = [];
	for (var x:int = 0; x < 100; x++)
	{
		for (var y:int = 0; y < 100; y++)
		{
			grid[x * 100 + y] = Math.random() < 0.5;
		}
	}
}

public function retrieve(x:int, y:int):Boolean
{
	return grid[x * 100 + y];
}

Instead of putting your 2D grid in a nested array, we can just use a one-dimensional array, and use an expression x * 100 + y within the lookup to differentiate between cells.

If you're targetting the version 9 player still, then this is probably the fastest mechanism you're going to get. (there is probably no need to, the latest Flash player penetration statistics suggests about 95% adoption in the western hemisphere, and above 90% adoption elsewhere)

Fast (again, but with Vector)

public function generate():void
{
	grid = new Vector.<Boolean>(10000, true);
	for (var x:int = 0; x < 100; x++)
	{
		for (var y:int = 0; y < 100; y++)
		{
			grid[x * 100 + y] = Math.random() < 0.5;
		}
	}
}

public function retrieve(x:int, y:int):Boolean
{
	return grid[x * 100 + y];
}

Moving to use the FP10 Vector class gives you some great benefits. The Flash Player can be told up-front how big the array is going to be, and it knows the type of element. It is all-round quicker to do it this way. However, this is not the quickest structure we can use!

Faster

public function generate():void
{
	shift = 7;
	grid = new Vector.<Boolean>(100 << shift, true);

	for (var x:int = 0; x < 100; x++)
	{
		for (var y:int = 0; y < 100; y++)
		{
			grid[(x << shift) | y] = Math.random() < 0.5;
		}
	}
}

public function retrieve(x:int, y:int):Boolean
{
	return grid[(x << shift) | y];
}

By referencing the cell using [x * 100 + y] we get the computer to do a multiplication and an addition. That's pretty quick, but while we consider these two of the most primitive mathematical operations, they are not two primitive calculations for a computer! Instead, we can use [(x << shift) | y] which replaces the multiplication and addition with a bit-shift and a bitwise disjunction. They are about as simple calculations as a computer can make, and the time it gains us is small, but significant if we are working with big grids.

I do not intend to go into the details of bitwise operations here, but for further reading, try this Wikipedia article.

Interestingly, if you try this approach with Array, it does not run as quickly as the example labelled 'Fast'. This is because, as Jackson Dunstan and JP Auclair noted, it will leave 'gaps' in the Array (for example no values will be entered in the above Vector for values, 100 - 127. For a Vector of a known size, that is not a performance problem, but Arrays work differently.

Results Summary

The results on the horizontal access are milliseconds that it took to iterate through the grid 1000 times. The difference in speed by adopting Vector and the bitwise-shift approach is to cut the calculation time by nearly a quarter. The bigger the grid is, the more this technique becomes useful.

After-Thought - Game Of Life

The Game Of Life is a grid structure, in which each cell is a Boolean switch; either 'on' or 'off'. Iteratively, the grid changes, according to a very simple instruction set:

1. Each grid cell's value is determined by the values of the eight adjacent grid cells;
2. For each cell, If exactly three of those adjacent cells are 'on', then in the next iteration, that cell will be 'on';
3. For each cell, if two adjacent cells are 'on' then in the next iteration that cell will remain in it's current state;
4. Otherwise, that cell's value in the next iteration will be set to 'off'.

At the edges, either those cells just have fewer neighbours, or the neighbours are thought to 'wrap around' the 2D space, so that the cells' universe resembles a torus in 3D space.

The result of these simple rules is an interesting pattern which is very interesting for a great number of reasons. The example below should show you what I mean. It will run only when the mouse is over the application. Click on it to break the iteration cycle and populate the cells with random data.

Introduction

RacetrackStats is an in-Flash performance profiler that gives real-time feedback about how the code it is contained within is performing. It can be found at GitHub:

http://github.com/alecmce/RacetrackStats

RacetrackStats is inspired by and seeks to move forward from Mr Doob‘s Stats package (http://code.google.com/p/mrdoob/wiki/stats)

In Action

Below is the first alpha of RacetrackStats in action.

source: http://github.com/alecmce/RacetrackStats/blob/master/test/demo/RacetrackStatsDemo.as

The SWF comprises three small animations (from left to right):

• A mixture of computation and rendering: A simple BitmapData-driven particle system attempting to model smoke using 100000 pixels and a heavy glow filter and blur filter;
• Heavy computation: A prime-factorisation algorithm, which computes 24 * 100 prime factor decompositions per frame. As it continues to run, the numbers get larger which leads to heavier calculation cycles;
• Extremely heavy rendering: A cycadelic circle pattern that has hundreds of semi-transparent circular sprites moving around and overlapping with each other.

The ‘Elastic Racetrack’

RacetrackStats attempts to go beyond Mr Doob’s Stats by measuring how the elastic racetrack is being stretched. The Elastic Racetrack was a phrase coined to describe how the original AVM1 Flash Player segmented each second into frames and attempted to balance the requirements of code, refreshing the screen and doing work like garbage collection. The AVM2 player’s model is sufficiently similar, that the name remains appropriate.

Code Execution

It does this by hooking into the Event.ENTER_FRAME and Event.RENDER events to record when portions of the code start and end. By recording when the ENTER_FRAME starts and when the RENDER starts, the intervening time is taken to be code execution.

Pre-Render Code Execution

Commonly this part of the code cycle is almost unused. If you exploit stage.invalidate and Event.RENDER in order for your classes to execute code after the main code execution has completed, then it will be captured here, between the top-priority Event.RENDER and the bottom-priority Event.RENDER calls.

Rendering

A problem is, the time between the RENDER ending and the ENTER_FRAME starting is used to draw the screen but if time is left over in which the Flash Player has nothing to do, it will idle during this time also. To counteract this, RacetrackStats attempts to throttle the FlashPlayer so that the application is always running as fast as it can, minimising, or even eliminating that idle time. I call this the “render” portion – the “Event.RENDER” event is badly named – screen rendering happens after the RENDER event has finished.

Work To Do

As soon as you add weight like this to an application, the speed at which it runs changes. By measuring the speed, you change the speed. It is the classic scientific paradox. It is mitigated by shrinking down the weight of the stats package as far as possible. At the moment, functionality rather than size is the chief concern, though I have tried to minimize the package by avoiding embedding fonts, and so forth.

I would love to hear what you think about the package, whether positive or negative. I’d also really appreciate it if you use it in your applications. If you have any problems, questions, queries or comments, please leave a comment below, or open an issue on GitHub.

The new as3signals library devised by Robert Penner offers a replacement to the native AS3 event model. One benefit is that signals are more lightweight, and therefore faster. Grant Skinner’s Performance Harness is a widely accepted library for comparing the speeds of code execution.

I found the following results on Mac OS X, Flash Player 10.0.42.34, with a release build.

When an event (signal) is dispatched but nothing is listening for it:

When an event (signal) is dispatched and handled by one method listener:

The source code for my test methods follows:

• Dispatching events without listeners
• Dispatching events with listeners

If you browse these tests, you will notice that more tests were run than I have displayed above. The graphs above reference results from running the dataEventOptimised and dataSignal methods in each context.

These tests are not scientific. No attempt has been to control for player version, computer version, computer specifications, so on and so forth. You are invited to download and run these tests for yourself. If you do, remember that testing on a release build not a debug build is appropriate, and then please post your results as a comment, particularly if your results differ from my own.

Updates

For a comparison with good old fashioned callbacks, please put on your sarcasm snorkel and visit va.lent.in’s follow up post.

From the as3signals Google Group there was a suggestion that the Flash Player 10.1 might produce different results. Here are my results; they appear to corroborate the earlier results:

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
performancetests.EventsTest (5 iterations)
Player version: MAC 10,1,51,66 (regular)
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
method...................................................ttl ms...avg ms
dataEvent                                                  2344   468.80
dataEventOptimised                                         2270   454.00
dataSignal                                                  313    62.60
simpleEvent                                                2755   551.00
simpleEventOptimised                                       2285   457.00
simpleSignal                                                174    34.80
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
performancetests.CapturedEventsTest (5 iterations)
Player version: MAC 10,1,51,66 (regular)
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
method...................................................ttl ms...avg ms
dataEvent                                                  2708   541.60
dataEventOptimised                                         2703   540.60
dataSignal                                                 1182   236.40
simpleEvent                                                2724   544.80
simpleEventOptimised                                       2717   543.40
simpleSignal                                               1042   208.40
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

Today an interesting discussion took place on Twitter, in which I was involved. It caught my attention for a variety of reasons, and I wanted to document the conversation, the problem and the solution here. It started when it was identified that Flash’s event dispatcher is sub-optimal in performance terms, and revolved around trying to find a solution.

Why replace the ENTER_FRAME?

Every event that is dispatched creates an object. An ENTER_FRAME creates as many objects per second as there are frames. If you have mutliple objects dispatching ENTER_FRAME events, that’s many objects creating event objects many times per second. Computationally, chains of “many” are one of those things you want to avoid. So, can we do better?

Doing Better

Robert Penner proposed creating an as3signal and using a MovieClip with two frames to dispatch that signal on each frame. He posted his idea to this GitHub gist.

One drawback to this approach is that it requires a MovieClip symbol with two empty frames, to which the two event dispatcher methods could be attached. I remembered reading in this excellent article by Bit 101 how using a [Frame] metadata tag would force your application to have two frames. This seemed to be what Penner needed for his functionality to work correctly, so I came up with my own GitHub gist which extends the concept. The code is also added ‘below the fold‘, at the bottom of this article.

[Update, after Jackson's comment, below] The idea behind the approach is that a frame-loop is an internal Flash player structure. It sits underneath the AS3 functionality, and so it doesn’t produce ENTER_FRAME events. By hooking into them we can produce our own iterative ‘event’ (Penner proposes using an as3signal), which doesn’t construct an object each time it is dispatched. It is a lovely idea, and quite distinct from invoking one ENTER_FRAME dispatcher on the root or stage of the application.

[Update, after Joa Ebert tweeted test results] Whether this method is superior to the ‘one-event ticker’ is open to question. Joa Ebert applied the frameloop concept to AudioBox and found no memory nor performance improvements.

Background

It all started today with a statement on Twitter from Robert Penner:

Listening to a single #AS3 enterFrame will create over 1000 event instances per minute. @robpenner

In fact, at a decent frame rate, you’re looking at 1800 event instances per minute. Across the blogosphere and on Twitter, there has been a lot of talk about the cost of object construction in AS3. People are pushing the limitations of the player, and are looking for performance optimisation wherever they can find it. Strategies such as object pooling are becoming mainstream in order to avoid the creation and destruction of objects. In the meanwhile, the internal Flash event model is creating and destroying huge numbers of objects to furnish us with an event model.

At the same time however, there has been a murmur of discomfiture about the state of the event model. (Not that I have much of a voice, but I chimed in to this debate as well!). The most notable result of this murmur was Penner’s decision to create as3signals. It is an on-going project to which I have contributed in a small way, and which I whole-heartedly support.

After Penner’s tweet, the #as3 twitterati (please tweet if there are glaring omissions from this list) became very excited indeed.

My initial thoughts led to the idea that maybe the setInterval/setTimeout functions, which are hangovers from AS2 might offer a solution – perhaps they shortcut the event system? Not only ain’t it so, they’re even worse as this Action Script Viewer deconstruction of the setInterval methods demonstrate.

So what else? Mike Chambers (aka @Mesh) in conversation with @TheFlashBum pointed towards a solution using a ‘ticker’; a single ENTER_FRAME dispatcher, and @bengarney confirmed that he also uses this technique.

It seems that @scottjanousek and @robpenner had the idea of using the player frameloop (which the solution offered here exploits) at pretty much the same time. (@scottjanousek’s tweets are protected, but it was reported by this tweet.)

Whether and how this vein of thought will develop is really interesting. It is fascinating how a tweet from one of the best-known ActionScript developers can provoke such a lot of attention from the general community. It is interesting too to see the envelope of what is possible being pushed.

Read the rest of this entry »

A common scenario in coding is to have a constant that you would like to be shared across classes. Defining the constant separately is bad because if you change the constant value in one class it does not get changed in another, and you’re likely to have a bad dose of debugging. However, defining a constant in an external class and referencing it when you need it is bad because it is really slow.

How Slow?

Using Grant Skinner’s Performance Harness I did a quick test to determine exactly how slow various mechanisms for referencing variables and constants actually are. The results are as follows (based on accessing the variable/constant 10,000,000 times!):

There isn’t a significant difference between the speed of access of member variables, local variables, or member constants. Perhaps a static constant in the same package is a little slower, but then it would only be defined as public static if it was referenced elsewhere as an external static constant, so it is inevitably a slow choice at some stage.

I tested package constants on the basis that this blog I came across suggested that I could get a performance saving by using package constants. This does not appear to be the case; or at least not significantly.

download the test source code

Yes, you probably know this already, perhaps with the expception of the package constant, which I had never considered before. However, I’d never done this test definitively and having recently come across Skinner’s test harness I thought I’d be thorough.

Suggested Solution

My technique for solving the dilemma of wanting a single source for constants but accessing them quickly is to create a static constant repository, but reference them into member constants in your speed critical classes, as follows:

A constants class:

package example
{
	public class Constants
	{
		public static const MY_CONSTANT:int = 100;
	}
}

A class that uses the constant, in time-critical code:

package another
{
	import example.Constants;

	public class TimeCritialCode
	{
		private const MY_CONSTANT:int = Constants.MY_CONSTANT;

		public function timeCriticalLoop():void
		{
			... important stuff referencing MY_CONSTANT ...
		}
	}
}