Performance issue with use of eltype()?

performance

#1

I am at a loss to explain the performance difference between these two functions. Can someone help?

julia> function foo(a::AbstractVector)
           T = eltype(a)
           c = Set{T}[Set{T}() for x in a]
           return length(c)
       end
foo (generic function with 1 method)

julia> function bar(a::Vector{T}) where T
         c = Set{T}[Set{T}() for x in a]
         return length(c)
       end
bar (generic function with 1 method)

julia> a = rand(1:100_000, 2_000_000);

julia> eltype(a)
Int64

julia> @benchmark foo($a)
BenchmarkTools.Trial:
  memory estimate:  961.30 MiB
  allocs estimate:  10000004
  --------------
  minimum time:     3.654 s (14.18% GC)
  median time:      3.797 s (17.07% GC)
  mean time:        3.797 s (17.07% GC)
  maximum time:     3.939 s (19.76% GC)
  --------------
  samples:          2
  evals/sample:     1

julia> @benchmark bar($a)
BenchmarkTools.Trial:
  memory estimate:  961.30 MiB
  allocs estimate:  10000003
  --------------
  minimum time:     283.377 ms (0.00% GC)
  median time:      983.086 ms (65.25% GC)
  mean time:        1.080 s (68.63% GC)
  maximum time:     2.720 s (87.05% GC)
  --------------
  samples:          6
  evals/sample:     1

julia> foo(a) == bar(a)
true

#2

Please don’t cross post or at least link to the other places you post to.

It’s unrelated to eltype but closure capture variable. See my comment in https://github.com/JuliaLang/julia/issues/23618


#3

@yuyichao this is a separate issue. Notice that the generator is explicit with Set{T}[...] in both functions, unlike the github issue I posted.


#4

Didn’t notice that although it’s actually still the same issue. The explicitly specified type hides the type instability on the final value but not in the loop.


#5

Neither foo nor bar is warning of any type instability.


#6

This is fast for any abstract array, in case that is an issue:

function foobar(a::AV) where AV<:AbstractVector{T} where T
                c = Set{T}[Set{T}() for x in a]
                return length(c)
end

#7

The type instability is hiden in the (not inlined in this case) implementation of comprehension.

If you want to see it, you’ll need to look into the line that implements comprehention

      c::Array{Set{Int64},1} = $(Expr(:invoke, MethodInstance for copy!(::Array{Set{Int64},1}, ::Base.Generator{Array{Int64,1},getfield(Main, Symbol("##1#2")){DataType}}), :(Base.copy!), :($(Expr(:foreigncall, :(:jl_alloc_array_1d), Array{Set{Int64},1}, svec(Any, Int64), :(:ccall), 2, Array{Set{Int64},1}, :((Base.select_value)((Base.slt_int)(SSAValue(4), 0)::Bool, 0, SSAValue(4))::Int64)))), SSAValue(2)))::Array{Set{Int64},1}

And show the code_warntype of that. You can get a hint about it from ::Base.Generator{Array{Int64,1},getfield(Main, Symbol("##1#2")){DataType}} showing that the closure is only parametrized for {DataType} and not {Type{Int64}}.


#8

Ah, cool. I understand. Thanks.