Quantcast

Multiple dispatch algorithm.

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Multiple dispatch algorithm.

Ford O.
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: 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. <[hidden email]> 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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: 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:
<a href="https://github.com/JeffBezanson/phdthesis/blob/master/main.pdf" target="_blank" rel="nofollow" onmousedown="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FJeffBezanson%2Fphdthesis%2Fblob%2Fmaster%2Fmain.pdf\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNG0RMD7F3zZiYWcHsO9ltZTuFRSUA&#39;;return true;" onclick="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FJeffBezanson%2Fphdthesis%2Fblob%2Fmaster%2Fmain.pdf\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNG0RMD7F3zZiYWcHsO9ltZTuFRSUA&#39;;return true;">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. <<a href="javascript:" target="_blank" gdf-obfuscated-mailto="S3_tK_aGAwAJ" rel="nofollow" onmousedown="this.href=&#39;javascript:&#39;;return true;" onclick="this.href=&#39;javascript:&#39;;return true;">ford...@...> 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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: 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: <a href="http://stackoverflow.com/a/32148113/176071" target="_blank" rel="nofollow" onmousedown="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fstackoverflow.com%2Fa%2F32148113%2F176071\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNE7iM9uRjovxluhpc4YAio0LfOS7g&#39;;return true;" onclick="this.href=&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fstackoverflow.com%2Fa%2F32148113%2F176071\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNE7iM9uRjovxluhpc4YAio0LfOS7g&#39;;return true;">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:
<a href="https://github.com/JeffBezanson/phdthesis/blob/master/main.pdf" rel="nofollow" target="_blank" onmousedown="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FJeffBezanson%2Fphdthesis%2Fblob%2Fmaster%2Fmain.pdf\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNG0RMD7F3zZiYWcHsO9ltZTuFRSUA&#39;;return true;" onclick="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FJeffBezanson%2Fphdthesis%2Fblob%2Fmaster%2Fmain.pdf\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNG0RMD7F3zZiYWcHsO9ltZTuFRSUA&#39;;return true;">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. <[hidden email]> 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
Loading...