Rick Minerich's Development Wonderland : interop

A Speedy Alternative to F# DelegateEvents

RickM — Fri, 04 Jun 2010 16:19:58 GMT

DelegateEvents use DynamicInvoke under the hood and so can be slow when trigged frequently. As we have an existing model which requires an event interface, this was was causing our F# implementation to be a bit slower than the C# we were comparing it to. Thankfully, F# allows you to implement your own eventing via IDelegateEvent. With a standard Invoke version of DelegateEvent provided by James Margetson, our implementation in F# is running at equivalent speed to C#.

The other day I was working with Steve on trying to discover why a particular segment of apparently equivalent code was running ~25% slower in F# when compared to C#. We broke out AQTime and did a line by line release-mode profile. The frequent triggering of a DelegateEvent immediately jumped out as the cause.

Needless to say, I was a bit concerned. What could be causing this slow eventing in my favorite language? After a brief review of the generated IL, nothing in particular seemed fishy. So, I quickly built a sample and sent it off to my favorite language team.

The contents of the F# library assembly:

type FsEventClass(num) =
     let event = new DelegateEvent<System.EventHandler<System.EventArgs>>()
     
     [<CLIEvent>]
     member this.Event = event.Publish
             
     member this.Run () = 
         let args = [| this :> obj ; System.EventArgs.Empty :> obj |]
         for i in 1 .. num do
             args.[1] <- new System.EventArgs() :> obj
             event.Trigger( args )

And this, the C# client:

static void Main(string[] args)
 {
     int iters = 1000000;
 
     DateTime fsStart = DateTime.Now;
     FSharpEventingLib.FsEventClass fs = new FSharpEventingLib.FsEventClass(iters);
     int fsCalled = 0;
     fs.Event += (s, a) => fsCalled++;
     fs.Run();
     DateTime fsEnd = DateTime.Now;
     TimeSpan fsTime = fsEnd - fsStart;
     System.Console.WriteLine(String.Format("F# took: {0} when called {1} times", fsTime, fsCalled)); 
 }

Finally, the program output:

F# took: 00:00:05.6830000 when called 1000000 times

As it turns out, the F#’s current DelegateEvent uses a DynamicInvoke under the hood and that can slow things down quite a bit. This won’t be important in most cases as Event is implemented with a standard Invoke. However, in our case we had to fit to an existing C# model and so needed to do an event trigger for each resulting scanline of an image.

A big thanks to James Margetson of the F# Team for the following fast replacement for DelegateEvent. Within same day I had mentioned my issue he had this solution for me.

The new library contents:

type FastDelegateEvent() =
     let mutable multicast : System.EventHandler = null
 
     member x.Trigger(sender:obj,args:System.EventArgs) =
         match multicast with
         | null -> ()
         | d -> d.Invoke(sender,args)   // DelegateEvent used: d.DynamicInvoke(args) |> ignore
  
     member x.Publish =
         { new IDelegateEvent<System.EventHandler> with
             member x.AddHandler(d) =
                 multicast <- System.Delegate.Combine(multicast, d) :?> System.EventHandler
             member x.RemoveHandler(d) =
                 multicast <- System.Delegate.Remove(multicast, d)  :?> System.EventHandler }
 
 type FsFastEventClass(num) =
    let event = new FastDelegateEvent()
 
    [<CLIEvent>]
    member this.Event = event.Publish
 
    member this.Run () =
        for i in 1 .. num do           
            event.Trigger(this, new System.EventArgs())

The program output with FastDelegateEvent:

F# took: 00:00:00.0390000 when called 1000000 times

This new event class completely resolved our issue. With it our F# version is just as fast, if not faster, than the C# equivalent.

F# Discoveries This Week 12/21/2009

RickM — Mon, 21 Dec 2009 17:10:31 GMT

By far the most exciting news this week was the preview release of Microsoft Research Accelerator. Posts on this topic by Satnam Signh and Tomas Petricek have left the F# world buzzing. This, however, is just the tip of the F# iceberg. News of the F# Survival Guide’s release and a number of other exciting posts follow.

-- F# --

Satnam Singh demonstrates GPGPU and x64 multicore programming with Accelerator

Microsoft recently released a preview of the Accelerator V2 GPU and x64 multicore programming system on Microsoft Connect. This system provides a civilized level of abstraction for writing data-parallel programs that execute on GPUs and multicore processors. An experimental FPGA target is under development.

Tomas Petricek explores Microsoft Research Accelerator

The project used Microsoft Research Accelerator, which is a C# library for developing array-based computations and executing them on a GPU. […] In this article, we'll look at the simplest way of using Accelerator from F#. Accelerator provides a managed interface that can be naturally used from both C# and F#.

The F# Survival Guide – a Free eBook

Welcome to the F# Survivial Guide by John Puopolo with Sandy Squires. We wrote this book to introduce mainstream developers to the world of functional programming through the lens of F#, Microsoft's first fully-supported multi-paradigm language.

Matthew Podwysocki builds a Shopping Cart in F#

Where functional programming has an immediate impact and probably the largest is programming in the small. Here, we can focus on such things as immutable values, higher order functions, recursion, pattern matching and others come into play. When we’re talking about mixing paradigms, object oriented programming has a larger effect on programming in the medium where we’re organizing our code and can some times offer a more elegant solution than a functional programming one.

Brian McNamara explores IObserver and IObservable

At core, IObservable is just about two new small interfaces, IObservable<T> and IObserver<T>, being added to .Net 4.0. We’ll come to the details of those interfaces shortly. What is exciting and useful about IObservable is that these interfaces admit very nice programming models, including LINQ (e.g. for C#) and the Observable module (for F#), that provide useful combinators for transforming and using event streams.

Steffen Forkmann maps the Reactive Framework operators to F#

The “Reactive Extensions for .NET (Rx)” comes with lot’s of operators for using IObservable<T>. This code mimics the signature of the default F# sequence combinators and allows to use observables like sequences. It is a similar approach like Matthews Podwysocki’s blog post about mapping the IParallelEnumerable.

Robert Pickering introduces FunctionalNHibernate

It’s already fairly well documented that F# doesn’t play too well with NHibernate and Fluent NHibernate, although you can make it play a littler nice with a bit of effort. However there are a few fundamental problems with this approach.

Bistro FSharp Extensions 0.9.5.0 is released

The new release drastically improves the project's interaction with the inference capabilities of F#. A majority of controllers can now be written without the need for discriminated union annotations, or let bindings for naming.

Julien Ortin continues his series on Purely Functional Data Structures with a Splay heap, a double-ended queue and a Pairing heap.

This post describes the F# implementation of the <insert data structure here> from Chris Okasaki’s “Purely functional data structures”.

Jared Parsons makes F# type inference friendly to C#

When working with the exposed core Vim engine API, I’ve found a number of generated F# constructs which are not easily accessible from C#. The problem stems from the manner in which native F# types are exposed. Many of them are generic and lack type inference friendly helper methods that force awkward usage patterns in C#.

Alex Pedenko discusses code compression with F# and MVC

While the underlying concepts are the same, a recent stint with Django (which is a strong influence in the Bistro framework) reminded me of how little work you have to do in python to get going with a controller, and that bistro and the fs extensions still have some catching up to do on the brevity front.

Matt Davey muses over F# within a Single Dealer Platform

I’ve been thinking about F# for a while and its use within finance. A number of banks have been looked at F# from an analytical viewpoint – obvious, and hence boring. What is more interesting it how F# possible elevates the building of a Single Dealer Platform (SDP).

Mark Needham does Word Count using a Dictionary

Having spent some time unsuccessfully trying to make my F# attempt at the word count problem work I decided to follow the lead of the other examples I've read and make use of a Dictionary to keep count of the words.

-- Misc Others --

Functional Programming eXchange – a Ning network for FP

Mark Dominus on why Monads are like burritos

Crash Monad Tutorial

Stuart Sierra on why Objects are not Abstract Data Types

Perlisms - “Epigrams in Programming” by Alan J. Perlis

Image Processing in F#: From Image File to Array

RickM — Thu, 03 Sep 2009 18:09:37 GMT

F# has fantastic array manipulation functionality. To leverage this functionality for some very elegant image processing, it is first necessary to to convert image files into a byte arrays. Unfortunately, this process is not as simple as one might hope.

It’s a dark path of missing documentation, incorrect code samples and some ugly .NET interop. With all of the other difficulties involved, I want to otherwise keep things simple and so will make the following assumptions:

The image file will be properly handled by .NET’s image codecs (it’s known to have some issues with Tiffs in particular)
The Image format is 24 bits per pixel BGR
The end user will handle exceptions

By far the most difficult things in writing this small sample was that it seemed every BitmapData implementation I ran into was completely broken. In fact, this was the case for even the .NET Framework SDK sample code. For each example I tried the following two tests succeeded:

[<Fact>]
member x.first_matches_GetPixel() =
  let pixel = bmp24Bgr.GetPixel(0,0)
  Assert.Equal( pixel.B, array24Bgr.[0] )
  Assert.Equal( pixel.G, array24Bgr.[1] )
  Assert.Equal( pixel.R, array24Bgr.[2] )
 
[<Fact>]
member x.last_on_first_scanline_matches_GetPixel() =
  let pixel = bmp24Bgr.GetPixel( bmp24Bgr.Width - 1 , 0 )
  let offset = (bmp24Bgr.Width - 1) * 3 
  Assert.Equal( pixel.B, array24Bgr.[offset] )
  Assert.Equal( pixel.G, array24Bgr.[offset + 1] )
  Assert.Equal( pixel.R, array24Bgr.[offset + 2] )

Unfortunately, the following two tests would fail:

[<Fact>]
member x.first_on_last_scanline_matches_GetPixel() =
  let pixel = bmp24Bgr.GetPixel( 0 , bmp24Bgr.Height - 1 )
  let offset = bmp24Bgr.Width * (bmp24Bgr.Height - 1) * 3
  Assert.Equal( pixel.B, array24Bgr.[offset] )
  Assert.Equal( pixel.G, array24Bgr.[offset + 1] )
  Assert.Equal( pixel.R, array24Bgr.[offset + 2] )
 
[<Fact>]
member x.last_matches_GetPixel() =
  let pixel = bmp24Bgr.GetPixel( bmp24Bgr.Width - 1, 
                                 bmp24Bgr.Height - 1 )
  let offset = (bmp24Bgr.Width * bmp24Bgr.Height * 3) - 3
  Assert.Equal( pixel.B, array24Bgr.[offset ] )
  Assert.Equal( pixel.G, array24Bgr.[offset + 1] )
  Assert.Equal( pixel.R, array24Bgr.[offset + 2] )

On closer inspection it seemed something was turning everything after the first scanline into garbage.

Well, it turns out that each scanline in BitmapData’s allocated memory block can have some padding on the end. This mean’s you can’t simply block-copy the memory into your array as is done in so many examples. Instead, it is necessary to iterate over each scanline and copy only up to the padding. A fact missing from everywhere but a small corner of the .NET Framework BitmapData documentation.

A big thanks to Bob Powell for his article on exactly how the BitmapData class works. Once I saw his diagram, I knew exactly what was going on and reworked my code to Marshal the data out of each scanline separately, minus the padding.

open System.Drawing
open System.Drawing.Imaging
open System.Runtime.InteropServices
 
let getBytesFromBitmap (bytesPerPixel: int) (bmp: Bitmap) =
  let imgRect = new Rectangle(0, 0, bmp.Width, bmp.Height)
  let bmpBits = bmp.LockBits(imgRect, ImageLockMode.ReadOnly,
                             bmp.PixelFormat)
  try
    let pixelBytes = bmp.Height * bmp.Width * bytesPerPixel
    let byteArray: byte[] = Array.zeroCreate pixelBytes
 
    let scanlineBytes = bmp.Width * bytesPerPixel 
    let stride: nativeint = nativeint bmpBits.Stride
    for i in [ 0 .. bmp.Height - 1 ] do
        let bmpOffset = stride * nativeint i
        let arrayOffset = scanlineBytes * int i
        Marshal.Copy( bmpBits.Scan0 + bmpOffset, byteArray, 
                      arrayOffset, scanlineBytes)
    byteArray
  finally        
    bmp.UnlockBits( bmpBits ) 

This code is not as pretty or efficient as it might be, but at least it works and is fairly safe. I’d love to clean this up and so I encourage you to leave critiques and/or example code in the comments section.

Also, I’ve made my Visual Studio 2008 solution containing the above code and a few small extras available. Let me say again that any comments or critiques are welcome. I hope that in posting this I’ve saved you the some of the pain I had in writing it.

Ninja Edit: The idea of this function exiting with still locked bits was really bothering me and so I put everything after LockBits into a try-finally.