ActionScript3 Number Buffers

2012-09-21

Updated: 2012-09-22

For the young ones and the older nostalgics out there who want to know what it was like to program Java in the mid-to-late '90s, I can recommend a round of ActionScript 3. The VM it runs on, the ActionScript Virtual Machine [a], is slow at allocating objects and suffers from GC pauses, the collections API is slow and in general, it's just like pre-HotSpot [b] Java.

With that off my chest and out of the way, let's drag Flash a little bit closer to the millenium and hope it doesn't die from some unknown Y2K [c] bug.

1. The Problem

Flash is good at one thing - throwing polygons onto the screen. However, since Flash is bad at optimizing function calls, however, you should try to pack as many polygons into each throw as possible. The way to do this is to pass vertex buffers to the drawing API.

A vertex buffer is simply a Vector of Numbers, and the problem is: How do we create this buffer fast enough?

2. Vector.<Number>

Let's start with the obvious method. We create the vector and push the vertices:

var v:Vector.<Number> ();
// 1st vertex
v.push (0, 0, 0); 

// 2nd vertex
v.push (1, 0, 0); 

// 3rd vertex
v.push (0, 1, 0); 

drawTriangle (v);

This works, but it is slow. The Vector[d] starts off with too little internal storage to hold all the coordinates, which means that the push sometimes will result in an internal re-allocation and copy of the old buffer. We can do better if we pre-allocate the whole buffer in the constructor call:

var v:Vector.<Number> (9);

// 1st vertex
v[0] = 0; v[1] = 0; v[2] = 0;

// 2nd vertex
v[3] = 0; v[4] = 0; v[5] = 0;

// 3rd vertex
v[6] = 0; v[7] = 0; v[8] = 0;

drawTriangle (v);

This is a lot faster. To run, at least; you'll be paying in the time it takes to write all those indices. The obvious next step is to encapsulate this in a utility class.

3. NumberBuffer

We start by taking a look at Java's java.nio.Buffer[e] API, and whip up a NumberBuffer.

/**
 * A fast vector of Numbers.
 * 
 * @author Leo Sutic leo@sutic.nu
 */
public class NumberBuffer 
{
    public var buffer:Vector.<Number>;
    public var length:int = 0;
    public var read:int = 0;
    
    public function NumberBuffer(size:int) {
        buffer = new Vector.<Number> (size);
    }
    
    /**
     * Reads the next Number from the buffer.
     * 
     * @return the number at the read pointer
     */
    public function next () : Number {
        var n:Number = buffer[read];
        ++read;
        return n;
    }
    
    /**
     * Writes a single number to the buffer.
     */
    public function write (n:Number) : void {
        buffer[length] = n;
        ++length;
    }
    
    /**
     * Copies the contents of another 
     * NumberBuffer into this buffer.
     * 
     * @param source the buffer to copy from
     * @param off the start offset in the source 
     * buffer to copy
     * @param len the number of elements to copy
     */
    public function copy (source:NumberBuffer, 
        off:int, len:int) : void {
        var srcVec:Vector.<Number> = source.buffer;
        var dstVec:Vector.<Number> = buffer;
        var end:int = off + len;
        for (var i:int = off; i < end; ++i) {
            dstVec[length] = srcVec[i];
            ++length;
        }
    }
        
    /**
     * Resets the buffer without affecting the
     * underlying Vector.
     */
    public function reset () : void {
        length = 0;
        read = 0;
    }
    
    /**
     * Sets the read pointer to 0.
     */
    public function beginRead () : void {
        read = 0;
    }
}

4. NumberBufferStack

Finally, to get rid of the object allocation cost as we allocate and use buffers on each frame, we will borrow a trick from games programming - the per-frame stack allocator [f][1]. The idea here is that we start each frame with no buffers in use, and at the end of each frame we have also no buffers in use. The time each buffer is used is bounded by the beginning of frame rendering and the end. Therefore we can maintain a list of buffers and just hand them out in order throughout the frame rendering. At the start of the render, we hand out buffer[0], then buffer[1] up to buffer[n]. Since we render a lot of pixels with each buffer, n will be small enough to be manageable. At the end of each frame, we simply reset the "next buffer to hand out"-pointer to zero; and we're ready for the next frame. The result is code that looks like this:

function beginFrame () : void {
    ...
}

function renderFrame () : void {
    var b:NumberBuffer = pool.get ();

    // Use b, don't dispose it
    ...
    
    // Use another buffer
    var b2:NumberBuffer = pool.get ();

    // Use b and b2, don't dispose
    ...
}

function endFrame () : void {
    // Dispose *all* used 
    // buffers in one go.
    pool.disposeAll ();
}

Here's the implementation:

/**
 * A stack allocator for number buffers.
 * 
 * @author Leo Sutic leo@sutic.nu
 */
public class NumberBufferStack
{
    /**
     * The pool of NumberBuffers.
     */
    private var pool:Vector.<NumberBuffer> 
        = new Vector.<NumberBuffer> ();
    
    /**
     * Number of NumberBuffers in the 
     * pool vector.
     */
    private var inPool:int = 0;
    
    /**
     * Number of NumberBuffers from the 
     * pool vector that have been given 
     * out.
     */
    private var poolUsed:int = 0;
    
    /**
     * Initial buffer size when creating
     * new NumberBuffers.
     */
    private var initBufferSize:int;
    
    /**
     * Creates a new stack.
     *
     * @param initBufferSize initial buffer 
     * size for the NumberBuffers that are 
     * created as needed.
     */
    public function NumberBufferStack (
        initBufferSize:int) {
        this.initBufferSize = initBufferSize;
    }
    
    /**
     * Obtains a new number buffer from this 
     * stack.
     * @return an empty NumberBuffer
     */
    public function getNumberBuffer () 
        : NumberBuffer {
        
        var n:NumberBuffer = null;
        if (inPool == poolUsed) {
            n = new NumberBuffer (initBufferSize);
            pool[inPool] = n;
            ++inPool;
            ++poolUsed;
            return n;
        }
        n = pool[poolUsed];
        n.reset ();
        ++poolUsed;
        return n;
    }
    
    /**
     * Deallocates all buffers that have been 
     * given out.
     */
    public function disposeAll () : void {
        poolUsed = 0;
    }
}

4.1. For Large Values of n

For large values of n, a mark / reset mechanism can be implemented. The mark function will push the current poolUsed value onto a stack, and reset pops the value back. This has the effect of disposing all buffers since the last call to mark.

Footnotes

Links

2012-09-21, updated 2012-09-22

Nikon D3200 Sharpness

Bigshot JavaScript Performance Lessons

#as3, #tech

ActionScript3 Number Buffers

​1. The Problem

​2. Vector.<Number>

​3. NumberBuffer

​4. NumberBufferStack

​4.1. For Large Values of n