Back to Questions
1.1k
views6
comments
discriminated unions faster than integers?
f#

a friend posed a question - implementing a modified Knight's Tour problem (number of ways to navigate a n x m field moving like a Knight chess piece). i threw something real quick together in f#, and then tried an experiment. i encoded the next move to take as a discriminated union of possible directions - LeftC/LeftCW (clockwise/counterclockwise) etc, and had a function that actually calculated the new coordinate through a pattern match:

1
2
3
4
5
6
7
8
9
10
11
12

let move direction position = 
    let m = fun x y -> (fst position) + x, (snd position) + y

    match direction with
    | LeftC -> m -2 -1
    | LeftCW -> m -2 1
    | RightC -> m 2 -1
    | RightCW -> m 2 1
    | UpC -> m -1 -2
    | UpCW -> m 1 -2
    | DownC -> m -1 2
    | DownCW -> m 1 2

now, when (thinking that this would be faster) i changed it to be just an integer implementation, e.g. modified the type of "direction" to be int * int, and move to be 

1
2
3

let move direction position = (fst position) + (fst direction), (snd position) + (snd direction)

and encoded the direction values directly in the calling code, it was 2x slower!

idears? is it the fact that i'm then calling fst and snd on direction rather than doing a pattern match? is it that the discriminators are stored as narrower fields than an int32? i'm lost...

.
1

let move direction position = (fst position) + (fst direction), (snd position) + (snd direction)

I think the problem is that your new code sucks donkey brains through a straw. ;-)

Try:

1

let move (dx, dy) (px, py) = px+dx, py+dy

To avoid all those superfluous calls to fst and snd (yuk!).

By on 4/11/2009 6:54 AM ()

Well it's certainly prettier without the calls, but F# compiles both to the same IL, byte for byte.

By on 4/12/2009 11:10 PM ()

Discriminated unions have a tag field to tell which type they are. (When there is extra, different data involved on cases, subclasses are generated too, but that's not the issue here.)

So, to do such a pattern match, a jump table is created, and that generates nice native code. In this case, everything lines up perfectly, so the actual switch comes down to a single jmp afaik. The lambda "m" gets inlined, so that's handy too.

As to why this is any faster or slower, my only guess is that there's an extra 2 field accesses per execution, and sometimes the JIT doesn't do such a hot job with those? Also, if you mark "move" inline, does that cause much of a perf difference?

By on 4/10/2009 11:34 PM ()

Well, I guess I shouldn't talk without benchmarking :P. Here's a small micro benchmark:

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

#light

type Direction = | LeftC | LeftCW | RightC | RightCW | UpC | UpCW | DownC | DownCW

let move1 direction position = 
    let m = fun x y -> (fst position) + x, (snd position) + y
    match direction with
    | LeftC -> m -2 -1
    | LeftCW -> m -2 1
    | RightC -> m 2 -1
    | RightCW -> m 2 1
    | UpC -> m -1 -2
    | UpCW -> m 1 -2
    | DownC -> m -1 2
    | DownCW -> m 1 2
    
let move2 direction position = (fst position) + (fst direction), (snd position) + (snd direction)

//System.Diagnostics.Debugger.Launch()

let arrSize = 1000000

let ps1 = Array.init arrSize (fun _ -> RightC)
let ps2 = Array.init arrSize (fun _ -> -1, -2)
let rs = Array.init arrSize (fun _ -> 0,0)

let mutable res = (0,0)
let sw = System.Diagnostics.Stopwatch.StartNew()
for i = 0 to 100000000 do
  //res <- move1 ps1.[i % arrSize] rs.[i % arrSize]
  res <- move2 ps2.[i % arrSize] rs.[i % arrSize]
printfn "%A" (sw.ElapsedMilliseconds)

I had to mark both inlnie and set arrSize to something suitable before move1 was faster than move2. Even so, the times generally seemed to be within 10% of each other.

By on 4/11/2009 12:37 AM ()

This is where it's good to break out Reflector or ildasm. Perhaps the F# compiler is able to inline/optimize one but not the other?

By on 4/9/2009 6:23 PM ()

fair 'nuff. i'll check it out tomorrow...

By on 4/9/2009 9:51 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