Hello fellow evolutionists,
I’m not sure this list is the best place to talk about this, so please redirect
me if it should be discussed elsewhere.
While trying to implement algebraic data types in Swift, I stumble upon an
interesting problem. Let’s consider the following example:
protocol Term {}
struct Zero: Term {}
struct Succ: Term {
let pred: Term
}
var term: Term = Zero()
for _ in 0 ..< 20000 {
term = Succ(pred: term)
}
This code will take forever to execute (about 1 minute on my mbp late 2013),
whereas if I replace the structures with reference types it will finish almost
instantly, which is what one would expect from such a simple data structure.
Most likely, the problem lays in the fact that a deep copy is produced every
time a new level of recursion is created. However, I guess this case could be
detected by the compiler, as the `term` variable passed as parameter is
immediately affected to the rvalue of the expression using it.
An even more powerful approach would be to keep track of the reference on the
original `term` value under the hood, and update it if necessary in a
copy-on-write fashion. As I understand it, this would enable this code to be
efficiently executed as well:
protocol Term {}
struct Leaf: Term {}
struct Tree: Term {
let left: Term
let right: Term
}
var tree: Term = Leaf()
for _ in 0 ..< 20000 {
tree = Tree(left: tree, right: tree)
}
Interestingly, while enumerations are value types, indirect enumerations don’t
suffer the performance issue of the above examples. Note however that the issue
will reappear if the enum isn’t marked `indirect`.
protocol Term {}
indirect enum Nat: Term {
case zero
case succ(Term)
}
var term = Nat.zero
for _ in 0 ..< 20000 {
term = .succ(term)
}
Thanks,
Dimitri Racordon
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
