Type inference for map and broadcast differs on empty vectors

matthias314 · April 10, 2023, 9:36pm

Both map and broadcast can infer the element type if a function is applied to an empty vector, at least in many circumstances:

julia> f(x) = 3*x
julia> map(f, Int[])
Int64[]
julia> f.(Int[])
Int64[]

However, if used with constructors, broadcast does a better job than map:

julia> map(Some, Int[])
Any[]
julia> Some.(Int[])
Some{Int64}[]

Is this intended, or is it a bug? (Tried on Julia 1.9.0-rc2)

Benny · April 11, 2023, 6:20am

It does this on v1.8.5 too, and it used to infer Some on v1.4.1 (but not Some{Int}).

It seems the difference starts at _collect(c, itr, ::EltypeUnknown, isz::Union{HasLength,HasShape}) in array.jl.
The _similar_for calls are relevant to empty vectors, and the method signatures are different too.
But the root difference seems to be Base.@default_eltype(Base.Generator(Some,Int[])), which is Any on v1.8.5 but Some on v1.4.1. It used to return Some by accessing the .f field of the Generator, but now it computes Base.promote_typejoin_union(Some) to Any.
promote_typejoin_union(::Type{T}) where T in promotion.jl has many branches but there’s 2 of note there. If T isa DataType, it just returns T, but if T isa UnionAll, it returns Any. Some is not a concrete type, but an iterated union Some{T} where T. I’m not sure why it was decided to remove that type information instead of returning T, but it actually is commented # TODO: compute more precise bounds so that may change eventually.

Aside: I have no idea what Some is for, I read the docs before and didn’t know why there needed to be a distinction between nothing and Some{nothing}. It doesn’t seem necessary for Base.something to find the first argument that isn’t nothing.

jishnub · April 11, 2023, 6:35am

I had created an issue about this sometime back:

github.com/JuliaLang/julia

`map(::Type, ::AbstractArray)` may be concretely inferred

opened 11:35AM - 12 Aug 22 UTC

jishnub

This is a somewhat special case for concrete or a `UnionAll` of concrete types, …and doesn't hold in general. Looking at an example: ```julia julia> struct A{T} x::T end julia> Base.zero(::Type{A{T}}) where {T} = A(zero(T)) julia> Base.:(+)(a::A, b::A) = A(a.x + b.x) ``` In such a case, an operation like `map(A, [1,2,3])` may be concretely inferred, but isn't. ```julia julia> @code_typed map(A, [1,2,3]) CodeInfo( 1 ─ %1 = %new(Base.Generator{Vector{Int64}, Type{A}}, A, A)::Base.Generator{Vector{Int64}, Type{A}} │ %2 = invoke Base._collect(A::Vector{Int64}, %1::Base.Generator{Vector{Int64}, Type{A}}, $(QuoteNode(Base.EltypeUnknown()))::Base.EltypeUnknown, $(QuoteNode(Base.HasShape{1}()))::Base.HasShape{1})::Union{Vector{Any}, Vector{A{Int64}}} └── return %2 ) => Union{Vector{Any}, Vector{A{Int64}}} ``` Using a function barrier may help avoid issues arising from instabilities, but not all packages have been written with such instabilities in mind, Some benchmarks: ```julia julia> function f(v) y = map(A, v) x = zero(eltype(y)) for i in y x += i end x end f (generic function with 1 method) julia> function g(v) y = map(A, v)::Vector{A{eltype(v)}} x = zero(eltype(y)) for i in y x += i end x end g (generic function with 1 method) julia> function finner(y) x = zero(eltype(y)) for i in y x += i end x end finner (generic function with 1 method) julia> function f2(v) y = map(A, v) finner(y) end f2 (generic function with 1 method) julia> @btime f($(rand(1000))); 23.892 μs (2002 allocations: 39.20 KiB) julia> @btime f2($(rand(1000))); 2.273 μs (1 allocation: 7.94 KiB) julia> @btime g($(rand(1000))); 2.296 μs (1 allocation: 7.94 KiB) ``` Ideally, `f` should be as performant as `g` without the need for a function barrier. Another case is where the mapped type is a supertype: ```julia julia> @code_typed map(Real, [1,2,3]) CodeInfo( 1 ─ %1 = %new(Base.Generator{Vector{Int64}, Type{Real}}, Real, A)::Base.Generator{Vector{Int64}, Type{Real}} │ %2 = invoke Base._collect(A::Vector{Int64}, %1::Base.Generator{Vector{Int64}, Type{Real}}, $(QuoteNode(Base.EltypeUnknown()))::Base.EltypeUnknown, $(QuoteNode(Base.HasShape{1}()))::Base.HasShape{1})::Union{Vector{Int64}, Vector{Real}} └── return %2 ) => Union{Vector{Int64}, Vector{Real}} ``` This may be inferred as a `Vector{Int64}`. Some of this probably requires https://github.com/JuliaLang/julia/issues/42372, so I'm unsure if this may be addressed at present.

matthias314 · April 11, 2023, 8:02pm

So the problem is the following: If we say

@default_eltype(Base.Generator(Some, Int[]))

then (code taken from array.jl)

macro default_eltype(itr)
    I = esc(itr)
    return quote
        if $I isa Generator && ($I).f isa Type
            T = ($I).f
        else
            T = Core.Compiler.return_type(_iterator_upper_bound, Tuple{typeof($I)})
        end
        promote_typejoin_union(T)
    end
end

we end up in the if branch. This gives Some , which is later promoted to Any. Wouldn’t the problem disappear if ($I).f isa Type were replaced by isconcretetype(($I).f)?

(For concrete types this would still use the assumption that a constructor for a type T returns an element of type T. Maybe this could be fixed by removing the if branch completely.)