Back to Questions
1.1k
views4
comments
Some timings on summing
f#

For what it’s worth I tried timing 2 different ways of summing a list of integers. I used the #time directive – I don’t know if that’s the right way to time things or not. It produced what appeared to be wall time and CPU time.

------------------------

The first method was by using a fold:

1
2
3
4

    #time;;
        [1..1000000]
        |>List.fold1_left (+);;
    #time;;

This produced results that looked like:

1
2

    Real: 00:00:00.611, CPU: 00:00:00.531, GC gen0: 8, gen1: 5, gen2: 1
    val it : int = 1784293664

I don’t what all of it means, but I would guess that it took .531 seconds to run. Assuming that’s the case, I ran it a bunch of times, getting a variety of results:
.703; .390; .546; .531; .562

------------------------

Next I tried a “for loop”:

1
2
3
4
5
6
7
8
9

    #time;;
    let xy n =
        let ay = ref 0
        for j = 1 to n do
            ay := !ay + j 
        done
        printfn("%A") ay    
    xy(100000000);;
    #time;;

This produced the following timings:
.00; .00; .15; .00; .00

Bumping the 1 million up to 100 million (for the for loop) resulted in:
.218; .218; .234; .234; .234

------------------------

Next, I tried adding random numbers instead. I started what follows by defining:

1

  let rand = new System.Random()

Then using fold I wind up with:

1
2
3
4

#time;;
[for i in 0..1000000 -> rand.Next()]
|>List.fold1_left (+);;
#time;;

This produced the following timings:
.796; .921; .640; .937; .609
----------------------

Doing it with the for loop:

1
2
3
4
5
6
7
8
9

#time;;
let xy n =
    let ay = ref 0
    for j = 1 to n do
        ay := !ay + rand.Next() 
    done
    printfn("%A") ay    
xy(1000000);;
#time;;

This produced times all equal to .31. Not as dramatically different, but still twice as good.

----------------------

I don’t know how to look at the IL code, nor am I confident it would mean a tremendous amount to me. But it seems, at least for these simple cases that using a for loop with a mutable variable works better than the List.

I’d like to ask a few questions…

  • Am I doing the timing correctly? Or, is there a better way to do that?
  • Any thoughts on the speed differences?
  • Is there some dark side to using a for loop and a mutable variable?

Thanks for listening.

Mitchell

.

> Any thoughts on the speed differences?

Your timings are a bit slanted by the construction of the list. Essentially, you're timing the act of creating a list of 1000000 cons cells and <i>then<i> summing them. Most of that time is in the creation. When compared with raw calculation in a loop, recursively pattern matching over a list (as fold_left does) will certainly be slower. It's not really a fair comparison. [:)] > Is there some dark side to using a for loop and a mutable variable? Not really. Mutable state isn't necessarily a bad thing -- especially when it's neatly encapsulated inside a function like you've done. In that case there aren't any side effects. In fact, you'll find lots of code in the F# libraries themselves that are written similarly. However, if you want to write in a more functional style that doesn't use a for-loop with a mutable accumulation variable, you could define the function in terms of recursion. This function should be just as fast: <code lang=fsharp> #time;; let xy n = let rec aux acc i = if i > n then acc else aux (acc + i) (i + 1) printfn("%A") (aux 0 1) xy(100000000);; </code>

By on 1/29/2008 5:51 AM ()

Dustin,

Thanks for the response. I tried out your code and interestingly it was about twice as fast as my "for loop". Then, just for fun I tried adding random numbers rather than the consecutive integers. Oddly, in that case both routines took exactly the same amount of time, 2.109 seconds on my machine.

Thanks again.

Mitchell

By on 1/31/2008 1:56 PM ()

You can replace the list with a sequence. This is a basic collection that only implments IEnumerable, because it only implments IEnumerable - its lazy there's no construction time:

1
2

{ for i in 0..1000000 -> rand.Next() }
|>Seq.fold1 (+);;

Given the following snippets:

1)

1
2

[for i in 0..1000000 -> rand.Next()]
|>List.fold1_left (+);;

2)

1
2

{ for i in 0..1000000 -> rand.Next() }
|>Seq.fold1 (+);;

3)

1
2
3
4
5
6
7

let xy n =
    let ay = ref 0
    for j = 1 to n do
        ay := !ay + rand.Next() 
    done
    printfn("%A") ay    
xy(1000000);;

On my laptop this gives the following timings:

1) 00.934, 00.933, 01.194

2) 00.545, 00.530, 00.499

3) 00.46, 00.41, 00.40

So the sequence still has a little extra overhead, but its only a gnat's whisker off the mutable solution.

By on 1/29/2008 12:52 PM ()

Robert,

Thanks for the suggestion, the information and the experimentation. I'll have to read up on what a sequence is.

Mitchell

By on 1/30/2008 5:00 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper