Why construction of Dict via generator is not type-stable?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Why construction of Dict via generator is not type-stable?

bogumil.kaminski
Consider the following two functions:

function f1(t, a)
    [t(x) for x in a]
end

function f2(t, a)
    Dict((x, t(x)) for x in a)
end

When I run @code_warntype on them I get:

julia> @code_warntype f1(sin, [1.0, 2.0])
Variables:
  #self#::#f1
  t::Base.#sin
  a::Array{Float64,1}

Body:
  begin
      return $(Expr(:invoke, LambdaInfo for collect(::Base.Generator{Array{Float64,1},Base.#sin}), :(Base.collect), :($(Expr(:new, Base.Generator{Array{Float64,1},Base.#sin}, :(t), :(a))))))
  end::Array{Float64,1}

julia> @code_warntype f2(sin, [1.0, 2.0])
Variables:
  #self#::#f2
  t::Base.#sin
  a::Array{Float64,1}
  #1::##1#2{Base.#sin}

Body:
  begin
      #1::##1#2{Base.#sin} = $(Expr(:new, ##1#2{Base.#sin}, :(t)))
      SSAValue(0) = #1::##1#2{Base.#sin}
      SSAValue(1) = $(Expr(:new, Base.Generator{Array{Float64,1},##1#2{Base.#sin}}, SSAValue(0), :(a)))
      return $(Expr(:invoke, LambdaInfo for Dict{K,V}(::Base.Generator{Array{Float64,1},##1#2{Base.#sin}}), :(Main.Dict), SSAValue(1)))
  end::Union{Dict{Any,Any},Dict{Float64,Float64},Dict{Union{},Union{}}}

I have the folowing questions:
  1. Why when f2 is used as written above the return type is not Dict{Float64,Float64} (like in the case of f1 where it is Array{Float64,1})?
  2. How to fix f2 so that Julia can infer the return type?
  3. Is there a way to change f2 so that first empty Dict{<element type of a>,<element type of t(a)>}() variable is created, where <element type of a> and <element type of t(a)> are determined based on the passed arguments, and only next this dictionary is populated with data?
With kind regards,
Bogumil Kaminski
Reply | Threaded
Open this post in threaded view
|

Why construction of Dict via generator is not type-stable?

Lutfullah Tomak
What about storing eltypes in  variables and directly calling 'Dict{eltypa,eltypet_a}(...)'? I think there is some issue about this github too.
Reply | Threaded
Open this post in threaded view
|

Re: Why construction of Dict via generator is not type-stable?

Ralph Smith
In reply to this post by bogumil.kaminski
Until the issue with generators is resolved, this may suffice:

f2x{T}(t::Function,a::AbstractArray{T})::Dict{T,T} = Dict((x,t(x)) for x in a)


I think that diverts all the ambiguities to checks by conversion methods.

On Sunday, November 13, 2016 at 11:16:20 AM UTC-5, [hidden email] wrote:
I have the folowing questions:
  1. Why when f2 is used as written above the return type is not Dict{Float64,Float64} (like in the case of f1 where it is Array{Float64,1})?
  2. How to fix f2 so that Julia can infer the return type?
  3. Is there a way to change f2 so that first empty Dict{<element type of a>,<element type of t(a)>}() variable is created, where <element type of a> and <element type of t(a)> are determined based on the passed arguments, and only next this dictionary is populated with data?

Reply | Threaded
Open this post in threaded view
|

Re: Why construction of Dict via generator is not type-stable?

bogumil.kaminski
Thank you.
However, my problem is that t(x) does not have to have type T.
And this is exactly the question - how to determine type of t(x) given that we know that x has type T.

On Monday, November 14, 2016 at 12:29:56 AM UTC+1, Ralph Smith wrote:
Until the issue with generators is resolved, this may suffice:

f2x{T}(t::Function,a::AbstractArray{T})::Dict{T,T} = Dict((x,t(x)) for x in a)


I think that diverts all the ambiguities to checks by conversion methods.

On Sunday, November 13, 2016 at 11:16:20 AM UTC-5, [hidden email] wrote:
I have the folowing questions:
  1. Why when f2 is used as written above the return type is not Dict{Float64,Float64} (like in the case of f1 where it is Array{Float64,1})?
  2. How to fix f2 so that Julia can infer the return type?
  3. Is there a way to change f2 so that first empty Dict{<element type of a>,<element type of t(a)>}() variable is created, where <element type of a> and <element type of t(a)> are determined based on the passed arguments, and only next this dictionary is populated with data?

Reply | Threaded
Open this post in threaded view
|

Re: Why construction of Dict via generator is not type-stable?

Lutfullah Tomak
You could find `ta=t.(a)` first and then construct a `Dict{eltype(a),eltype(ta)}` but it is just a workaround and wastes some memory.
Reply | Threaded
Open this post in threaded view
|

Re: Why construction of Dict via generator is not type-stable?

bogumil.kaminski
Actually I could do:

function f2{T}(t, a::Vector{T})
    Dict{T, code_typed(t, (T,))[1].rettype}((x, t(x)) for x in a)
end

but this does not solve the problem as the compiler still is unable to determine the exact return type of f2.

On Monday, November 14, 2016 at 4:06:20 PM UTC+1, Lutfullah Tomak wrote:
You could find `ta=t.(a)` first and then construct a `Dict{eltype(a),eltype(ta)}` but it is just a workaround and wastes some memory.
Reply | Threaded
Open this post in threaded view
|

Re: Why construction of Dict via generator is not type-stable?

Jeffrey Sarnoff
(afaik requires @generated functions to take everything to a type stable post-precompilation state)

assuming
(a1) If `typeof(x)  == typeof(y)` then `typeof( t(x) )` is the same as `typeof( t(y) )`.    
(a2) If `typeof(x) != typeof(y)` then `typeof( t(x) )` might differ from `typeof( t(y) )`.    
(a3) There are relatively few (dozens not millions) possible types that x may have when `t(x)` is called.  

(b1) If `typeof(x)  == typeof(y)` then  `typeof( f2(x) )` is the same as `typeof( t(y) )`.    
(b2) If `T is the typeof(x) and T != typeof(y)`, `typeof( f2(t, a::Vector{typeof(x)}) )` may differ from `typeof( f2(t, a::Vector{typeof(y)}) )`.    
(b2) There are relatively few (dozens not millions) possible types that T may have when `f2{T}(t, a::Vector{T})` is called.  

Given (a123), If you write one version of the function `t` for each [abstract] type of x that is to be processed,   
you could annotate each of them with the correct return type.   If you can do that, then you could create an  
ObjectIdDict, t_oid, that maps the type of `x` to the return type of `t`.  Given (b123) and t_oid, you can create an  
ObjectIdDict, f2_oid, that maps the type `T` in `f2` to the return type of `f2`.   
Using t_oid and f2_oid the return type for each call of `t` and each call of `f2` is determinate and available.  


On Monday, November 14, 2016 at 5:32:51 PM UTC-5, [hidden email] wrote:
Actually I could do:

function f2{T}(t, a::Vector{T})
    Dict{T, code_typed(t, (T,))[1].rettype}((x, t(x)) for x in a)
end

but this does not solve the problem as the compiler still is unable to determine the exact return type of f2.

On Monday, November 14, 2016 at 4:06:20 PM UTC+1, Lutfullah Tomak wrote:
You could find `ta=t.(a)` first and then construct a `Dict{eltype(a),eltype(ta)}` but it is just a workaround and wastes some memory.
Reply | Threaded
Open this post in threaded view
|

Re: Why construction of Dict via generator is not type-stable?

Ralph Smith
In reply to this post by bogumil.kaminski
If you can accept an extra call of your function t,


f2
{T}(t::Function,a::AbstractArray{T})::Dict{T,typeof(t(a[1])} = Dict((x,t(x)) for x in a)


credit to mauro3 in discussion of Julia issue 1090.


On Monday, November 14, 2016 at 6:17:38 AM UTC-5, [hidden email] wrote:
Thank you.
However, my problem is that t(x) does not have to have type T.
And this is exactly the question - how to determine type of t(x) given that we know that x has type T.

On Monday, November 14, 2016 at 12:29:56 AM UTC+1, Ralph Smith wrote:
Until the issue with generators is resolved, this may suffice:

f2x{T}(t::Function,a::AbstractArray{T})::Dict{T,T} = Dict((x,t(x)) for x in a)


I think that diverts all the ambiguities to checks by conversion methods.

On Sunday, November 13, 2016 at 11:16:20 AM UTC-5, [hidden email] wrote:
I have the folowing questions:
  1. Why when f2 is used as written above the return type is not Dict{Float64,Float64} (like in the case of f1 where it is Array{Float64,1})?
  2. How to fix f2 so that Julia can infer the return type?
  3. Is there a way to change f2 so that first empty Dict{<element type of a>,<element type of t(a)>}() variable is created, where <element type of a> and <element type of t(a)> are determined based on the passed arguments, and only next this dictionary is populated with data?

Reply | Threaded
Open this post in threaded view
|

Re: Why construction of Dict via generator is not type-stable?

Pablo Zubieta
In reply to this post by bogumil.kaminski
FWIW this is should work fine on master and the solution is likely to be backported to the next 0.5.x version (https://github.com/JuliaLang/julia/pull/19245).

On Sunday, November 13, 2016 at 10:16:20 AM UTC-6, [hidden email] wrote:
Consider the following two functions:

function f1(t, a)
    [t(x) for x in a]
end

function f2(t, a)
    Dict((x, t(x)) for x in a)
end

When I run @code_warntype on them I get:

julia> @code_warntype f1(sin, [1.0, 2.0])
Variables:
  #self#::#f1
  t::Base.#sin
  a::Array{Float64,1}

Body:
  begin
      return $(Expr(:invoke, LambdaInfo for collect(::Base.Generator{Array{Float64,1},Base.#sin}), :(Base.collect), :($(Expr(:new, Base.Generator{Array{Float64,1},Base.#sin}, :(t), :(a))))))
  end::Array{Float64,1}

julia> @code_warntype f2(sin, [1.0, 2.0])
Variables:
  #self#::#f2
  t::Base.#sin
  a::Array{Float64,1}
  #1::##1#2{Base.#sin}

Body:
  begin
      #1::##1#2{Base.#sin} = $(Expr(:new, ##1#2{Base.#sin}, :(t)))
      SSAValue(0) = #1::##1#2{Base.#sin}
      SSAValue(1) = $(Expr(:new, Base.Generator{Array{Float64,1},##1#2{Base.#sin}}, SSAValue(0), :(a)))
      return $(Expr(:invoke, LambdaInfo for Dict{K,V}(::Base.Generator{Array{Float64,1},##1#2{Base.#sin}}), :(Main.Dict), SSAValue(1)))
  end::Union{Dict{Any,Any},Dict{Float64,Float64},Dict{Union{},Union{}}}

I have the folowing questions:
  1. Why when f2 is used as written above the return type is not Dict{Float64,Float64} (like in the case of f1 where it is Array{Float64,1})?
  2. How to fix f2 so that Julia can infer the return type?
  3. Is there a way to change f2 so that first empty Dict{<element type of a>,<element type of t(a)>}() variable is created, where <element type of a> and <element type of t(a)> are determined based on the passed arguments, and only next this dictionary is populated with data?
With kind regards,
Bogumil Kaminski