Hi,

I'm doing a little research on parallelizing functional algorithms using .NET 4 and F#. And I've come across some questions while trying to figure out Parallel QuickSort.

Basically, I started with the most simple sequential version:
let rec qsort_seq = function

| [] -> []

| head ::

tail ->

let (left, right) = List.partition (fun x -> x <

head) tail

qsort_seq left @ [head] @ qsort_seq right

And came to:
let rec qsort_par list =

match list with

| [] -> []

| head ::

tail ->

let (left, right) = List.partition (fun x -> x <

head) tail

let t1 = Task.Factory.StartNew(fun _ -> qsort_par

left)

let t2 = Task.Factory.StartNew(fun _ -> qsort_par

right)

t1.Result @ [head] @ t2.Result

Now it's running even slower. :) Obviously I'd have to limit the number of Task's created and maybe do some other optimizations. Therefore:
let qsort_par lst =

let rec qsort rec_lvl

= function

| [] -> []

| head :: tail ->

let (left, right) = List.partition (fun x -> x <

head) tail

if rec_lvl < 3 then

let t1 =

System.Threading.Tasks.Task.Factory.StartNew(fun

_ -> qsort (rec_lvl + 1) left )

let t2 =

System.Threading.Tasks.Task.Factory.StartNew(fun

_ -> qsort (rec_lvl + 1) right)

t1.Result @ [head] @ t2.Result

else

qsort (rec_lvl + 1) left @ [head] @ qsort (rec_lvl + 1) right

qsort 1

lst

After that the speed-up is marginal.

Therefore, I'd be very grateful for any comments... Is this a proper way of doing it? Or maybe I should start from the beginning or use other idioms (async?)? How to keep it as simple as it could be?

And primarily I'd like to get some recommendations on which algorithms would be best to parallelize using .NET 4 while maintaining their functional simplicity.

Thanks in advance,
Michal