Julia v0.5.0 dictionary iteration is >10x slower than v0.4.6 #18331
Comments
|
I think this is a dup of #16190. |
|
It certainly will be nice to have a fix for this in 0.5. |
|
Yes it is dup of #16190, changing the value type to a I'm not sure how the allocation elimination works on 0.4 so not sure how this regressed. Likely related to linearizing the IR. |
|
Cc @vtjnash |
|
Actually, profiling shows that the allocation was in charge of the 500ns -> 3us performance difference (which actually didn't regress from 0.4), the big regression seems to actually come from So indeed @vtjnash |
|
The profile |
|
I'm not sure why dispatching on this particular type seems to be much more expensive, although it is a complex type so it has to go through type_eqv and the sort order of the table is different now. The real issue is that methods is returning too many matches: julia> Base._methods_by_ftype(Tuple{typeof(convert), Type{Tuple{Float64,Distributions.Distribution{Distributions.Univariate,Distributions.Continuous}}}, Tuple{Float64,Distributions.Distribution{Distributions.Univariate,Distributions.Continuous}}}, -1)
2-element Array{Any,1}:
svec(Tuple{Base.#convert,Type{Tuple{Float64,Distributions.Distribution{Distributions.Univariate,Distributions.Continuous}}},_<:Tuple{Float64,Distributions.Distribution{Distributions.Univariate,Distributions.Continuous}}},svec(Tuple{Float64,Distributions.Distribution{Distributions.Univariate,Distributions.Continuous}}),convert{T<:Tuple{Any,Vararg{Any,N}}}(::Type{T}, x::T) at essentials.jl:69)
svec(Tuple{Base.#convert,Type{Tuple{Float64,Distributions.Distribution{Distributions.Univariate,Distributions.Continuous}}},Tuple{Float64,Distributions.Distribution{Distributions.Univariate,Distributions.Continuous}}},svec(Tuple{Float64,Distributions.Distribution{Distributions.Univariate,Distributions.Continuous}}),convert{T<:Tuple{Any,Vararg{Any,N}}}(::Type{T}, x::Tuple{Any,Vararg{Any,N<:Any}}) at essentials.jl:67)also looking at this method lookup result, it looks like the type system is confused and returns an inappropriate typevar from (lldb) p jl_($15->sig)
Tuple{Base.#convert, Type{#T<:Tuple{Any, Vararg{Any, N<:Any}}}, #T<:Tuple{Any, Vararg{Any, N<:Any}}}
(lldb) p jl_svec_t *env = jl_emptysvec; jl_lookup_match(v, (jl_value_t*)$15->sig, &env, $15->tvars);
(jl_value_t *) $18 = 0x000000010c55e0b0
(lldb) p jl_($18)
Tuple{Base.#convert, Type{Tuple{Float64, Distributions.Distribution{Distributions.Univariate, Distributions.Continuous}}}, _<:Tuple{Float64, Distributions.Distribution{Distributions.Univariate, Distributions.Continuous}}}
(lldb) p jl_(env)
svec(Tuple{Float64, Distributions.Distribution{Distributions.Univariate, Distributions.Continuous}})another side issue too is that diff --git a/src/gf.c b/src/gf.c
index 0e69c74..21d2a7d 100644
--- a/src/gf.c
+++ b/src/gf.c
@@ -1332,9 +1332,9 @@ jl_lambda_info_t *jl_get_specialization1(jl_tupletype_t *types)
for (i = 0; i < jl_nparams(types); i++) {
jl_value_t *ti = jl_tparam(types, i);
// if one argument type is DataType, multiple Type{} definitions
- // might match. also be conservative with tuples rather than trying
- // to analyze them in detail.
- if (ti == (jl_value_t*)jl_datatype_type || jl_is_tuple_type(ti)) {
+ // might match.
+ // /* also be conservative with tuple types rather than trying to analyze them in detail. */
+ if (is_kind(ti)) {
jl_value_t *matches = jl_matching_methods(types, 1, 0);
if (matches == jl_false)
return NULL; |
The time is being spent in typemap, but that's not the regression. This case wasn't optimized at all in either the old or new code. But the |
|
Can we get the |
|
fwiw, it's easy to make a version that is 2x faster than OP (and same timing on v0.4 / v0.5): dd = Dict{FT, Any}()
function lratio2(dd::Dict)
num::Float64 = 0.0
denom::Float64 = 0
for (k, v) in dd
pDiscrete = v[1]
pContinuousGivenDiscrete = 1.2
denom += pDiscrete * pContinuousGivenDiscrete
end
return num / denom
end |
|
removing the milestone since it's easy to fix the user code but perhaps difficult to teach the compiler to do that same transform |
|
Then we should document (now) what needs to be done and what kind of code is likely to hit this. |
|
I'm trying to understand and test the user code fix. Are you suggesting that
be changed to
... or am I missing something? If so, this change is not a work around and still experiences the same slowness. |
|
No, I'm suggesting that parametizing Dict is the source of your performance issue. Making the function signature less restrictive was just a necessary side-effect to allow that easily |
|
I don't think using |
|
With the recommended changes, the "real" code is not showing any improvements. I'm afraid it may be slowing down elsewhere, as suggested. I'll look more into the details when I get a chance. |
|
I've identified what is going on.
Overall, this fix resolves the immediate problem, but it is not a good solution for the language, especially when the language is being sold as 1) high performance and 2) designed so that static analysis of the code is easy. I'm certain that similar iteration is a very common use case. |
|
It looks like this was fixed on 0.6, probably by #21377. I get medians of
This would be worth adding to BaseBenchmarks.jl so it can be automatically tracked for regressions. |
After porting my code to Julia v0.5.0, I am seeing a 3x reduction in speed in a critical area. I have narrowed the root cause down to what appears to be slow dictionary iteration in v0.5.0.
Reproducer code:
https://gist.github.com/chipkent/c8e3acc4f64bd78db4fe40f2c42072f2
The text was updated successfully, but these errors were encountered: