Stuck with another allocation question

General Usage Performance
1

The following program

using BenchmarkTools

const Example1 = Tuple{Int, Float64, Float64, Float64}
const Example2 = Tuple{Int, Float64}

function init!(v, n)
    for i in 1:n
        push!(v, (i, rand(), rand(), rand()))
    end
end

function where(v, f::F) where F <: Function
    ans = similar(v, eltype(v), 0)
    for i in 1:length(v)
        if f(v[i])
            push!(ans, v[i])
        end
    end
    ans
end

function select(v, R, f::F) where F <: Function
    ans = similar(v, R, 0)
    for i in 1:length(v)
        push!(ans, f(v[i]))
    end
    ans
end

function test1()
    v1 = Vector{Example1}()
    init!(v1, 100000)
    v2 = where(v1, e -> e[2] > 0.5 && e[3] > 0.5 && e[4] > 0.5)
end

function test2()
    v1 = Vector{Example1}()
    init!(v1, 100000)
    v2 = where(v1, e -> e[2] > 0.5 && e[3] > 0.5 && e[4] > 0.5)
    v3 = select(v2, Example2, e -> (e[1], e[2] * e[3] * e[4]))
end

@btime test1()
@btime test2()

shows

  2.984 ms (31 allocations: 6.00 MiB)
  3.311 ms (12195 allocations: 6.87 MiB)

in the console. Juno profiler shows allocations at push!(ans, f(v[i])) in select. I have checked the types in select with

println(typeof(ans), " ", typeof(f(v[i])), " ", Base.allocatedinline(typeof(f(v[i]))))

showing

Vector{Tuple{Int64, Float64}} Tuple{Int64, Float64} true

@code_warntype for select also looks unsuspicious too me:

Variables
  #self#::Core.Const(select)
  v::Vector{Tuple{Int64, Float64, Float64, Float64}}
  R::Core.Const(Tuple{Int64, Float64})
  f::Core.Const(var"#49#50"())
  @_5::Union{Nothing, Tuple{Int64, Int64}}
  ans::Vector{Tuple{Int64, Float64}}
  i::Int64

Body::Vector{Tuple{Int64, Float64}}
1 ─       (ans = Main.similar(v, R, 0))
│   %2  = Main.length(v)::Int64
│   %3  = (1:%2)::Core.PartialStruct(UnitRange{Int64}, Any[Core.Const(1), Int64])
│         (@_5 = Base.iterate(%3))
│   %5  = (@_5 === nothing)::Bool
│   %6  = Base.not_int(%5)::Bool
└──       goto #4 if not %6
2 ┄ %8  = @_5::Tuple{Int64, Int64}::Tuple{Int64, Int64}
│         (i = Core.getfield(%8, 1))
│   %10 = Core.getfield(%8, 2)::Int64
│   %11 = ans::Vector{Tuple{Int64, Float64}}
│   %12 = Base.getindex(v, i)::Tuple{Int64, Float64, Float64, Float64}
│   %13 = (f)(%12)::Tuple{Int64, Float64}
│         Main.push!(%11, %13)
│         (@_5 = Base.iterate(%3, %10))
│   %16 = (@_5 === nothing)::Bool
│   %17 = Base.not_int(%16)::Bool
└──       goto #4 if not %17
3 ─       goto #2
4 ┄       return ans

Now I’m stuck understanding the reason for these allocations. What am I missing?

2

See this entry in the performance tips: Performance Tips · The Julia Language.

To force specialization on the type, use:

function select(v, ::Type{R}, f::F) where F <: Function where R
    ans = similar(v, R, 0)
    for i in 1:length(v)
        push!(ans, f(v[i]))
    end
    ans
end
3 Likes
3

Excellent. This solved the problem, thank you very much!