Why does sortperm! allocate here?

General Usage Performance
,
2

sortperm! (and other sorting functions) use a “scratch” space for efficiency. If not given a pre-allocated one, they will allocate a new one.

To do the pre-allocation:

function main()
    Cartesians    = Vector{CartesianIndex{2}}(undef, 10000)
    SortedIndices = collect(LinearIndices(Cartesians))
    _, t = Base.Sort.make_scratch(nothing, eltype(SortedIndices), length(Cartesians))

    # Fill the array with random CartesianIndex{2} values
    for i in 1:100
        # Assuming you want indices in the range 1:10 for both dimensions
        Cartesians[i] = CartesianIndex(rand(1:10), rand(1:10))
    end

    for iter = 1:5
        b = @allocated sortperm!(SortedIndices, Cartesians; scratch=t)
        println("Iteration ", iter, " : ", b , " allocated bytes")
    end
end

(the above returns 0 allocated memory for each iter on my machine)

4 Likes