185779 (2) [Avatar] Offline
#1
The predicate in the quicksort is backwards, it should be

let smaller, larger = List.partition (fun number -> number < firstElement) restOfList


The discussion about determining depth does not make sense to me. On an 8 core system,

Math.Log(float System.Enviroment.ProcessorCount, 2.) + 4


gives 7. (Note that the '4' should actually be '4.') But further down, the text says

The formula limits the number of tasks to approximately sixteen times the number of cores.


That's actually doubly strange, because if it's true, why use the log function? Just multiply ProcessorCount by 16.

The text also refers to a nonexistent 'log2' function.

All of that might be cleared up if the code sample actually contained the line of code that computes the depth, but it doesn't.
Riccardo Terrell (18) [Avatar] Offline
#2
Here my answers:

1) You are correct about the quick-sort, it is backwards. This code fix was corrected a little while ago, and it will be part of the final edit
2) You are correct, '4' should actually be '4.' good catch!
3) The function 'log2' is an abbreviation for Log in base 2. For example, log2(x) represents the logarithm of x to the base 2. I will clarify in the book, thank you for inquiring.
4) About “
limiting the number of tasks to approximately sixteen times the number of cores
”, it means that the number of tasks can be up to sixteen, but not necessarily. Preferably, we want a workload that is balanced, and that doesn’t start more tasks which are not required.

The Quicksort algorithm is a recursive divide-and-conquer algorithm. Ideally, we would like the Quicksort to be balanced, because if so, by starting a Task during each iteration (recursion), when we reach the “depth” level, all processors are saturated. However, this is a rare case, where the Quicksort generates a very unbalanced workload because the fragments produced are not of equal size.
Here is the formula from the example

depth = log2(ProcessorCount) + 4


calculates the depth argument to limit the number of running tasks, which adapts the degree regardless the cases.

Running the QuickSort algorithm, the depth value aims to limit the number of running tasks to approximately sixteen times the number of cores. For example, in the case of 4 cores machine, the depth is

depth = log2(ProcessorCount) + 4, 
depth = log2(2) + 4
depth = 2 + 4


which results in approximately a range between 36 to 64 concurrent tasks, because during each iteration we are starting two tasks for each branch that doubles in each iteration. However, there are cases where the Tasks exploited in QuickSort can be less than sixteen times the number of cores.

I will update the book with a foot note and an explanation, to make it more clear.
I will also expand the code example adding the call of the QuickSort using the computed depth


Thank you for the feedback.
185779 (2) [Avatar] Offline
#3
Ah, now I understand that 'depth' is not the same as 'limit on the number of running tasks'. Thanks!