<: vs === speed for types

[bramtayl]

It looks like === is (non-intuitively) a lot faster for types, going back at least far as d194625 and as also discussed here #25828 (comment) and here #30076 (comment)

[Keno]

Why is that non-intuitive? === is a trivial structural equality check, while <: is a type system predicate. == is of course more expensive than <:.

[bramtayl]

Oh, well that makes sense.

[nalimilan]

Though shouldn't <: include a fast-path for when types are ===? Also I think the problem was much deeper than that when this was discussed (see references, maybe it's changed since then).

[JeffBezanson]

Though shouldn't <: include a fast-path for when types are ===?

It has that fast path already. The linked comments also seem to be primarily about inference. It is also expected that === will be faster than <: in many cases when called at run time. So I think we'd need further examples for this issue to be actionable.

[bramtayl]

I mean I might have mis-titled the issue, maybe I should re-title it to === infers better than <:?

[JeffBezanson]

Maybe; a test case would still be very helpful. Is there really a case where we can infer === (implying we know the exact structure) but not <: ? The other way is of course possible since === is strictly more precise.

[bramtayl]

Maybe @nalimilan can provide the test case? My attempt to make up a test case (based on the comment above) didn't really pan out.

julia> using BenchmarkTools

julia> unstable(x) = x ? 0 : missing

julia> input = map(unstable, rand(Bool, 1000))

julia> @btime map(x -> x isa Int || typeof(x) === Int, input);
  1.199 μs (2 allocations: 1.08 KiB)

julia> @btime map(x -> x isa Int, input);
  1.199 μs (2 allocations: 1.08 KiB)

[nalimilan]

I don't know, the only situation where I know this mattered (when I wrote that comment at least), was in the implementation of map. If removing === in there doesn't make a difference for performance (in particular with Union{T,Missing}), then that means it's fixed.

[bramtayl]

Ok, so here's my own inexpert attempt to benchmark:

using BenchmarkTools
import Base: Generator
import Base.Iterators: Filter

unstable(x) = x ? 0 : missing

input = rand(Bool, 1000000)
size_known = Generator(unstable, input)
size_unknown = Generator(unstable, Filter(x -> rand(Bool), input))

Then here's how I hacked Base:

import Base: grow_to!, collect_to!, promote_typejoin
function grow_to!(dest, itr, st)
    T = eltype(dest)
    y = iterate(itr, st)
    while y !== nothing
        el, st = y
        S = typeof(el)
        if S <: T
            push!(dest, el::T)
        else
            new = sizehint!(empty(dest, promote_typejoin(T, S)), length(dest))
            if new isa AbstractSet
                # TODO: merge back these two branches when copy! is re-enabled for sets/vectors
                union!(new, dest)
            else
                append!(new, dest)
            end
            push!(new, el)
            return grow_to!(new, itr, st)
        end
        y = iterate(itr, st)
    end
    return dest
end
function collect_to!(dest::AbstractArray{T}, itr, offs, st) where T
    # collect to dest array, checking the type of each result. if a result does not
    # match, widen the result type and re-dispatch.
    i = offs
    while true
        y = iterate(itr, st)
        y === nothing && break
        el, st = y
        if el isa T
            @inbounds dest[i] = el::T
            i += 1
        else
            R = promote_typejoin(T, typeof(el))
            new = similar(dest, R)
            copyto!(new,1, dest,1, i-1)
            @inbounds new[i] = el
            return collect_to!(new, itr, i+1, st)
        end
    end
    return dest
end

This is just the code from Base with the === terms removed

Then here are my benchmarks:

# BEFORE
julia> @btime collect(size_unknown);
  4.699 ms (19 allocations: 1.13 MiB)

julia> @btime collect(size_known);
  471.802 μs (3 allocations: 879.09 KiB)

# AFTER
julia> @btime collect(size_unknown);
  4.517 ms (19 allocations: 1.13 MiB)

julia> @btime collect(size_known);
  452.055 μs (3 allocations: 879.09 KiB)

So, I don't see any difference, but I'm not sure if I did this right

[bramtayl]

Ok, here's another one, same as above except:

input = trues(1000000)
input[1000000] = false

# BEFORE
julia> @btime collect(size_unknown);
  18.435 ms (20 allocations: 5.00 MiB)

julia> @btime collect(size_known);
  11.666 ms (7 allocations: 16.21 MiB)

# AFTER
julia> @btime collect(size_unknown);
  19.714 ms (20 allocations: 5.00 MiB)

julia> @btime collect(size_known);
  7.885 ms (4 allocations: 16.21 MiB)

[nalimilan]

Thanks! So there would be a difference only for BitArray? Even then it's not that large, but it would be interesting to find where it comes from.

[bramtayl]

Which difference are you looking at? The only one that struck me was the reduction in allocations for size_known in the second case. Which suggests that removing === makes things... better?

[JeffBezanson]

Which suggests that removing === makes things... better?

I haven't looked into it yet, but that's entirely possible --- === is more precise, so it is harder to infer than <:, so there might be cases where we can optimize out <: but not ===.

[vtjnash]

The specific shape of that expression also acts as an inference barrier (the === was kept as an expensive way to compute true to prevent current inference from propagating incorrect information into the branch, #25828 (comment))

[bramtayl]

Yup I'm officially lost now

[nalimilan]

For reference (maybe a bit off-topic), val isa T is much more efficient than S = typeof(val); S <: T when val is inferred as Union{T, Missing}. See #26681. Whether to use === or <: may not be the real question.

[tkf]

I just had an example (JuliaFolds/Transducers.jl@6d99ccf) that changing isa-based comparison with ===-based one fixed absurdly long compilation time (= more than 10 minutes; I've never seen it's finished). I'm not sure if it's related, but this issue was the inspiration for me to try ===-based comparison.

[JeffBezanson]

@tkf - could you make a branch with the code that takes too long to compile and provide instructions to reproduce that?

[tkf]

@JeffBezanson Rather than hijacking this issue, I posted a new one here: #30744