Lukas Domagala

I ran into some rather interesting numbers while trying to optimize my Connect Four implementation. Try to guess what this code will print out:

let test=
    let stop1 = Stopwatch.StartNew()
    let list = [1..1000000]     
    let bla = list |> List.fold (fun state x -> state + x) 0
    stop1.Stop()
    let stop2 = Stopwatch.StartNew()
    let seq = seq{1..1000000} |> Seq.fold (fun state x -> state + x) 0
    stop2.Stop()  
    let stop3 = Stopwatch.StartNew()
    let arr = [|1..1000000|]     
    let arr1 = arr|> Array.fold (fun state x -> state + x) 0
    stop3.Stop()
    let stop4 = Stopwatch.StartNew()
    let seqList = [1..1000000] |> Seq.fold (fun state x -> state + x) 0
    stop4.Stop()  
    printfn "list: %d seq: %d array: %d seqList: %d" 
            stop1.ElapsedTicks 
            stop2.ElapsedTicks 
            stop3.ElapsedTicks 
            stop4.ElapsedTicks

list: 18357402 seq: 10837883 array: 8420279 seqList: 15246287

It seems creating a list enumerable takes about double the time it takes to create either a sequence or an array. Usually this does not matter that much, but it can give you worse performance if you are using fold/map instead of manual looping. I guess there is a performance hit for simplicity…

Lets see how well we can do in the imperative world:

let test2=
    let stop1 = Stopwatch.StartNew()
    let mutable i = 1
    let mutable y = 0
    while i < 1000000 do
        y <- y+i
        i <- i+1
    stop1.Stop()
    printfn "loop: %d" stop1.ElapsedTicks

loop: 40852

Interesting, it seems most of the time is wasted creating the data structure we want to loop over, so what happens if we don’t count the creation of the array?

let test3=
    let array = [|1..1000000|] 
    let stop = Stopwatch.StartNew()
    let result = array |> Array.fold (fun state x -> state + x) 0
    stop.Stop()  
    printfn "array: %d" stop.ElapsedTicks

array: 65653

Well we are getting closer. Although we have to problem now that we have to cache the arrays we want to loop over. Lets try not being so wasteful and doing it all in a nice recursive loop:

let test4=
    let sum x=
        let rec loop x y =
            if y = 0 then x
            else loop (x+y) (y-1)
        loop 0 x
    let stop = Stopwatch.StartNew()
    let result =sum 1000000
    stop.Stop()
    printfn "recursive: %d" stop.ElapsedTicks

recursive: 28952

Nice, its faster then the imperative version. The problem with this code is that it does not state its intent at all. When i folded over the array version it took a second and i knew what the code was supposed to do. The same thing can’t be said for the imperative or the recursive version. It seems you have to sacrifice a lot of performance for readability sometimes. I´m not really looking forward to rewriting all my tight loops into these recursive monsters…