Hi Group.

I need to implement Prolog-style depth-first search for solving an optimization problem. To avoid producing unnecessary garbage, I chose to represent the DFS stack as an array of nodes (which are structs).

The following code does no actual search, but only traverses all ints from 0 to 2^N-1 in a particular way. The code works, but it could be faster: By using an array of 2n ints instead of an array of n structs (of 2 ints) I get roughly ~60% more performance, both with Microsoft.NET and Mono-2.x.

Can someone tell me why this is? (Is there something slow about structs in F#?)
Thank you in advance!

Best Regards,
Stefan Kral.

Attached snippets:
dfs1_array.fs
dfs1_flatarrayoftwoints.fs
shell-log of runs on Intel Core2 (EM64, 64-bit Linux, Mono 2.2)
---
#light (* dfs1_array.fs: array of structs -*- tuareg -*-)
type node = struct val key:int; val idx:int; new(k,i) = {key=k; idx=i} end

let expand (xs:node []) (ix:int) (x:node) : int =
if x.idx < 0 then ix
else
xs.[ix+1] <- (new node (x.key &&& (~~~ (1 <<< x.idx)), x.idx-1))
xs.[ix+2] <- (new node (x.key, x.idx-1))
ix+2

let rec trav (acc:int) (xs:node []) (ix:int) : int = if ix < 0 then acc else trav (acc+1) xs (expand xs (ix-1) xs.[ix])

let main (args:string array) =
let n = int args.[1]
let stack = Array.create (n+1) (new node(-1,-1))
stack.[0] <- new node((1 <<< n) - 1, n - 1)
Printf.printfn "n = %d, acc = %d" n (trav 0 stack 0)

main (System.Environment.GetCommandLineArgs ())
---
#light (* dfs1_flatarrayoftwoints.fs -*- tuareg -*- *)

let expand (pairs:int array) (ix:int) (x_key:int) (x_idx:int) : int =
if x_idx < 0 then ix
else
pairs.[ix+2] <- x_key &&& (~~~ (1 <<< x_idx))
pairs.[ix+3] <- x_idx - 1
pairs.[ix+4] <- x_key
pairs.[ix+5] <- x_idx - 1
ix+4

let rec trav (acc:int) (pairs:int array) (ix:int) = if ix < 0 then acc else trav (acc+1) pairs (expand pairs (ix-2) pairs.[ix] pairs.[ix+1])

let main (args:string array) =
let n = int args.[1]
let pairs = Array.create (2 * (n+1)) (-1)
pairs.[0] <- (1 <<< n) - 1
pairs.[1] <- n - 1
Printf.printfn "n = %d, acc = %d" n (trav 0 pairs 0)

main (System.Environment.GetCommandLineArgs ())
---
stefan@conroe:~/Desktop/mubench.fs/dfs> time mono dfs1_array.exe 26

n = 26, acc = 134217727

real 0m2.842s

user 0m2.800s

sys 0m0.008s

stefan@conroe:~/Desktop/mubench.fs/dfs> time mono dfs1_flatarrayoftwoints.exe 26

n = 26, acc = 134217727

real 0m1.797s

user 0m1.768s

sys 0m0.000s

---