Back to Questions
1.8k
views3
comments
fold_left: functional versus imperative speed
f#functional

I've often wondered how efficient it was in F# to express algorithms in terms of higher order functions like fold. Here is an example of a simple calculation of the extent (bounding box) of a given geometry. The simple functional solution using fold is about 10 times slower than the obvious imperative solution. I am curious how much of the gap in performance is something that we can imagine being addressed in future in the F# compiler, how much of it may come to the JIT compiler, and how much of it is just the nature of the beast. Here is the (simplified) code. (Compiling with optimization level 3, naturally)

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#light
open System

[<Struct>]
type Coord2D = { X:double; Y:double } with 
    static member Min a b = {X=Math.Min(a.X,b.X); Y=Math.Min(a.Y,b.Y)}
    static member Max a b = {X=Math.Max(a.X,b.X); Y=Math.Max(a.Y,b.Y)}

and Extent2D = { Min:Coord2D; Max:Coord2D } with
    static member Inf = {Min=Coord2D.NegInf; Max=Coord2D.Inf}
    static member NegInf = {Min=Coord2D.Inf; Max=Coord2D.NegInf} 

and Geometry = 
    | EmptyGeometry
    | Point of Coord2D
    | Line of array<Coord2D>
    | Polygon of array<Coord2D>

let Extent = function
    | EmptyGeometry -> failwithf "Empty Geometry has no extent"
    | Point c -> { Min=c; Max=c }
    | Line cs | Polygon cs -> 
        cs |> Array.fold_left (fun e c -> {Min=Coord2D.Min e.Min c; Max=Coord2D.Max e.Max c}) Extent2D.NegInf

let ExtentIterative = function
    | EmptyGeometry -> failwithf "Empty Geometry has no extent"
    | Point c -> { Min=c; Max=c }
    | Line cs | Polygon cs ->
        let mutable xmin = Double.PositiveInfinity
        let mutable ymin = Double.PositiveInfinity
        let mutable xmax = Double.NegativeInfinity
        let mutable ymax = Double.NegativeInfinity
        for i in 0 .. cs.Length-1 do
            let c = cs.[i]
            if c.X < xmin then xmin <- c.X
            if c.Y < ymin then ymin <- c.Y
            if c.X > xmax then xmax <- c.X
            if c.Y > ymax then ymax <- c.Y
        done
        {Min={X=xmin;Y=ymin}; Max={X=xmax;Y=ymax}}

 let p = Polygon [| for i in 1 .. 10000 -> {X=double i; Y=double i*2.0} |]
    
begin
    for i in 1 .. 10000 do 
        ExtentIterative p |> ignore // 2 seconds; functional Extent takes about 20
end

The functional version of the code might in theory reduce to the imperative version given, depending on just how far functions are expanded & analyzed, tail calls turned to loops, redundant structures being reused, etc. The fold function itself would turn into Should we ever expect that Extent will be as fast as ExtentIterative?

Interestingly, if compiled with no optimization, the iterative version gets six times slower, taking about 12 seconds, while the functional version gets only 30% slower at 26 seconds..

Thanks for any insight!

Cheers,

Sebastian Good

.

My guess is that the performance difference does not come from using 

1

Array.fold_left

per se. 

1

Array.fold_left

should be almost as fast as a loop. Where I think the problem is is in the function passed to 

1

Array.fold_left

. This function allocates 3 objects per iteration: 2 Coord2D and 1 Extent2D. So in total Extent will allocate 30003 objects whereas 

1

ExtentIterative

will allocate only 3.

By on 6/6/2008 11:33 PM ()

indeed, but one always has the hope in a program written functionally that the compiler can recognize all these allocations are unnecessary and the original object can be side-effected to conserve memory. once it knows that, it might even be able to hold the four relevant values in registers, which is what i assume ultimately happens with the imperative loop. we assume, for instance, that the compiler is very smart about not allocating unnecessary tuples during a tail recursion.

By on 6/7/2008 11:07 AM ()

Yep, this kind of "localized" imperative programming can occasionally be needed with F#.

It goes without saying that you should generally only adjust code in this way once you have determined that a particular piece of code is the hot spot for an application. Functional first, imperative later. :-)

Kind regards

Don

By on 6/7/2008 11:25 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