Idiomatic F# – Functional vs. Imperative

re: Idiomatic F# – Functional vs. Imperative

ChrSmith — Fri, 24 Apr 2009 20:13:45 GMT

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.

re: Idiomatic F# – Functional vs. Imperative

James Hugard — Fri, 24 Apr 2009 18:50:12 GMT

(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

re: Idiomatic F# – Functional vs. Imperative

Jason Kikel — Fri, 24 Apr 2009 18:32:51 GMT

@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

re: Idiomatic F# – Functional vs. Imperative

James Hugard — Fri, 24 Apr 2009 18:17:45 GMT

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

re: Idiomatic F# – Functional vs. Imperative

James Hugard — Fri, 24 Apr 2009 17:44:57 GMT

@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

re: Idiomatic F# – Functional vs. Imperative

Jason Kikel — Fri, 24 Apr 2009 15:48:11 GMT

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.

re: Idiomatic F# – Functional vs. Imperative

jcmincke — Fri, 24 Apr 2009 10:46:21 GMT

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)

Advantages:

- Shorter code, async manages all threading aspects.

- No side effect

Regards

J-C

re: Idiomatic F# – Functional vs. Imperative

Keith Farmer — Fri, 24 Apr 2009 00:27:15 GMT

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

re: Idiomatic F# – Functional vs. Imperative

Tom Jakcson — Fri, 24 Apr 2009 00:15:37 GMT

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

re: Idiomatic F# – Functional vs. Imperative

MichaelGG — Thu, 23 Apr 2009 21:42:37 GMT

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) "