Why is this piece of code not faster?

Question

I've made a "copy" of a piece of java code that runs in approx. 400 ms (https://gist.github.com/threecee/cb1c55ad1ce9ac4b1903). My version in F# that uses Parallel.ForEach and I have also tried with PSeq but none of the versions is faster than 7 seconds.

It's not that I must have my piece of code faster than the one I copied but I would really like to know what could have been done to improve the performance in a sample calculations like this in F#.

open System.Threading.Tasks
#time 
let calculateProducts n =
    let bits = [| for i in 1 .. ((n+1)*(n+1)) -> 0 |]
    let inner i =
        [|i..n|] |> Array.map (fun j -> bits.[j*i] <- 1) |> ignore
    Parallel.ForEach([|1 .. n|], (fun i -> inner i)) |> ignore
    bits |> Array.sum
printfn "%i" (calculateProducts 8000)

What the code does is calculating all the unique products x*y where x: 1->8000 and y: 1-8000.

UPDATE: The updated code after using Array.init as jpe suggested in an answer look likes this:

open System.Threading.Tasks
#time 
let calculateProducts n =
    let bits = Array.init ((n+1)*(n+1)) (fun _ -> 0)        
    let inner i =
        let arr = Array.init (n-i+1) (fun x -> x+i)
        Parallel.ForEach(arr, (fun j -> bits.[j*i] <- 1)) |> ignore
    let arr = Array.init n (fun x -> (x+1))
    Parallel.ForEach(arr, (fun i -> inner i)) |> ignore
    bits |> Array.sum
printfn "%i" (calculateProducts 8000)

Just using `Parallel.ForEach` does not automatically imply better performance... There´s a performance penalty due to thread-/task-initialization, which probably takes longer than the actual operation within the loop. — Matze, Dec 06 '14 at 19:00
@Matze, so what do you suggest to improve this? I do think it should be possible to come to close to the performance of the linked to java code. — Tomas Jansson, Dec 06 '14 at 19:03

score 5 · Accepted Answer · edited May 23 '17 at 11:51

You need to use the built in array initialization code as your current array initialization takes ages in the example. Thus replace the line

let bits = [| for i in 1 .. ((n+1)*(n+1)) -> 0 |]

with line

let bits = Array.init ((n+1)*(n+1)) (fun _ -> 0)

and you should get performance comparable to the Java code.

Update: As John Palmer suggested, Array.zeroCreate will make initializing an array to zeros even faster. Thus if you just need to initialize the array to zeros and not compute any initial values, then use

let bits = Array.zeroCreate ((n+1)*(n+1))

Update: The reason why it is so fast has previously been explained here. Short summary: it uses the appropriate IL bytecode command newarr for initialization that in turn has been optimized in the runtime of .Net to be very fast. Array.init is faster than straight forward "manual" initialization because it calls zeroCreateUnchecked to initialize the array and then runs the initialization function over the already initialized array.

If you wonder where the code is then here are the links: implementation of Microsoft.FSharp.Collections.Array that in turn calls internal implementation in Microsoft.FSharp.Primitives.Basics.Array.

Thank you sir. Didn't know that Array.init is so much faster. Do you know it is faster? — Tomas Jansson, Dec 06 '14 at 19:53

score 0 · Answer 2 · answered Dec 11 '14 at 11:03

I think the theoretical answer for WHY Java is so much faster could be here: http://palladin.github.io/StreamsPresentation/#/10

Using that library in F# should possibly (or at least its "promised" to) be faster.

Its source is available at: https://github.com/nessos/Streams

Or at nuget: https://www.nuget.org/packages/Streams/

Hopefully then you are comparing Java apples and F# apples (ok not apples, but streams ;-)

It wont change your code to much either I think...

Why is this piece of code not faster?

2 Answers2