The Computer Language
Benchmarks Game

binary-trees F# Mono LLVM #4 program

source code

// The Computer Language Benchmarks Game
// http://benchmarksgame.alioth.debian.org/
//
// contributed by Reed Adams

open System


type Node =
    | Branch of Node * Node * int
    | Leaf of int

let rec GenNode depth item =
    if depth = 0
    then Leaf(item)
    else
        let i = item * 2
        let d = depth - 1
        Branch( (GenNode d (i - 1)), (GenNode d i), item )

let inline GenTree depth = GenNode (depth - 1)

let rec GetCheckSum = function
    | Leaf i          -> i
    | Branch(l, r, i) -> i + (GetCheckSum l) - (GetCheckSum r)


[<EntryPoint>]
let main argv =

    let depth = if argv.Length > 0
                then Int32.Parse(argv.[0])
                else 20

    let min_depth = 4
    let max_depth = Math.Max(min_depth + 2, depth)

    let stretch_depth = max_depth + 1

    GenTree stretch_depth 0
    |> GetCheckSum
    |> printfn "stretch tree of depth %i\t check: %i" stretch_depth

    let long_lived_tree = GenTree max_depth 0

    for cur_depth in min_depth ..2 ..max_depth do
        let iterations = 1 <<< (max_depth - cur_depth + min_depth)
        let mutable check = 0
        for i in 1 ..iterations do
            check <- check
                     + GetCheckSum (GenTree cur_depth i)
                     + GetCheckSum (GenTree cur_depth -i)

        printfn "%i\t trees of depth %i\t check: %i" (iterations * 2) cur_depth check

    long_lived_tree
    |> GetCheckSum
    |> printfn "long lived tree of depth %i\t check: %i" max_depth
    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



Wed, 09 Nov 2016 23:28:57 GMT

MAKE:
mv binarytrees.fsharp-4.fsharp binarytrees.fsharp-4.fs
/usr/local/bin/fsharpc --target:exe --platform:x86 -O  -o binarytrees.fsharp-4.fsharp_run.exe binarytrees.fsharp-4.fs
F# Compiler for F# 4.0 (Open Source Edition)
Freely distributed under the Apache 2.0 Open Source License

/home/dunham/benchmarksgame_onecore/binarytrees/tmp/binarytrees.fsharp-4.fs(6,1): warning FS0221: The declarations in this file will be placed in an implicit module 'Binarytrees.fsharp-4' based on the file name 'binarytrees.fsharp-4.fs'. However this is not a valid F# identifier, so the contents will not be accessible from other files. Consider renaming the file or adding a 'module' or 'namespace' declaration at the top of the file.
rm binarytrees.fsharp-4.fs
16.38s to complete and log all make actions

COMMAND LINE:
/usr/local/bin/mono --llvm --gc=sgen binarytrees.fsharp-4.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