(Compiler) Performance of Dict

Yes, but the types are not nested. There is nothing inherently slow with Dicts. But code like

might be slow to compile (not because of dicts but because of the nesting of types).

2 Likes

That is true. The type is Dict{AbstractString, Any} and it then contains more Dicts of the same type. Not sure, why it is AbstractString and not String.

for reference, I get

julia> @time a = TOML.parsefile("myfile.toml")
  1.242109 seconds (2.40 M allocations: 120.457 MiB, 11.85% gc time)
Dict{AbstractString,Any} with 6 entries:
  
julia> @time a = TOML.parsefile("myfile.toml")
  0.001002 seconds (2.15 k allocations: 97.641 KiB)
Dict{AbstractString,Any} with 6 entries:

The file has 2613 Bytes. Not sure for what it is allocating 120 MB.

I wonder what would happen if we just added a bunch of Dict{Any,Any} or Dict{Symbol,Any} stuff to the sysimage and told people to prefer that (Any,Any should already have some coverage, but I wonder what would happen if we purposely made it pretty complete)

Lets switch to a concrete example. Here are the numbers I get from Winston:

julia> @time using Winston
  2.744007 seconds (2.26 M allocations: 119.856 MiB, 2.29% gc time)

julia> @time plot(1:100)
  2.838665 seconds (7.31 M allocations: 376.682 MiB, 4.47% gc time)

The last time is not really complete since the window starts rendering after about 7 seconds. In its core, Winston uses a Dict for configuration

https://github.com/JuliaGraphics/Winston.jl/blob/master/src/Winston.jl#L113

My hyothesis, that is not proven but your post seems to indicate that it might be true, is that the performance issues are due to the usage of Dicts. Maybe we could learn from that example, how either

  • Dicts can be accelerated, or
  • How such code can be refactored to run fast.

Try compiling just the dict portions to the sysimage and see what happens.

If memory serves, the top three inference times for Revise’s startup are all setindex! functions for different Dict types, which is why I chose that for the example in https://github.com/JuliaLang/julia/pull/31466.

And I agree with @ChrisRackauckas that certain programming patterns are unnecessarily hard on the compiler. Changing a Dict{AbstractFloat,AbstractString} to a Dict{Any,Any} is probably quite reasonable.

But in other ways, I think this is precisely the wrong time to be distorting your programming style in ways you might later regret to achieve faster startup. While faster compile/interpret performance will in aggregate be a really big job (indeed, its own research problem), areas like getting setindex! to precompile properly seem completely doable. My latest attempt to improve precompilation is Change precompilation format to be more amenable to copying by timholy · Pull Request #32705 · JuliaLang/julia · GitHub, which (as you’ll see from my comment) may not be in exactly the right direction but is attempting to address one of the bigger limitations. I’d guess that Jeff & Jameson haven’t yet been able to switch to making compile time their main priority, but once they do I suspect we’ll see a few gains fairly quickly (and the particular issue in 32705 seems quite “ripe” to me), and others will unfold over much longer time scales.

9 Likes

I want to believe Tim, but since compile time is a non-trivial problem, I have some doubts that there will be a solution soon. This is really not meant as a critique and I want that you prove me wrong. My hope would be that 1.4 (which I expect in summer 2020) contains improvements.

Yes, hoping for improvements in 1.4 (and further improvements in later releases) seems reasonable. But at least for your own personal use, I’d guess if you compile Julia yourself from master you might see some major benefits earlier than summer 2020.

2 Likes

Check out

It seems that the road is already paved with the new ORC jit.
You get concurrent compilation, object cache jit-dylib, the ability to delete compiled functions.

The only problem is the global method table a.k.a global multiple dispatch, which makes it very hard to cache compilation. Because as I pointed out in the past it is hard to prove that adding a module will not alter previously compiled code.

1 Like

Because as I pointed out in the past it is hard to prove that adding a module will not alter previously compiled code.

That’s what our backedges are for. It will always be possible to load one tiny thing and force recompilation of a huge amount of code. For example, loading a module that does this:

import Base: +
+(x::Int, y::Int) = 0   # surprise!

will invalidate any method that adds Ints, so future calls will have to compile everything they need from scratch. The bigger problem is indeed tricky, but questions like “can we at least cache more of the results of inference? will it help in some circumstances?” are certainly going to have affirmative answers.

2 Likes

Can Julia use the JIT concurrency and speculative JITing? That seems like it would solve a lot of the issues.

OT: Wasn’t actions like this - overwriting methods in other modules - the classical counterargument to method merging cross modules? I wasn’t aware that this is possible for Base, i always had the impression you can extend Base.

That’s what our backedges are for. It will always be possible to load one tiny thing and force recompilation of a huge amount of code.

If type piracy is disallowed, can one still cause invalidations? Would it be enough to forbid type piracy to be able to cache compiled code?

Looks like there were efforts to do “Speculative compilation support in LLVM ORC JIT Infrastructure” for Julia as Google Summer of Code 2019 project: New LLVM JIT Features - #5 by jpsamaroo

1 Like

10 posts were split to a new topic: Code isolation side discussion

Perhaps code isolation should be it’s own thread.

5 Likes

Done.

Yes. Julia performs an optimization in the case that there’s only one (or a couple, I think) methods to possibly call in the face of a type-instability, it’ll avoid doing the dynamic dispatch. Example:

julia> f(x) = 1
f (generic function with 1 method)

julia> g(x) = f(x[])*2
g (generic function with 1 method)

julia> @time g(Ref{Any}(1))
  0.007295 seconds (3.41 k allocations: 216.416 KiB)
2

julia> @time g(Ref{Any}(1))
  0.000015 seconds (5 allocations: 176 bytes)
2

The outer function g doesn’t know what it’ll get out of a Ref{Any}, so that’s a type instability, but it knows that there’s only one possible method for f, so it can avoid the expensive consequence of a type instability — the dynamic dispatch. Even better, it’s “fixed” our type instability because it knows that f will only ever return the number 1!

julia> @code_typed g(Ref{Any}(1))
CodeInfo(
1 ─     Base.getfield(x, :x)::Any
└──     return 2
) => Int64

So this is now compiled and happily marching along. Then some package adds another method — note that the argument could be a type it defines itself; definitely not piracy. It’s a method that never gets called, and yet it forces the recompilation of g… and of course causes our previous example to become somewhat type-unstable again. Add enough other methods and eventually Julia will give up on the small unions and just return Any:

julia> struct TT end

julia> f(::TT) = 3//2
f (generic function with 2 methods)

julia> @time g(Ref{Any}(1))
  0.048927 seconds (137.27 k allocations: 7.199 MiB)
2

julia> @time g(Ref{Any}(1))
  0.000025 seconds (5 allocations: 176 bytes)
2

julia> @code_typed g(Ref{Any}(1))
CodeInfo(
1 ── %1  = Base.getfield(x, :x)::Any
... # so much code ...
18 ┄ %38 = φ (#5 => %15, #16 => %33)::Union{Rational{Int64}, Int64}
└───       return %38
) => Union{Rational{Int64}, Int64}
10 Likes

That’s really informative @mbauman, many thanks. Also, it’s really important to learn this type of compiler details to develop a sense of where performance opportunities lie. For me the compiler is still a magic black box… A box of black magic, actually :-D.