Tuesday, February 14, 2012

Units of measure for array indices

In F#, arrays play an important part in optimizing performance-critical parts of your code. This is especially true on Xbox 360, where arrays of value types can help avoid snags due to slow garbage collection. Unfortunately, index out-of-bound exceptions are common when working with arrays. This post shows a little trick to help detect cases where the wrong variable is used as the index.

/// An array whose index has a unit of measure
type MarkedArray<[<Measure>] 'K, 'T> = MarkedArray of 'T[]
    member this.Content =
        let (MarkedArray arr) = this

    member this.First : int<'K> =
        LanguagePrimitives.Int32WithMeasure 0

    member this.Last : int<'K> =
        let (MarkedArray arr) = this
        LanguagePrimitives.Int32WithMeasure (arr.Length - 1)

    member this.Item
        with get (i : int<'K>) =
            let (MarkedArray arr) = this
            arr.[int i]
        and set (i : int<'K>) (v : 'T) =
            let (MarkedArray arr) = this
            arr.[int i] <- v

The interesting bit lies in the definition of this.Item. It allows to access the content of a MarkedArray using the usual array notation arr.[idx]

To illustrate how this is used, imagine you are making an Asteroids clone. You'll probably need arrays for the positions and velocities of the ships (assuming it's a multiplayer game), and similarly for the asteroids. Using units of measures as shown in the previous post will help avoid mixing speeds and positions, but it's still possible to pick a position from the wrong array.

This is the problem that MarkedArray solves, see below.
[<Measure>] type Ship
[<Measure>] type Asteroid

type State =
  { shipPositions : MarkedArray<Ship, TypedVector3<m>>
    shipVelocities : MarkedArray<Ship, TypedVector3<m/s>> 
    asteroidPositions : MarkedArray<Asteroid, TypedVector3<m>>
    asteroidVelocities : MarkedArray<Asteroid, TypedVector3<m/s>> }

let getShipPosition (state : State) (idx : int<Ship>) : TypedVector3<m> =
  state.asteroidPositions.[idx] // Fails: idx has the wrong type, expected int<Asteroid>

Note also that creating marked arrays isn't as tedious as one might fear, thanks to type inferrence
let state' = { state with shipPositions = state.shipPositions.Content |> Array.map f |> MarkedArray }

A small remark to finish off, this is how to iterate over all positions in a marked array, note the 1<Ship> increment:
for idx in state.shipPositions.First .. 1<Ship> .. state.shipPositions.Last do
By the way, both TypedVector3 and MarkedArray are available in XNAUtils on bitbucket.