Asynchronous workflows in F#

Work has been really busy and I haven't had time to work on any of my side projects until last night, when I had chance to play with asynchronous workflows in F#. I've been wanting to explore to a greater extent what is out there in the world of concurrent and distributed computing, but in order to get started I needed to find some project that would be the catalyst. Not that having a project is absolutely necessary but it helps keep me on task and focused towards an end goal. Some of the ideas I've been tossing around were creating an engine to decrypt/encrypt PGP MIME messages, or build a better load/stress engine, both of which require a large up-front investment of time.

After about a week of going nowhere I stumbled upon the idea of doing swarm animations, and possibly throw in some additional AI behavior if I had time. The thing about doing swarm animations is that each entity in the swarm needs to move in relation to each of it's neighbors which involves a nearest neighbor search, one of those computationally costly and hard to tackle problems. I'm going to start with a really naive brute force approach and evolve it over time, into something more efficient. One of the things that I've been looking at is the Stolfi and Guibas method for creating Voronoi diagrams in order to speed up the nearest neighbor search. It's a divide an conquer algorithm so it should lend itself to parallelization, but that comes later, today I start with asynchronous workflows. The bit of code below had the following runtime on my Dell D620 dual-core laptop when executed using fsi:

Async time: 00:00:34.7309424
Sync time: 00:00:40.1761800

let largest = 800;;

type point = {
    x : double;
    y : double;
}

let rand = new Random();;

let rand_double(max) = 
  System.Convert.ToDouble(rand.Next(max - 1)) + rand.NextDouble();;

let rec quick_sort(x) =
  match x with
  | pivot :: rest ->
      let left, right = List.partition (( > ) pivot) rest in
      quick_sort left @ pivot :: quick_sort right
  | [] -> [];;

let distance(p1, p2) =
  Math.Sqrt(Math.Abs(((p1.x - p2.x) ** 2.0) - ((p1.y - p2.y) ** 2.0)));;

let time(f) =
  let start = DateTime.Now in
  f();
  DateTime.Now - start;;

let neighbors(p, pl) = 
  [for n in pl -> (distance(n, p), n)];;

let async_neighbors(p, pl) = 
  let a = Async.Parallel[for n in pl -> async {return (distance(n, p), n)}] in
  Async.Run(a);;

let sync_test() =
  let pl = [for x in 1..5000 -> {x=rand_double(largest);y=rand_double(largest)}] in
  [for p in pl -> neighbors(p, pl)] |> ignore;;

let async_test() = 
  let pl = [for x in 1..5000 -> {x=rand_double(largest);y=rand_double(largest)}] in
  let a = Async.Parallel[for p in pl -> async { return neighbors(p, pl) }] in
  Async.Run(a) |> ignore;;

let async_test2() = 
  let pl = [for x in 1..5000 -> {x=rand_double(largest);y=rand_double(largest)}] in
  let a = Async.Parallel[for p in pl -> async { return async_neighbors(p, pl) }] in
  Async.Run(a) |> ignore;;  

let cleanup() = 
  GC.Collect();
  GC.WaitForPendingFinalizers();;

do Console.WriteLine("Async time: " + any_to_string(time(async_test)));;  
do cleanup();;
do Console.WriteLine("Sync time: " + any_to_string(time(sync_test)));;

Print this post