Unnecessary GC frame?

[chriselrod]

julia> evtest = @NamedTuple{evid::Int8, base_time::Float64}[(evid = 1, base_time = 0.0), (evid = -1, base_time = 0.0)]  
2-element Vector{@NamedTuple{evid::Int8, base_time::Float64}}:
 (evid = 1, base_time = 0.0)
 (evid = -1, base_time = 0.0)

julia> fl1(t, events) = findlast(x -> x.evid ∈ (1, 4) && x.base_time <= t, events)
fl1 (generic function with 1 method)

julia> fl2(t, events) = findlast(x -> ((x.evid == 1) | (x.evid == 4)) && x.base_time <= t, events)
fl2 (generic function with 1 method)

julia> fl3(t, events) = findlast(x -> any(==(x.evid), (1,4)) && x.base_time <= t, events)
fl3 (generic function with 1 method)

julia> fl4(_, events) = findlast(x -> x.evid ∈ (1, 4), events)
fl4 (generic function with 1 method)

julia> fl5(t, events) = begin
           f = let t=t
               x -> x.evid ∈ (1, 4) && x.base_time <= t
           end
           findlast(f, events)
       end
fl5 (generic function with 1 method)

julia> f(t) = x -> x.evid ∈ (1, 4) && x.base_time <= t
f (generic function with 1 method)

julia> fl6(t, events) = findlast(f(t), events)
fl6 (generic function with 1 method)

julia> @btime fl1(0.0, $evtest)
  23.302 ns (1 allocation: 16 bytes)
1

julia> @btime fl2(0.0, $evtest)
  3.834 ns (0 allocations: 0 bytes)
1

julia> @btime fl3(0.0, $evtest)
  26.154 ns (1 allocation: 16 bytes)
1

julia> @btime fl4(0.0, $evtest)
  3.364 ns (0 allocations: 0 bytes)
1

julia> @btime fl5(0.0, $evtest)
  25.884 ns (1 allocation: 16 bytes)
1

julia> @btime fl6(0.0, $evtest)
  20.045 ns (0 allocations: 0 bytes)
1

I have a very hard time telling these codes apart with Cthulhu.

We can optimize in for Tuples as one workaround, but I think the compiler should be able to handle this well.

[gbaraldi]

The issue with this is that the operations on the tuple aren't inferred nothrow/terminates
i.e < constprop > in(::Int8,::Core.Const((1, 4)))::Bool (+c,+e,!n,!t,+s,+m,+i) for fl1

[chriselrod]

It's a loop over a tuple of length 2, I don't think we need to solve the halting problem in the general case to know it terminates.

[gbaraldi]

No we don't. But it doesn't know that 😆 . In fact it should probably be fully unrolled.

[chriselrod]

function in(x, itr)
    anymissing = false
    for y in itr
        v = (y == x)
        if ismissing(v)
            anymissing = true
        elseif v
            return true
        end
    end
    return anymissing ? missing : false
end

I guess because we don't do any loop analysis in the Julia compiler?

Now, we don't have to be able to unroll it, or even infer 2, but would be nice to figure out under more general situations that loops like this are going to terminate eventually.
Also any idea why it isn't nothrow?

Body::Bool (+c,+e,!n,!t,+s,+m,+i)
1 ──       nothing
2 ──       goto #3
3 ──       nothing
4 ── %4  = Base.getfield(itr, 1, true)::Int64
└───       goto #5
5 ──       goto #6
6 ──       nothing
7 ┄─ %8  = φ (#6 => %4, #17 => %24)::Int64
│    %9  = φ (#6 => 2, #17 => %25)::Int64
└─── %10 = (%8 === x)::Bool
8 ──       goto #10 if not %10
9 ──       return true
10 ─ %13 = Base.sle_int(1, %9)::Bool
└───       goto #12 if not %13
11 ─ %15 = Base.sle_int(%9, 2)::Bool
└───       goto #13
12 ─       nothing
13 ┄ %18 = φ (#11 => %15, #12 => false)::Bool
└───       goto #15 if not %18
14 ─ %20 = Base.getfield(itr, %9, true)::Int64
│    %21 = Base.add_int(%9, 1)::Int64
└───       goto #16
15 ─       goto #16
16 ┄ %24 = φ (#14 => %20)::Int64
│    %25 = φ (#14 => %21)::Int64
│    %26 = φ (#14 => false, #15 => true)::Bool
│    %27 = Base.not_int(%26)::Bool
└───       goto #18 if not %27
17 ─       goto #7
18 ─       nothing
19 ─       return false

I don't see anything that looks like it can throw here. getfield?

[gbaraldi]

Iterate can throw

[chriselrod]

Where/how? Base.iterate has been inlined above.

[gbaraldi]

Well, before optimization, I'm not super sure where it goes wrong here.

[aviatesk]

I don't think that adding effect annotations to in or findprev would actually solve the issue. Since arrays typically aren't represented as constants in the compiler, they're usually not eligible for concrete evaluation in the first place.

It looks like we can eliminate the allocation if we inline the findprev call. After #50048 you can use the callsite inlining and achieve zero allocation:

julia> evtest = @NamedTuple{evid::Int8, base_time::Float64}[(evid = 1, base_time = 0.0), (evid = -1, base_time = 0.0)];

julia> fl1(t, events) = @inline findlast(x -> x.evid ∈ (1, 4) && x.base_time <= t, events)
fl1 (generic function with 1 method)

julia> @btime fl1(0.0, $evtest)
  4.208 ns (0 allocations: 0 bytes)
1

julia> fl3(t, events) = @inline findlast(x -> any(==(x.evid), (1,4)) && x.base_time <= t, events)
fl3 (generic function with 1 method)

julia> @btime fl3(0.0, $evtest)
  4.209 ns (0 allocations: 0 bytes)
1

julia> fl5(t, events) = begin
           f = let t=t
               x -> x.evid ∈ (1, 4) && x.base_time <= t
           end
           @inline findlast(f, events)
       end
fl5 (generic function with 1 method)

julia> @btime fl5(0.0, $evtest)
  4.208 ns (0 allocations: 0 bytes)
1

[gbaraldi]

I agree, the weird thing is that they aren't arrays but tuples, which get inferred as constant by the compiler, but it doesn't try to do too much with that information at the effect level.

[aviatesk]

We need specialized implementations for tuples with Base.@assume_effects :terminates_locally to make them constant folded.