[swift-dev] [Performance Question]

[Robert Widmann]

> On Aug 19, 2017, at 10:50 PM, Félix Fischer via swift-dev <swift-dev at swift.org> wrote:
> 
> Hi all.
> 
> I’m a CS student, and as such I’ve heard that the compiling process is very hard, O(2^n) in the worst case (because of the type checker). I’m curious as to how true this is. Is it truly EXP? Is there a shortcut (from the dev perspective) to avoid this cost (maybe by defining all of the types manually).

I’ll give you a constructive proof <https://gist.github.com/CodaFi/5add20c3d1fb23475e476fbdfa59a355> that type checking (specifically overload resolution) grows exponentially in the size of the input expression in the worst case.  Without a reduction in the current feature set, this is an NP-Hard problem and thus a generally more efficient solution is out of our reach.  So, we have to optimize for the real world.  In most (nearly all) cases, type checking is very nearly linear in the size of the expression.  So algorithms and heuristics to better select the right overload and remove bad ones go a lot further than optimizing something like matchTypes (not to say it’s not worth it!)

If you want a CS-y place to look for why this is so hard, check out  Type Inference in the Presence of Overloading, Subtyping, and Recursive Types <http://dl.acm.org/citation.cfm?id=141540> - note that we do not have recursive types, but we do have the other two.


> 
> I have another question regarding the compiling times. I’ve read and heard from many members of the Core Team that there is a technical debt regarding compiling times. How true is this? Can compiling times be shortened to a 50% of what they are at the moment? And what is the lower bound? Is it known?
> 
> Thanks for your patience. :)
> I’m probably asking something obvious, but I don’t know this and I have looked it up as much as I’ve been able to.
> 

~Robert Widmann

> Best regards,
> Félix
> _______________________________________________
> swift-dev mailing list
> swift-dev at swift.org
> https://lists.swift.org/mailman/listinfo/swift-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-dev/attachments/20170820/4288a33b/attachment.html>