### Author:  [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)
#### Post date: [August 30, 2022, 3:57pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/1 "2022-08-30T15:57:01Z")
Just reading through “[In place sorting for views](https://discourse.julialang.org/t/in-place-sorting-for-views/56194)” and cannot wrap my head around the following allocations in my case:
```julia
x = [2,1,10,15,20]
@btime sort!(view($x, 2:4))
53.308 ns (2 allocations: 96 bytes)
```
To check I also tried the following, which looks fine:
```julia
@btime sort!($x)
29.256 ns (0 allocations: 0 bytes)
@btime view($x, 2:4)
2.933 ns (0 allocations: 0 bytes)
```
I have allocations for the in-place view sort on both `1.7.3` and `1.8.0`. I’m surprised this didn’t work, so I’m probably missing something stupid here?
---
### Author:  [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)
#### Post date: [October 13, 2022, 10:05am UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/2 "2022-10-13T10:05:58Z")
Still experiencing problems with this? Anyone an idea?
---
### Author:  [@Palli](https://discourse.julialang.org/u/Palli)
#### Post date: [October 13, 2022, 11:12am UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/3 "2022-10-13T11:12:11Z")
It is weird with sort!(x) going to the same function as sort!(view(x, 2:4)) and still view alone not allocation. So it reminded me of another issue, that a debugged, and showed to be very weird:
>
>
> On Julia 1.8.1 I noticed the following:
> \`\`\`julia
> function manymul(N, C, A, B a…lpha, beta)
> for i in 1:N
> mul!(C, A, B, alpha, beta)
> #BLAS.gemm!('N', 'N', alpha, A, B, beta, C) # eliminates allocations
> C, A = A, C
> end
> C
> end
>
> D = 16
> A = randn(D, D)
> B = randn(D, D)
> C = zero(A)
>
> N = 100000
> @time manymul(N, C, A, B, 1.0, 0.5) #allocates N times (32 bytes each) with \`mul!()\`, 0 times with \`gemm!()\`
> \`\`\`
> Cthulhu suggests this is due to runtime dispatch related to \`MulAdd()\`. This can impact performance of e.g. ODE solving involving \`mul!()\` for small matrix sizes. The example above takes around 10% longer with \`mul!()\` vs. \`gemm!()\`, according to benchmarktools (single-threaded BLAS).
>
> Is this known/intended?
>
> My \`versioninfo()\`:
> \`\`\`
> Julia Version 1.8.1
> Commit afb6c60d69a (2022-09-06 15:09 UTC)
> Platform Info:
> OS: macOS (x86\_64-apple-darwin21.4.0)
> CPU: 12 × Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
> WORD\_SIZE: 64
> LIBM: libopenlibm
> LLVM: libLLVM-13.0.1 (ORCJIT, skylake)
> Threads: 1 on 6 virtual cores
> Environment:
> JULIA\_EDITOR = code
> JULIA\_NUM\_THREADS =
> JULIA\_PKG\_USE\_CLI\_GIT = true
> \`\`\`
So I suggest you may file an issue on this, but is this a problem in practice? We often want to eliminate allocations entirely, a worth goal, and sometimes (e.g. for real-time) needed, but here since it’s just 2, not growing, maybe not a huge issue for you?
---
### Author:  [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)
#### Post date: [October 13, 2022, 11:22am UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/4 "2022-10-13T11:22:53Z")
Thanks for the reply @Palli !
It indeed wouldn’t be a problem if I had to do this once. In my case I have a big array (millions of elements) and have to sort specific parts of it (in-place ideally). Since this will happen in a loop the allocs will build up quickly. Something like:
```julia
using BenchmarkTools
function test(arr::Vector{Int64}, cuts::Vector{UnitRange{Int64}})
for cut in cuts
sort!(view(arr, cut))
end
end
function main()
data = reverse(collect(1:20))
cut_at = [1:2, 4:8, 11:14, 16:18]
@btime test($data, $cut_at)
end
main()
```
Giving:
```julia
131.689 ns (8 allocations: 384 bytes)
```
---
### Author:  [@mkoculak](https://discourse.julialang.org/u/mkoculak)
#### Post date: [October 13, 2022, 11:36am UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/5 "2022-10-13T11:36:39Z")
So my guess would be that there might be a bug somewhere:
```julia
x = [2.0,1.0,10.0,15.0,20.0]
@btime sort!(view($x,2:4))
26.131 ns (0 allocations: 0 bytes)
```
---
### Author:  [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)
#### Post date: [October 13, 2022, 12:11pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/6 "2022-10-13T12:11:34Z")
Oeh good find! … it indeed also for me works with `Float64` but not with `Int64`:
```julia
x = [2,1,10,15,20]
y = [2.0,1.0,10.0,15.0,20.0]
@btime sort!(view($x,2:4))
33.898 ns (2 allocations: 96 bytes)
@btime sort!(view($y,2:4))
19.645 ns (0 allocations: 0 bytes)
```
---
### Author:  [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)
#### Post date: [October 13, 2022, 12:26pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/7 "2022-10-13T12:26:15Z")
Submitted [an issue](https://github.com/JuliaLang/julia/issues/47152) for this
---
### Author:  [@adienes](https://discourse.julialang.org/u/adienes)
#### Post date: [October 13, 2022, 12:32pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/8 "2022-10-13T12:32:18Z")
Look like there is a special sorting function for Int64—could these two allocations be caused by `min, max = extrema(v)` on line 714 of [the source for sort!](https://github.com/JuliaLang/julia/blob/36034abf26062acad4af9dcec7c4fc53b260dbb4/base/sort.jl#L664-L703)
Looks like line 729 could actually allocate quite a lot more… that being said it’s not my impression that the `sort!` promises to be non-allocating, only that it promises to mutate the input in-place. Likely this integer sort optimization ([Counting sort](https://en.wikipedia.org/wiki/Counting_sort)) is faster than generic sort algorithms, especially on large vectors, by enough to make up for the extra allocations.
---
### Author:  [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)
#### Post date: [October 13, 2022, 12:37pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/9 "2022-10-13T12:37:28Z")
I don’t it’s `extrema` causing the observed allocs?
```julia
x = [2,1,10,15,20]
@btime a,b = extrema($x)
3.432 ns (0 allocations: 0 bytes)
```
Will look at 729, what is reached when
---
### Author:  [@lmiq](https://discourse.julialang.org/u/lmiq)
#### Post date: [October 13, 2022, 12:54pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/10 "2022-10-13T12:54:52Z")
As pointed above, it may be that those allocations are worthwhile, because the sorting algorithm is faster. You should benchmark that with the actual size of your arrays and views to see. If you are sorting small arrays of Ints, you may need some customized sorting method for optimal efficiency.
---
### Author:  [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)
#### Post date: [October 13, 2022, 1:07pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/11 "2022-10-13T13:07:28Z")
Yeah, it seems that when sorting parts of the same vector casting to Float first and sorting is faster than without casting:
```julia
function test(arr::AbstractVector, cuts::Vector{UnitRange{Int64}})
for cut in cuts
sort!(view(arr, cut))
end
end
data = reverse(collect(1:20))
cut_at = [1:2, 4:8, 11:14, 16:18]
@btime test($data, $cut_at)
132.309 ns (8 allocations: 384 bytes)
@btime test(Float64.($data), $cut_at)
102.239 ns (1 allocation: 224 bytes)
```
---
### Author:  [@Palli](https://discourse.julialang.org/u/Palli)
#### Post date: [October 13, 2022, 1:09pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/12 "2022-10-13T13:09:58Z")
> [@lmiq](#):
>
> it may be that those allocations are worthwhile, because the sorting algorithm is faster.
I doubt that. I mean the faster alg. may be worthwhile with them, but even better without. It seems that should always be possible for views.
---
### Author:  [@lmiq](https://discourse.julialang.org/u/lmiq)
#### Post date: [October 13, 2022, 1:23pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/13 "2022-10-13T13:23:22Z")
Yeah, I missed the point that the algorithm for sorting integers _does not_ allocate for the full array. It shouldn’t either for the view.
---
### Author:  [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)
#### Post date: [October 13, 2022, 1:23pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/14 "2022-10-13T13:23:27Z")
I think you are right, if we take the sort from [here](https://github.com/JuliaLang/julia/blob/36034abf26062acad4af9dcec7c4fc53b260dbb4/base/sort.jl#L498) and implement it, we have 0 allocs and are faster, at least for this case:
```julia
function s!(v::AbstractVector)
# function sort!(v::AbstractVector, lo::Integer, hi::Integer, ::InsertionSortAlg, o::Ordering)
lo, hi = extrema(v)
lo_plus_1 = (lo + 1)::Integer
@inbounds for i = lo_plus_1:hi
j = i
x = v[i]
while j > lo
y = v[j-1]
if !( x < y )
break
end
v[j] = y
j -= 1
end
v[j] = x
end
return v
end
function ins_sort(arr::AbstractVector, cuts::Vector{UnitRange{Int64}})
for cut in cuts
s!(view(arr, cut))
end
end
function base_sort(arr::AbstractVector, cuts::Vector{UnitRange{Int64}})
for cut in cuts
sort!(view(arr, cut))
end
end
data = reverse(collect(1:20))
cut_at = [1:2, 4:8, 11:14, 16:18]
@btime ins_sort($data, $cut_at)
# 34.997 ns (0 allocations: 0 bytes)
@btime base_sort($data, $cut_at)
# 134.454 ns (8 allocations: 384 bytes)
ins_sort(data, cut_at) == base_sort(data, cut_at)
# true
```
---
### Author:  [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)
#### Post date: [October 13, 2022, 1:26pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/15 "2022-10-13T13:26:03Z")
Apparently, this got fixed in 1.9-DEV: [Unexpected allocation in sort! of Int64 view · Issue #47152 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/47152#issuecomment-1277609906)
---
### Author:  [@Lilith](https://discourse.julialang.org/u/Lilith)
#### Post date: [October 13, 2022, 1:26pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/16 "2022-10-13T13:26:53Z")
This is fixed in Julia 1.9. As a workaround, you can use `sort!(x; alg=InsertionSort)`.
---
### Author:  [@CodeGodz](https://discourse.julialang.org/u/CodeGodz)
#### Post date: [October 13, 2022, 1:32pm UTC](https://discourse.julialang.org/t/allocation-when-sorting-a-view/86558/17 "2022-10-13T13:32:17Z")
For me, on `1.8-rc3`, the workaround also allocs:
```julia
x = [2,1,10,15,20]
@btime sort!(view($x,2:4), alg=InsertionSort)
31.403 ns (2 allocations: 96 bytes)
```