Sortperm is slow (then also sortslices and sortperm); Julia's oldest performance issue(s)

General Usage Performance
1

Continuing the discussion from 10x faster sortperm():

Sortperm is at least 77.6% slower in Julia than in Python/NumPy.

Note, this is known, the next oldest performance issue (and third oldest issue from 2013):

[It’s similar in speed for Float64 and Int64 as expected, but it doesn’t go much down with smaller types down to Int8 (nor much with NumPy), a bit surprising, because of radix sort?]

We are not (no longer?) “3x slower for sortperm” (as once for MATLAB in 2013, but I didn’t test it, assume it similar speed to NumPy).

I thought AI might be able to help (I could share a link to my answer), even fix if someone has access to more powerful AI than mine…

AI though SortingLab would help but it didn’t maybe in the past:

using BenchmarkTools
using SortingLab

# Generate 10 million random Float64 values
const data = rand(10_000_000)

println("--- Base Julia sortperm ---")
@btime sortperm($data);

println("--- SortingLab fsortperm (Fast Radix) ---")
@btime fsortperm($data);


julia> @btime sortperm($data);
  1.980 s (6 allocations: 152.59 MiB)

--- SortingLab fsortperm (Fast Radix) ---
  1.984 s (6 allocations: 152.59 MiB

vs. Python:

import numpy as np
import timeit

# Generate 10 million random Float64 values
data = np.random.rand(10000000)

# Benchmark NumPy's argsort (defaults to Quicksort, but supports Radix/Mergesort)
t = timeit.timeit(lambda: np.argsort(data), number=3)
print(f"NumPy argsort average time: {t / 3:.4f} seconds")

NumPy argsort average time: 1.1151 seconds
NumPy argsort average time: 1.0962 seconds

Interestingly with as many integers (this time tested with MORE load, i.e. after starting Firefox again):

rng = np.random.default_rng()
array_1d = rng.integers(0, 100, size=10000_000)

NumPy argsort average time: 0.5763 seconds

julia> @btime sortperm($data);
1.903 s (6 allocations: 152.59 MiB)

julia> @btime fsortperm($data);
1.911 s (6 allocations: 152.59 MiB)


I haven't tested:
https://github.com/LSchwerdt/SimultaneousSortperm.jl/pull/3

The oldest (if you want to look at or "fix" the oldest and only other 3-digit performance issue):
https://github.com/JuliaLang/julia/issues/130#issuecomment-1123823801