Xcode going sloooow !

[fatlazycat]

More of an observation than anything.

If i let Xcode do type inference on the code below it goes very slow compared to normal operation.

let hyphenParser = Prefix { $0 != "-" }.skip("-").take(Prefix { $0 != "-" }).map{ (String($0), String($1)) }

If I put in the types and do

let hyphenParser: Parsers.Map<Parsers.Take2<Parsers.SkipSecond<Prefix<Substring>, String>, Prefix<Substring>>, (String, String)> = Prefix { $0 != "-" }.skip("-").take(Prefix { $0 != "-" }).map{ (String($0), String($1)) }

compilation etc is back to normal.

This expected ?

I was trying to parse rows such as

start-A
start-b
A-c
A-b
b-d
A-end
b-end

Perhaps there is a better way than the parser I had ?

Thanks

[tgrapperon]

It is expected that Xcode will have more work to do when inferring the types, as it has to check all the possible solutions. The sluggishness is not desired, but can happen unfortunately in certain conditions where Swift has difficulties resolving types.
Operators and literals are two things that can particularly make the combinatoric of the type system explode, and you have both of them, several times.
Prefix can work on Collection, and there are many of them. Combined with the uncertainties of the predicate content, that makes a lot of potential routes to explore. What happens if you help the compiler by casting your first prefix as Prefix<Substring>? And the first "-" by "-"[...] if it doesn't improve?

[fatlazycat]

Just casting first prefix as Substring helped a lot thanks

[stephencelis]

@fatlazycat Thanks for starting this discussion! It's actually a pretty interesting issue, and it'd be good for us to document the problem. If we turn on some build settings, we can get some good feedback on how slow to compile an expression is:

swiftSettings: [
  .unsafeFlags([
    "-Xfrontend", "-warn-long-expression-type-checking=10",
  ])
]

And yup, the expression in question is painfully slow:

While it might seem that Prefix could be causing problems, as it has numerous initializers and overloads, it builds very quickly when we drop the map:

If we attempt to map each Prefix individually, things get even worse: they stop compiling!

Trying to avoid the closure in each map with String.init doesn't help (and actually hangs longer):

If we use String.init(_:) instead, we get something that compiles faster than the original problem, though still quite slow:

So the overload space of String.init definitely seems to be a big contributor to the problem.

What if we converted the substring to a string a different way? Like string interpolation?

Almost instantaneous.

Comparing this to your solution of explicitly providing the generic in Prefix<Substring>:

We get something that's also quite fast.

And for completeness' sake, if we specify map's types, we also get something that compiles very, very quickly:

So the problem appears to be a combination of a generic Prefix and String.init's many overloads.

Maybe there's some way of improving our APIs to avoid this gotcha, and maybe we can better document this limitation in the meantime.

It's also quite possible that there are improvements that could be made in the Swift compiler, so we may file a bug report to see if they think this can be improved.

[fatlazycat]

@stephencelis Ah very interesting ! Thanks for mentioning the build setting, that looks very useful. When I first encountered the issue I was wondering what was going on and just did a manual approach to try and determine the issue.

[stephencelis]

Submitted this to the Swift tracker: https://bugs.swift.org/browse/SR-15588

Not sure it's something they can/will resolve, but if you want to follow the ticket!

[iampatbrown]

@stephencelis this is an awesome break down. Thanks for documenting this for everyone :)

[tgrapperon]

String.init(_ code completion gives 16 variants in Xcode 13. That's 256 routes to check for the tuple result, many of which are protocol with associated types. I don't know if it can improve drastically. I know that Slava Pestov is reworking parts of the type system using stronger mathematical grounds, and he is maybe interested in this case. It may worth bringing this example to his attention.

On the API side, as possible workaround could be to introduce typealiases for first order parsers of Substring, like public typealias PrefixOfSubstring = Prefix<Substring>. This would probably help with the discoverability and usage of such parsers: we would have PrefixOfSubstring as a possible completion of Prefix, and get faster compilation time when we rightfully select it.
The documentation could state that using _OfSubstring parsers can improve compilation time, without affecting parsing speed at runtime.