Vector prepend! allocates when there's capacity

[dpinol]

#59717 fixed prepend! for small vectors, but the problem still persists in some cases:

1) First insertion allocates in Vector's with capacity 3 or smaller

using Test
function tinyVectorAlwaysAllocates()
    sut = Vector{Int}(undef, 3)
    empty!(sut)

    @test (@allocations(insert!(sut, 1, 1))) == 0
    @test length(sut.ref.mem) == 3
end
tinyVectorAlwaysAllocates()

Test Failed at REPL[11]:5
  Expression: #= REPL[11]:5 =# @allocations(insert!(sut, 1, 1)) == 0
   Evaluated: 1 == 0

2) Fourth insertion allocates in Vectorwith capacity 5

using Test
function fourthInsertReallocates()
    sut = Vector{Int}(undef, 5)
    empty!(sut)

    for i in 1:4
        @test (@allocations(insert!(sut, 1, i))) == 0
    end
    @test length(sut.ref.mem) == 5
end
fourthInsertReallocates()

Test Failed at REPL[8]:6
  Expression: #= REPL[8]:6 =# @allocations(insert!(sut, 1, i)) == 0
   Evaluated: 1 == 0

3) Suggestion for test

In https://github.com/JuliaLang/julia/blob/master/test/arrayops.jl#L533 I suggest checking the lack of allocations with @test (@allocations(insert!(sut, 1, 1))) == 0 instead of with @test length(v.ref.mem) == 5, since the test as it is would fail to detect the allocation if capacity was 3 instead of 5.

[vtjnash]

No, this is already correct. Having "capacity" is not sufficient nor desirable of a characteristic, unless there is enough capacity to work with the correct big-O complexity.

[dpinol]

@vtjnash thank you for the quick reply, but I don't get what you mean.
Why recreate the Memory if there's enough capacity to shift the data while keeping the same big-O complexity?

[oscardssmith]

The problem is that shifting data is O(n), so we only want to do so when the shift leaves a proportional amount of free space at both ends (since we really don't want to shift all the data and then have to resize shortly after anyway).

[dpinol]

The problem is that shifting data is O(n), so we only want to do so when the shift leaves a proportional amount of free space at both ends (since we really don't want to shift all the data and then have to resize shortly after anyway).

Thanks, but in the first case, there's nothing to shift because the vector is empty. It makes absolutely no sense to reallocate the memory, specially when the new one has the same length.

    sut = Vector{Int}(undef, 3)
    empty!(sut)

    @test (@allocations(insert!(sut, 1, 1))) == 0
    @test length(sut.ref.mem) == 3

The same happens with sparse vectors: setting the first item will always allocate.

using Test
using SparseArrays
vectorWithCap(cap::Int) = empty!(Vector{Int}(undef, cap))
function main()
    v = SparseVector(3, vectorWithCap(3), vectorWithCap(3))
    println("capacity before", length(v.nzind.ref.mem))
    @time v[2] = 1
    println("capacity after", length(v.nzind.ref.mem))
    @time v[1] = 1
end; main()

[oscardssmith]

That is fixed by #59717.

[dpinol]

That is fixed by #59717.

thanks, #56029 fixed it for large vectors and #59717 fixed it for vectors larger than 3, but I just built master and it still reallocates for lengths 1, 2 & 3.

[oscardssmith]

yeah, I can see the argument for fixing it for the tiny sizes, but I'm really not sure if it's worth it.

[dpinol]

We'll, it introduces a 125% time & 50% allocations overhead in this case.
I'm not saying it's a critical bug, but it is a performance bug that appears in 2 different cases. I also find troubling seeing julia tests which supposely check for reallocations, but they actually don't (see point 3 above).

with insert!

function main()
    v = Vector{Int}(undef, 3) 
    empty!(v)
    insert!(v, 1, 42)
end; 
@benchmark main()

with push!

function main()
    v = Vector{Int}(undef, 3) 
    empty!(v)
    push!(v, 42)
end; 
@benchmark main()