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

Tooling
1

You may know that several of us have been hard at work stamping out invalidations as a way of reducing Julia’s latency. Kristoffer Carlsson and I thought it might be fun to have a contest to do the opposite: see who can come up with truly horrendous methods that obliterate almost everything :stuck_out_tongue:. There are no prizes other than the fame and glory that come with impressing your colleagues at your devilishness.

For those who haven’t read the blog post, very briefly the goal is to come up with a method definition that would force Julia to recompile a bunch of already-compiled code. Generally, this means creating a method that is more specific than the one that got compiled in. You can read about how you measure invalidations here.

Here are the competition rules:

  • the winners will be announced on Friday, Oct 2.
  • you must use a released “nightly” binary (Julia Downloads (nightly binaries))
  • when we verify your submission, we’ll start from a fresh Julia session that’s only loading SnoopCompileCore: no cheating by loading a lot of other packages and invalidating their methods, too.
  • scoring will be based solely on length(uinvalidated(invalidations))
  • you’re allowed to define new structs, but your submission rests on the number of invalidations triggered by a single method definition.
  • we will award separate prizes for “non-pirating” and “pirating” method definitions. (See definition of type piracy.)

For context, a fresh Julia session contains about 48,000 MethodInstances. See how many of them you can obliterate!

32 Likes
2

As a small example, this causes a meager ~100 invalidations:

julia> using SnoopCompileCore

julia> struct MyCustomString
           s::Vector{UInt8}
       end

julia> invalidations = @snoopr Base.convert(::Type{String}, m::MyCustomString) = String(m.s);

julia> using SnoopCompile

julia> length(uinvalidated(invalidations))
108

Looking at the output of

trees = invalidation_trees(invalidations)

and figuring out why a certain invalidation happen via e.g.

trees[end].mt_backedges[end][2] |> ascend

can be pretty interesting. Perhaps some of the invalidations in my example can even be fixed (maybe by you!).

9 Likes
3

You should add phase 2, where in the week after submissions are due, you get 10 points per competitor method that you can get to not cause invalidations by improving base.

3 Likes
4

:laughing: I think we just need to add that. So, call it official: week 2 is “sabotage week”! Undermine your competitors by submitting a PR (doesn’t yet have to be accepted) to Julia or its standard libraries that prevents their submission from taking the trophy! We’ll offer recognition on Friday, Oct 9 for the person who most reduced the number of invalidations of one of the official submissions.

This one is only for the non-pirating submissions (there’s nothing you can do about the pirating ones).

10 Likes
5

How do we submit?

6

Just post here? Does that seem fair? First to post a solution gets the credit…we’ll make a subjective decision about things that are too close to count as novel.

If that doesn’t seem fair, I’m open to alternatives…but I thought it would be kind of fun to marvel at the submissions as they roll in.

7

This is allowed under those rules, right? :wink:

               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.6.0-DEV.1090 (2020-09-30)
 _/ |\__'_|_|_|\__'_|  |  Commit 395e47f4da* (0 days old master)
|__/                   |

julia> using SnoopCompile

julia> inv = @snoopr Base.:+(x::Int, y::Int) = Base.inferencebarrier(Base.add_int(x, y));

julia> length(uinvalidated(inv))
16956
15 Likes
8

Wow, we already have an incredibly impressive contestant for the “piracy” category. Approximately one-third of all MethodInstances…

6 Likes
10

I think this competition is a great idea! A really good and fun way to get everyone active in the fight against invalidation!

Can anyone explain why it takes a number of method definitions in a row for the number of invalidations to “settle”? See:

julia> using SnoopCompile

julia> begin 
           inv = @snoopr Base.:+(x::Int, y::Int) = Base.inferencebarrier(Base.add_int(x, y))
           length(uinvalidated(inv))
       end
17002

julia> begin 
           inv = @snoopr Base.:+(x::Int, y::Int) = Base.inferencebarrier(Base.add_int(x, y))
           length(uinvalidated(inv))
       end
1694

julia> begin 
           inv = @snoopr Base.:+(x::Int, y::Int) = Base.inferencebarrier(Base.add_int(x, y))
           length(uinvalidated(inv))
       end
1590

julia> begin 
           inv = @snoopr Base.:+(x::Int, y::Int) = Base.inferencebarrier(Base.add_int(x, y))
           length(uinvalidated(inv))
       end
1458

julia> begin 
           inv = @snoopr Base.:+(x::Int, y::Int) = Base.inferencebarrier(Base.add_int(x, y))
           length(uinvalidated(inv))
       end
1455

julia> begin 
           inv = @snoopr Base.:+(x::Int, y::Int) = Base.inferencebarrier(Base.add_int(x, y))
           length(uinvalidated(inv))
       end
1455
11

Slight problem: the method for measuring invalidations only works on 1.6-DEV which isn’t released, so the rules of the contest seem to be impossible to meet.

12

Turns out the inferencebarrier isn’t needed:

julia> using SnoopCompile

julia> inv = @snoopr Base.:+(x::Int, y::Int) = Base.add_int(x, y);

julia> length(uinvalidated(inv))
16987
3 Likes
13

Slightly better:

julia> using SnoopCompileCore

julia> invalidations = @snoopr Base.:+(x::T, y::T) where {T<:Base.BitInteger} = Base.add_int(x, y);

julia> using SnoopCompile

julia> length(uinvalidated(invalidations))
17117
4 Likes
14

Along a similar vein:

julia> using SnoopCompile

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

julia> length(uinvalidated(invalidations))
18180
5 Likes
15

This one might deserve its own category for underhandedness (i.e. cheating):

julia> using SnoopCompileCore

julia> invalidations = @snoopr Base.length(::Set{Core.MethodInstance}) = Inf
Any[]

julia> using SnoopCompile

julia> length(uinvalidated(invalidations))
Inf
42 Likes
16

An entry for the non-piracy category.
(Since the playing feild seems more open)

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


julia> using SnoopCompile

julia> struct DoNotCare<:Real end

julia> inv = @snoopr Base.:(==)(x::DoNotCare, ::Any) = true;

julia> length(uinvalidated(inv))
282
7 Likes
17

Does this count in the non-piracy category?

julia> using SnoopCompileCore

julia> struct X end

julia> inv = @snoopr Base.convert(::Union{}, ::X) = nothing;

julia> using SnoopCompile

julia> length(uinvalidated(inv))
1177
7 Likes
18

A direct rip-off of @mbauman for nonpiracy:

julia> using SnoopCompile

julia> struct X end

julia> inv = @snoopr Base.convert(::Any, ::X) = nothing;

julia> length(uinvalidated(inv))
2203
8 Likes
19

The only way to improve on this is to make a type that can store hyper-real numbers efficiently so you can get a bigger infinity (assuming Inf is aleph null)

2 Likes
20

Aren’t the rules to use the nightly release or am I missing something?

3 Likes
21

Ah yes, I misread that as using a released version, not a nightly release!

1 Like