Idiomatic F# – Functional vs. Imperative


Our story begins with this guy, Stuart Bowers, sipping functional programming cool aid out of a kickass mug from Cafe Press.

IMAGE_154

Stuart is a developer on Amalga and full-time F# developer at Microsoft. The world is at a loss because this man does not blog…

Anyways, he has been reviewing chapters some chapters of my book and we recently had a long conversation about what should be idiomatic F# style which I’d like to share.

The Problem

Question: What is the ‘correct F# way’ to write the following code:

Create a shared, mutable value and spawn two thread pool threads to sum elements in a list. (Intentionally creating a race condition, which was the point of the code example.)

The Imperative (?) Way

Let’s start with how to do this imperatively.

open System.Threading

let sumArray (arr : int[]) =
    let total = ref 0

    // Add the first half
    let thread1Finished = ref false
    ThreadPool.QueueUserWorkItem(
        fun _ -> for i = 0 to arr.Length / 2 - 1 do
                    total := arr.[i] + !total
                 thread1Finished := true
        ) |> ignore

    // Add the second half
    let thread2Finished = ref false
    ThreadPool.QueueUserWorkItem(
        fun _ -> for i = arr.Length / 2 to arr.Length - 1 do
                    total := arr.[i] + !total
                 thread2Finished := true
        ) |> ignore

    // Wait while the two threads finish their work
    while !thread1Finished = false ||
          !thread2Finished = false do

          Thread.Sleep(0)

    !total

The imperative code is very straight forward and offers a few benefits:

  • Simplicity. Not a whole lot is actually going on, just two calls to QueueUserWorkItem and a couple of boolean flags to keep track of when the threads complete.

However, there are some drawbacks too:

  • Redundancy. Both lambdas passed to QueueUserWorkItem are essentially the same, so the code is duplicated. If you want to spice things up, such as adding logging you will either forget to update the code in both locations or simply add it twice.
  • Hidden data. The key difference between the two threads is the range of elements in the array that they sum. The first array counts 0 to len / 2 – 1, the second thread to len / 2 to len. However, this crucial fact is buried in the code in two separate places.

The Functional (?) Way

Now let’s examine how to do this in a more functional style.

open System.Threading

let sumArray (arr : int[]) =
    // Define a location in shared memory for counting
    let total = ref 0

    // Define two flags in shared memory
    let thread1Finished, thread2Finished = ref false, ref false
    
    // Generate a lambda to sum a section of the array. 
    let sumElements (startIndex,endIndex) flag = 
          fun (_:obj) -> 
              for i = startIndex to endIndex do
                total := arr.[i] + !total
              flag := true  
    
    // Divy up the array
    let firstHalf  = 0,(arr.Length / 2 - 1)  
    let secondHalf = (snd firstHalf)+1,(arr.Length - 1)
    
    // Generate Delegates to sum portions of the array
    let thread1Delegate = sumElements  firstHalf  thread1Finished
    let thread2Delegate = sumElements  secondHalf thread2Finished
    
    [ thread1Delegate; thread2Delegate ]       // Queue up the delegates     
    |> List.map ThreadPool.QueueUserWorkItem   // Queue the use work items
    |> ignore                                  // Ignore the results 
        
    // Wait while the two threads finish their work
    while !thread1Finished = false ||
          !thread2Finished = false do

          Thread.Sleep(0)

    !total

Let me start with the drawbacks of this functional style first:

  • Too many values. There are seven let bindings in the function – presumably they are all important.
  • Concept count. This more functional way of doing thing certainly requires you to understand a bit about F# coding. (Mapping the thread code to a curried QueueUserWorkItem is pretty hot though.)

While arguably obfuscated, the functional style offers some clear benefits:

  • Important data is called out. Rather than hard coding the ‘0 to len / 2’ and ‘len / 2 to len’ values, the bounds for which to sum array elements is called out explicitly and on consecutive lines. This makes declaring an off-by-one error much easier to spot and fix.
  • Code reuse. Rather than hard coding the two thread pool functions, a sumElements function is introduced which takes explicit bounds to sum.

Personally I’m partial to the simplicity of the first example, but the value in calling out the range values in the second example shouldn’t be discounted. One of the best things I like about F# is that being a multi-paradigm language there is usually more than one approach to solve a problem, meaning you have options.

Thanks goes to Stuart for letting me post his code. I’m curious to hear what you think with regard to the two styles, please leave a comment and let me know what you think.

Comments (11)

  1. MichaelGG says:

    Well, the top sample is more "throw away". You could lighten up the bottom one by not adding let bindings for the indicies and delegates. Just write them inline in the list.

    I also wouldn’t use List.map. I think I’d go with:

    " |> List.iter (ThreadPool.QueueUserWorkItem >> ignore) "

  2. Tom Jakcson says:

    I really do like the second one, I think it’s worth the ink for the reader.

    1. It’s only longer because it’s far more verbose about the meaning of the values (it gives them names instead of using them inline)

    2. It only appears to have more concepts because fewer concepts are buried in the code (See #1).

    I will admit, however, than the pipeline stuff at the end is a little dense.

    -tjackson

  3. Keith Farmer says:

    I’d as soon use the PLINQ to handle the parallelization, but that wouldn’t be useful to discussing F# imperatively. 🙂

  4. jcmincke says:

    My 2 cents here:

    open System.Threading

    let sumArray (arr : int[]) =

       let mid = (arr.Length / 2 )

       let subArr1 = Array.sub arr 0  mid

       let subArr2 = Array.sub arr (mid) (arr.Length-mid)

       let task1 = async { return Array.sum subArr1 }

       let task2 = async { return Array.sum subArr2 }

       let partialSums = Async.Run (Async.Parallel [ task1; task2 ])

       let r = (Array.get partialSums 0) + (Array.get partialSums 1)

       r

    Advantages:

    – Shorter code, async manages all threading aspects.

    – No side effect

    Regards

    J-C

  5. Jason Kikel says:

    In general I like the functional style more, but I’m not sure your example is fair.  I can see what you are trying to demonstrate, but the situation is contrived.  

    For example, the imperative solution doesn’t have to have two separate thread pool functions.  The core difference between the imperative and functional examples really is whether the thread pool functionality is passed to a higher order function (List.map, List.iter) or whether the functions are manually invoked individually.  

    We can create a sumElements function in the imperative solution and call it twice with different ranges without any of the negatives you describe (hidden data, redundancy, or losing code reuse).

    At the end of the day, jcmincke’s snippet is likely the ‘best’ approach, but I feel that’s outside of what you’re trying to illustrate with this example.

  6. James Hugard says:

    @Chris & Stuart – Won’t the value of ‘total’ often be wrong?

    I fear that I’m missing something fundemental here.  Both examples are multithreaded, both examples update a shared mutable value, but neither protects accesss to that variable in any way.  If both threads retrieve the current value of ‘total’ (the same value), then add something to it, then store the result back, won’t one thread step on the update of the other?

    @jcmincke – looks like your example does not have that problem & is more succint to boot!  However, it makes copies of the arrays which could be a performance issue memory wise.

    Respectfully, all examples will run slower on a single-core by forcing two threads.  They are also limited to arrays of ints.

    The following adapts to the number of cores and can work on any kind of sequence.  It pays the cost of finding the length of a sequence and the cost of skipping sequence elements (sequentially), but should run faster on large arrays as more cores are added.

    #light

    open System.Threading

    let inline sumAsync (xs : ‘a seq) =

       let n = System.Environment.ProcessorCount

       let slice = Seq.length xs / n

       let sumSliceAsync start size =

           async { return xs |> Seq.skip start |> Seq.take size |> Seq.sum }

       {1..n}

       |> Seq.map (fun n -> sumSliceAsync ((n-1)*slice) slice)

       |> Async.Parallel

       |> Async.Run

       |> Seq.sum

  7. James Hugard says:

    Oops.  Forgot about lengths that don’t evenly divide by the number of cores!  Also, forgot about handling lengths smaller than the number of cores! (note, the inline is needed to allow operation on any type ‘a)

    Try this on for size:

    let inline sumAsync (xs : ‘a seq) =

       let len = Seq.length xs

       let n = min len System.Environment.ProcessorCount

       let sliceSize = len / n

       let sumSliceAsync sliceN size =

           let start = (sliceN-1) * size

           let size  = if sliceN < n then size else len – start

           async { return xs |> Seq.skip start |> Seq.take size |> Seq.sum }

       {1..n}

       |> Seq.map (fun sliceN -> sumSliceAsync sliceN sliceSize)

       |> Async.Parallel

       |> Async.Run

       |> Seq.sum

  8. Jason Kikel says:

    @James

    I believe the unsafe sharing of data between threads is intentional and was being used to demonstrate problems of imperatively sharing data between thread pools.  Chris was just posing the question of imperative vs functional as a tangent to that example.

    Further, your code solves the problem nicely but can be improved by leveraging the parallelfx library (PLINQ in particular).

    #light

    open System

    open System.Linq

    let psum (coll:IParallelEnumerable<‘a>) =

      ParallelEnumerable.Sum(coll)

    let inline sumAsync (xs : ‘a seq) =

      xs.AsParallel()

      |> psum  

  9. James Hugard says:

    (Man, wish I could edit my posts)

    On a sufficiently large number of cores, I suppose one would also like to make sure the code does not reduce to the trivial case of summing 0 or 1 elements on each thread:

    open System.Threading

    let inline sumAsync (xs : ‘a seq) =

       let len = Seq.length xs

       let n = min len System.Environment.ProcessorCount

       let sliceSize = len / n

       if sliceSize < 2

       then

           xs |> Seq.sum

       else

           let sumSliceAsync sliceN size =

               let start = (sliceN-1) * size

               let size  = if sliceN < n then size else len – start

               async { return xs |> Seq.skip start |> Seq.take size |> Seq.sum }

           {1..n}

           |> Seq.map (fun sliceN -> sumSliceAsync sliceN sliceSize)

           |> Async.Parallel

           |> Async.Run

           |> Array.sum

  10. ChrSmith says:

    Some great responses! To answer the two big points, yes the example is contrived and yes it does have a data race. The imperative example was one from my book to set the stage for introducing the lock function so it was intentional.

Skip to main content