Extreme Performance issue with Generic Sequence and Generator

Question

I am trying to create my own Sequence type that is Generic. The simplest example that I could create that shows the performance issue is:

// Warning, this code will cause Xcode to hang if you run this in a playground
// Instead I recommend running it in the REPL  or running it with the command
// line tool

struct TakeGenerator<T: GeneratorType>: GeneratorType {
    typealias Element = T.Element

    var generator: T

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

struct Take<T: SequenceType>: SequenceType {
    typealias Generator = TakeGenerator<T.Generator>

    let seq: T
    let test: ((element: T.Generator.Element) -> Bool)?

    func generate() -> Generator {
        return Generator(generator: seq.generate())
    }
}

// NOTE: The times below reflect how long it takes to run this code from 
// the command line with only that line uncommented (other than the type
// declarations)
//
// The command I use is: `time xcrun swift <filename>`

var array = [1,2,3,4]
Take(seq: array, test: {$0 < 3}) // 0.104 seconds to execute
Take(seq: [1,2,3,4], test: nil) // 0.100 seconds to execute
Take(seq: ([1,2,3,4] as [Int]), test: {$0 < 3}) // 0.140 seconds to execute
Take(seq: [1,2,3,4], test: {$0 < 3}) // 17.939 seconds to execute

Note: Obviously this is a useless type, as is, because it just generates the same thing as the generated type, but my real type is slightly more complex and useful.

As you can see in my code comments, there is an extreme performance issue with the last version of the constructor. Instead of taking a tenth of a second, it is taking almost 18 seconds.

I am not even doing any actual generation. I imagine it has something to do with figuring out the types because it is only a problem if both the array is a literal and a test method is provided. There is also no performance issue if I change the test property declaration to be hardcoded to an Int:

let test: ((element: Int) -> Bool)?

Can anyone shed any light on what might be causing this performance issue and how I might fix it?

Answer 1

This is definitely a type inference issue. Using swiftc test.swift to compile it takes up the majority of the time; running ./test is instantaneous. Furthermore, sample shows the majority of the time is spent in

Call graph:
    2677 Thread_113719   DispatchQueue_1: com.apple.main-thread  (serial)
      2677 start  (in libdyld.dylib) + 1  [0x7fff946715c9]
        2677 main  (in swift) + 1725  [0x105919a2d]
          2677 frontend_main(llvm::ArrayRef<char const*>, char const*, void*)  (in swift) + 1960  [0x10591b908]
            2677 swift::CompilerInstance::performSema()  (in swift) + 2064  [0x105b7de80]
              2677 swift::performTypeChecking(swift::SourceFile&, swift::TopLevelContext&, unsigned int)  (in swift) + 1464  [0x106830d08]
                2677 swift::TypeChecker::typeCheckTopLevelCodeDecl(swift::TopLevelCodeDecl*)  (in swift) + 136  [0x10687d518]
                  2677 swift::ASTVisitor<(anonymous namespace)::StmtChecker, void, swift::Stmt*, void, void, void, void>::visit(swift::Stmt*)  (in swift) + 291  [0x10687d683]
                    2677 swift::TypeChecker::typeCheckExpression(swift::Expr*&, swift::DeclContext*, swift::Type, swift::Type, bool, swift::FreeTypeVariableBinding, swift::ExprTypeCheckListener*)  (in swift) + 971  [0x10683a2ab]
                      2677 swift::constraints::ConstraintSystem::solve(llvm::SmallVectorImpl<swift::constraints::Solution>&, swift::FreeTypeVariableBinding)  (in swift) + 363  [0x10681e8fb]
                        2677 swift::constraints::ConstraintSystem::solve(llvm::SmallVectorImpl<swift::constraints::Solution>&, swift::FreeTypeVariableBinding)  (in swift) + 945  [0x10681eb41]
                          ...

File a bug!