Compiler Explorer

Source code

// adapted from original implementation submitted by Isaac Gouy:
// https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/binarytrees-swift-8.html
final class Tree {
  private var left, right: Tree?

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

static func with(_ depth: Int) -> Tree {
    return (depth == 0)
      ? Tree(nil, nil)
      : Tree(with(depth - 1), with(depth - 1))
  }

borrowing func nodeCount() -> Int {
    return (left == nil)
      ? 1
      : 1 + left!.nodeCount() + right!.nodeCount()
  }

// Honestly, we should just go ahead and allow mutating methods
  // directly on classes. It's niche, but we can already implement
  // them with protocol extensions, and we allow the other two
  // ownership specifiers.
  consuming func clear() {
    // this deletes all of the nodes in the tree, since we never
    // escaped any of them.
  }
}

func main(_ n: Int) {
  let minDepth = 4
  let maxDepth = minDepth + 2 > n ? minDepth + 2 : n
  let stretchDepth = maxDepth + 1

stretch(stretchDepth)
  let longLivedTree = Tree.with(maxDepth)

for depth in stride(from: minDepth, to: stretchDepth, by: 2) {
    let iterations = 1 << (maxDepth - depth + minDepth)
    var sum = 0
    for _ in 1...iterations {
      sum += count(depth)
    }
    print("\(iterations)\t trees of depth \(depth)\t check: \(sum)")
  }
  let count = longLivedTree.nodeCount()
  longLivedTree.clear()
  print("long lived tree of depth \(maxDepth)\t check: \(count)")
}

func stretch(_ depth: Int) {
  print("stretch tree of depth \(depth)\t check: \(count(depth))")
}

func count(_ depth: Int) -> Int {
  let t = Tree.with(depth)
  let c = t.nodeCount()
  t.clear()
  return c
}

do {
  let n =
    if CommandLine.argc > 1 {
      Int(CommandLine.arguments[1])!
    } else {
      10
    }
  main(n)
}