Phillip Trelford's Array

POKE 36879,255

F# Talk at Edge UG: Slides and Demos

The Edge UG, based in London, is the “Uber Usergroup for all developers and IT Pros working on the Microsoft technology stacks.” This statement doesn’t seem too wide of the mark either; when put to a show of hands most attendees responded yes to experience of both C++ and C#, with plenty also playing with WPF and Silverlight!

I presented a 1 hour talk introducing F# with 4 demos (attached to this post):

  • Full-screen WPF POS Checkout sample with Barcode scanner integration (in 100 lines)
  • Twitter WPF client script (200 lines)
  • Matermind board game in WPF (300 lines)
  • Lunar Lander XNA game (>400 lines)

Expect a video of the talk should be on the Edge UG site soon.

Some tweet feedback from the event:

ebrucucen:F# session started with @ptrelford at #edgeuk

johanbarnard: Watching really interesting F# presentation by @ptrelford at #EdgeUG.

ptrelford:Talking about F# again in front of a lot of people

ColinMackay: F# is more fun than I expected. Demos use XNA to create games in F#. #edgeug

raybooysen: Lunar lander in XNA and F#! #edgeug

johnno31: @ptrelford when can we have pizza??

My tweet was delivered from the F# Twiiter client script during the talk!

F_ Introduction_EdgeUG.ppsx (660.16 kb)

FSharpDemos.zip (53.40 kb)

P.S. To see more F# related talks please join the new F# London User Group

C# is not C

Chances are that if you are habitually applying C-style Micro-Optimization tricks when coding C#, like moving variable declarations out of loops, you are probably:

  1. Prematurely optimizing
  2. Doing it completely wrong

mccarthy-youre-doing-it-wrong-s

To demonstrate the point lets start by ignoring that there is a perfectly good Array.Reverse function in the framework and write our own:

static void Reverse1<T>(T[] xs)
{
    for (int i = 0; i < xs.Length / 2; i++)
    {
        T x = xs[i];
        xs[i] = xs[xs.Length - 1 - i];
        xs[xs.Length - 1 - i] = x;
    }
}

Now micro-optimize by taking the temp declaration out of the loop:

static void Reverse2<T>(T[] xs)
{
    T x;
    for (int i = 0; i < xs.Length / 2; i++)
    {
        x = xs[i];
        xs[i] = xs[xs.Length - 1 - i];
        xs[xs.Length - 1 - i] = x;
    }
}

 

The IL (byte code) generated for both implementations is identical in both release and debug builds. If you don’t believe me then check it for yourself by using the ildasm tool.

Another micro-optimization would be to store a copy of the array length in a local variable:

static void Reverse3<T>(T[] xs)
{           
    int len = xs.Length;
    for (int i = 0; i < len / 2; i++)
    {
        T x = xs[i];
        xs[i] = xs[len - 1 - i];
        xs[len - 1 - i] = x;
    }
}

 

This does actually result in the generation of different IL code, however IL generation is only part of the story. The difference in execution time between these implementations is negligible. The reason is that the IL code is just-in-time (JIT) compiled to machine code before execution and this compilation step will apply further optimizations.

Premature optimization is wrong on so many levels:

  • the optimization was probably unnecessary anyway
  • code can become less readable for no tangible benefit
  • you’re double guessing 2 compilation steps
  • you’re probably not even considering high level optimizations
    Further reading:

Pareto principle

The Sad Tragedy of Micro-Optimization Theater

Micro-Optimization and Meatballs

Micro-optimization tips to increase performance

Sorted with F# custom operators

F# lets you define your own operators, and like a man with a new hammer hunting for nails :) I’ve found an application of F# custom operators for sorting multiple columns:

let inline (|?) a b = if a = 0 then b else a

 

Lets start by trying to sort the table position of the current top 5 of English Football’s Premier League (compiled on 2010-01-21):

Team Played Goal Difference Points
Arsenal 22 34 48
Chelsea 21 34 48
Man Utd 22 30 47
Spurs 22 18 38
Man City 21 12 38

 

Lets say we represent the table as an array of tuples:

let table = [|  
        ("Arsenal", 22, 34, 48) 
        ("Chelsea", 21, 34, 48)          
        ("Spurs",   22, 18, 38) 
        ("Man City",21, 12, 38)
        ("Man Utd", 22, 30, 47)
    |] 

 

If we could just sort on points, and wanted to sort the array in place, we could write:

do  Array.Sort(table, fun (_,_,_,a) (_,_,_,b) -> b - a)   

 

But as we can see from the table, some of the teams have the same points, so we need to order on points and goal difference. In the case of Arsenal and Chelsea at the top of the table, they not only have the same points, they have the same goal difference. In this situation the custom is to sort alphabetically (lucky for you if your team starts with the letter ‘A’).

The sort function must now apply secondary sorting criteria if the first expression gives zero:

do  Array.Sort(table, fun a b -> 
        let nameA, _, gdA, pointsA = a
        let nameB, _, gdB, pointsB = b
        let points = pointsB - pointsA
        let gd = gdB - gdA
        let names = String.Compare(nameA, nameB)
        if points <> 0 then points
        else if gd <> 0 then gd
        else names
    )  

Now the custom operator introduced at the start of the article really captures it:

do  Array.Sort(table, fun a b -> 
        let nameA, _, gdA, pointsA = a
        let nameB, _, gdB, pointsB = b
        pointsB - pointsA |? gdB - gdA |? String.Compare(nameA, nameB)                
    )  

The beauty of using the custom operator here, say over a function, is operators can be placed between expressions so can be used to compose the sort.

Finally, there are however a couple of other ways to hammer this nail:

  • sort by mapping the table entry tuple
  • using LINQ OrderBy and ThenBy

Mapping the table entry is easy on the eye but it does require the generation of temporary tuples and a new array:

do  table |> Array.sortBy (fun (name,_,gd,points) -> -points,-gd,name) 

 

Using LINQ is also pretty easy on the eye but requires the generation of a new sequence:

do  table.OrderByDescending(fun (_,_,_,p) -> p)
        .ThenByDescending(fun (_,_,gd,_) -> gd)
        .ThenBy(fun (name,_,_,_) -> name)

 

PS If you are looking for a similar pattern in C#, Jon Skeet shows a similar (but more verbose) way of composing sort expressions using the ?? operator in his C# in Depth book.

PPS Tomas Petricek has a nice article with some sample use of custom operators in F#. Coincidentally he has just authored a book with Mr Skeet on Functional Programming.

PPPS For clarity I should point out that I am a Man Utd supporter, so the timing for this article could be seen as somewhat unfortunate.