On Friday, November 4, 2016 at 8:05:30 PM UTC, Matt Bauman wrote: > > I posted an answer to this a year ago on Stack Overflow: > http://stackoverflow.com/a/32148113/176071 >
Thanks. I see "so it's just a linear search to check if the type of the argument tuple is a subtype of the signature. So that's just O(n), right? The trouble is that checking subtypes with full generality (including Unions and TypeVars, etc) is hard. Very hard, in fact. Worse than NP-complete [..] that is, even if P=NP, this problem would still take non-polynomial time! It might even be PSPACE or worse." That sounds bad.. I'm not to worried about PSPACE, only "worse" and/or non-polynomial time. But I assume that is also only a problem with functions with many arguments, and if you hit it you know.. You'll never be surprised at runtime. [This kind of reminds me, SQL query tuning is exponential in general, not a problem in practice, or you just deal with it by simplifying your query or give hints; and PostgreSQL at least has genetic algorithm as a fallback: https://www.postgresql.org/docs/9.1/static/geqo-pg-intro.html ] And thankfully you add "But, really, your question was about the *runtime* complexity of dispatch. In that case, the answer is quite often *"what dispatch?"* — because it has been *entirely eliminated*!" as I expected. If Julia would need: https://en.wikipedia.org/wiki/EXPSPACE I would get a little worried, not for: https://en.wikipedia.org/wiki/PSPACE "PSPACE is also equal to PCTC, problems solvable by classical computers using closed timelike curves <https://en.wikipedia.org/wiki/Closed_timelike_curve>,[6] <https://en.wikipedia.org/wiki/PSPACE#cite_note-6> as well as to BQPCTC, problems solvable by quantum computers <https://en.wikipedia.org/wiki/Quantum_computer> using closed timelike curves.[7] <https://en.wikipedia.org/wiki/PSPACE#cite_note-7>" https://en.wikipedia.org/wiki/Closed_timelike_curve "who discovered a solution to the equations of general relativity <https://en.wikipedia.org/wiki/General_relativity> (GR) allowing CTCs known as the Gödel metric <https://en.wikipedia.org/wiki/G%C3%B6del_metric>; and since then other GR solutions containing CTCs have been found, such as the Tipler cylinder <https://en.wikipedia.org/wiki/Tipler_cylinder> and traversable wormholes <https://en.wikipedia.org/wiki/Wormhole#Traversable_wormholes>. [..] Some physicists speculate that the CTCs which appear in certain GR solutions might be ruled out by a future theory of quantum gravity <https://en.wikipedia.org/wiki/Quantum_gravity> which would replace GR, an idea which Stephen Hawking <https://en.wikipedia.org/wiki/Stephen_Hawking> has labeled the chronology protection conjecture <https://en.wikipedia.org/wiki/Chronology_protection_conjecture>. Others note that if every closed timelike curve in a given space-time passes through an event horizon <https://en.wikipedia.org/wiki/Event_horizon>, a property which can be called chronological censorship, then that space-time with event horizons excised would still be causally well behaved and an observer might not be able to detect the causal violation.[2] <https://en.wikipedia.org/wiki/Closed_timelike_curve#cite_note-monroe-2> > The internal implementation of the method caches has since changed, but > the concepts should still apply. If I remember right, Stefan's remarks > were about the addition of triangular subtyping, which will plug into the > dispatch system seamlessly since it's "just" an extension to the type > system. > > On Friday, November 4, 2016 at 10:44:28 AM UTC-5, Mauro wrote: >> >> Have a read of: >> https://github.com/JeffBezanson/phdthesis/blob/master/main.pdf >> >> (Note that multiple dispatch is not a 1.0 thing, it was there from the >> beginning.) >> >> On Fri, 2016-11-04 at 16:22, Ford O. <ford...@gmail.com> wrote: >> > Hi, >> > >> > I have watched the Julia 1.0 video where Stefan briefly mentions new >> > multiple dispatch algorithm. I don't have much insight into this so I >> would >> > like to ask: >> > >> > What is the cost of multiple dispatch? ( What is the complexity of >> naive >> > implementation? What is the complexity of current implementation in >> julia? ) >> > >> > Could you briefly highlight the difficulties of creating an efficient >> > implementation? >> > >> > Thank you >> >
