Allocation when sorting a view

General Usage Performance
1

Just reading through “In place sorting for views” and cannot wrap my head around the following allocations in my case:

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:

@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?

2

Still experiencing problems with this? Anyone an idea?

3

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:

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?

4

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:

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:

 131.689 ns (8 allocations: 384 bytes)
5

So my guess would be that there might be a bug somewhere:

x = [2.0,1.0,10.0,15.0,20.0]

@btime sort!(view($x,2:4))
26.131 ns (0 allocations: 0 bytes)
2 Likes
6

Oeh good find! … it indeed also for me works with Float64 but not with Int64:

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)
1 Like
7

Submitted an issue for this

1 Like
8

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!

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) is faster than generic sort algorithms, especially on large vectors, by enough to make up for the extra allocations.

1 Like
9

I don’t it’s extrema causing the observed allocs?

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

10

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.

11

Yeah, it seems that when sorting parts of the same vector casting to Float first and sorting is faster than without casting:

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)
12

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.

13

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.

14

I think you are right, if we take the sort from here and implement it, we have 0 allocs and are faster, at least for this case:

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
15

Apparently, this got fixed in 1.9-DEV: Unexpected allocation in sort! of Int64 view · Issue #47152 · JuliaLang/julia · GitHub

1 Like
16

This is fixed in Julia 1.9. As a workaround, you can use sort!(x; alg=InsertionSort).

1 Like
17

For me, on 1.8-rc3, the workaround also allocs:

x = [2,1,10,15,20]
@btime sort!(view($x,2:4), alg=InsertionSort)
31.403 ns (2 allocations: 96 bytes)