a wandering wolf

Does a wandering wolf dreams of a wondering, sometimes programming sheep?

このエントリーをはてなブックマークに追加

Let MailboxProcessor Act

Preface

This is the translated text of the topic I’ve written - Let MailboxProcessor Act (ja: MailboxProcessor に処理をさせよう), which is the post for F# Advent Calendar 2013.

About MailboxProcessor

MailboxProcessor is a class to execute asynchronous computations which is built in F# standard library(FSharp.Core). I wrote this topic in another post.

#102 Asynchronous programming with MailboxProcessor (ja: #102 MailboxProcessorで非同期プログラミング) - a wandering wolf

When you pass values as messages to MailboxProcessor(we call it “actor” below), the actor do certain computations. When you need the results of the computations, recieve them as messages. MailboxPRocessor is something like that.

We can get the result from the actor synchronously or asynchronously, whichever we want, so it is used a lot for asynchronous computations.

The purpose of this post

We let this MailboxProcessor act some simple computations asynchronously and in parallel. Also we will take each elapsed time of the computations (only for the comparison).

(* f: a function to exam *)
let timer (f: unit -> unit) =
  let sw = System.Diagnostics.Stopwatch()
  sw.Start()
  f()
  sw.Stop()
  printfn "elapsed time: %d[ms]" sw.ElapsedMilliseconds

Solve FizzBuzz question

At first, we try to solve FizzBuzz question - this will be solved after “Hello, World!” coding if you are a newbie in the programming language - with MailboxProcessor.

(* define a type of a message for FizzBuzz *)
type FizzBuzzMessage = int * AsyncReplyChannel<int * string>

(* solve FizzBuzz simply *)
let fizzbuzz = function
| x when x % 15 = 0 -> "FizzBuzz"
| x when x % 3 = 0  -> "Fizz"
| x when x % 5 = 0  -> "Buzz"
| x                 -> x.ToString()

(* write a computation for an actor to compute *)
let fizzbuzzBody (inbox: MailboxProcessor<FizzBuzzMessage>) =
    let rec loop () = async {
        let! x, replyChannel = inbox.Receive()
        let converted = x |> fizzbuzz
        replyChannel.Reply (x, converted)
        return! loop()
    }
    loop()

(* create an actor (an agent of MailboxProcessor) *)
let fizzbuzzActor = new MailboxProcessor<FizzBuzzMessage>(fizzbuzzBody)

(* Ouverture! *)
fizzbuzzActor.Start()

The code below is for this actor to act.

(* output function. execute with integers from min to max *)
let output<'T> (inbox: MailboxProcessor<int * AsyncReplyChannel<int * 'T>>) min max =
    seq {min..max}
    |> Seq.map(fun i ->
                let f = fun replyChannel -> i, replyChannel
                inbox.PostAndAsyncReply f)
    |> Async.Parallel
    |> Async.RunSynchronously
    |> Array.iter (fun tpl -> snd tpl |> printfn "%A" )

(* how to use 'output' *)
fun _ -> output fizzbuzzActor 1 30
|> timer

When we run it, print the result of fizzbuzz function and then the elapsed time. The following list is my result of 5 times execution.

1: 150[ms]
2: 126[ms]
3: 145[ms]
4: 127[ms]
5: 149[ms]

The results show that the parallel computations of fizzbuzz finish in a moment.

Obtain the Fibonacci numbers

After solving FizzBuzz, we try to obtain the Fibonacci numbers (i.e. to get the n-th Fibonacci number).

(* define a type of a message for Fibonacci numbers *)
type FibonacciMessage = int * AsyncReplyChannel<int * int64>

(* define a function to represent the Fibonacci series *)
let rec fibonacci = function
| 0 -> 0L
| 1 -> 1L
| x -> (fibonacci (x-1)) + (fibonacci (x-2))

(* write a computation for an actor to compute *)
let fibBody (inbox: MailboxProcessor<FibonacciMessage>) =
    let rec loop() = async {
        let! x, replyChannel = inbox.Receive()
        let converted = x |> fibonacci
        replyChannel.Reply (x, converted)
        return! loop()
    }
    loop()

(* create an actor and start computing *)
let fibActor = new MailboxProcessor<FibonacciMessage>(fibBody)
fibActor.Start()

(* take the elapsed time to compute fibonacci function with arguments from 0 to 50 *)
fun _ -> output fibActor 0 50
|> timer

May I have your attention, please. The code above will take very long time to finish. Please take care of running it.

1: 512231[ms]
2: 512068[ms]
3: 512477[ms]
4: 519210[ms]
5: 512220[ms]

Gah! X-(

Improve computations

Now that F# is not the one of pure functional programming languages. In spite of avoiding side effects to be ubiquitous, we use them if needed.

Let us rewrite the previous code. We will improve it with memoization.

(* a map for memoization. give it default values *)
let dict = ref Map.empty
dict := Map.add 0 0L !dict
dict := Map.add 1 1L !dict

(* a memoized Fibonacci function. change the ref map destructively *)
let rec fibonacci2 n =
    if Map.containsKey n !dict then (!dict).[n]
    else
        let result = (fibonacci2 (n-1)) + (fibonacci2 (n-2))
        dict := Map.add n result !dict
        result

(* write a computation for an actor to compute. using the same type of message above *)
let fibBody2 (inbox: MailboxProcessor<FibonacciMessage>) =
    let rec loop() = async {
        let! x, replyChannel = inbox.Receive()
        let converted = x |> fibonacci2
        replyChannel.Reply (x, converted)
        return! loop()
    }
    loop()

(* create an actor and start computing *)
let fibActor2 = new MailboxProcessor<FibonacciMessage>(fibBody2)
fibActor2.Start()

(* compute the Fibonacci number from 0 to 50 in parallel again *)
fun _ -> output fibActor2 0 50
|> timer

Run it.

1: 128[ms]
2: 152[ms]
3:  89[ms]
4: 105[ms]
5: 107[ms]

Yes! As fast as “Lighting Bolt”!!

You may have a question about accessing dict in parallel, but it’s OK. When we add a computed value for the same key, we only overwrite the same value.

Postface

Although we may be attracted to the power of memoization, what I want to say is that we can write parallel computations easily and succinctly using computation expressions with async block(or asynchronous workflows) and MailboxProcessor. In fact, you can write your parallel computations succinctly when you write body functions with top-down.

If you take an interest in MailboxProcessor, you may also have some fun with ‘the Actor model`. Let’s try it! ;-)