incorrect pure annotations

[vtjnash]

The Base.@pure annotation means "the result of this function is not dependent on any part of the system other than the arguments". Therefore, any function which can be overloaded should not be marked @pure, as inference will not be able to get the correct answer. In general, you should trust that inference can figure out that returning a constant has no side-effects, and permit it to still construct its method dependency edges (e.g. avoid annotating anything as @pure)

[andyferris]

Hi Jameson,

Thanks for the information. I'm still trying to read between the lines here - is this related to worlds / JuliaLang/julia#265? As in, the system cannot update functions when a new @pure method is defined which is a specialization of an existing one, because a "method dependency edge" isn't generated for the constant inserted by a @pure function? Or is it really that inference cannot handle multiple @pure methods per function, even if every such method is defined prior to compiling any dependent code?

I'm only asking because I was a little surprised to see "any function which can be overloaded should not be marked @pure" so I'm wondering if consecutively defining two @pure methods (which are not designed to be overloaded by users, and with no dependent methods in between) is a Bad Thing.

If this is related to enforcing consistent worlds, would it be fundamentally a bad thing if @pure functions (and const variables for that matter, since you can redefine a const at the REPL) could be part of the "many-worlds" system, with dependency edges and annotated ages? I can see a semantic argument to enforcing the definition of @pure that you gave above (and const could become truly constant), but then I wonder if I should just receive an error when I try to change them. (i.e. just turn undefined behavior into an error).

Two more questions: Can I redefine an @inline method and have the new system recompile its dependencies? (i.e. is a method dependency edge generated even when the code is inlined?)

Finally, with "you should trust that inference can figure out that returning a constant has no side-effects" the reason I use @inline, @pure and @generated so much is because I don't understand the rules for how the compiler determines what is side-effect free and thus where it inserts a constant as the output of a standard method. For instance, if I have a (normal) function that returns a type, is it side-effect free if that type hasn't been seen before and therefore is added to the type cache? Is it side-effect free if there is something allocated as an intermediate step to determine this type, but that allocated object doesn't "escape" the method? (Is this is explained somewhere in the docs?)

[vtjnash]

It's not specifically related to worlds, although it wasn't as interesting (observable) when everything was treated incorrectly.

which are not designed to be overloaded by users, and with no dependent methods in between)

right. If the method shouldn't be overloaded (including anything that it needs to call), then it's not incorrect. But quite often those functions are simply returning constants or static-parameters, in which case the annotation is unnecessary.

would it be fundamentally a bad thing if @pure functions ... could [have] dependency edges and annotated ages?

yes, @pure is fundamentally about disabling dependency edges. When it finally gains that ability (if ever), that will be the day we can finally eliminate @pure. I'm still holding out hope that it'll be possible, but it's not easy to figure out quite the right semantics.

Can I redefine an @inline method and have the new system recompile its dependencies

Of course. If you don't see that happen somewhere, file a bug report.

side-effect free

It's a simplistic recursive algorithm right now (i.e. a function is effect-free if it doesn't do anything that has a side-effect). And yes allocation of immutables and Types is effect-free.

[andyferris]

Cool. Thanks for the clarifications. I was planning to redo a lot of core stuff in this package in light of the improved subtype algorithm, since it "breaks" my current constructors and so-on (which are a mess of trial-and-error to work around the kinks in the old subtype algorithm), so I'll revisit the @pure methods while I am at it.

It's a simplistic recursive algorithm right now (i.e. a function is effect-free if it doesn't do anything that has a side-effect). And yes allocation of immutables and Types is effect-free.

Is there a simple list of side-effects/effect-free operations? I'm guessing this list of effect-free is quite short:

julia> f(a,b) = a+b
f (generic function with 1 method)

julia> g() = f(1,2)
g (generic function with 1 method)

julia> g()
3

julia> @code_warntype g()
Variables:
  #self#::#g

Body:
  begin 
      return (Base.box)(Int64,(Base.add_int)(1,2))
  end::Int64

I would be natural for users to assume that 1+2 would be effect-free. Sometimes, it's simple stuff like this which leads me to use @pure.

EDIT: sorry that code snippet was munged.

[vtjnash]

That method is effect-free and would get constant-folded. It's purity is debatable, although generally the distinction is unnecessary in practice.

[andyferris]

But it isn't constant folded, in the sense that inference wraps it as Const(3). Otherwise, the output of this would be inferrable:

julia> h() = Val{g()}
h (generic function with 1 method)

julia> @code_warntype h()
Variables:
  #self#::#h

Body:
  begin 
      return (Core.apply_type)(Main.Val,(Base.box)(Int64,(Base.add_int)(1,2)))::Type{_} where _<:Val
  end::Type{_} where _<:Val

although generally the distinction is unnecessary in practice.

True in most cases. I seem to have a habit of pushing the boundaries... :) The above example has been annoying for both StaticArrays and TypedTables.

[vtjnash]

inference is not the same as constant-folding. but yes, I wouldn't be surprised if you needed to have a @pure tuple_product(dims::Dims) = prod(dims) function to handle some of those cases.

[andyferris]

Indeed. :)

[JeffreySarnoff]

"...any function which can be overloaded should not be marked @pure"
If no other definition of fn exists, is this a proper use or an improper use?

@pure fn(a::Int64) = a + one(Int64)
@pure fn(b::UInt8) = b + one(UInt8)

[andyferris]

That should be fine - I think "specialised" would be more accurate than "overloaded" - ie a signature that is more specific than a previous, pure one.

And even then, it depends on the order of definition and usage. The point being the "world" (fix for JuliaLang/julia#265) is not updated for pure functions as a "dependency edge" is not generated so the compiler can go back and insert the specialised result. Paraphrasing Jameson, needing to do that would defeat the purpose of pureness, where you are asserting a transformation can be made at any stage without ill effect.

In practice, if all your specializations are defined before they are used anywhere, then you shouldn't run into inconsistencies. I.e. It's the same rules of v0.5 where the compiler might not use the latest version of functions in all cases (but v0.5 is still a useful language).

Furthermore, here, I think if a user creates a new subtype of StaticArray outside this package and some @pure function for its size or whatever, then when the first functions compile for that subtype they will already use the latest specialisation, which is good.

The worlds would become inconsistent if, after using the package for a while, a user decided to change the size definition for a SVector. I would say that is a feature, not a bug :)

Of course, we should investigate which pure annotations can be removed without screwing performance (inferrability), but I haven't got around to it yet.

(Does what I wrote make sense, @Jameson?)

[JeffreySarnoff]

helpful

[vtjnash]

That sounds mostly right. The only part I would suggest is wrong is:

Furthermore, here, I think if a user creates a new subtype of StaticArray outside this package and some @pure function for its size or whatever, then when the first functions compile for that subtype they will already use the latest specialisation, which is good.

@pure asserts that it doesn't need to use the latest specialization, so there's no actual guarantee that it will. It's not hard to construct examples in which it won't. As the compiler gets better, it may even become more likely. Although if you're simply suggesting that if this package doesn't use @pure anywhere, then you can't be held responsible for another package author's choices, I think that's entirely reasonable?

@JeffreySarnoff in your example, it appears that that declaration is in fact valid, although it is generally better to let the compiler (which can also observe this fact without too much difficulty) handle this particular optimization, so I would suggest that it is unnecessary and thus "improper".

[c42f]

It's not hard to construct examples in which it won't

I'd love to see a simple practical example where using @pure can give unexpected results. When declaring a new StaticArray subtype and pure methods to go with it, no functions will yet be specialized for this type, so naively this seems safe. But it would be instructive to know how this (or something similar) can fail in practice.

[JeffreySarnoff]

I'd like to see a simple (yet not likely discovered and made as optimized without @pure) practical example where for one function with two distinct signatures of the same arity (one which is subsumptive of another).
The places that I have seen it used are not given to be read as exemplars of the general sense of right use.

[vtjnash]

no functions will yet be specialized for this type, so naively this seems safe

This is not not necessarily true / sufficient for a function to be pure, since the compiler works to specialize for classes of types, not just concrete types. Hence the properties of any element of that class can't be changed / overridden for any method marked @pure.

I didn't record specifics, but I opened this issue because someone asked me why StaticArrays.jl was giving unexpected results / not passing tests. By removing some incorrect @pure annotations in this package that I pointed out were affecting their tests, they reported back to me that it started working.

For practical examples of where people have run into this, see any of the duplicate issues associated with JuliaLang/julia#265.

[andyferris]

This is not not necessarily true / sufficient for a function to be pure, since the compiler works to specialize for classes of types, not just concrete types. Hence the properties of any element of that class can't be changed / overridden for any method marked @pure.

OK, I hadn't seen this before. I'm still not clear of exactly what situations this occurs in (specifics would be welcomed, but we can work with this). I suppose the ridiculous proportion of generated functions in this package would have sheltered us somewhat...

One use case for @pure is getting returned constants into type variables. How would you recommend doing this? For example, compare the package definition of @pure size() vs not-pure size2(), we get:

julia> using StaticArrays

julia> f() = Val{size(SMatrix{3,3})}
f (generic function with 1 method)

julia> f()
Val{(3,3)}

julia> @code_warntype f()
Variables:
  #self#::#f

Body:
  begin 
      return Val{(3,3)}
  end::Type{Val{(3,3)}}

julia> size2{N,M}(::Type{SMatrix{N,M}}) = (N,M)
size2 (generic function with 1 method)

julia> g() = Val{size2(SMatrix{3,3})}
g (generic function with 1 method)

julia> g()
Val{(3,3)}

julia> @code_warntype g()
Variables:
  #self#::#g

Body:
  begin 
      return (Core.apply_type)(Main.Val,$(QuoteNode((3,3))))::Type{_<:Val}
  end::Type{_<:Val}

Another current use case is the reverse, to try to get input constants into type variables. In StaticArrays, this is used for similar_type: here @pure is used to make the API nicer, so we can write similar_type(typeof(v), 3) and get a 3-vector type back (as opposed to needing similar_type(typeof(v), Val{3})). It is in this function where we see specializations - like similar, there is a default array type (SVector and so-on), but users can override this to something more specific for their own types.

I suppose we could change the API in both cases to use the Size trait, and get rid of the @pure.

[vtjnash]

I assume you must have had something before @pure was added? The reason that the compiler doesn't infer arithmetic is really just that it can't (while maintaining reasonable limits on memory consumption and load times for the typical package), given the current convergence structure of inference. Not all usages of @pure in here are broken, however. Only the ones that may be overloaded or redefined later are invalid. The rest will hopefully be replaced by more intelligent inference, but don't cause any serious short-term issues.

As for making tuples of parameters, that works just fine for me:

julia> struct T{A, B} end

julia> f{A, B}(::Type{T{A, B}}) = (A, B)
f (generic function with 1 method)

julia> g() = Val{f(T{1, 2})}
g (generic function with 1 method)

julia> @code_typed g()
CodeInfo(:(begin 
        return $(QuoteNode(Val{(1, 2)}))
    end))=>Type{Val{(1, 2)}}

Currently the only generic advice I can offer is my trailing type parameters package (https://github.com/vtjnash/ComputedFieldTypes.jl) to store the computation results combined with function boundaries such that the computation is memoized over the inner loop. I realize though that allowing any sort of computed field types (aka JuliaLang/julia#18466) also ensures that it'll be heap allocated, so not a huge win here.

[andyferris]

Thanks for the advice.

I assume you must have had something before @pure was added?

Nope, StaticArrays was authored specifically for v0.5. These packages (ImmutableArrays, FixedSizeArrays and StaticArrays) are typically using the latest-and-greatest to maximise performance and genericism and compatibility with AbstractArray, so are pushing the boundaries pretty hard.

Given this history, we always expected to have to rewrite parts of the package to take advantage of v0.6 (or it would seem likely that someone else would!). Were there any compiler optimizations in v0.5 (specializations for non-concrete types) which these overloaded @pure functions would clash with, or are these new so that it would simply be the usual # 265 problems? If not, perhaps making a clean break for v0.6 would be best, and leave the v0.5 code as-is.

The reason that the compiler doesn't infer arithmetic is really just that it can't (while maintaining reasonable limits on memory consumption and load times for the typical package), given the current convergence structure of inference.

So, you are saying that if +(::Int, ::Int) were @pure it would slow down compilation significantly?

As for making tuples of parameters, that works just fine for me:

That is a (very nice!) improvement in v0.6. My result was for v0.5. It's truly wonderful that creating tuples is now pure (i.e. constant propagates), and I see also indexing them is also pure:

julia> h() = Val{f(T{1, 2})[1]}
h (generic function with 1 method)

julia> h()
Val{1}

julia> @code_typed h()
CodeInfo(:(begin 
        return $(QuoteNode(Val{1}))
    end))=>Type{Val{1}}

This was a really tricky thing to work around in v0.5... and was one of the reasons for not keeping the sizes as type vars as they were in FixedSizeArrays.

[andyferris]

See #105.

We still use @pure but they are never specialized. These generally related to the Size trait, which is a single concrete type.

[andyferris]

Possibly related to #106, but that seems unlikely.

[andyferris]

I think this has been fixed for a while, but I'm closing this with #121