# Why does sortperm! allocate here?
**URL:** https://discourse.julialang.org/t/why-does-sortperm-allocate-here/112028
**Category:** Performance
**Tags:** sortperm, memory-allocation
**Created:** [March 24, 2024, 12:02am UTC](https://discourse.julialang.org/t/why-does-sortperm-allocate-here/112028 "2024-03-24T00:02:52Z")
**Posts on this page:** 5
**Page:** 1
### Author:  [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)
#### Post date: [March 24, 2024, 12:02am UTC](https://discourse.julialang.org/t/why-does-sortperm-allocate-here/112028/1 "2024-03-24T00:02:52Z")
Hello!
I think I am missing something really simple, I just don’t get why allocations occur, when I have preallocated index array.
```julia
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
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [March 24, 2024, 1:32am UTC](https://discourse.julialang.org/t/why-does-sortperm-allocate-here/112028/2 "2024-03-24T01:32:05Z")
`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:
```julia
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)
---
### Author:  [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)
#### Post date: [March 24, 2024, 11:20am UTC](https://discourse.julialang.org/t/why-does-sortperm-allocate-here/112028/3 "2024-03-24T11:20:45Z")
Amazing Dan, thank you!
I confirm it does not allocate any more.
I would argue that the documentation for `sortperm!` is lacking.
```julia
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
---
### Author:  [@Dan](https://discourse.julialang.org/u/Dan)
#### Post date: [March 24, 2024, 1:32pm UTC](https://discourse.julialang.org/t/why-does-sortperm-allocate-here/112028/4 "2024-03-24T13:32:04Z")
> [@Ahmed\_Salih](#):
>
> I would argue that the documentation for `sortperm!` is lacking.
Yeah. Documenting this sounds like a good idea. You are right about the intuitive assumption regarding function with `!` at end.
---
### Author:  [@Ahmed\_Salih](https://discourse.julialang.org/u/Ahmed_Salih)
#### Post date: [March 24, 2024, 1:47pm UTC](https://discourse.julialang.org/t/why-does-sortperm-allocate-here/112028/5 "2024-03-24T13:47:39Z")
Filed issue: [Missing documentation: sortperm! is not truly non-allocating unless scratchspace is provided · Issue #53834 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/53834)