I am currently (re)-implementing a persistent binary tree data structure in Swift, and in the simplest case, I'm already seeing pretty good performance with entirely safe code. This is awesome (my naive implementation is only about 1.5x slower than a pretty optimized Rust version).
The insert function is a recursive function, which takes a Node currently defined as something like (simplified for demonstration purposes):
final class Node<Key: Hashable & Comparable, Value> {
var entry: (key: Key, value: Value)
var left: Node<Key, Value>?
var right: Node<Key, Value>?
init(
entry: (key: Key, value: Value),
left: Node<Key, Value>? = nil,
right: Node<Key, Value>? = nil
) {
self.entry = entry
self.left = left
self.right = right
}
}
and if possible, should mutate it in place, but if there are multiple reference to the Node itself, then it should copy itself, and mutate itself in place. Here is the definition for insert that I have now, the code itself isn't all that relevant...
static func insert(node: inout Node<Key, Value>?, entry: Entry<Key, Value>) -> (Node<Key, Value>, Bool)
...except in a few places. First, I have a guard at the top of the function. Since this appears to always create a reference, any time I do something like isKnownUniquelyReferenced(&node) it always returns false (obviously), so I can't do a conditional copy if there is only one reference.
guard let node else {
return ... // Returns a tree with entry as the single item
}
So my first question is, how to handle this particular case, where I have an optional where I need to conditionally copy the inner value (if not nil) before a mutation, but where I know there is going to be more than once reference to it (even if I own both of them).
After the guard, any mutations can be implemented using something like:
...
let (inserted, isNewKey) = insert(node: &node.left, entry: entry)
node.left = inserted
...
So my first thought was to leverage something like GitHub - Swift-CowBox/Swift-CowBox: Easy Copy-on-Write Semantics for Swift Structs., but that appears to kill my performance, possibly due to my use of guards and causing too many copies? I am still learning about __shared and __owned, so I am unsure if those will provide the right solutions here. Lastly, it looks like some clever use of modify accessors might do the trick here? But again, I'm still new to Swift so not entirely sure if this is the right path? Lastly, perhaps not using optional, and instead using a recursive enum to represent a Node or Empty? I was a bit worried about performance in this case. It also looks like this pitch would be very close to what I want/need?
So my question is essentially this: What is the current best practice for safe persistent trees in Swift? Or more generally, how to match something like Rust's RC::make_mut semantics in Swift? Here are the relevant docs for make_mut:
Makes a mutable reference into the given Rc.
If there are other Rc pointers to the same allocation, then make_mut will clone the inner value to a new allocation to ensure unique ownership. This is also referred to as clone-on-write.