Sunday, December 13, 2009

Inheritance nightmares

I was first exposed to object-oriented programming when learning C++. I am now starting to realize how confusing that has been. In particular, inheritance in C++ is often used and abused to implement various kinds of relationships between classes. I am writing "abused", because the only legitimate use of inheritance is for IS-A relationships. Other relationships such as HAS-A and IS-IMPLEMENTED-IN-TERMS-OF should not use inheritance. In these cases composition is preferable. It is therefore important to be able to differentiate between the different kinds of relationships.

However understanding IS-A relationships is not as easy it might seem. To illustrate the problem, the case of squares and rectangles is sometimes used.

All squares are also rectangles, and it seems natural that a class "Square" should be related to a class "Rectangle": Square IS-A Rectangle.

In C#, this could be written:

class Rectangle
{
}

class Square : Rectangle
{
}


Now that we have our class hierarchy, let us start adding methods and fields:


class Rectangle
{
float length;
float width;

public Rectangle(float l, float w)
{
length = l;
width = w;
}

public float GetLength() { return length; }
public float GetWidth() { return width; }
}


So far, no problem. Things get tricky when we want to add setter methods:


class Rectangle
{
float length;
float width;
...
public void SetLength(float l) { length = l; }
public void SetWidth(float w) { width = w; }
}

class Square : Rectangle
{
...
public void SetSize(float s) { SetLength(s); SetWidth(s); }
}


The problem is that Square inherits SetLength and SetWidth, which makes it possible to have squares with non-matching lengths and widths. A non-satisfactory solution consists of overriding SetLength and SetWidth in Square:


class Rectangle
{
float length;
float width;
...
public virtual void SetLength(float l) { length = l; }
public virtual void SetWidth(float w) { width = w; }
}

class Square : Rectangle
{
...
public override void SetLength(float s) { base.SetLength(s); base.SetWidth(s); }
public override void SetWidth(float s) { base.SetLength(s); base.SetWidth(s); }
}


This solution is not satisfactory because users of Rectangle may expect that it should be possible to set widths and lengths independently.


void SetWidthAndLength(Rectangle rect)
{
rect.SetWidth(1.0);
rect.SetLength(2.0);
Debug.Assert(rect.GetWidth() == 1.0);
Debug.Assert(rect.GetLength() == 2.0);
}


These assertions fail when SetWidthAndLength is passed an instance of Square. Many articles go on by stating that Rectangle and Square are in fact not IS-A related, although the initial intuition told otherwise. This is usually the point where the Liskov Substitution Principle is introduced. While understanding this principle is certainly a good thing for anyone learning about object-oriented programming, one of the biggest selling points of object-oriented design is that it is supposed to be intuitive.

After all, all squares are rectangles, aren't they? Indeed, this is true of immutable squares and rectangles. Remove the setters, and all problems disappear. The substitution principle falls in line with what intuition tells us.

Going a bit further, let us consider a function which transforms squares.


Square TransformSquare(Square square, SquareScaling scale)
{
float scaleFactor = ...;
return scale.Do(square, scaleFactor);
}


If we have at hand a library which provides translation and rotation operations on rectangles, we are very close to being able to use these with "Transform". All we need is to write a bit of code to turn rectangles which have identical lengths and widths into squares:


class RectangleUniformScalingAdapter : SquareScaling
{
RectangleUniformScaling adaptee;
...
public override Square Do(Square square, float factor)
{
Rectangle tmp = adaptee.Do(square, factor, factor);
Debug.Assert(tmp.GetLength() == tmp.GetWidth());
return new Square(tmp.GetLength());
}
}


On the other hand, if we are provided a function working on rectangles, a library providing transformations on squares would not be very valuable.

In other words, we could say that RectangleUniformScaling IS-(almost)-A SquareScaling. Note how the IS-A relationship is reversed.

If different parts of the interfaces of Rectangle and Square do not agree on the direction of the relationship, we have a problem.


class Rectangle
{
float width;
float length;

public virtual float GetWidth() { /* Easy to implement */ }
// Uniform scaling
public virtual void Scale(float scale) { /* could use Square.Scale() */ }
public virtual void Scale(float scaleWidth, scaleLength) {...}
}

class Square
{
public virtual float GetWidth() {/* could use Rectangle.GetWidth() */ }
public virtual void Scale(float scale) { /* Easy to implement */ }
public virtual void Scale(float scaleWidth, scaleLength) { /* Impossible to implement */ }
}


Who should inherit from who?

At this point, readers interested in F# and functional programming languages might wonder what all this has got to do with F#. I think that the common mix of mutability and inheritance is not a very strong basis for good software design. I never really realized that until I took a look at functional programming and immutability.

Sunday, December 6, 2009

A bit of F# in your C#

At work, I'm using way more C# than F#.

I have however noticed that functional programming concepts from F# have found their way into my C# code. The first sign of this is when LINQ extension methods start appearing where foreach loops used to be.

F# has a higher-order function called "fold" which can be used for collecting information from a sequence into a single object. A common use is for summing, but it can also be used for extracting one item from the sequence. For instance, it can be used for finding the minimal item according to a specific ordering.

This is a problem Jon Skeet has tackled in a blog from 2005 entitled A short case study in LINQ efficiency.

For instance, given a sequence of pairs of string*number denoting names and ages of people, find the youngest person. Note that we are not only interested in finding the age of the person, we want both the name and the age.

Here is a solution in F# which uses "fold".


let people = [("me", 32.0); ("someoneelse", 75.0)];;
let cmp a b =
match a, b with
| Some (_, a1), (_, a2) when a1 <= a2 -> a
| _ -> Some b;;

let youngest = List.fold cmp None people;;


Function "fold" iterates over each item in the list. For each item, it invokes a function to which it passes the item together with a value called the accumulator. The function returns the new value for the accumulator.

In the example above, the type of the accumulator is "Some person or None", where "None" denotes "no one".

Function cmp simply compares an accumulator with a person, and returns the person if the accumulator is "None", the youngest of the person and the accumulator otherwise.

This solution, when translated to C# 4.0, gives an elegant and efficient solution. I wonder why Jon Skeet did not mention it. If he missed it, he's not alone, a search on Google for how to implement one's own LINQ extension method shows many articles using precisely this problem as illustration.


var people = new Tuple<string, double>[] {
Tuple.Create("me", 32.0),
Tuple.Create("someoneelse", 75.0) };

var youngest =
people.Aggregate(null as Tuple<string, double>,
(youngestSoFar, v) =>
(youngestSoFar != null && youngestSoFar.Item2 <= v.Item2) ?
youngestSoFar : v);


I haven't done any time measurements, but this solution should iterate over the array of people no more than once, and might even be just as efficient as the method using foreach.

F# on the Xbox 360

This article describes how to build an XNA Game Studio application using an F# library in such a way that it can be run on the Xbox 360. It applies to the current version of F#, 1.9.7.8

A method was first described in this blog by Jack Palevich. Most of his blog post still applies, except for step 2.

In order for an .net assembly to be usable on the Xbox 360, it must be linked against dlls for the Xbox 360, which can be found in <Program Files directory>\Microsoft XNA\XNA Game Studio\v3.1\References\Xbox360.

In particular, it must be linked against mscorlib.dll for the Xbox 360, which is the difficult part.

By default, when you create an F# library in Visual Studio, it is linked against FSharp.Core.dll, which references mscorlib for the PC.

In order to avoid conflicts between versions of mscorlib, one must build an F# library targeted at the Compact Framework 2.0, which is what the XNA .net framework is built upon.

The problem is that neither Visual Studio nor msbuild support this for F# libraries. The only solution is to compile the F# library using the F# compiler directly:


"C:\Program Files\FSharp-1.9.7.8\bin\fsc.exe"
-o:obj\Release\XBox360.dll
--standalone --noframework --define:TRACE --optimize+ --tailcalls+
-r:"C:\Program Files\FSharp-1.9.7.8\CompactFramework\2.0\bin\FSharp.Core.dll"
-r:"C:\Program Files\Microsoft XNA\XNA Game Studio\v3.1\References\Xbox360\Microsoft.Xna.Framework.dll"
-r:"C:\Program Files\Microsoft XNA\XNA Game Studio\v3.1\References\Xbox360\mscorlib.dll"
-r:"C:\Program Files\Microsoft XNA\XNA Game Studio\v3.1\References\Xbox360\System.Core.dll"
-r:"C:\Program Files\Microsoft XNA\XNA Game Studio\v3.1\References\Xbox360\System.dll"
--target:library --warn:3 --warnaserror:76 --fullpaths --flaterrors
<your F# source files here>


Beside specifying the correct XNA assemblies using "-r:", this command line also does the following:

- Enables optimization using --optimize+ and --tailcalls+
- Embeds the F# core library in the assembly, using --standalone

Not very pretty, and hopefully future versions of F# and its integration into Visual Studio will remove the need to call fsc.exe explicitly.

Tuesday, July 14, 2009

Asteroids 3d strikes back

I got back to working on my asteroids clone, written in F# using the XNA framework.

Wednesday, July 8, 2009

Interfaces made convenient by type constraints

If my previous entry convinced you to make extensive use of interfaces, you may have encountered a problem, namely that calling methods implementing interfaces requires casting:

let link = new Link("link", config, ...)
// We want to write:
link.Send(data)
// But that does not compile. Instead, we must write:
(link :> ILinkOutput).Send(data)


The bad news are that there is no work around. The good news is that this situation does not happen too often in practice, as the creator of a link is in general not the user. New instances are often forwarded to other objects or functions, which will see them as ILinkOutput, thus not requiring a cast:

let register (p : ISender) (l : ILinkOutput) =
p.AddOutputLink(l) // OK: p is an ISender, no need for explicit cast
l.ConnectInputTo(p) // OK: l is an ILinkOutput, no need for explici cast

let link = new Link(...)
let process = new Process(...)
register process link // OK: process and link automatically upcasted


Now, what happens if we have a function taking a process and which needs to use two of its interfaces? There are two obvious solutions, which are not so pretty.

Ugly-ish:
let register (p1 : ISender) (l : Link) (p2 : IReceiver) =
p1.AddOutputLink(l) // Nice
p2.AddInputLink(l) // Nice
(l :> ILinkOutput).ConnectInputTo(p1) // Not so nice
(l :> ILinkInput).ConnectOutputTo(p2) // Not so nice


Uglier:
let register (p1 : ISender) (l1 : ILinkOutput) (l2 : ILinkOutput) (p2 : IReceiver) =
p1.AddOutputLink(l) // Nice
p2.AddInputLink(l) // Nice
l1.ConnectInputTo(p1) // Nice (is it?)
l2.ConnectOutputTo(p2) // Nice (is it?)

// Set up two processes communicating with each other.
// As links are uni-directional, use two links.
let p1 = new Process(...)
let p2 = new Process(...)
let link_p1_p2 = new Link(...)
let link_p2_p1 = new Link(...)

// p1 -> p2
register p1 link_p1_p2 link_p2_p1 p2 // Oops!!!
// p2 -> p1
register p2 link_p2_p1 link_p1_p2 p1 // Oops!!!


So many 1s and 2s... We really meant to write:

// p1 -> p2
register p1 link_p1_p2 link_p1_p2 p2
// p2 -> p1
register p2 link_p2_p1 link_p2_p1 p1


The correct solution uses generics and type constraints:

let register
(p1 : ISender)
(l : 'L
when 'L :> ILinkInput
and 'L :> ILinkOutput)
(p2 : IReceiver) =

p1.AddOutputLink(l)
p2.AddInputLink(l)
l.ConnectInputTo(p1)
l.ConnectOutputTo(p2)

// Set up two processes communicating with each other.
// As links are uni-directional, use two links.
let p1 = new Process(...)
let p2 = new Process(...)
let link_p1_p2 = new Link(...)
let link_p2_p1 = new Link(...)

// p1 -> p2
register p1 link_p1_p2 p2
// p2 -> p1
register p2 link_p2_p1 p1


Another use of type constraints is for cases when you want to pass lists of ISenders to a function.

Problem:
let sendAll (ps : ISender list) data =
ps
|> List.iter (fun p -> p.Send(data))

let p1 = new Process(...)
let p2 = new Process(...)

sendAll [ (p1 :> ISender) ; (p2 :> ISender) ] data // Blah!


Solution:
let sendAll (ps : 'S list when 'S :> ISender) data =
ps
|> List.iter (fun p -> p.Send(data))

let p1 = new Process(...)
let p2 = new Process(...)

sendAll [ p1; p2 ] data


Which can also be written:
let sendAll (ps : #ISender list) data =
ps
|> List.iter (fun p -> p.Send(data))

let p1 = new Process(...)
let p2 = new Process(...)

sendAll [ p1; p2 ] data

Breaking up classes using interfaces

When I started writing F# programs whose code span over multiple files, I was surprised to see that the order of compilation of these files matters. If the code in file B.fs refers to types or functions in A.fs, then A.fs must be compiled before B.fs.

Now, what happens if A.fs and B.fs depend on each other? In this case, you have a problem. The easy fix is to merge the two files, but this solution does not scale well. Another solution is to break code into smaller pieces, building small "islands" of circular dependencies, which can each be moved into their own file. Easily said, but not so easily said.

Consider an application involving processes and links. Processes can be executed, and can communicate with each other using unidirectional links.

The code might look like this:

type Process(name, config, ...) =
// Construction
...

// Methods
// Connection to links
member x.AddInputLink(link : Link) = ...
member x.AddOutputLink(link : Link) = ...

// Control execution
member x.ExecuteInSomeWay(args) = ...
member x.ExecuteInSomeOtherWay(args) = ...
member x.CheckIsReady() = ...
member x.MarkAsReady() = ...

// Debugging, and other stuff...
member x.ToggleDebugging(b) = ...
member x.SetDebugOutput(o) = ...
...

and type Link(name, config, ...) =
// Construction
...

// Methods
// Connection to processes
member x.ConnectOutputTo(p : Process) = ...
member x.ConnectInputTo(p : Process) = ...

// Read/Write data
member x.Send(data) = ...
member x.Receive() = ...

// Debugging ...
member x.ToggleDebugging(b) = ...
member x.SetDebugOutput(o) = ...
...



As Process and Link are mutually dependent, their code must be all in one file. That may seem OK at first, but things will become harder to manage as more code is added over time.

A first solution is to introduce interfaces for Process and Link, simply duplicating all their method signatures, and replace all occurrences of classes Process and Link by their interfaces. The interfaces can be moved to a separate file, which should be shorter, as it contains no code. Classes Process and Link can now each live in separate files.

Interfaces.fs:
type IProcess =
// Connection to links
abstract AddInputLink : ILink -> ...
abstract AddOutputLink : ILink -> ...

// Control execution
abstract ExecuteInSomeWay : Args -> ...
...

// Debugging, and other stuff...
member x.ToggleDebugging : bool -> unit
...

and type ILink =
// Connection to processes
abstract ConnectOutputTo Process -> unit
...



Process.fs:
open Interfaces

type Process(name, config, ...) =
// Construction
...

// Interface implementations
interface IProcess with
member x.ExecuteInSomeWay(args) = ...
...


Link.fs:
open Interfaces

type Link(name, config, ...) =
// Construction
...

// Interface implementation
interface ILink with
member x.ConnectOutputTo(p : IProcess) = ...
...


Still, Interfaces.fs may be excessively long, and we may end up in a situation where all interfaces are defined in one large file. Not very pleasant.

The next step consists of breaking up the interfaces. The debugging-related methods obviously belong to a IDebugable interface, which need not be concerned with the details of processes and links.

A process which is connected to the input side of a link has no need to have access to the methods taking care and transferring data from the link to the process, which indicates that ILink could be split in e.g. IInputLink and IOutputLink.

There is another case of excessive method exposure. Links do not control the execution of processes, that's the task of the scheduler. The final decomposition may look as shown below.

IActivable.fs:
type IActivable =
abstract CheckIsReady : unit -> bool
abstract MarkAsReady : bool -> unit


IExecutable.fs:
type IExecutable =
abstract ExecuteInSomeWay : Args -> ...
abstract ExecuteInSomeOtherWay : Args -> ...


InputInterfaces.fs:
type IReceiver =
abstract AddInputLink : ILinkInput -> unit

and type ILinkInput =
abstract Receive : unit -> Data
abstract ConnectOutputTo : IReceiver -> unit


OutputInterfaces.fs:
type ISender =
abstract AddOutputLink : ILinkOutput

and type ILinkOutput =
abstract Send : Data -> unit
abstract ConnectInputTo : ISender -> unit


The techniques shown here are by no means specific to F#, and are part of the "proper programming" techniques every object-oriented programmer should know and use. Before using F#, I almost exclusively used interfaces for polymorphism, on "as-needed" basis. The fact is, interfaces are also useful for modular programming.

Decomposing programs into interfaces and implementation helps writing reusable, readable code. It does have a cost, though, as it requires more typing. As long as keyboards remain cheaper than brains, the benefits should outweigh the costs.

Concurrency on a single thread

When I wrote my article about concurrency, I did a bit of searching to find out how to use multi-threading in F#. One of the hits was a blog entry on HubFS by gneverov titled "Hell Is Other Languages : Concurrency on a single thread". At that time, I was a bit confused by the article. Why would one want single-threaded concurrency when we already had multi-threaded concurrency? Part of the answer lies in reactive programming.

Recently, I read an article by Shawn Hargreaves, "Pumping the Guide", where he describes some design issues with using the Guide on the Xbox. The Guide is the part of the Xbox GUI which is used for performing common operations, such as entering text, selecting a device where game data is saved, seeing which of your friends are online and what they are doing... The problem is to have the game still running in the background while the Guide is opened.

The solution chosen by the XNA team was to make calls to the Guide non-blocking. This however makes it harder for game developers to use it, as it forces them to keep track of the application state explicitly, including both the state of the game and the state of the Guide.

Kevin Gadd's shows a elegant solution to this problem in C# using custom enumerators in an article aptly named "Asynchronous programming for xna games with Squared.Task".

Kevin's implementation in C# is as pretty as it can get, but it would probably look even better in F# using asynchronous computations. Although the async { ... } notations is exactly what we want, the Async functions do not seem to support the kind of single-threaded concurrency that Kevin's Square.Task does.

The code by gneverov however should be easy to modify to execute one single step in one of the active tasks, if it does not already support that.

Thursday, July 2, 2009

WiX again.

In my previous post I expressed my disappointment with WiX. However, after an additional day of struggling with it, I may change my mind. I managed to find a pretty straightforward solution to (almost) all my problems. Getting there wasn't straightforward at all, though.

Here are the lessons I learned in the process:

Do not overwrite existing files using <File> elements.
When your software gets uninstalled, it will remove your file, but the old file won't be restored. The solution that first popped up in my mind, namely to backup old files, isn't as easy as it seems. The problem is that the backup copy will be left behind after the software gets uninstalled.

<CopyFile> is not your friend.
...at least as far as backing up existing files goes. I tried to back up the old file by copying it into my application's folder using CopyFile, and failed miserably. Maybe I missed something, but it seems CopyFile is designed to make copies of the files you install, not of existing files.

<CustomAction> is way too complex for its own good (and yours).
CustomAction can be used in many different ways, using slightly different syntaxes. I attempted to use it to backup files, and finally succeeded. It wasn't easy. I tried to use it to run a command (COPY), but it failed. Same problem with other commands such as REN and DEL. No success running batch files either. I tried running a jscript, and that failed too. Since the creator pf WiX advises against using scripts in custom actions, I did not insist. I ended up using "xcopy.exe", which worked (with a catch: the target must be an existing directory, otherwise xcopy demands to interact with the user, and we don't want that).

I found ONE use of CustomAction, and I am not planning on trying out other uses. At least not for a while.

<RemoveFile> is your friend.
Unlike CopyFile, it's easy to use to clear up stuff in your application's folder. I used it to remove the backup after restoring it during uninstallation.

In case you wonder how to handle back-ups in WiX, that's the way I did it:


<Property Id='XCOPY'>xcopy.exe</Property>
...
<CustomAction Id='Backup'
Property='XCOPY'
ExeCommand='"[ExistingFolder]PlugIn.dll" "[OldFiles]" /Y'
Result='check'
Execute='deferred' />

<CustomAction Id='Install'
Property='XCOPY'
ExeCommand='"[NewFiles]PlugIn.dll" "[ExistingFolder]" /Y'
Result='check'
Execute='deferred' />

<CustomAction Id='Restore'
Property='XCOPY'
ExeCommand='"[OldFiles]PlugIn.dll" "[ExistingFolder]" /Y'
Result='ignore'
Execute='deferred' />

<InstallExecuteSequence>
<Custom Action='BackupPlugIn' Before='InstallPlugIn'>Not Installed</Custom>
<Custom Action='InstallPlugIn' After='InstallFiles'>Not Installed</Custom>
<Custom Action='RestorePlugIn' Before='RemoveFiles'>Installed</Custom>
</InstallExecuteSequence>

...
<Directory Id='NewFiles' Name='New Files'>
<Component Id='NewFiles' Guid='...'>
<File Id='NewFile' Name='Plugin.dll' Source='build/PlugIn.dll' />
</Component>
</Directory>

<Directory Id='OldFiles' Name='Old Files'>
<Component Id='OldFiles' Guid='...'>
<CreateFolder />
<RemoveFile Id='CleanUpBackup' Name='PlugIn.dll' On='uninstall' />
</Component>
</Directory>


Note how I avoided overwriting files in the "Component" elements. I do that using CustomAction instead, both when installing my plug-in and when restoring the old one.

Something that's missing are rollback actions. There should be one for each deferred action, namely an action removing the xcopy-ed file. I don't know of any standard program to remove files on Windows, and I'd rather not write one myself. Where is "rm"?

UPDATE:


WiX experts are probably shaking their heads when they read this code:


<Custom Action='RestorePlugIn' Before='RemoveFiles'>Installed</Custom>
</InstallExecuteSequence>


While it does do what I intended when the user removes the software, it is also executed when users perform other actions than install or uninstall, such as repair an installation. As a result, an attempt to repair an installation will restore the old plug-in, which of course is more likely to destroy the installed software...

Wednesday, July 1, 2009

WiX, because we can.

For today's post, I thought I might write on something that's not directly related to F#. Instead, this article deals with WiX, a piece software intended to help creating installers. WiX and F# do share their approach to writing programs, though, namely the declarative way.

First, I must say I am no expert in installers. I have built a couple rpm packages on Linux, and found the experience OK, but not particularly enjoyable. I have also used NullSoft Scriptable Install System (NSIS for short) for top10, and gave up with it. My main gripe is that NSIS is really more a scripting language, and not a particularly good one at that. I don't think it's worse than the other install systems out there, though I haven't tried them all. I did try WISE, for instance, but failed to install it. Now, that's irony...

The problem is that these tools try to solve the problem using a procedural approach. The programmer has to specify what to do during an installation, which typically includes copying files on the hard disk, setting up a few shortcuts, messing up with the registry. Specifying all this is a tedious task, but it's not even half the job. One must also specify what to do when the user decides to uninstall the software. Typically, this means clearing up the mess in the registry, removing the shortcuts, deleting files.

Obviously, it should be possible to deduce the uninstallation process from the installation process. It's not just a matter of convenience, but of correctness.

WiX attracted a bit of attention when it came out, being Open Source software produced by Microsoft. Another side of it worth of interest is that it uses a declarative approach to specifying installation procedures. Instead of writing the sequence of operations needed to (un)install software, one specifies what to install, and where. Which is the way it should be.

As attractive as it seems to be, I must say I am disappointed. The three full days of experimenting I have spent on WiX have been rather painful.

The first issue is that WiX is based on Windows Installer, a.k.a MSI, whose documentation is pretty hard to grasp for a newcomer. Part of the problem resides in the core design choices, which seem genuinely weird to me. An MSI installer is not a program, it's a database, which contains a description of a workflow, where the actions make up the installation procedure. Now, installations a probably some of the most linear processes one can think of, meaning workflows are complete overkill. Why one would use a database to store a workflow is another mystery.

WiX attempts to hide these layers of insanity. All you need to do to copy a file on the system is specify which file you want to copy, and where. WiX takes care of generating the code to undo the copy if it fails, as well as the code to remove the file when uninstalling.

Sadly, WiX only goes halfway. If your installation process happens to write over an existing file, the uninstallation process won't restore the original file. This must be handled manually, and requires a decent understanding of MSI, its workflows, custom actions and databases.

What's worse, WiX adds another layer of wickedness of its own, namely XML. That was probably the only technology missing in the stack...

In case you urgently need a headache, I suggest you go have a look at Suggested InstallExecuteSequence, which is the sequence of actions one should take to install software. That's 60 of them, no less. If that sounds like a lot, well it is. The catch is that the same sequence is used for uninstallation. Approximately half of these actions are active when installing, the other half being active while uninstalling. The question that immediately pops up is "why not use two separate sequences"? But then, one would not need conditions, such a shame...

Wednesday, May 20, 2009

XNA asteroid clone aborted

I have decided to abort my attempt to write a 3d asteroids clone for the XBox 360. As, there already are quite a few 2d clones of the original Asteroids, I had decided to make a 3d version. The problem, as I pointed in an earlier post, is that one needs a considerably larger number of asteroids to make the game interesting. The magic number here seems to be 1000 asteroids.

I wanted collision response between asteroids. Doing collision detection is quadratic in the number of objects, unless one uses space partitioning. My experiments showed that the naive way (without space partitioning) works fine for 100 asteroids, but does not scale up.

I implemented an octree data structure to speed things up. The idea here is to partition space in boxes of varying size, where each box contains at most about 10 asteroids. Collision detection can then be done on groups of 10 asteroids.

The optimization worked fine when the game was run on the PC, but not on the XBox. The game run at 60 fps on the PC, with noticeable "hickups" every few seconds though. The game run at less than 10 fps on the XBox.

The culprit is the gargabe collector on the XBox. When looking on the net, one finds that the suggested solution is to minimize the number of live objects, which involves using structs. Unfortunately, most of the nice constructs of F#, such as discriminated unions and records, are translated to classes. Replacing these by structs is feasible, but it's not a very pleasant experience.

I also feel that I do not want to invest time developing skills to avoid garbage collection when the correct solution is to fix the garbage collector on XBox.

That does not mean I am giving up on XNA and the XBox, but I will have to find other computationally easier projects.

Sunday, April 12, 2009

Race condition in "First obstacles and solutions"

I fixed a bug in my asteroids clone yesterday which turned out to be a race condition. The problem was in map_parallel:


let map_parallel (func : 'a -> 'b) (items : 'a[]) =
let results = Array.zero_create (items.Length)
let count = ref items.Length
use notify = new System.Threading.AutoResetEvent(false)

items
|> Array.iteri (
fun i item ->
System.Threading.ThreadPool.QueueUserWorkItem (
fun _ ->
let res = func item
results.[i] <- res
!: System.Threading.Interlocked.Decrement count |> ignore
!: if !count = 0 then notify.Set() |> ignore
) |> ignore
)
notify.WaitOne() |> ignore
results


I have marked the two faulty lines in the code above with "!:". The (hopefully) correct version is:

let c = System.Threading.Interlocked.Decrement count
if c = 0 then notify.Set() |> ignore


In the faulty version, it is possible for two threads to execute "then notify.Set()". The second thread may then raise an exception as "notify" may already have been disposed of.

The code in the original post was corrected.

Sunday, March 29, 2009

Structs that look like records

I've spent some time trying to improve my asteroids clone in F# for the XBox360. I present the first results in this post.

But first, some non-technical considerations. Microsoft has now made available to XNA creators (i.e. game programmers) the download statistics of their games. A vast majority of creators seem disappointed, but I think that's more a sign of too high expectations than a failure of the platform itself.
One of the creators reported that full game downloads went down when Microsoft raised the time limit in trial versions from 4 minutes to 8 minutes. Players have the ability to download a trial version of an XBox Live Community Game before buying the full version. Trial versions typically have some features disabled (this is up to the game creator) and a mandatory time limit (which cannot be controlled by game creators).
What happened there, apparently, is that the game is played in short sessions shorter than 8 minutes at a time, making the free trial version sufficiently appealing that gamers did not feel a need to buy the full version.

Asteroids is not typically a game you play for long periods at a time, so I expect my game may suffer the same problem.

Back to the technical side of things. I found a way to make structs look like records. Here is the declaration:


type State =
struct
val props : Properties
val pos : Vector3
val speed : Vector3
val impulses : Vector3
val force : Vector3

new (props, pos, speed, impulses, force) =
{ props = props ;
pos = pos ;
speed = speed ;
impulses = impulses ;
force = force }

static member inline Default (props, ?pos, ?speed, ?impulses, ?force) =
State(
props,
pos = defaultArg pos Vector3.Zero,
speed = defaultArg speed Vector3.Zero,
impulses = defaultArg impulses Vector3.Zero,
force = defaultArg force Vector3.Zero)

member inline x.Clone (?pos, ?speed, ?impulses, ?force) =
new State (
x.props,
pos = defaultArg pos x.pos,
speed = defaultArg speed x.speed,
impulses = defaultArg impulses x.impulses,
force = defaultArg force x.force )


... and here is how it's used:


member x.ApplyCenterForce (v : Vector3) =
let force = x.force + v
x.Clone (force = force)


This is very similar to the old code:


let applyCenterForce (v : Vector3) (x : State) =
let force = x.force + v
{ x with force = force }


Looking back at the first snipplet, notice how I declared "x.Clone":


static member inline Default (props, ?pos, ?speed, ?impulses, ?force) =

The question marks before the arguments mean that these arguments are optional. If the caller does not provide them, they automatically get the "None" value.

new State (
x.props,
pos = defaultArg pos x.pos,
speed = defaultArg speed x.speed,
impulses = defaultArg impulses x.impulses,
force = defaultArg force x.force )

"defaultArg" is a convenience F# standard function which returns the first value unless it's "None", in which case the second value is returned.

The function was declared "inline" to avoid creating lots of "Option" objects at call sites. For instance, the disassembled version of "ApplyCenterForce" looks like this:

public HeavyObject.State ApplyCenterForce(Vector3 v)
{
return new HeavyObject.State(this._props, this._pos, this._speed, this._impulses, this._force + v);
}


Compare with the version without "inline":


public HeavyObject.State ApplyCenterForce(Vector3 v)
{
Vector3 vector = this._force + v;
return this.Clone(null, null, null, new Option(vector));
}


As the entire point with structs is to avoid allocating objects on the heap, having an "Option" created for each call to ApplyCenterForce is not quite acceptable.

It's not clear that using structs is a clear win in all situations. Performance on the PC is negatively affected, as garbage collection is almost free there, whereas copying structs when passing them as parameters to functions isn't. Performance on the XBox360, however, is improved, as garbage collection is kept under control.

Wednesday, March 25, 2009

First obstacles and solutions

I've got forward with my asteroids clone on the XBox 360 using XNA, and I started noticing a few issues, not all technical.

First, a 3d space is mostly empty. I did not realize the probability of being hit by an asteroid is pretty low. In order to make the game somewhat interesting, I need a good 1k asteroids in a 100m x 100m x 100m cube. I doubt any player will have the patience and perseverance to shoot each of these 1000 asteroids. I have ideas about solving that problem, but I'm not sure which one to pick yet.

Regarding performance, the game initially ran fine with 100 asteroids, but as I say above, I will need 10 times that amount. The initial bottleneck was collision detection, which was quadratic. I solved this on the PC using space partitioning with an octree.


#light

open Microsoft.Xna.Framework
open System.Collections.Generic

type NodeData<'a> =
{ bbox : BoundingBox ;
sub_nodes : Node<'a> [] }

and Node<'a> =
| Leaf of BoundingBox * 'a []
| Node of NodeData<'a>


let mkBBox (p1 : Vector3) (p2 : Vector3) =
let x1, x2 =
if p1.X < p2.X then (p1.X, p2.X) else (p2.X, p1.X)
let y1, y2 =
if p1.Y < p2.Y then (p1.Y, p2.Y) else (p2.Y, p1.Y)
let z1, z2 =
if p1.Z < p2.Z then (p1.Z, p2.Z) else (p2.Z, p1.Z)

BoundingBox (Vector3 (x1, y1, z1), Vector3 (x2, y2, z2))


let map_parallel (func : 'a -> 'b) (items : 'a[]) =
let results = Array.zero_create (items.Length)
let count = ref items.Length
use notify = new System.Threading.AutoResetEvent(false)

items
|> Array.iteri (
fun i item ->
System.Threading.ThreadPool.QueueUserWorkItem (
fun _ ->
let res = func item
results.[i] <- res
let c = System.Threading.Interlocked.Decrement count
if c = 0 then notify.Set() |> ignore
) |> ignore
)
notify.WaitOne() |> ignore
results


let rec partition (count_limit) (intersect) (items : 'a []) (bbox : BoundingBox) multi_threaded =
if items.Length < count_limit
then
(bbox, items) |> Leaf
else
let in_bbox =
items
|> Array.filter (fun item -> intersect item bbox)

let center = 0.5f * (bbox.Min + bbox.Max)
let pts = bbox.GetCorners ()

let sub_nodes =
pts
|> (if multi_threaded then map_parallel else Array.map) (
fun pt ->
let sub_box = mkBBox center pt
partition count_limit intersect in_bbox sub_box false
)

{ bbox = bbox ;
sub_nodes = sub_nodes }
|> Node


let rec getVisible (view : BoundingFrustum) addVisible (partition : Node<'a>) =
match partition with
| Leaf (bbox, items) ->
if bbox.Intersects (view)
then
items |> Array.iter addVisible
| Node data ->
if data.bbox.Intersects (view)
then
data.sub_nodes
|> Array.iter (getVisible view addVisible)


It's pretty rough code, but there are some interesting bits anyway. In "partition", the function creating the octree, I use multithreading in the top call in an attempt to take advantage of the multiple cores. My timings on the PC show however little global benefit in using multithreading, but I don't know how much "partition" contributes to the overall execution time. It's too early to draw any conclusion, but at least performance is not negatively affected.

Note that I reimplemented map_parallel (which I had introduced in an earlier Tutorial about concurrency) without using asynchronous computations. It's obviously inferior to the older version as it does not handle exceptions, but it has the advantage of actually working on both the PC and the XBox360. The older version causes an "error code 4" on the XBox. I don't know why, I'll try to report that on hubfs with a smaller test case as soon as I get time.

The octree made the PC version run nicely with 1000 asteroids and more, but the XBox360 is still running very slowly, which makes me think that I have finally hit the limitations of its garbage collector. Note that I have not verified that, not being very comfortable with the development kit yet.

Currently, each asteroid is represented using a record, and records get translated to classes by the F# compiler. The records are stored in an array. I wonder if it would work better with structs instead, the idea being that an array of structs should be seen as one object, whereas an array of classes is composed of 1001 objects in this case. As the performance of garbage collection is dependent on the number of objects, but not so much on their size, an array of struct should offer better performance.

The sad thing is that I really liked records, I wish F# allowed the [<Struct>] attribute on records.

Saturday, March 14, 2009

F# game running on the console

I have just succeeded to write and run my first game on my XBox360. Here is proof of it:



The game is composed of an F# library and a top-level C# application. The game, a 3d clone of Asteroids, is still very far from being complete. For instance controls require a keyboard, and the code is still riddled with bugs. Never the less, the first attempt to deploy on the XBox was successful, which is quite encouraging. See Grammerjack's old blog for details on each step of the deployment process.

The F# code is written in a pure functional way, which I fear is not going to work out in the end. Such code relies heavily on the garbage collector, and the current version of the XBox360 .NET environment is known to be weak on this point.

I wonder if it's possible to modify the .NET code emitted by the F# compiler to replace instantiations of new objects by references to items in pre-allocated arrays. This would make it possible to keep purity in the F# source code while maintaining decent performance.
Right now, I feel that if I was to write code relying heavily on in-place modifications, I would rather do that in C# than in F#.