Slow inplace sorting of a view

[Arkoniak]

Related to this discourse thread: https://discourse.julialang.org/t/in-place-sorting-for-views/56194

using BenchmarkTools
using StableRNGs

rng = StableRNG(2021);
v = rand(rng, 1000);
v2 = rand(rng, 2000);

v2[500:1499] .= v;

In Julia 1.7.0-DEV

julia> @btime sort!(vv) setup = (vv = deepcopy($v)) evals = 1;
  12.844 μs (0 allocations: 0 bytes)

julia> @btime sort!(vv) setup = (vv1 = deepcopy($v2); vv = @view vv1[500:1499]) evals = 1;
  23.333 μs (0 allocations: 0 bytes)

julia> versioninfo()
Julia Version 1.7.0-DEV.538
Commit 85354cf8ef (2021-02-15 11:47 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, skylake)
Environment:
  JULIA_NUM_THREADS = 4

In julia 1.5.3

julia> @btime sort!(vv) setup = (vv = deepcopy($v)) evals = 1;
  16.985 μs (0 allocations: 0 bytes)

julia> @btime sort!(vv) setup = (vv1 = deepcopy($v2); vv = @view vv1[500:1499]) evals = 1;
  11.745 μs (0 allocations: 0 bytes)

julia> versioninfo()
Julia Version 1.5.3
Commit 788b2c77c1 (2020-11-09 13:37 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, skylake)
Environment:
  JULIA_NUM_THREADS = 4

Julia 1.4.1

julia> @btime sort!(vv) setup = (vv = deepcopy($v)) evals = 1;
  15.678 μs (0 allocations: 0 bytes)

julia> @btime sort!(vv) setup = (vv1 = deepcopy($v2); vv = @view vv1[500:1499]) evals = 1;
  13.833 μs (0 allocations: 0 bytes)

julia> versioninfo()
Julia Version 1.4.1
Commit 381693d3df* (2020-04-14 17:20 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-8.0.1 (ORCJIT, skylake)
Environment:
  JULIA_NUM_THREADS = 4

As mentioned in discourse topic, if I create custom type, and add @inbounds to setindex/getindex, then timings became the same. Just a guess, but can it be related to #39308?

[KristofferC]

I tried on 1.6-RC1 and the result was:

  11.584 μs (0 allocations: 0 bytes)

for the view while on 1.7 it is

 18.640 μs (0 allocations: 0 bytes)

so it seems the regression is quite new.

Would be good with a bisection.

[Arkoniak]

Good, I'll try to find the breaking point then and report it.

[Arkoniak]

Well, I am sorry, but it seems that I have to ask you to help me to help you :-) I've tried doing bisection a couple of times and it left me puzzled. First of all, BenchmarkTools for some reason provide unstable results, i.e. process was like this:

1. Switch to a commit
2. Rebuild julia with make clean && make -C deps uninstall && make
3. Run julia and execute commands that I wrote at the beginning of this issue.

Now, 3 step was strange, because I can get one result, exit julia, run it again and get totally different result. So at some point I was kind of afraid, that precompilation may create artifacts which somehow interfere results of running commands between different builds of Julia.

So, I am 99% sure, that the whole process was corrupted, but bisection lead me to an innocent looking commit: 5e048f3

Just to confirm, I've made two separate builds of Julia in different directories, and the output looks like this

➜  julia_bisect git:(5e048f3e53) ./julia ../view_test2.jl
(12.687999999999999, 23.03)

➜  julia_bisect2 git:(057c316537) ./julia ../view_test2.jl
(12.465, 15.466999999999999)

Here 5e048f3e53 and 057c316537 are two close commits. File view_test2.jl can be found here: https://gist.github.com/Arkoniak/6f8399522fc0d866cf5a400961ff5810 (I removed all dependencies from BenchmarkTools.jl and StableRNGs.jl). Data for the file can be found in https://gist.github.com/Arkoniak/3f9eec7803a60942188acf6d6a4010ff or it can be generated with the following script

using StableRNGs

rng = StableRNG(2021)
v = rand(1000)
open("data.txt", "w") do f
    for x in v
        println(f, x)
    end
end

So, I have the following questions:

1. Can anyone verify this commit?
2. How should I rebuild Julia properly? Maybe some special directories should be cleaned? Unfortunately, I cannot spin new virtual machine, because I do not know how.
3. Is it legit to run julia after rebuild? Or maybe I should pass some special keys, like -O2, --project=. or something else to exclude interference with other julia versions installed on my machine?

[Arkoniak]

Interestingly enough, there is optimization dependence
Good commit:

➜  julia_bisect2 git:(057c316537) ./julia ../view_test2.jl
(12.377, 15.126999999999999)

➜  julia_bisect2 git:(057c316537) ./julia -O 2 ../view_test2.jl
(12.507000000000001, 15.293000000000001)

➜  julia_bisect2 git:(057c316537) ./julia -O 3 ../view_test2.jl
(12.854, 22.282)

Bad commit:

➜  julia_bisect git:(5e048f3e53) ./julia  ../view_test2.jl
(12.375, 22.448)

➜  julia_bisect git:(5e048f3e53) ./julia -O 2 ../view_test2.jl
(12.043, 22.66)

➜  julia_bisect git:(5e048f3e53) ./julia -O 3 ../view_test2.jl
(12.846, 15.334)

[StefanKarpinski]

Bump. Seems like a lot of work was done here... what does it take to finish this up?

[nalimilan]

I confirm the performance difference on 1.6.3, but on 1.7.0-rc2 it has almost vanished:

julia> @btime sort!(vv) setup = (vv = deepcopy($v)) evals = 1;
  10.210 μs (0 allocations: 0 bytes)

julia> @btime sort!(vv) setup = (vv1 = deepcopy($v2); vv = @view vv1[500:1499]) evals = 1;
  12.870 μs (0 allocations: 0 bytes)

And it's even smaller on master:

julia> @btime sort!(vv) setup = (vv = deepcopy($v)) evals = 1;
  13.161 μs (0 allocations: 0 bytes)

julia> @btime sort!(vv) setup = (vv1 = deepcopy($v2); vv = @view vv1[500:1499]) evals = 1;
  13.622 μs (0 allocations: 0 bytes)