Performance regression from Julia 1.6.3 and 1.8.0-DEV

[goerch]

My benchmarks show the following numbers: on Julia 1.6.3

100000 elements
  AVLTrees.AVLSet                          23.564 ms (200002 allocations: 9.16 MiB)
1000 elements
  AVLTrees.AVLSet                          179.500 μs (2002 allocations: 93.78 KiB)
10 elements
  AVLTrees.AVLSet                          1.790 μs (22 allocations: 992 bytes)

and on Julia 1.8.0-DEV

100000 elements
  AVLTrees.AVLSet                          244.832 ms (200002 allocations: 9.16 MiB)
1000 elements
  AVLTrees.AVLSet                          2.013 ms (2002 allocations: 93.78 KiB)
10 elements
  AVLTrees.AVLSet                          9.033 μs (22 allocations: 992 bytes)

[krynju]

Interesting, I'll try running that on my pc on these two versions later
Can you print the versioninfo() on both?

[goerch]

Profiler indicates the problem lies still in rotate_*. Tested versions:

Julia Version 1.6.3
Commit ae8452a9e0 (2021-09-23 17:34 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, skylake)

Works fine.

Julia Version 1.7.0-rc1
Commit 9eade6195e (2021-09-12 06:45 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, skylake)

Problem occurs.

Julia Version 1.8.0-DEV.780
Commit 05515f4a72 (2021-10-20 12:57 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, skylake)

Problem occurs, too. I have to use 1.7.0-rc1 to profile, because Juno profiling seems broken on nightly.

[goerch]

Here is an image from 1.7.0 profiling:

I'm currently using dispatch like

left(tree::Nothing) = @assert false
function left(tree::Node{T}) where T
    tree.left
end

left!(tree::Nothing, left::Tree{T}) where T = @assert false
function left!(tree::Node{T}, left::Tree{T}) where T
    tree.left = left
end

to avoid that kind of problem, but I don't know if this is the appropriate way to do it.

[krynju]

yeah, reproducible on my end
i'll try to address this this week

julia> @btime testbase5(10)
  834.247 ns (21 allocations: 976 bytes)

julia> @btime testbase5(1000)
  94.800 μs (2001 allocations: 93.77 KiB)

julia> @btime testbase5(100000)
  16.380 ms (200001 allocations: 9.16 MiB)

julia> versioninfo()
Julia Version 1.6.3
Commit ae8452a9e0 (2021-09-23 17:34 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: AMD Ryzen 7 5800X 8-Core Processor
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, generic)

julia> @btime testbase5(10)
  7.000 μs (21 allocations: 976 bytes)

julia> @btime testbase5(1000)
  1.443 ms (2001 allocations: 93.77 KiB)

julia> @btime testbase5(100000)
  157.969 ms (200001 allocations: 9.16 MiB)

julia> versioninfo()
Julia Version 1.8.0-DEV.746
Commit e09a6e4d78* (2021-10-14 19:27 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: AMD Ryzen 7 5800X 8-Core Processor
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, znver3)

[goerch]

Hm, I'm not sure. This could be a breaking change between 1.6.3 and 1.7.0. OTOH probably pretty difficult to isolate?

[krynju]

Maybe, we'll see. If that's julia related I'll just open an issue in julia
your benchmarks covers all ops, any idea which one is specifically the culprit? Or both delete and insert are? (lookup is super quick, so i doubt it's that)

[goerch]

Just checked the method of #18 (comment). Works for AVLTrees, too. Will try my first pull request(?).

[krynju]

i thought of dispatching on that explicitly, adding these left!/other related methods will be a big change

I would try something like this first instead of the thing you're proposing, should probably help in this instability:

function rotate_left(t::AVLTree{K,D}, x::Node{K,D}, x_right::Node{K,D}) where {K,D}

to =>

function rotate_left(t::AVLTree{K,D}, x::Node{K,D}, x_right::Node{K,D}, x_right_left) where {K,D}

and the right one same idea

That will create two signatures, one where that last arg is nothing and other one where it's a Node and should be stable like that

Let me know if you'll be doing this as a PR, if not I can tackle it later this week

[goerch]

There might be an interesting generalization of the accessor trick. Something along the lines of

_getproperty(x::Nothing, f) = @assert false
_getproperty(x::Node{K,D}, f) where {K,D} = getfield(x, f)
Base.getproperty(x::Union{Nothing, Node{K,D}}, f::Symbol) where {K,D} =
    _getproperty(x, f)

_setproperty!(x::Nothing, f, v) = @assert false
_setproperty!(x::Node{K,D}, f, v) where {K,D} =
    # setfield!(x, f, convert(fieldtype(typeof(x), f), v))
    setfield!(x, f, v)
_setproperty!(x::Node{K,D}, f, ::Nothing) where {K,D} =
    setfield!(x, f, nothing)
_setproperty!(x::Node{K,D}, f, v::Node{K,D}) where {K,D} =
    setfield!(x, f, v)
Base.setproperty!(x::Union{Nothing, Node{K,D}}, f::Symbol, v) where {K,D} =
    _setproperty!(x, f, v)
Base.setproperty!(x::Union{Nothing, Node{K,D}}, f::Symbol, v::Union{Nothing, Node{K,D}}) where {K,D} =
    _setproperty!(x, f, v)

This works for me with AVLTrees 0.32 on Julia 1.7.0-rc1. Only drawback is that conversions for the bf-arithmetic have to be explicit (reactivating the commented line above, which is used by Base.getproperty leads to dynamic dispatch).

Benchmark results:

100000 elements
  AVLTrees.AVLSet                          33.687 ms (200002 allocations: 9.16 MiB)
1000 elements
  AVLTrees.AVLSet                          240.900 μs (2002 allocations: 93.78 KiB)
10 elements
  AVLTrees.AVLSet                          1.310 μs (22 allocations: 992 bytes)

[goerch]

Patching 0.34 was even easier (no conversions for bf-arithmetic neccessary). Benchmark results:

100000 elements
  AVLTrees.AVLSet                          24.722 ms (200002 allocations: 9.16 MiB)
1000 elements
  AVLTrees.AVLSet                          179.300 μs (2002 allocations: 93.78 KiB)
10 elements
  AVLTrees.AVLSet                          805.747 ns (22 allocations: 992 bytes)

[krynju]

Thanks! I'll try to review the PR either today or sometime during the weekend.
I want to check in Cthulhu what's the root cause of this and how the PR affects the code generated

[goerch]

Please see: https://discourse.julialang.org/t/dynamic-dispatch-with-union-nothing/70174/5

[krynju]

Related julia issue JuliaLang/julia#42754