[swift-dev] [swift-evolution] Inefficiency in recursive value types

[John McCall]

> On Mar 13, 2017, at 8:55 AM, Dimitri Racordon via swift-evolution <swift-evolution at swift.org> wrote:
> 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.

More of a swift-dev topic.  CC'ing there, BCC'ing evolution.

> 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:

Yes, this is something we're already looking at doing in general for this kind of "existential" use of a protocol, precisely because of this kind of nested-type problem.

> 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)
> }

I do have to note that this is a very strange of writing Nat.  Why recurse through a protocol type instead of recursing concretely?

John.

> 
> var term = Nat.zero
> for _ in 0 ..< 20000 {
>     term = .succ(term)
> }
> 
> Thanks,
> Dimitri Racordon
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20170313/2b661463/attachment.html>