The Computer Language
Benchmarks Game

binary-trees F# Mono LLVM program

source code

(*
      The Computer Language Benchmarks Game
      http://benchmarksgame.alioth.debian.org/ 

      Contributed by Don Syme
      Port of C# version by by Marek Safar and optimized by kasthack
*)

open System

[<AllowNullLiteral>]
type TreeNode(left:TreeNode,right:TreeNode,item) = 
    member __.CheckSum =
        match right with 
        | null -> item 
        | _ -> item + left.CheckSum - right.CheckSum

let rec mkTree(item, depth) =
    if depth = 0 then TreeNode(null, null, item)
    else TreeNode(mkTree (2*item - 1, depth-1), mkTree(2*item, depth-1), item)

//let bottomUpTree (item, depth) = mkTree(item, depth - 1)
let bottomUpTree (item, depth) = mkTree(item, depth - 1)

let minDepth = 4
[<EntryPoint>]
let main argv = 
    let n = if argv.Length > 0 then Int32.Parse(argv.[0]) else 0
    let maxDepth = Math.Max(minDepth + 2, n)
    let stretchDepth = maxDepth + 1
    let mutable check = bottomUpTree(0, stretchDepth).CheckSum
    Console.WriteLine("stretch tree of depth {0}\t check: {1}", stretchDepth, check)
    let longLivedTree = bottomUpTree(0, maxDepth)
    for depth in minDepth .. 2 .. maxDepth do
         let iterations = 1 <<< ( maxDepth - depth + minDepth )
         check <- 0
         for i in 1 .. iterations do 
            check <- check + bottomUpTree(i, depth).CheckSum
            check <- check + bottomUpTree(-i, depth).CheckSum
         Console.WriteLine("{0}\t trees of depth {1}\t check: {2}",iterations * 2, depth, check)
    Console.WriteLine("long lived tree of depth {0}\t check: {1}",maxDepth, longLivedTree.CheckSum)
    0

    

notes, command-line, and program output

NOTES:
32-bit Ubuntu one core
F# Compiler for F# 4.0 (Open Source Edition)
Mono JIT compiler version 4.5.1 (master/3e844dd Fri May  6 19:24:07 PDT 2016)
	LLVM:          yes(3.6.0svn-mono-master/9f79399)
	GC:            sgen



Sat, 07 May 2016 18:02:51 GMT

MAKE:
mv binarytrees.fsharp binarytrees.fs
/usr/local/bin/fsharpc --target:exe --platform:x86 -O  -o binarytrees.fsharp_run.exe binarytrees.fs
F# Compiler for F# 4.0 (Open Source Edition)
Freely distributed under the Apache 2.0 Open Source License
rm binarytrees.fs
4.59s to complete and log all make actions

COMMAND LINE:
/usr/local/bin/mono --llvm --gc=sgen binarytrees.fsharp_run.exe 20

PROGRAM OUTPUT:
stretch tree of depth 21	 check: -1
2097152	 trees of depth 4	 check: -2097152
524288	 trees of depth 6	 check: -524288
131072	 trees of depth 8	 check: -131072
32768	 trees of depth 10	 check: -32768
8192	 trees of depth 12	 check: -8192
2048	 trees of depth 14	 check: -2048
512	 trees of depth 16	 check: -512
128	 trees of depth 18	 check: -128
32	 trees of depth 20	 check: -32
long lived tree of depth 20	 check: -1