# Why does sortperm! allocate here?

Hello!

I think I am missing something really simple, I just don’t get why allocations occur, when I have preallocated index array.

``````function main()
Cartesians    = Vector{CartesianIndex{2}}(undef, 100)
SortedIndices = collect(LinearIndices(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)
println("Iteration ", iter, " : ", b , " allocated bytes")
end
end

main()

Iteration 1 : 896 allocated bytes
Iteration 2 : 896 allocated bytes
Iteration 3 : 896 allocated bytes
Iteration 4 : 896 allocated bytes
Iteration 5 : 896 allocated bytes
``````

Could anyone explain it to me?

Kind regards

`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

Amazing Dan, thank you!

I confirm it does not allocate any more.

I would argue that the documentation for `sortperm!` is lacking.

``````help?> sortperm!
search: sortperm! partialsortperm! sortperm partialsortperm

sortperm!(ix, A; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, [dims::Integer])

Like sortperm, but accepts a preallocated index vector or array ix with the same axes as A. ix is initialized to contain the values LinearIndices(A).

│ Warning
│
│  Behavior can be unexpected when any mutated argument shares memory with any other argument.

│ Julia 1.9
│
│  The method accepting dims requires at least Julia 1.9.

Examples
≡≡≡≡≡≡≡≡
``````

Do you think it is worth opening an issue on Github for? For me before this I’ve naturally associated any function which is in-place `!` to also be allocation free, while I do admit that this does not have to be the case, I believe most have this default expectation?

Kind regards

1 Like

Yeah. Documenting this sounds like a good idea. You are right about the intuitive assumption regarding function with `!` at end.

1 Like
2 Likes