Tuned Swift for completely unscientific benchmark

main.swift

// roughly 1.8x of best tuned solution.
// quite concerning since I have written a pool manually and added a GC for better cache locality.

import Foundation

struct Node {
    var x: Int
    var y: Int
    var left: Int = -1
    var right: Int = -1
    
    init(x: Int) {
        self.x = x
        self.y = Int(arc4random())
    }
}

class Tree {
    var root: Int = -1
    var pool: [Node] = []
    var count: Int = 0
    
    public func contains(_ x: Int) -> Bool {
        let (lower, middle, upper) = split(root: root, value: x)
        root = merge(lower, middle, upper)
        return middle != -1
    }
    
    public func insert(_ x: Int) {
        var (lower, middle, upper) = split(root: root, value: x)
        if middle == -1 {
            middle = pool.count
            pool.append(Node(x: x))
            count += 1
        }
        root = merge(lower, middle, upper)
    }
    
    public func erase(_ x: Int) {
        let (lower, middle, upper) = split(root: root, value: x)
        if middle != -1 {
            count -= 1
        }
        root =  merge(lower, upper)
        
        if count * 2 < pool.count && pool.count >= 8192 {
            compact()
        }
    }
    
    private func move(node: Int, dest: inout [Node]) -> Int {
        if node == -1 {
            return -1
        }
        
        let index = dest.count
        dest.append(pool[node])
        dest[index].left = move(node: dest[index].left, dest: &dest)
        dest[index].right = move(node: dest[index].right, dest: &dest)
        
        return index
    }

    private func compact() {
        var newPool = [Node]()
        newPool.reserveCapacity(count)
        root = move(node: root, dest: &newPool)
        pool = newPool
    }

    private func merge(_ lower: Int, _ upper: Int) -> Int {
        guard lower != -1 else {
            return upper
        }
        
        guard upper != -1 else {
            return lower
        }

        if pool[lower].y < pool[upper].y {
            pool[lower].right = merge(pool[lower].right, upper)
            return lower
        } else {
            pool[upper].left = merge(lower, pool[upper].left)
            return upper
        }
    }
    
    private func merge(_ lower: Int, _ middle: Int, _ upper: Int) -> Int {
        let lower = merge(lower, middle)
        return merge(lower,  upper)
    }
    
    typealias BinarySplit = (lower: Int, upper: Int)
    typealias TernarySplit = (lower: Int, middle: Int, upper: Int)
    
    private func splitBinary(root: Int, value: Int) -> BinarySplit {
        guard root != -1 else {
            return (-1, -1)
        }
        
        if pool[root].x < value {
            let (lower, upper) = splitBinary(root: pool[root].right, value: value)
            pool[root].right = lower
            return (root, upper)
        } else {
            let (lower, upper) = splitBinary(root: pool[root].left, value: value)
            pool[root].left = upper
            return (lower, root)
        }
    }

    private func split(root: Int, value: Int) -> TernarySplit {
        let (lower, equalGreater) = splitBinary(root: root, value: value)
        let (equal, greater) = splitBinary(root: equalGreater, value: value + 1)
        return (lower: lower, middle: equal, upper: greater)
    }
}

let tree = Tree()
var cur = 5;
var res = 0

for i in 1..<1000000 {
    let a = i % 3
    cur = (cur * 57 + 43) % 10007
    switch a {
    case 0: tree.insert(cur)
    case 1: tree.erase(cur)
    case 2: if tree.contains(cur) { res += 1 }
    default: break
    }
}
print(res)