CODEWITHSUNDEEP
swiftfunctional-programminglazy-evaluationtype-inferenceswift4
Dennis Vennink
Dennis Vennink

Reputation: 1173

Long compile time when using a function (Swift 4)

The following code compiles within reasonable time on its ownEXAMPLE:

public struct LazyProduct6Sequence <
  T1: LazySequenceProtocol, T2: LazySequenceProtocol, T3: LazySequenceProtocol,
  T4: LazySequenceProtocol, T5: LazySequenceProtocol, T6: LazySequenceProtocol
>: LazySequenceProtocol {
  public typealias Element = (T1.Element, T2.Element, T3.Element, T4.Element, T5.Element, T6.Element)
  public typealias Iterator = AnyIterator<Element>

  private let iterator: Iterator

  internal init (
    _ sequence1: T1, _ sequence2: T2, _ sequence3: T3,
    _ sequence4: T4, _ sequence5: T5, _ sequence6: T6
  ) {
    self.iterator = AnyIterator(
      sequence1.flatMap { element1 in
        sequence2.flatMap { element2 in
          sequence3.flatMap { element3 in
            sequence4.flatMap { element4 in
              sequence5.flatMap { element5 in
                sequence6.map { element6 in
                  (element1, element2, element3, element4, element5, element6)
                }
              }
            }
          }
        }
      }.makeIterator()
    )
  }

  public func makeIterator () -> Iterator {
    return self.iterator
  }
}

public func product <
  T1: LazySequenceProtocol, T2: LazySequenceProtocol, T3: LazySequenceProtocol,
  T4: LazySequenceProtocol, T5: LazySequenceProtocol, T6: LazySequenceProtocol
> (
  _ sequence1: T1, _ sequence2: T2, _ sequence3: T3,
  _ sequence4: T4, _ sequence5: T5, _ sequence6: T6
) -> LazyProduct6Sequence<T1, T2, T3, T4, T5, T6> {
  return LazyProduct6Sequence(sequence1, sequence2, sequence3, sequence4, sequence5, sequence6)
}

However, when compiling code that uses it, it takes about 40 seconds to compile (or refuses to compile at all)EXAMPLE:

_ = product([1, 2].lazy, [3, 4].lazy, [5, 6].lazy, [7, 8].lazy, [9, 10].lazy, [11, 12].lazy)

Why does it take such a huge amount of time to compile?

Upvotes: 0

Views: 144

Answers (1)

Dennis Vennink
Dennis Vennink

Reputation: 1173

From what I can gether this has to do with Swift's type inference system. Adding explicit return types to each closure didn't help very much as the compile times stayed pretty much the same. But compilation is near instantaneous when I add an explicit type to the assignment that uses the functionEXAMPLE:

let sequence: LazyProduct6Sequence<
  LazyRandomAccessCollection<[Int]>,
  LazyRandomAccessCollection<[Int]>,
  LazyRandomAccessCollection<[Int]>,
  LazyRandomAccessCollection<[Int]>,
  LazyRandomAccessCollection<[Int]>,
  LazyRandomAccessCollection<[Int]>
> = product(
  [1, 2].lazy,
  [3, 4].lazy,
  [5, 6].lazy,
  [7, 8].lazy,
  [9, 10].lazy,
  [11, 12].lazy
)
let iterator = sequence.makeIterator()

while let element = iterator.next() {
  print(element)
}

Obviously this isn't ideal and is fugly.

I have no idea why it happens, since there is only one function that matches the expression.

It might be worth mentioning that for lower arities, the compilation time goes down. If I overload product to also take eager Sequences then compiling will freeze my machine.

EDIT: I've since then figured out that these type of Sequences should be lazy by default. Reworking my function using the same naming convention as Swift's zip the above example becomes:

public struct Product6Iterator <Sequence1: Sequence, Sequence2: Sequence, Sequence3: Sequence, Sequence4: Sequence,
    Sequence5: Sequence, Sequence6: Sequence>: IteratorProtocol {
  public typealias Element = (Sequence1.Element, Sequence2.Element, Sequence3.Element, Sequence4.Element,
    Sequence5.Element, Sequence6.Element)

  private let iterator: AnyIterator<Element>

  internal init (_ sequence1: Sequence1, _ sequence2: Sequence2, _ sequence3: Sequence3, _ sequence4: Sequence4,
      _ sequence5: Sequence5, _ sequence6: Sequence6) {
    self.iterator = AnyIterator(
      sequence1.lazy.flatMap { element1 in
        sequence2.lazy.flatMap { element2 in
          sequence3.lazy.flatMap { element3 in
            sequence4.lazy.flatMap { element4 in
              sequence5.lazy.flatMap { element5 in
                sequence6.lazy.map { element6 in
                  (element1, element2, element3, element4, element5, element6)
                }
              }
            }
          }
        }
      }.makeIterator()
    )
  }

  public mutating func next () -> Element? {
    return self.iterator.next()
  }
}

public struct Product6Sequence <Sequence1: Sequence, Sequence2: Sequence, Sequence3: Sequence, Sequence4: Sequence,
    Sequence5: Sequence, Sequence6: Sequence>: Sequence {
  public typealias Iterator = Product6Iterator<Sequence1, Sequence2, Sequence3, Sequence4, Sequence5, Sequence6>
  public typealias Element = Iterator.Element

  private let sequence1: Sequence1
  private let sequence2: Sequence2
  private let sequence3: Sequence3
  private let sequence4: Sequence4
  private let sequence5: Sequence5
  private let sequence6: Sequence6

  internal init (_ sequence1: Sequence1, _ sequence2: Sequence2, _ sequence3: Sequence3, _ sequence4: Sequence4,
      _ sequence5: Sequence5, _ sequence6: Sequence6) {
    self.sequence1 = sequence1
    self.sequence2 = sequence2
    self.sequence3 = sequence3
    self.sequence4 = sequence4
    self.sequence5 = sequence5
    self.sequence6 = sequence6
  }

  public func makeIterator () -> Iterator {
    return Iterator(sequence1, sequence2, sequence3, sequence4, sequence5, sequence6)
  }
}

public func product <Sequence1: Sequence, Sequence2: Sequence, Sequence3: Sequence, Sequence4: Sequence,
    Sequence5: Sequence, Sequence6: Sequence> (_ sequence1: Sequence1, _ sequence2: Sequence2, _ sequence3: Sequence3,
    _ sequence4: Sequence4, _ sequence5: Sequence5, _ sequence6: Sequence6) -> Product6Sequence<Sequence1, Sequence2,
    Sequence3, Sequence4, Sequence5, Sequence6> {
  return sequence1.product(sequence2, sequence3, sequence4, sequence5, sequence6)
}

public extension Sequence {
  func product <Sequence2: Sequence, Sequence3: Sequence, Sequence4: Sequence, Sequence5: Sequence,
      Sequence6: Sequence> (_ sequence2: Sequence2, _ sequence3: Sequence3, _ sequence4: Sequence4,
      _ sequence5: Sequence5, _ sequence6: Sequence6) -> Product6Sequence<Self, Sequence2, Sequence3, Sequence4,
      Sequence5, Sequence6> {
    return Product6Sequence(self, sequence2, sequence3, sequence4, sequence5, sequence6)
  }
}

This, along with other similar Sequence extensions, can be found in a library I've created called SequenceExtensions.

Upvotes: 1

Related Questions