Things that don't work on Xbox

Although it is possible to write F# code that runs on the Xbox 360 using XNA Game Studio, not everything works.

There are API problems, probably due to the fact that the F# core assembly I am using is built for the compact framework. Although the .NET framework on the Xbox 360 is based on the compact framework, there are obviously significant differences.
I hope I will be able to take a look at this when Microsoft releases the source code of the F# code library in an easily compilable form (the F# team has said that they intended to release the F# compiler and libraries under an Open Source license when it reaches a stable state).

For instance a call to sprintf (for debugging purposes) resulted in an exception, due to a missing method, it seems.

Similarly, attempts to use async workflows also fail. This is really a shame, as it means you are on your own when it comes to concurrent applications. For instance, the map_parallel function I used in tutorial 7 raises an exception.

In addition to binary compatibility issues specific to F#, there are also generic practical issues.

After implementing my own version of Async.Parallel, I realized it probably would not be much help, as the overhead of multi-threading is a bit too much for the time intervals of computations which must run in a 60th of a second (16.7 ms). Using parallel_map resulted in a factor two performance drop, in my case. For those interested, here is the code I was using (no guarantee of correctness of any kind!):

let map_parallel (func : 'T0 -> 'T1) (data : 'T0[]) : 'T1[] =
    let results = Array.zeroCreate data.Length
    let num_threads = 4
    let ranges = Array.init num_threads (fun i -> i * data.Length / num_threads, (i + 1) * data.Length / num_threads - 1)

    let count = ref num_threads
    let notify = new System.Threading.AutoResetEvent(false)
    
    for (start, stop) in ranges do
        System.Threading.ThreadPool.QueueUserWorkItem (
            fun _ ->
                try
                    for i in start..stop do
                        results.[i] <- func data.[i]
                finally
                    let n = System.Threading.Interlocked.Decrement count
                    if n = 0 then
                        System.Threading.Thread.MemoryBarrier()
                        notify.Set() |> ignore
        )
        |> ignore
    
    notify.WaitOne() |> ignore
    results

What works well is to dispatch rendering and updating on two threads. The rendering thread must remain on the "main" thread, the updating thread can run on a separate thread.

Is F# worth the trouble on Xbox? I would say it is. Compared to C#, the language has good support for manipulating arrays, an "inline" keyword that comes very handy when writing generic code that must run fast. This makes it a good language for computation-heavy applications (of which simulation-oriented games are).

Another area where the language should shine is in high-level UI code. I have thoughts about using custom workflows to conveniently map operations spanning over multiple frames on the game update loop.

Array-oriented programming

I have been working for quite some time now on Asteroid Hunter. This has not left me much time for exploration and experimentation with F#, but there is quite a bit a learned during the process anyway.

One of the biggest technical challenges of developing games for the Xbox platform using XNA Game Studio is probably how to keep garbage collection from eating too much performance.

The classical way which I think all developers are using is to preallocate your objects, and recycle them during gameplay. As a complement, one can also use structs instead of classes, as structs do not require garbage collection. The goal here is to never allocate new space, as every megabyte allocated triggers a new garbage collection. Depending on the number of objects the heap contains, a garbage collection can take from a few milliseconds to fractions of seconds, the latter being unacceptable for a game refreshing the screen 60 times per second.

There is another way, and I know no one who uses it. In this approach, it's ok to allocate a lot of memory space, as long as it's used by few objects. In other words, an array of value types, such as floats or structs, is cheap to allocate.

In a first version of the game, I used records to model asteroids, and stored these records in immutable arrays. This approach quickly showed its limits. I modified the code to use arrays of structs, also immutable. It was better, but this method incurred very high copying costs, as changing one field, for instance the position, required to copy the entire struct (composed of a couple more vectors for the speed, orientation, angular velocity...).

In the current version, I no longer have a datatype representing a single asteroid. Instead, I use multiple arrays of vectors, one array for the positions, one array for the speeds, etc. I rely heavily on higher order functions in the Array module, such as Array.map, Array.map2 and Array.mapi.

The code below illustrates the kind of programming style I am describing above. Take it with a nip of salt, it was written in quite a rush, and the Dream Build Play deadline left me little (as in "none at all") time for code cleanup.

type AsteroidArrays =
    { pos : Vector3[] ;
      speed : Vector3[] ;
      wspeed : Vector3[] ;
      wpos : Quaternion[] ;
      bsph : BoundingSphere[] ;
      heat_level : float32[] ;
      mass : float32[] ;
      radius : float32[] ;
      rank : int[] ;        // -1 means dead.
      heat_rate : float32[] ;
      color : Vector3[] }


let integrate (V : Vector3) (dt : float32) (impulses : Pair list) (arr : AsteroidArrays) =
    let speed = Array.copy arr.speed
    for impulse in impulses do
        let idx = impulse.fst
        let impulse = impulse.snd
        speed.[idx] <- speed.[idx] + impulse
        
    let pos =
        Array.map2 (fun pos speed -> pos + dt * speed |> WarpCoord.warp V) arr.pos speed

    let rot =
        Array.map (fun wspeed -> new Quaternion(dt * wspeed, 0.0f)) arr.wspeed

    let wpos =
        Array.map2 (fun wpos rot ->
                let x = wpos + Quaternion.Multiply(rot * wpos, 0.5f)
                x.Normalize()
                x)
            arr.wpos
            rot

    let bsph =
        Array.map2 (fun pos radius -> new BoundingSphere(pos, radius)) arr.pos arr.radius
                    
    { arr with
        pos = pos ;
        speed = speed ;
        wpos = wpos ;
        bsph = bsph }

When I dived into redesigning my asteroids from arrays of structs to a record of arrays, I was nervous I would never make it in time. When all you have is four days work, you don't want to spend two days on a redesign. Happily, it took less than four hours, which positively surprised me. The F# mode in Visual Studio may lack most of the refactoring tools available in C#, yet rewriting code goes a lot faster than I would have expected.

This immutable approach does not perform too badly compared to the mutable way, as all values typically need to be touched anyway. I haven't actually done any measurements, but I don't expect the immutable approach to be worse than twice as slow as in-place modifications.

I don't know if memory fragmentation could be a problem. The arrays in question are small enough that they are allocated on the regular heap (as opposed to the large object heap), and the remote performance monitor reports zero compactions. Moreover, all my arrays have fixed sizes, which should keep fragmentation at bay.

If you read some of my earlier posts in this blog, you might have guessed that I have my doubts about object-oriented programming. As far as performance-critical parts of the code are concerned, I am now convinced that one should stay away from objects, be it in the form of structs or classes. Whether one can get away with immutable arrays or not (as opposed to mutable arrays) probably depends on how much performance is needed.

That will be all for now, I am planning to write about concurrency and generic space-partitioning in my next posts.

Asteroid Hunter submitted to Dream Build Play

Asteroid Hunter, the 3d variant of "Asteroids" written in F#, is participating in Dream Build Play.

The game features 12 levels of increasing difficulty. In addition to the solo mode, you can also play against up to 3 of your friends on split screen.



I am hoping to publish the game on the XBox Live Indie Games channel later this spring.