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?

Data structures: Finger Tree (Part 1)

So last time we passed prologue and now reached the main part entitled “Finger Trees”.

Initially this data structure was described in this paper.

Linear data structures are widely used in common-day life of every programmer, .NET BCL contains many of such structures, like List, LinkedList (in fact LinkedList is doubly linked list) etc. What we’ll try to do in this post is to create the structure (based on 2-3 trees) with following characteristics:

• Immutable (modification returns new instance of structure with changes applied)
• Enqueue/Dequeue both in start and end in amortized constant time
• Concatenation support

Quick reminder, scheme of 2-3 tree from previous post

type TwoThree<'T> = 
    | Leaf
    | Two of 'T * TwoThree<'T> * TwoThree<'T>
    | Three of 'T * 'T * TwoThree<'T> * TwoThree<'T> * TwoThree<'T>

This definition is very simple and this is one of its biggest advantages. However this structure cannot enforce abidance of main tree invariant: all leaves should be located on the same level. That's why this rule is put in the code of modification operation and this is the reason of complexity and unreadability of this code. This is the balance: reduce complexity in one place and will be increased in another. But everything is not so bad, we can bring more order in code by modifying the structure of 2-3 tree (all data is removed from interim nodes, the only data containers - leaves)

type Tree<'T> =
    | Empty 
    | Single of 'T
    | Multi of Tree<Node<'T>>
and Node<'T> = 
    | Node2 of 'T * 'T
    | Node3 of 'T * 'T * 'T

Notice, that structure of the tree is not regular, first level will be Tree<T>, second - Tree<Node<T>>, third - Tree<Node<Node<T>>> and so on. Operations on such tree usually take log2(N) time, where N - number of elements. However we would like to perform enqueue and dequeue in a constant time...It is time to explain the mistery of the name "Finger tree".

Finger is the structure that provides efficient access to the nodes of the tree near specified location. We'll take end nodes from left and right side and treat them in a different manner - they will behave like a buffer with end elements. The appearance of 2-3 tree with fingers applied is presented on the code below:

type Finger<'T> = 
    | One of 'T
    | Two of 'T * 'T
    | Three of 'T * 'T * 'T
    | Four of 'T * 'T * 'T * 'T
type Node<'T> = 
    | Node2 of 'T * 'T
    | Node3 of 'T * 'T * 'T
type FingerTree<'T> = 
    | Empty
    | Single of 'T
    | Multi of Finger<'T> * FingerTree<Node<'T>> * Finger<'T>

As we may notice the common view of structure remains the same. For further progress we need to extend types with possibiliy to enumerate themselves, later this feature will be used i.e. for fold operations.

type Finger<'T> = 
    | One of 'T
    | Two of 'T * 'T
    | Three of 'T * 'T * 'T
    | Four of 'T * 'T * 'T * 'T

    member x.SeqLeft = 
        seq { match x with
                | One(a) -> yield a
                | Two(a, b) -> yield a; yield b
                | Three(a, b, c) -> yield a; yield b; yield c
                | Four(a, b, c, d) -> yield a; yield b; yield c; yield d  }
    member x.SeqRight = 
        seq { match x with
                | One(a) -> yield a
                | Two(b, a) -> yield a; yield b
                | Three(c, b, a) -> yield a; yield b; yield c
                | Four(d, c, b, a) -> yield a; yield b; yield c; yield d  }

type Node<'T> = 
    | Node2 of 'T * 'T
    | Node3 of 'T * 'T * 'T

type FingerTree<'T> = 
    | Empty
    | Single of 'T
    | Multi of Finger<'T> * FingerTree<Node<'T>> * Finger<'T>

module Nodes = 
    let seqLeft t = 
        seq { match t with
                | Node2(a, b) -> yield a; yield b
                | Node3(a, b, c) -> yield a; yield b; yield c }

    let seqRight t = 
        seq { match t with
                | Node2(b, a) -> yield a; yield b
                | Node3(c, b, a) -> yield a; yield b; yield c }

    let nodeToFinger n = 
        match n with
        | Node2(a, b) -> Two(a, b)
        | Node3(a, b, c) -> Three(a, b, c)

Finger module (code below) contains operations to push and pop values from finger buffers. All operations are trivial except corner case: push to full buffer. Such situation is impossible and controlled by top level push/pop functions, detailed description will be given later in text, for now this should be accepted as an axiom.

let raiseImpossible() = failwith "this should never happen"
let raiseEmpty() = failwith "tree is empty"

module Fingers =
    let peekLeft (t : Finger<_>) = t.SeqLeft |> Seq.head 
    let peekRight (t : Finger<_>) = t.SeqRight |> Seq.head 
    let pushLeft a = function
        | One(b) -> Two(a, b)
        | Two(b, c) -> Three(a, b, c)
        | Three(b, c, d) -> Four(a, b, c, d)
        | _ -> raiseImpossible()
    let popLeft = function
        | Two(_, a) -> One(a)
        | Three(_, a, b) -> Two(a, b)
        | Four(_, a, b, c) -> Three(a, b, c)
        | _ -> raiseImpossible()
    let pushRight a = function
        | One(b) -> Two(b, a)
        | Two(c, b) -> Three(c, b, a)
        | Three(d, c, b) -> Four(d, c, b, a)
        | _ -> raiseImpossible()
    let popRight = function
        | Two(a, _) -> One(a)
        | Three(b, a, _) -> Two(b, a)
        | Four(c, b, a, _) -> Three(c, b, a)
        | _ -> raiseImpossible()
    let seqLeft (t : Finger<_>) =  t.SeqLeft
    let seqRight (t : Finger<_>) = t.SeqRight

To make the picture complete - peek functions for the tree

let peekLeft t = 
    match t with
    | Empty -> raiseEmpty()
    | Single(v) -> v
    | Multi(l, _, _) -> Fingers.peekLeft l

let peekRight t =
    match t with
    | Empty -> raiseEmpty()
    | Single(v) -> v
    | Multi(_, _, r) -> Fingers.peekRight r

Operation “push-to-tree” is rather trivial, except the situaton when finger already contains four elements, in that case we push three elements into middle tree and leave finger with two items. This means, that Fingers.pushLeft should never be called for Finger.Four.

type private CommonOperations() =

    static member pushLeft<'T> (this : FingerTree<'T> ) (a : 'T) : FingerTree<'T> = 
        match this with
        | Empty -> Single(a)
        | Single(b) -> Multi(One a, Empty, One b)
        | Multi(Four(b, c, d, e), m, r) -> Multi(Two(a, b), CommonOperations.pushLeft m (Node3(c,d,e)), r)
        | Multi(l, m, r) -> Multi(Fingers.pushLeft a l, m, r)

Worth noting that pushLeft function is calling itself with different type parameter inside its body. This case is called polymorphic recursion and it cannot be defined in let-bound functions in F#. Instead it can be declared as method of class with full type annotations. This trick is widely used in CommonOperations type. pushRight function is mirror image of pushLeft, so it will be omitted.

Implementation of popLeft function is also non-complex but in that case special situation - one remaining element in finger buffer.

    static member popLeft<'T> (this : FingerTree<'T> )  : FingerTree<'T> =
        match this with
        | Empty -> raiseEmpty()
        | Single(_) -> Empty
        | Multi(One(_), Empty, One(v)) -> Single(v)
        | Multi(One(_), Empty, r) -> Multi(One(Fingers.peekLeft r), Empty, Fingers.popLeft r)
        | Multi(One(_), m, r) -> Multi (Nodes.nodeToFinger (peekLeft m), (CommonOperations.popLeft m), r)
        | Multi(l, m, r) ->  Multi (Fingers.popLeft l, m, r)

popRight is also the mirror case of popLeft.

Enumerating of tree in different directions.

    static member seqLeft<'T> (t : FingerTree<'T>) : seq<'T> = 
        seq { match t with
                | Empty -> ()
                | Single v -> yield v
                | Multi(l, m, r) ->
                    yield! Fingers.seqLeft l
                    yield! CommonOperations.seqLeft m |> Seq.collect Nodes.seqLeft
                    yield! Fingers.seqLeft r  }

    static member seqRight<'T> (t : FingerTree<'T>) : seq<'T> = 
        seq { match t with
                | Empty -> ()
                | Single v -> yield v
                | Multi(l, m, r) ->
                    yield! Fingers.seqRight r
                    yield! CommonOperations.seqRight m |> Seq.collect Nodes.seqRight
                    yield! Fingers.seqRight l  }

We examined enqueue/dequeue and traversing and now proceed to concatenation. This operation is rather primitive when one of arguments is Empty of Single tree and the only difficult case is concatenation of two Multi trees. Left end of first tree and right end of second tree is passed without changes to result tree and middle part is the result of applying merge function with the following signature (tree1-middle)FingerTree<Node<'T>> -> (tree1-right-end)Finger<'T> -> (tree2-left-end)Finger<'T> -> (tree2-middle)FingerTree<Node<'T>> -> (result)FingerTree<Node<'T>> . It is very easy to define function for transforming two fingers to the list of nodes and use it to create generalized concatenation function.

let flip f x y = f y x

    static member flatten a x b = [ yield! Fingers.seqLeft a; yield! x; yield! Fingers.seqLeft b]
    
    static member nodes l = 
        match l with
        | [a; b] -> [Node2(a, b)]
        | [a; b; c] -> [Node3(a, b, c)]
        | [a; b; c; d] -> [Node2(a, b); Node2(c, d)]
        | a::b::c::xs -> Node3(a, b, c)::CommonOperations.nodes(xs)
        | _ -> raiseImpossible()

    static member concat<'T> (t1 : FingerTree<'T>) (ts : 'T list ) (t2 : FingerTree<'T>) : FingerTree<'T> = 
        match t1, t2 with
        | (Empty, t) -> (ts, t) ||> List.foldBack (flip CommonOperations.pushLeft)
        | (t, Empty) -> (t, ts) ||> List.fold CommonOperations.pushRight
        | (Single v, t) -> (v::ts, t) ||> List.foldBack (flip CommonOperations.pushLeft)
        | (t, Single v) -> (t, v::ts) ||> List.fold (CommonOperations.pushRight)
        | Multi(l1, m1, r1), Multi(l2, m2, r2) -> Multi(l1,  CommonOperations.concat m1 (CommonOperations.nodes (CommonOperations.flatten r1 ts l2))  m2, r2)

Two finger trees can be concatenated by calling concat passing empty list as ts argument.

In this post we have explored the possibilities of simple finger tree. It can be basically used as an immmutable deque. Next post will illustarte how to enhance current implementation with effective searching of element with particular property.

Source code: SimpleFingerTree.zip