<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Aug 19, 2017, at 10:50 PM, Félix Fischer via swift-dev <<a href="mailto:swift-dev@swift.org" class="">swift-dev@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="auto" class="">Hi all.</div><div dir="auto" class=""><br class=""></div><div dir="auto" class="">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).</div></div></blockquote><div><br class=""></div><div>I’ll give you<a href="https://gist.github.com/CodaFi/5add20c3d1fb23475e476fbdfa59a355" class=""> a constructive proof</a> 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!)</div><div><br class=""></div><div>If you want a CS-y place to look for why this is so hard, check out <a href="http://dl.acm.org/citation.cfm?id=141540" class="">Type Inference in the Presence of Overloading, Subtyping, and Recursive Types</a> - note that we do not have recursive types, but we do have the other two.</div><div class=""><br class=""></div><br class=""><blockquote type="cite" class=""><div class=""><div dir="auto" class=""><br class=""></div><div dir="auto" class="">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?</div><div dir="auto" class=""><br class=""></div><div dir="auto" class="">Thanks for your patience. :)</div><div dir="auto" class="">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.</div><div dir="auto" class=""><br class=""></div></div></blockquote><div><br class=""></div><div>~Robert Widmann</div><br class=""><blockquote type="cite" class=""><div class=""><div dir="auto" class="">Best regards,</div><div dir="auto" class="">Félix</div>
_______________________________________________<br class="">swift-dev mailing list<br class=""><a href="mailto:swift-dev@swift.org" class="">swift-dev@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-dev<br class=""></div></blockquote></div><br class=""></body></html>