Regression in allocations of partialsort!

[Seelengrab]

I found this while starting to fall into the pit of decemberly despair that is advent of code:

1.6.7:

julia> @benchmark partialsort!(data, 1:3; rev=true) setup=(data=rand(10_000)) evals=1
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):   26.180 μs … 283.649 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     121.591 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   120.735 μs ±  37.872 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

                    ▁▃▂▃▅▅▄▆▆▇▆█▇█████▇▅▇▆▇▅▅▂▂▁▁                
  ▁▂▂▃▃▄▄▄▄▆▆▆▇█▇▇███████████████████████████████▇▇▇▆▅▄▄▄▃▂▃▂▂▂ ▆
  26.2 μs          Histogram: frequency by time          210 μs <

 Memory estimate: 80 bytes, allocs estimate: 2.

julia> versioninfo()
Julia Version 1.6.7
Commit 3b76b25b64 (2022-07-19 15:11 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, skylake)
Environment:
  JULIA_NUM_THREADS = 4

1.10/recent-ish master:

julia> @benchmark partialsort!(data, 1:3; rev=true) setup=(data=rand(10_000)) evals=1
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  31.265 μs … 717.012 μs  ┊ GC (min … max): 0.00% … 81.97%
 Time  (median):     48.968 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   53.924 μs ±  35.874 μs  ┊ GC (mean ± σ):  3.42% ±  5.12%

     ▁▄▅▅▇█▆▇▇▅▆▅▅▃▃▃▂                                          
  ▂▄▇█████████████████████▇▇▆▆▅▅▄▄▃▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▁▂▁▁▁▁▁▁▁▁▁ ▄
  31.3 μs         Histogram: frequency by time          106 μs <

 Memory estimate: 156.34 KiB, allocs estimate: 4.

julia> versioninfo()
Julia Version 1.10.0-DEV.6
Commit 4cf077cd9a (2022-11-14 21:07 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: 4 × Intel(R) Core(TM) i7-6600U CPU @ 2.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, skylake)
  Threads: 4 on 4 virtual cores
Environment:
  JULIA_NUM_THREADS = 4

The speedup in the average case is nice, but can it be achieved without allocating almost twice the memory that already exists? I think this may be due to the work-space work done recently, so may be related to #47715 (cc @LilithHafner). partialsort! doesn't take an algorithm keyword, so there's no workaround for now, I don't think.

[LilithHafner]

Like #47715, this is introduced in #45222 where we weighed runtime over allocations. I'll fix it using @StefanKarpinski's solution posted here once #47383 merges to avoid merge conflicts.

We'll probably add an alg keyword argument to PartialQuickSort to support this, but have to consider any potential ramifications on #47587 and related changes which may address Julia's largest and older sorting performance problem: #939.

[LilithHafner]

The speedup in the average case is nice, but can it be achieved without allocating almost twice the memory that already exists?

I imagine it is possible to get most of that speedup with only a small amount of extra allocations, but that won't make it into 1.9. You'll have to choose between the old performance and the new (faster & more memory). Out of curiosity, in your use case, will you prefer the performance characteristics of the old quicksort or the new one?

[Seelengrab]

Well for the toy use case of advent of code, faster is always better 😄 Having a choice of algorithm (and/or being able to pass in/preallocate the buffer used for sorting) would be plenty for my use case.

[LilithHafner]

partialsort!(my_indices, my_vector, alg=QuickSort) should preserve old performance characteristics.