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

[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> 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> @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> 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> @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 #42372, so I'm unsure if this may be addressed at present.

[vtjnash]

Note this comes explicitly from

julia/base/promotion.jl

Line 180 in 6f8e24c

return Any # TODO: compute more precise bounds

since we don't attempt to compute the inferred result at all

julia/base/array.jl

Line 755 in 6f8e24c

T = ($I).f

and then that function makes it even worse

julia/base/array.jl

Line 759 in 6f8e24c

promote_typejoin_union(T)

Some of this probably requires #42372, so I'm unsure if this may be addressed at present.

n.b. we currently assume this for @default_eltype

[matthias314]

What about changing the test

julia/base/array.jl

Lines 754 to 755 in 6f8e24c

	if $I isa Generator && ($I).f isa Type
	T = ($I).f

to only testing for concrete types?

if $I isa Generator && isconcretetype(($I).f)
    T = ($I).f

This would fix the problem with the parametric type A defined above:

julia> map(A, Int[])
Any[]        # current
A{Int64}[]   # new

I ran most of the tests involving map, and I only found one that failed:

julia> map(Integer, Any[])  # from test/functional.jl
Integer[]   # current
Any[]       # new

On the other hand, we would still have

julia> map(Integer, Integer[])
Integer[]

and in other cases we even get more precise results:

julia> map(Integer, Int[])
Integer[]   # current
Int64[]     # new

I have also tried to test for not being a UnionAll type. (Integer is concrete, but not UnionAll.) However, that leads to an error during compilation.