Re: [julia-users] Multiple dispatch algorithm.

[Mauro]

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.  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

Re: [julia-users] Multiple dispatch algorithm.

[Matt Bauman]

I posted an answer to this a year ago on Stack 
Overflow: http://stackoverflow.com/a/32148113/176071

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. > 
> 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 
>

Re: [julia-users] Multiple dispatch algorithm.

[Páll Haraldsson]

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 
,[6] 
 as well as to BQPCTC, 
problems solvable by quantum computers 
 using closed timelike 
curves.[7] "

https://en.wikipedia.org/wiki/Closed_timelike_curve
"who discovered a solution to the equations of general relativity 
 (GR) allowing CTCs known 
as the Gödel metric ; and 
since then other GR solutions containing CTCs have been found, such as the 
Tipler 
cylinder  and 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 
 which would replace GR, an 
idea which Stephen Hawking  
has labeled the chronology protection conjecture 
. Others 
note that if every closed timelike curve in a given space-time passes 
through an 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] 





> 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.  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 
>>
>