A playful competition: who can define a method that invalidates the most code?

Turns out the BitInteger union is not needed. I was starting to feel that using Union Types might even have to become its own category, as I was building larger and larger ones to get more invalidations with a single method. But this is just as effective with convert:

julia> using SnoopCompileCore

julia> invalidations = @snoopr Base.convert(::Type{T}, x::Number) where T<:Real = T(x);

julia> using SnoopCompile

julia> length(uinvalidated(invalidations))
18362
4 Likes

Some i had high hopes for but that didn’t work out:

Redefining Expr:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.0-DEV.1073 (2020-09-29)
 _/ |\__'_|_|_|\__'_|  |  Commit 4f0145b7b0* (3 days old master)
|__/                   |

julia> using SnoopCompile

julia> inv = @snoopr Base.Expr(args...) = Core._expr(args...);

julia> length(uinvalidated(inv))
868

Redefining @nospecialize to actually specialize.
I thought this should invalidate a bunch of things that otherwise wouldn’t be invalidatable, but seems not to have.
MIght have missed something

julia> inv = @snoopr Base.@eval macro nospecialize(x)
           x
       end
Any[]

julia> length(uinvalidated(inv))
0

Same idea for @noinline

julia> inv = @snoopr Base.@eval macro noinline(x)
           :(@inline x)
       end
Any[]

julia> length(uinvalidated(inv))
0

Does changing macros effect code that’s already defined?

No, changing a macro shouldn’t change anything for already applied macro, only future use. There might be exceptions, i.e. code that uses eval.

Redefining a macro doesn’t have any effect on already-evaluated uses of the macro—the current meaning of the macro is used at parse time and after that there’s no connection. I’m pretty sure that’s how all macro systems work. Otherwise it would be like trying to go back and fix the results of past calls to functions when you redefine them.

2 Likes

Today, I learned.
Thinking about it, yes, that makes sense.

1 Like

If these macros called some auxiliary inner function (inside the methods they modify) that could be invalidated, then this could work. But I do not know if it is the case (would guess no).

No because that still only affects future macro expansions: code that’s already been order and macro-expanded will not be released and expanded.

3 Likes

Just to clarify, I meant something like: @my_macro args expands to my_aux_f(args...) inside the method body of a function outer, so changing function my_aux_f (not macro my_macro) could invalidate the method outer. Having a programmer write the call to my_aux_f and a macro to do the same has indistinguishable results no?

For a concrete example, if I somehow change print, and @show is expanded to print, then every method calling @show may be invalidated, no?

Yikes, realized I forgot to announce the results on Friday. To evaluate the submissions, I tested each using a script that I executed from the linux prompt to ensure there weren’t differences in my typing at the REPL (since hitting certain keys can force the compilation of new methods). In a couple of cases, this led to a pretty different count than provided by the submitter, perhaps mostly because some REPL methods did not compile. (At least the rank order was consistent with the numbers provided by the applicants.)

Without further ado, here are the results of my analysis and the winners…

For the category of “pirating methods,” we had several submissions including a nail-biter for the win:

  • third place variants of overloading +:
    • the original submission was Base.:+(x::Int, y::Int) = Base.inferencebarrier(Base.add_int(x, y)) (the inferencebarrier isn’t required ) by @simeonschaub at 15782
    • an improved/more evil version Base.:+(x::T, y::T) where {T<:Base.BitInteger} = Base.add_int(x, y) by @StefanKarpinski at 15933
  • second place: Base.getproperty(x, s::Symbol) = getfield(x, s) by @simonbyrne at 17035
  • first place Base.convert(::Type{T}, x::Number) where T<:Real = T(x) by @tomerarnon at 17093

In the non-pirating category, we had:

  • second place struct DoNotCare<:Real end; Base.:(==)(x::DoNotCare, ::Any) = true by @oxinabox at 58
  • convert methods:
    • struct X end; Base.convert(::Any, ::X) = nothing by @oxinabox at 1666 was disqualified (sorry) because to be a valid convert method it should have been Base.convert(::Type{Any}, ::X) (which has 1152 and would have won), so the winner is…
    • first place struct X end; Base.convert(::Union{}, ::X) = nothing by @mbauman at 903

In case you’re curious, in the non-pirating category I believe that it’s not currently possible to do better than the following rather arcane submission:

struct X end
Base._str_sizehint(::X) = nothing

at 2622 invalidations. You can discover this and similar opportunities by installing MethodAnalysis and then running demos/abstract.jl and typing mipriv on the command line. (mipriv means “MethodInstances of private, a.k.a. non-exported, names”; the analog for exported names is miexp).

Congrats to the winners, and let the second phase commence! Announcement will likely be made on Saturday as I am reserving Friday afternoon for a family bike trip.

30 Likes

I’ld like to appeal. :man_judge: :joy:
convert(::Any, ::X) isn’t against the rules.
It’s not piracy since X is my own type, and i see no special rule for convert .
It’s not sensible julia code, but that wasn’t a requirement. :joy_cat:
I think the only vaguely sensible things submitted were my DoNotCare one and the MyCustomString one at the start.

15 Likes

I agree, although I am kicking myself for not realizing that Union{} is just a wonky subcategory. I do like it though since it’s a non-callable method :slight_smile:

7 Likes

…it looks like the referees and the linejudges are conferring… they seem to be going to the video…

5 Likes

…and the appeal is upheld! We have a new winner, @oxinabox :fireworks:

I realized the same remark could apply to the second: that the way convert is intended, it should probably be convert(::Type{Union{}}, ::X). So either way, @oxinabox wins.

11 Likes

I wonder if this is for amusement only or … what’s the plan?

I believe this is related to the push towards fixing invalidations: Finding and fixing invalidations: now, everyone can help reduce time-to-first-plot

1 Like

Thanks for the reference, but how invalidations are fixed? Is this by changing something in the language or by changing code in Base so it will not be invalidated?

Analyzing sources of compiler latency in Julia: method invalidations is a good read.

In short, an invalidation occurs when a new method is added that breaks an assumption inference made to compute some earlier result and compiled code based on that result. Code in Base can be tweaked in such a way that it relies less on assumptions that packages tend to invalidate. This can be done by adding type assertions and conversions in strategical places, or use Base.invokelatest to “shield” certain parts of the code from inference.

It should be noted that there is nothing wrong with invalidations and they are very useful in the sense that it can give you nice optimizations and recompiling a small set of methods is often fast. It is just when they get excessive it creates noticeable compiler latency so it is good to get rid of the most egregious ones. But I think we are pretty good on that front now after all of Tim’s work. There are a few patterns that are still pretty bad (like convert(::Type{T}, ...) where {T}). but that is not too common to define in packages.

10 Likes

I agree with everything that @kristoffer.carlsson said, but one more point worth noting is that invalidations can also block effective precompilation. Even a small method that is quick to re-infer can block a big method that is really expensive to infer. Consequently, fixing invalidations can make more (still not all, but more) methods precompilable, and that’s another contribution to reducing latency. I agree 100% that we shouldn’t (and can’t) be dogmatic about getting rid of them all, but any “frivolous” invalidations may ultimately be worth someone’s time and attention.

When pre-release versions of 1.6 become available, I hope package authors take a new look at adding more precompile directives to reduce package latency. Once those precompile statements are in place, we’ll also start learning more about the ways that packages invalidate each other (you can only detect invalidations in methods that have been inferred). If the story of Julia itself is any guide, tracking those down and eliminating them will be another big step in reducing latency in interactive settings where people do some stuff, then load more packages, do more stuff, etc.

14 Likes

Not as bad as the winning convert methods, but it’s also easy to rack up a lot of invalidations with constructors

julia> using SnoopCompileCore

julia> struct X <: Integer; i::Int; end

julia> invalidations = @snoopr (::Type{T})(x::X) where {T} = T(x.i);

julia> using SnoopCompile; length(uinvalidated(invalidations))
733
2 Likes