F# Performance of events (update)

There is another solution to the challenge we’ve met last time. In my previous post I’ve skipped it because it is F# specific and result cannot be used directly in other languages. However after discussion with ControlFlow I think this solution is also worth mentioning.

As you remember the problem was inability to call Invoke method of the delegate. Using statically resolved type parameters and member constraints we can make compiler do all the job for ensuring that type has method Invoke with particular signature and calling it properly.

type MCEvent< ^D, ^A when ^D :> Delegate and ^D : delegate< ^A, unit> and ^D : (member Invoke : obj * ^A -> unit) and ^D : null>() = 
    [<DefaultValue>]
    val mutable multicast : ^D
    
    member inline this.Trigger(sender : obj, arg : ^A) =
        match this.multicast with
        | null -> ()
        | d -> (^D : (member Invoke : obj * ^A -> unit)(this.multicast, sender, arg))

    member inline this.Publish =
        { new IDelegateEvent< ^D> with
            member x.AddHandler(d) =
                this.multicast <- System.Delegate.Combine(this.multicast, d) :?> ^D
            member x.RemoveHandler(d) =
                this.multicast <- System.Delegate.Remove(this.multicast, d)  :?> ^D }  

//test helper
type MCEventClass(num) =
   let event = new MCEvent<EventHandler<EventArgs>, _>()

   [<CLIEvent>]
   member this.Event = event.Publish

   member this.Run () =
       for i in 1 .. num do           
           event.Trigger(this, new System.EventArgs())

Test class is appeared to be almost the same as ones we’ve used in previous post. However if you open compiled assembly with Reflector you’ll see the difference

// FsFastEventClass
public void Run()
{
    int i = 1;
    int num = this.num;
    if (num >= i)
    {
        do
        {
            this.@event.Trigger(this, EventArgs.Empty);
            i++;
        }
        while (i != (num + 1));
    }
}

// MCEventClass
public void Run()
{
    int i = 1;
    int num = this.num;
    if (num >= i)
    {
        do
        {
            MCEvent<EventHandler<EventArgs>, EventArgs> event2 = this.@event;
            object sender = this;
            EventArgs e = new EventArgs();
            if (event2.multicast != null)
            {
                event2.multicast(sender, e);
            }
            i++;
        }
        while (i != (num + 1));
    }
}

As you see compiler have inlined code of Trigger method inside Run  and accessed field multicast directly. That’s why we replaced let binding with val.

namespace Benchmark
{
    class Program
    {
        const int Iters = 1000000;

        static void Run(string caption, Action action)
        {
            Console.WriteLine("{0} started", caption);
            var sw = Stopwatch.StartNew();
            action();
            sw.Stop();
            Console.WriteLine("{0}:{1}", caption, sw.Elapsed);
        }


        static void Main(string[] args)
        {
            Run("F# events", RunFSEventTest);
            Run("Fast events", RunFastEventTest);
            
            // initial pass to trigger generation of invoker (so generation time is not included in tests) 
            RunEventV2Test(1);
            Run("Precomputed events", () => RunEventV2Test(Iters));
            Run("MemberConstrainedEvents", RunMemberConstrainedEventTest);
        }

        private static void RunFSEventTest()
        {
            var fs = new Events.FsEventClass(Iters);
            int fsCalled = 0;
            fs.Event += (s, a) => fsCalled++;
            fs.Run();
        }

        private static void RunFastEventTest()
        {
            var fs = new Events.FsFastEventClass(Iters);
            int fsCalled = 0;
            fs.Event += (s, a) => fsCalled++;
            fs.Run();
        }

        private static void RunEventV2Test(int n)
        {
            var fs = new Events.GenFastEventClass(n);
            int fsCalled = 0;
            fs.Event += (s, a) => fsCalled++;
            fs.Run();
        }
        private static void RunMemberConstrainedEventTest()
        {
            var fs = new Events.MCEventClass(Iters);
            int fsCalled = 0;
            fs.Event += (s, a) => fsCalled++;
            fs.Run();
        }

        /*
F# events started
F# events:00:00:8.8833742
Fast events started
Fast events:00:00:00.0300628
Precomputed events started
Precomputed events:00:00:00.876707
MemberConstrainedEvents started
MemberConstrainedEvents:00:00:00.0251707
         */
    }
}

F# Performance of events

Events in F# are first class citizens, and this is in fact feature with vast amount of applications. We can compose events using combinators, pass events to functions, return them as a results… IDelegateEvent wrap delegates and under the hood use Delegate.DynamicInvoke for invoking methods bound to delegate, causing significant performance degradation. Rick Minerich has made good description of this problem and also suggested solution that has brilliant performance characteristics but binds event to particular delegate type.

So, is is possible to have both possibility to use arbitraty delegates and good performance characteristics? Linq expression trees come to the rescue. We cannot access Invoke method of delegate directly but we can create typed helper that will do this instead of us.

// helper type that will perform invocation
type Invoker<'D, 'A> = delegate of 'D * obj * 'A -> unit

// :)
type EventV2<'D, 'A when 'D :> Delegate and 'D : delegate<'A, unit> and 'D : null>() = 
    static let invoker = 
        let d = Expression.Parameter(typeof<'D>, "dlg")
        let sender = Expression.Parameter(typeof<obj>, "sender")
        let arg = Expression.Parameter(typeof<'A>, "arg")
        let lambda = Expression.Lambda<Invoker<'D, 'A>>(Expression.Invoke(d, sender, arg), d, sender, arg)
        lambda.Compile()
    
    let mutable multicast : 'D = null     
    
    member x.Trigger(sender:obj,args: 'A) =
        match multicast with
        | null -> ()
        | d -> invoker.Invoke(d, sender, args) // DelegateEvent used: d.DynamicInvoke(args) |> ignore

    member x.Publish =
        { new IDelegateEvent<'D> with
            member x.AddHandler(d) =
                multicast <- System.Delegate.Combine(multicast, d) :?> 'D
            member x.RemoveHandler(d) =
                multicast <- System.Delegate.Remove(multicast, d)  :?> 'D }            

// helper to be used in test
type GenFastEventClass(num) =
   let event = new EventV2<EventHandler<EventArgs>, _>()

   [<CLIEvent>]
   member this.Event = event.Publish

   member this.Run () =
       for i in 1 .. num do           
           event.Trigger(this, new System.EventArgs())

Performance measurements (I took code for other tests from Rick’s post):

class Program
    {
        const int Iters = 1000000;

        static void Run(string caption, Action action)
        {
            Console.WriteLine("{0} started", caption);
            var sw = Stopwatch.StartNew();
            action();
            sw.Stop();
            Console.WriteLine("{0}:{1}", caption, sw.Elapsed);
        }


        static void Main(string[] args)
        {
            Run("F# events", RunFSEventTest);
            Run("Fast events", RunFastEventTest);
            
            // initial pass to trigger generation of invoker (so generation time is not included in tests) 
            RunEventV2Test(1);
            Run("Precomputed events", () => RunEventV2Test(Iters));
        }

        private static void RunFSEventTest()
        {
            var fs = new Events.FsEventClass(Iters);
            int fsCalled = 0;
            fs.Event += (s, a) => fsCalled++;
            fs.Run();
        }

        private static void RunFastEventTest()
        {
            var fs = new Events.FsFastEventClass(Iters);
            int fsCalled = 0;
            fs.Event += (s, a) => fsCalled++;
            fs.Run();
        }

        private static void RunEventV2Test(int n)
        {
            var fs = new Events.GenFastEventClass(n);
            int fsCalled = 0;
            fs.Event += (s, a) => fsCalled++;
            fs.Run();
        }

        /*
F# events started
F# events:00:00:08.4989916
Fast events started
Fast events:00:00:00.0316716
Precomputed events started
Precomputed events:00:00:00.0821696
         */
    }

As you see the results of events with pregenerated indirect caller is very close to fast events, but we preserve ability to use arbitraty delegate. Cool, isn't it?