Back to Questions
1.8k
views8
comments
Huge difference in speed between two very similar functions
f#

Hi,

Addendum: How does one do syntax highlighting here?

I understand the importance of tail recursion, and I was keen to test the differences between normal recursion and tail recursion. To wit, I wrote the following two functions:

(* Ordinary recursion *)

let t_0_r = System.DateTime.Now;;

let rec flatten_list_r (s : ('a list) list) =

match s with

|[] -> [];

|_ as h :: t -> h @ flatten_list_r t;;

flatten_list_r [for x in [1 .. 2048] do yield [1 .. x]];;

let t_1_r = System.DateTime.Now;;

printfn "%s" ((t_1_r - t_0_r).ToString());;

(* Tail recursion *)

let t_0_t = System.DateTime.Now;;

let flatten_list_t (s : ('a list) list) =

let rec flatten_list_t_helper (s : ('a list) list) (accu : 'a list) =

match s with

|[] -> accu;

|_ as h :: t -> flatten_list_t_helper t (accu @ h);

flatten_list_t_helper s [];;

flatten_list_t [for x in [1 .. 2048] do yield [1 .. x]];;

let t_1_t = System.DateTime.Now;;

printfn "%s" ((t_1_t - t_0_t).ToString());;

But there is a huge difference in speed between the two functions. The first function runs in the following time:

> 00:00:05.1605160

val it : unit = ()

whereas the second function runs in the following time:

> 00:07:55.9207782

val it : unit = ()

Can someone (brianmcn?) please tell me why this is the case?

Thanks in advance for your help.

.

You've fallen victim to one of the common traps I wrote about a while ago:

[link:lorgonblog.spaces.live.com]

Basically, if you find yourself using '@', then you are probably doing something wrong. The List append operator is O(N) in its first argument, and in your tail-recursive code, the first argument keeps getting longer and longer...

So see if you can rewrite both functions using only the cons operator '::' (it is ok to build the answer in reverse order and then call List.rev at the end).

To see how to format code on hubfs, reply to this message by hitting 'Quote' and look at my message code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

 

open System.Diagnostics 

(* Ordinary recursion *) 
let bigListOfLists = [for x in [1 .. 2048] do yield [1 .. x]]

let rec flatten_list_r (s : ('a list) list) = 
    match s with 
    |[] -> []; 
    |_ as h :: t -> h @ flatten_list_r t;; 

let sw1 = Stopwatch.StartNew()
let ignoreResult1 = flatten_list_r bigListOfLists
printfn "Took %dms" sw1.ElapsedMilliseconds 

(* Tail recursion *) 
let flatten_list_t (s : ('a list) list) = 
    let rec flatten_list_t_helper (s : ('a list) list) (accu : 'a list) = 
        match s with 
        |[] -> accu; 
        |_ as h :: t -> flatten_list_t_helper t (accu @ h); 
    flatten_list_t_helper s [];; 

let sw2 = Stopwatch.StartNew()
let ignoreResult2 = flatten_list_t bigListOfLists
printfn "Took %dms" sw1.ElapsedMilliseconds
By on 7/20/2009 8:24 PM ()

Brian, you rock!

Here's my new attempt. It is much faster than my older version, but feel free to tell me if the code is correct idiomatically.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

(* Tail recursion *)

let flatten_list_t (s : ('a list) list) =

    let rec cons_append (u : 'a list) (v : 'a list) =

        match v with

        |[] -> u;

        |_ as h :: t -> cons_append (h :: u) t in

    let rec flatten_list_t_helper (s : ('a list) list) (accu : 'a list) =

        match s with

        |[] -> accu;

        |_ as h :: t -> flatten_list_t_helper t (cons_append accu h);

    flatten_list_t_helper s [];;

let sw_t = System.Diagnostics.Stopwatch.StartNew();;

let i_t = flatten_list_t [for x in [1 .. 2048] do yield [1 .. x]];;

printfn "%dms" sw_t.ElapsedMilliseconds;;

And this one ran in

1
2
3
4
5
6
7
8

>

4082ms

val it : unit = ()

> >
By on 7/21/2009 4:17 PM ()

Curious -- how efficient is List.rev? Assuming it's O(n), does it need to iterate over the list just once or does it need to make several passes?

By on 7/21/2009 11:54 PM ()

Curious -- how efficient is List.rev? Assuming it's O(n), does it need to iterate over the list just once or does it need to make several passes?

Just once. It just takes elements from the front of the original list, and adds them to the front of the result list.

You can look at the code in your F# install directory, to see for yourself.

By on 7/22/2009 5:47 AM ()

Come to think of it, I don't remember why I even thought it might take more than one iteration. I'll blame the heat for now.

The source is a good read. It's amazing how much of F# is written in F#.

By on 7/22/2009 6:37 PM ()

Hi,

How would I inspect the code in my F# installation directory?

On my computer, F# is installed in C:\Program Files\Microsoft F#\v4.0, but I don't see any code files there, only DLL files and executables.

(Sorry, I am fairly new to Windows. I used Linux until now.)

By on 7/22/2009 7:28 PM ()

Um, I hate to reprise an old discussion that might have been put to rest, but I have another question on the same topic.

As stated earlier, the modified tail recursive version ran very fast indeed. But another definition, which is very similar, takes an incredible amount of time to run.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

let rec flatten_list_w (s : ('a list) list) (a : 'a list) =

    let rec cons_append (u : 'a list) (v : 'a list) =

        match v with

        |[] -> u;

        |_ as h :: t -> cons_append (h :: u) t in

    match s with

        |[] -> a;

        |_ as h :: t -> flatten_list_w t (cons_append a h)

    |> List.rev;;

let sw_w = System.Diagnostics.Stopwatch.StartNew();;

let i_w = flatten_list_w [for x in [1 .. 2048] do yield [1 .. x]] [];;

printfn "%dms" sw_w.ElapsedMilliseconds;;

This version ran in

1
2
3
4

1332966ms

val it : unit = ()

What could be the reason for the huge difference?

Thanks for your help.

By on 7/26/2009 7:22 PM ()

You're calling List.rev (O(N)) in every iteration of flatten_list_w on the growing accumulator, thus again O(N^2).

BTW, regarding the source code, it only ships with the redist/2008 version of F#, so you'd need to download that to inspect the code (the code is not part of the VS2010Beta1 install).

By on 7/26/2009 9:17 PM ()

    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