binary-trees Swift #5 program

// The Computer Language Benchmarks Game
// http://benchmarksgame.alioth.debian.org/
//
// Swift adaptation of binary-trees Go #8,
// that in turn is based on Rust #4
//
// based on Marcel Ibes Swift #2 and Ralph Ganszky Swift #1

import Dispatch
import Foundation

indirect enum Tree {
    case Empty
    case Node(left: Tree, right: Tree)
}

func itemCheck(_ tree: Tree) -> UInt32 {
    switch tree {
    case .Node(let left, let right):
        switch (left, right) {
        case (.Empty, .Empty):
            return 1
        default:
            return 1 + itemCheck(left) + itemCheck(right)
        }
    case .Empty:
        return 1
    }
}

func bottomUpTree(_ depth: UInt32) -> Tree {
    if depth > 0 {
        return .Node(left: bottomUpTree(depth - 1),
                     right: bottomUpTree(depth - 1))
    }

    return .Node(left: .Empty, right: .Empty)
}

func inner(depth: UInt32, iterations: UInt32) -> String {
    var chk = UInt32(0)
    for _ in 0..<iterations {
        let a = bottomUpTree(depth)
        chk += itemCheck(a)
    }

    return "\(iterations)\t trees of depth \(depth)\t check: \(chk)"
}

let n: UInt32

if CommandLine.argc > 1 {
    n = UInt32(CommandLine.arguments[1]) ?? UInt32(10)
} else {
    n = 10
}

let minDepth = UInt32(4)
let maxDepth = (n > minDepth + 2) ? n : minDepth + 2
var messages: [UInt32: String] = [:]
let depth = maxDepth + 1

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

// Clean first pool and allocate long living tree
let longLivingTree = bottomUpTree(maxDepth)

let group = DispatchGroup()

let workerQueue = DispatchQueue(label: "workerQueue", qos: .userInteractive, attributes: .concurrent)
let messageQueue = DispatchQueue(label: "messageQueue", qos: .background)

group.enter()
workerQueue.async {
    for halfDepth in (minDepth / 2)..<(maxDepth / 2 + 1) {
        let depth = halfDepth * 2
        let iterations = UInt32(1 << (maxDepth - depth + minDepth))

        group.enter()
        workerQueue.async {
            let msg = inner(depth: depth, iterations: iterations)
            messageQueue.async {
                messages[depth] = msg
                group.leave()
            }
        }
    }

    messageQueue.async {
        group.leave()
    }
}

group.wait()

for msg in messages.sorted(by: { $0.0 < $1.0 }) {
    print(msg.value)
}

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

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


 Wed, 18 Sep 2024 23:02:37 GMT

MAKE:
/opt/src/swift-6.0-RELEASE/usr/bin/swiftc binarytrees.swift-5.swift -Ounchecked -wmo  -o binarytrees.swift-5.swift_run

14.92s to complete and log all make actions

COMMAND LINE:
 ./binarytrees.swift-5.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