The Computer Language
Benchmarks Game

binary-trees Swift program

source code

// The Computer Language Benchmark Game
// http://benchmarksgame.alioth.debian.org/
//
// contributed by Ralph Ganszky
// *reset*

import Dispatch
import Foundation

class TreeNode {
    var left, right: TreeNode?

    init(left: TreeNode?, right: TreeNode?) {
        self.left = left
	self.right = right
    }

    func check() -> Int {
	if left != nil {
	    return left!.check() + right!.check() + 1
	} else {
	    return 1
	}
    }
}

func createTree(_ depth: Int) -> TreeNode? {
    if depth > 0 {
	let node = TreeNode(left: createTree(depth-1),
			    right: createTree(depth-1))
	return node
    } else {
	let node = TreeNode(left: nil, right: nil)
	return node
    }
}

let n: Int
if CommandLine.argc > 1 {
    n = Int(CommandLine.arguments[1]) ?? 10
} else {
    n = 10
}
let minDepth = 4
let maxDepth = (n > minDepth + 2) ? n : minDepth + 2

// Create big tree in first pool
let tree = createTree(maxDepth+1)
let check = tree!.check()
print("stretch tree of depth \(maxDepth+1)\t check: \(check)")

// Cleal first pool and allocate long living tree
let longLivingTree = createTree(maxDepth)

// Allocate binary trees of increasing depth up to maxDepth depth
let group = DispatchGroup()
let rq = DispatchQueue(label: "Result", attributes: [])
let queue = DispatchQueue(label: "Worker", attributes: .concurrent)
var results = [String](repeating: "", count: (maxDepth-minDepth)/2+1)
for currentDepth in stride(from: minDepth, through: maxDepth, by: 2) {
    queue.async(group: group) {
        let idx = (currentDepth - minDepth) / 2
	let iterations = 1 << (maxDepth - currentDepth + minDepth)
	var totalChecksum = 0
	for i in 1...iterations {
	    let tree1 = createTree(currentDepth)
	    totalChecksum += tree1!.check()
	}
	rq.async{
	    results[idx] = "\(iterations)\t trees of depth \(currentDepth)\t check: \(totalChecksum)"
	}
    }
}
group.wait()

rq.sync {
    for result in results {
	print(result)
    }
}

// Check long living tree and print out check info
print("long lived tree of depth \(maxDepth)\t check: \(longLivingTree!.check())")

    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
Swift version 4.0 (swift-4.0-RELEASE)
Target: x86_64-unknown-linux-gnu




Wed, 20 Sep 2017 16:34:11 GMT

MAKE:
/usr/local/src/swift-4.0-RELEASE-ubuntu16.10/usr/bin/swiftc binarytrees.swift -Ounchecked -I Include/swift/apr -o binarytrees.swift_run
binarytrees.swift:65:6: warning: immutable value 'i' was never used; consider replacing with '_' or removing it
        for i in 1...iterations {
            ^
            _

14.88s to complete and log all make actions

COMMAND LINE:
./binarytrees.swift_run 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303