Dispatch issues with size() on v0.6-dev

[rdeits]

I think this is probably a Julia bug, but since I encountered it here first, I wanted to check with you all before I made noise over at Julia itself.

The following works in Julia v0.5:

julia> using StaticArrays

julia> immutable Foo{N, T} <: StaticVector{T}
              data::NTuple{N, T}
          end

julia> Base.size{N, T}(::Type{Foo{N, T}}) = (N,)

julia> Base.getindex(f::Foo, i) = f.data[i]

julia> f = Foo(1,2,3)
3-element Foo{3,Int64}:
 1
 2
 3

Running the same code on v0.6-dev gives:

julia> versioninfo()
Julia Version 0.6.0-dev.2831
Commit cb1aae9 (2017-02-15 11:49 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin15.6.0)
  CPU: Intel(R) Core(TM) i7-2860QM CPU @ 2.50GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, sandybridge)

julia> using StaticArrays

julia> immutable Foo{N, T} <: StaticVector{T}
              data::NTuple{N, T}
          end

julia> Base.size{N, T}(::Type{Foo{N, T}}) = (N,)

julia> Base.getindex(f::Foo, i) = f.data[i]

julia> f = Foo(1,2,3)
3-element Foo{3,Int64}:
Error showing value of type Foo{3,Int64}:
ERROR: The size of type `Foo{3,Int64}` is not known.

If you were trying to construct (or `convert` to) a `StaticArray` you
may need to add the size explicitly as a type parameter so its size is
inferrable to the Julia compiler (or performance would be terrible). For
example, you might try

    m = zeros(3,3)
    SMatrix(m)      # this error
    SMatrix{3,3}(m) # correct - size is inferrable

Stacktrace:
 [1] size(::Type{Foo{3,Int64}}) at /Users/rdeits/.julia/v0.6/StaticArrays/src/core.jl:126
 [2] size(::Type{Foo{3,Int64}}, ::Int64) at /Users/rdeits/.julia/v0.6/StaticArrays/src/abstractarray.jl:10
 [3] getindex(...) at /Users/rdeits/.julia/v0.6/StaticArrays/src/indexing.jl:361

(the rest of the stack trace has been omitted).

The issue seems to be that Julia is finding the fallback Base.size in StaticArrays/core.jl, despite the more specific one being available. Am I doing something wrong with the StaticArrays API, or is this just a Julia bug?

[rdeits]

This looks suspiciously similar to the "Specificity issue in ColorTypes:" at JuliaLang/julia#19998

[andyferris]

Interesting. Playing with my ajf/nopure branch (see #105) results in the same issue.

This does seem compiler-related in some way or another. I can get it to change the results of dispatch by simply trying to instantiate a new object! Particularly pay attention to the inconsistency of the last and 3rd last commands:

               _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: http://docs.julialang.org
   _ _   _| |_  __ _   |  Type "?help" for help.
  | | | | | | |/ _  |  |
  | | |_| | | | (_| |  |  Version 0.6.0-dev.2817 (2017-02-14 02:13 UTC)
 _/ |\__'_|_|_|\__'_|  |  Commit 2b1c2a0 (2 days old master)
|__/                   |  x86_64-linux-gnu

julia> using StaticArrays  # ajf/nopure branch

julia> immutable Foo{N, T} <: StaticVector{T}
           data::NTuple{N, T}
       end

julia> Base.getindex(f::Foo, i) = f.data[i]

julia> Base.@pure StaticArrays.Size{N, T}(::Type{Foo{N, T}}) = Size(N)

julia> foo = Foo(1,2,3)
3-element Foo{3,Int64}:
Error showing value of type Foo{3,Int64}:
ERROR: The size of type `Foo{3,Int64}` is not known.

If you were trying to construct (or `convert` to) a `StaticArray` you
may need to add the size explicitly as a type parameter so its size is
inferrable to the Julia compiler (or performance would be terrible). For
example, you might try

    m = zeros(3,3)
    SMatrix(m)      # this error
    SMatrix{3,3}(m) # correct - size is inferrable

Stacktrace:
 [1] StaticArrays.Size(::Type{Foo{3,Int64}}) at /home/ferris/.julia/v0.6/StaticArrays/src/traits.jl:42
 [2] size(::Type{Foo{3,Int64}}, ::Int64) at /home/ferris/.julia/v0.6/StaticArrays/src/abstractarray.jl:10
 [3] getindex(...) at /home/ferris/.julia/v0.6/StaticArrays/src/indexing.jl:361
 [4] alignment(::IOContext{Base.Terminals.TTYTerminal}, ::Foo{3,Int64}, ::Array{Int64,1}, ::Array{Int64,1}, ::Int64, ::Int64, ::Int64) at ./show.jl:1329
 [5] print_matrix(::IOContext{Base.Terminals.TTYTerminal}, ::Foo{3,Int64}, ::String, ::String, ::String, ::String, ::String, ::String, ::Int64, ::Int64) at ./show.jl:1458
 [6] print_matrix(::IOContext{Base.Terminals.TTYTerminal}, ::Foo{3,Int64}, ::String, ::String, ::String) at ./show.jl:1430
 [7] #showarray#250(::Bool, ::Function, ::IOContext{Base.Terminals.TTYTerminal}, ::Foo{3,Int64}, ::Bool) at ./show.jl:1680
 [8] display(::Base.REPL.REPLDisplay{Base.REPL.LineEditREPL}, ::MIME{Symbol("text/plain")}, ::Foo{3,Int64}) at ./REPL.jl:122
 [9] display(::Base.REPL.REPLDisplay{Base.REPL.LineEditREPL}, ::Foo{3,Int64}) at ./REPL.jl:125
 [10] display(::Foo{3,Int64}) at ./multimedia.jl:194

julia> Size(Foo{3,Int64})
ERROR: The size of type `Foo{3,Int64}` is not known.

If you were trying to construct (or `convert` to) a `StaticArray` you
may need to add the size explicitly as a type parameter so its size is
inferrable to the Julia compiler (or performance would be terrible). For
example, you might try

    m = zeros(3,3)
    SMatrix(m)      # this error
    SMatrix{3,3}(m) # correct - size is inferrable

Stacktrace:
 [1] StaticArrays.Size(::Type{Foo{3,Int64}}) at /home/ferris/.julia/v0.6/StaticArrays/src/traits.jl:42

julia> Size(Foo{3,Float64})
Size(3,)

julia> Foo(1.0,2.0,3.0)
3-element Foo{3,Float64}:
Error showing value of type Foo{3,Float64}:
ERROR: The size of type `Foo{3,Float64}` is not known.

If you were trying to construct (or `convert` to) a `StaticArray` you
may need to add the size explicitly as a type parameter so its size is
inferrable to the Julia compiler (or performance would be terrible). For
example, you might try

    m = zeros(3,3)
    SMatrix(m)      # this error
    SMatrix{3,3}(m) # correct - size is inferrable

Stacktrace:
 [1] StaticArrays.Size(::Type{Foo{3,Float64}}) at /home/ferris/.julia/v0.6/StaticArrays/src/traits.jl:42
 [2] size(::Type{Foo{3,Float64}}, ::Int64) at /home/ferris/.julia/v0.6/StaticArrays/src/abstractarray.jl:10
 [3] getindex(...) at /home/ferris/.julia/v0.6/StaticArrays/src/indexing.jl:361
 [4] alignment(::IOContext{Base.Terminals.TTYTerminal}, ::Foo{3,Float64}, ::Array{Int64,1}, ::Array{Int64,1}, ::Int64, ::Int64, ::Int64) at ./show.jl:1329
 [5] print_matrix(::IOContext{Base.Terminals.TTYTerminal}, ::Foo{3,Float64}, ::String, ::String, ::String, ::String, ::String, ::String, ::Int64, ::Int64) at ./show.jl:1458
 [6] print_matrix(::IOContext{Base.Terminals.TTYTerminal}, ::Foo{3,Float64}, ::String, ::String, ::String) at ./show.jl:1430
 [7] #showarray#250(::Bool, ::Function, ::IOContext{Base.Terminals.TTYTerminal}, ::Foo{3,Float64}, ::Bool) at ./show.jl:1680
 [8] display(::Base.REPL.REPLDisplay{Base.REPL.LineEditREPL}, ::MIME{Symbol("text/plain")}, ::Foo{3,Float64}) at ./REPL.jl:122
 [9] display(::Base.REPL.REPLDisplay{Base.REPL.LineEditREPL}, ::Foo{3,Float64}) at ./REPL.jl:125
 [10] display(::Foo{3,Float64}) at ./multimedia.jl:194

julia> Size(Foo{3,Float64})
ERROR: The size of type `Foo{3,Float64}` is not known.

If you were trying to construct (or `convert` to) a `StaticArray` you
may need to add the size explicitly as a type parameter so its size is
inferrable to the Julia compiler (or performance would be terrible). For
example, you might try

    m = zeros(3,3)
    SMatrix(m)      # this error
    SMatrix{3,3}(m) # correct - size is inferrable

Stacktrace:
 [1] StaticArrays.Size(::Type{Foo{3,Float64}}) at /home/ferris/.julia/v0.6/StaticArrays/src/traits.jl:42

[andyferris]

@vtjnash On the ajf/nopure branch I've tried to followed the rule that no @pure function is ever specialized - do you have any take on what this might be?

[vtjnash]

Are you trying to call the overloaded size function from the generated function? That's impossible (inference/codegen can't allow you provide new definitions) - you need to either compute the value outside and pass it in as a parameter, or only compute with it in the generated run time code.

[andyferris]

No, I'm trying to call the overloaded Size function (i.e. constructor) directly from the REPL. It doesn't change things if my Size method is @pure or not, and it doesn't change things if there is no other matching Size method (the one the generates the "pretty" error message in the above can be removed, resulting in a spurious method error instead of a spurious dispatch).

I.e. shorter summary:

julia> using StaticArrays; struct Foo{N, T} <: StaticVector{T}; data::NTuple{N, T}; end; Base.getindex(f::Foo, i) = f.data[i]; StaticArrays.Size{N, T}(::Type{Foo{N, T}}) = Size(N);

julia> foo = Foo(1.0,2.0,3.0);

julia> Size(Foo{3,Float64})
Size(3,)

julia> foo
3-element Foo{3,Float64}:
Error showing value of type Foo{3,Float64}:
ERROR: The size of type `Foo{3,Float64}` is not known.
# ... more error message

julia> Size(Foo{3,Float64})
ERROR: The size of type `Foo{3,Float64}` is not known.
# ... more error message

EDIT: the problem relates to showing the constructed type, specifically.

[andyferris]

Hmm... maybe what you said about generated functions has something to do with it, I don't know. I think the error begins with showing the type because show calls 2D indexing, which is a @generated function, which asks for size.

Are you trying to call the overloaded size function from the generated function? That's impossible (inference/codegen can't allow you provide new definitions)

Are you saying that @generated function generators are no longer interpretted, or use standard dynamic dispatch (or are otherwise recompiled) every time I want to create a new specialization of the @generated method? (I assumed the generator ran more-or-less like f(::ANY...) and would thus would typically use dynamic dispatch). Because this would totally destroy StaticArrays...

Note that the strangest behavior here is that it is effectively erasing the Size method for later use outside of the generator.

[andyferris]

Are you trying to call the overloaded size function from the generated function? That's impossible (inference/codegen can't allow you provide new definitions)

I've been puzzling over this. Is it that the generator is defined in a certain world-age and always uses methods from that age?

[andyferris]

you need to either compute the value outside and pass it in as a parameter, or only compute with it in the generated run time code.

@c42f @SimonDanisch FYI the implications of this would be that every function which is currently generated based on the array size (i.e. most functions in this package, lol) will now need a thunk for Julia v0.6, such as @inline map(func, a::StaticArray) = _map(func, Size(a), a) where _map is a @generated function that takes a Size instead of computing it internally. I'm not looking forward to broadcast...

(the alternative is to stick the static size into StaticArray{S,T,N}, which could be argued for anyway)

Jameson - I have to say that I was hoping that compiler improvements (and there have been some very nice improvements!) would make writing this package in particular simpler... :(

[vtjnash]

I assumed the generator ran more-or-less like f(::ANY...) and would thus would typically use dynamic dispatch

How something is dispatched (runtime or ahead-of-time) and what method gets called are now completely decoupled. It should not be possible to tell the difference now from observing runtime behavior (aside from measuring performance). Although, having any function marked @pure potentially apply during inference can have very bad interactions here, since it can get pretty confusing to figure out which methods are being inferred / used when.

I contemplated re-generating the function body every time it was called, but well, now that really would completely destroy every usage of them! So I instead went with never regenerating the function body. That also allows them to be inferable.

For generated functions, pretty much the only operation that's definitely always workable is loop unrolling. That's also all that base Julia uses them for, so it's also the only thing that gets tested regularly.

[andyferris]

How something is dispatched (runtime or ahead-of-time) and what method gets called are now completely decoupled. It should not be possible to tell the difference now from observing runtime behavior (aside from measuring performance).

OK, that does sound like a worthy objective :)

OTOH it wasn't clear to me that is what was happening with the function generator (I expected it to use the world that it was called from, like all other functions do now). And there is the small matter of the method table getting corrupted - do you want me to file an issue for that part?

I contemplated re-generating the function body every time it was called, but well, now that really would completely destroy every usage of them! So I instead went with never regenerating the function body. That also allows them to be inferable.

Would you consider options between these two extremes? I understand it would involve extra work. I haven't had a chance to look over the implementatation of worlds, but I understand there is a world-age counter and functions maintain dependency edges to (efficiently) find methods that might need recompiling when a new method is introduced (or overwritten). (Correct me if that's wrong).

Something less extreme than the former (regenerate every call) is to regenerate the function body every time the world-age counter has incremented since the last time it was called.

Something less exteme than the latter (never regenerate) is to append dependency edges detected from the generator to the generated function body (and have the body regenerated whenever the specialized method needs to be recompiled).

Are either of these feasible/workable and/or desirable in your mind?

[andyferris]

For generated functions, pretty much the only operation that's definitely always workable is loop unrolling. That's also all that base Julia uses them for, so it's also the only thing that gets tested regularly.

I'd like to point out that Base is purposefully conservative about introducing generated functions, and there has been efforts to reduce their number. On the other hand, packages have been much more adventurous (and I'm not talking about spurious use of eval from the function generator here :) ).

(If the only thing we wanted from them was to unroll an expression, it might be cleaner to have @unroll for i = 1:N... end for N constant (not just literal) and so-on, and get rid of @generated entirely. But I think @generated has lots of uses that are difficult to imagine/predict until you see them.)

[vtjnash]

And there is the small matter of the method table getting corrupted - do you want me to file an issue for that part?

Can you reproduce when the methods in question is not marked @pure? If so, this sounds like a bug in Julia. If not, then it is an incorrect usage of the annotation, and the compiler is correct.

Would you consider options between these two extremes?

I have, yes.

Something less extreme than the former (regenerate every call) is to regenerate the function body every time the world-age counter has incremented since the last time it was called.

The purpose of inference is not to infer world-counter ages. This is intentionally treated as unknowable, which then propagates as an assumption throughout much of the system for efficiency. There's a long discussion on JuliaLang/julia#19801 on why this isn't permitted to be expressible.

Something less exteme than the latter (never regenerate) is to append dependency edges detected from the generator to the generated function body (and have the body regenerated whenever the specialized method needs to be recompiled).

This is uncomputable in a Turing machine.

If the only thing we wanted from them was to unroll an expression

It has been proposed. I'm interested in seeing it happen at some point, partly because I think they'll be easier to understand and use, partly because I think they should be able to generate better code for large N.

[andyferris]

Can you reproduce when the methods in question is not marked @pure?

Yes. Well, there are other (non-matching) Size methods which are @pure, but not on the one in question (see e.g. the definition at the end of the first line here).

[andyferris]

I had a read of that discussion you linked. It seems to me that you were arguing that cfunction should always dispatch to the newest world definition of the Julia function. Is that right?

To clarify my position: what I was expecting here is that the generated function would be run as if it were defined in the newest world. My understanding of the problem of #265 was that you get different results depending on the order of defining (and executing) functions. The "worlds" fix makes that order-independent - every function lives in the newest world. It seems the dependence on the order of defining/executing methods still persists for @generated functions.

I'm trying to figure out if you are telling me that you believe there is no possible fix for @generated functions that gets rid of any effect of their relative order of definition (or execution) with respect to other functions/methods?

This is uncomputable in a Turing machine.

This response confuses me... you compute the dependency edges for standard functions, and a function generator is just a standard function that returns an expression (typically). AFAICT, if none of the called methods of the generator or of the current generated body have changed, then the old compiled code is provably safe. If any of those dependent methods do change, then you can join the latest world by both regenerating the code and recompiling the specialized method.

[vtjnash]

To clarify my position: what I was expecting here is that the generated function would be run as if it were defined in the newest world. The "worlds" fix makes that order-independent - every function lives in the newest world.

This is nonsensical; functions are just data, and data doesn't have a world.

I'm trying to figure out if you are telling me that you believe there is no possible fix for @generated functions that gets rid of any effect of their relative order of definition (or execution) with respect to other functions/methods?

Right. This is a feature. Their behavior is now independent of the relative ordering of their inference and evaluation.

This is uncomputable in a Turing machine.

The dependency edges were computed (well, over-approximated) by me. I am not a Turing machine.

if none of the called methods of the generator ... have changed

define "changed".

I decided to define it as "false" (same as for @pure). It made the implementation and explanation much easier. :P

Can you reproduce when the methods in question is not marked @pure?

OK. I think I can guess what might be wrong. I'm trying to take a shortcut around some of the runtime computational cost, but got some of it wrong. I've been trying to figure out how to patch that up. Yeah, open a bug – it'll be nice to have a test case instead of just knowing there's a theoretical issue there.

[c42f]

Here's a fairly minimal example with the latest julialang master of (a) the @generated changes, and (b) corrupt method tables (?)

julia> foo(::Type{Int}) = 1
foo (generic function with 1 method)

julia> @generated bar(x) = :($(foo(x)))
bar (generic function with 1 method)

julia> bar(42)
1

julia> foo(::Type{Float64}) = -1
foo (generic function with 2 methods)

julia> bar(42.0)
ERROR: MethodError: no method matching foo(::Type{Float64})
The applicable method may be too new: running in world age 21461, while current world is 21462.
Closest candidates are:
  foo(::Type{Float64}) at REPL[4]:1 (method too new to be called from this world context.)
  foo(::Type{Int64}) at REPL[1]:1
Stacktrace:
 [1] bar(...) at ./REPL[2]:1

(Julia version 0.6.0-dev.2884)

[Edited to remove some off the cuff brokeness, sorry :-/ ]

[c42f]

Oops, I really messed the second part of that example up, sorry!

[c42f]

@andyferris with the latest build I can't reproduce the second part of your example from #106 (comment)

[andyferris]

Is this fixed by #121? I'll close this - please open again if there is still a problem.