# Add Resizable AbstractArray interface for push! and append!?

**URL:** <https://discourse.julialang.org/t/add-resizable-abstractarray-interface-for-push-and-append/118049>\
**Category:** General Usage\
**Tags:** push, abstractvector, append\
**Created:** [August 11, 2024, 10:44am UTC](https://discourse.julialang.org/t/add-resizable-abstractarray-interface-for-push-and-append/118049 "2024-08-11T10:44:20Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [August 11, 2024, 10:44am UTC](https://discourse.julialang.org/t/add-resizable-abstractarray-interface-for-push-and-append/118049/1 "2024-08-11T10:44:20Z")

</div>

On Julia 1.10, the following `AbstractVector` implementation supports `push!` and `append!`:

```julia-repl
julia> begin
       struct MyVector <: AbstractVector{Int}
           v::Vector{Int}
           function MyVector(args...)
               new(Vector{Int}(args...))
           end
       end
       Base.size(mv::MyVector) = size(mv.v)
       Base.getindex(v::MyVector, i::Int) = getindex(v.v, i)
       Base.setindex!(mv::MyVector, v, i::Int) = mv.v[i] = v
       Base.resize!(mv::MyVector, nl::Integer) = resize!(mv.v, nl)
       end

julia> v = MyVector(undef, 5)
5-element MyVector:
 0
 0
 0
 0
 0

julia> push!(v, 6)
6-element MyVector:
 0
 0
 0
 0
 0
 6

julia> append!(v, [1,2,3])
9-element MyVector:
 0
 0
 0
 0
 0
 6
 1
 2
 3

```

Beyond [the `AbstractArray` interface](https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-array), the only other method needed was `resize!`. On Julia 1.11, this appears to be no longer the case:

```julia-repl
julia> begin
       struct MyVector <: AbstractVector{Int}
           v::Vector{Int}
           function MyVector(args...)
               new(Vector{Int}(args...))
           end
       end
       Base.size(mv::MyVector) = size(mv.v)
       Base.getindex(v::MyVector, i::Int) = getindex(v.v, i)
       Base.setindex!(mv::MyVector, v, i::Int) = mv.v[i] = v
       Base.resize!(mv::MyVector, nl::Integer) = resize!(mv.v, nl)
       end

julia> v = MyVector(undef, 5)
5-element MyVector:
 0
 0
 0
 0
 0

julia> push!(v, 6)
ERROR: MethodError: no method matching sizehint!(::MyVector, ::Int64)
The function `sizehint!` exists, but no method is defined for this combination of argument types.

Closest candidates are:
  sizehint!(::BitSet, ::Integer; first, shrink)
   @ Base bitset.jl:58
  sizehint!(::BitVector, ::Integer)
   @ Base bitarray.jl:809
  sizehint!(::Dict{T}, ::Any; shrink) where T
   @ Base dict.jl:193
  ...

Stacktrace:
 [1] _append!(a::MyVector, ::Base.HasLength, iter::Tuple{Int64})
   @ Base ./array.jl:1320
 [2] append!(a::MyVector, iter::Tuple{Int64})
   @ Base ./array.jl:1313
 [3] push!(a::MyVector, iter::Int64)
   @ Base ./array.jl:1314
 [4] top-level scope
   @ REPL[3]:1

```

If I follow the suggestion and implement `sizehint!`, I then get a stack overflow.

```julia
julia> Base.sizehint!(v::MyVector, nl::Integer) = sizehint!(v.v, nl)

julia> push!(v, 6)
ERROR: StackOverflowError:
Stacktrace:
      [1] sizehint!(a::Vector{Int64}, sz::Int64; first::Bool, shrink::Bool)
        @ Base ./array.jl:1480
      [2] sizehint!
        @ ./array.jl:1480 [inlined]
      [3] sizehint!
        @ ./REPL[4]:1 [inlined]
      [4] sizehint!
        @ ./array.jl:1519 [inlined]
      [5] _append!
        @ ./array.jl:1320 [inlined]
      [6] append!
        @ ./array.jl:1313 [inlined]
      [7] push!(a::MyVector, iter::Int64)
        @ Base ./array.jl:1314
      [8] _append!
        @ ./array.jl:1322 [inlined]
--- the above 3 lines are repeated 79981 more times ---
 [239952] append!
        @ ./array.jl:1313 [inlined]

```

The stack overflow is due to `push!` calling `append!` which in turn calls `push!`. This appears to be due to the following pull request that is in Julia 1.11.0-rc2:

> <https://github.com/JuliaLang/julia/pull/51903>
>
> First we add an optional API parameter for \`sizehint!\` that controls whether it …is for \`push!\` (default) or \`pushfirst!\`. Secondly, we make the offset zero when using \`sizehint!\` to shrink an array from the end, or the trailing size zero when using it to shring from the beginning.
> 
> Then we replace the prior implementations of \`prepend!\` and \`append!\` with ones that are safe even if the iterator changes length during the operation or if convert fails. The result of \`prepend!\` may be in an undefined order (because of the \`reverse!\` call) in the presence of concurrent modifications or errors, but at least all of the elements will be present and valid afterwards.
> 
> Replaces and closes #49905
> Replaces and closes #47391
> Fixes #15868
> 
> Benchmarks show that repeated \`push!\` performance (with sizehint) is nearly equivalent to the old append performance:
> \`\`\`
> julia\> @benchmark append!(x, 1:1000) setup=x=Vector{Float64}(undef,0)
> BenchmarkTools.Trial: 10000 samples with 10 evaluations.
> Range (min … max): 1.027 μs … 72.871 μs ┊ GC (min … max): 0.00% … 94.57%
> Time (median): 1.465 μs ┊ GC (median): 0.00%
> Time (mean ± σ): 1.663 μs ± 1.832 μs ┊ GC (mean ± σ): 6.20% ± 5.67%
> 
> ▂▃▅▆█▇▇▆▄▂▁                                      
> ▂▁▁▂▂▂▂▃▄▅▇█████████████▇▆▅▅▅▅▅▅▄▅▄▅▅▅▆▇███▆▅▄▃▃▂▂▂▂▂▂▂▂▂▂ ▄
> 1.03 μs Histogram: frequency by time 2.31 μs \<
> 
> Memory estimate: 19.69 KiB, allocs estimate: 0.
> 
> julia\> @benchmark append!(x, 1:1000) setup=x=Vector{Int}(undef,0)
> BenchmarkTools.Trial: 10000 samples with 10 evaluations.
> Range (min … max): 851.900 ns … 76.757 μs ┊ GC (min … max): 0.00% … 91.59%
> Time (median): 1.181 μs ┊ GC (median): 0.00%
> Time (mean ± σ): 1.543 μs ± 1.972 μs ┊ GC (mean ± σ): 6.75% ± 5.75%
> 
> ▆█▇▃                                                       
> ▂▃██████▇▅▅▄▅▅▃▂▂▂▃▃▃▂▃▃▃▂▂▂▂▂▁▂▁▂▁▂▂▂▁▁▂▂▁▁▁▁▁▁▁▂▂▂▃▃▃▃▂▂▂▂ ▃
> 852 ns Histogram: frequency by time 4.07 μs \<
> 
> Memory estimate: 19.69 KiB, allocs estimate: 0.
> \`\`\`

I discovered this while I was doing some maintenance on UInt12Arrays.jl, and I noticed that my tests were failing on Julia 1.11.0-rc2. There I noticed that `push!` and `append!` no longer work like above. I wonder if this might affect other `AbstractArray` or `AbstractVector` implementations.

Perhaps `resize!` and `sizehint!` should be added to the [`AbstractArray` interface](https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-array) as an optional method to enable `push!` and `append!`.

If we only wanted to depend on `resize!` for `push!` and `append!` to work, perhaps we should consider adding the following to `Base`:

```julia
import Base: push!, sizehint!

function push!(vec::AbstractVector, v)
    new_length = length(vec) + 1
    resize!(vec, new_length)
    vec[new_length] = v
    return vec
end

# do nothing
sizehint!(vec::AbstractVector, nl::Integer) = vec

```

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [August 11, 2024, 11:06am UTC](https://discourse.julialang.org/t/add-resizable-abstractarray-interface-for-push-and-append/118049/2 "2024-08-11T11:06:22Z")

</div>

Looking closer at the fixed issues by @Sukera and @Mason where the array would grow despite `push!` or `append!` failing perhaps we need the following.

```julia
import Base: push!, sizehint!
using Base: @_terminates_locally_meta

function push!(a::AbstractVector{T}, item) where T
    # convert first so we don't grow the array if the assignment won't work
    itemT = item isa T ? item : convert(T, item)::T
    new_length = length(a) + 1
    resize!(a, new_length)
    a[length(a)] = itemT
    return a
end

# specialize and optimize the single argument case
function push!(a::AbstractVector{Any}, @nospecialize x)
    new_length = length(a) + 1
    resize!(a, new_length)
    a[length(a)] = x
    return a
end
function push!(a::AbstractVector{Any}, @nospecialize x...)
    @_terminates_locally_meta
    na = length(a)
    nx = length(x)
    resize!(a, na + nx)
    for i = 1:nx
        a[na+i] = x[i]
    end
    return a
end

# do nothing
sizehint!(vec::AbstractVector, nl::Integer) = vec

```

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [August 11, 2024, 11:22am UTC](https://discourse.julialang.org/t/add-resizable-abstractarray-interface-for-push-and-append/118049/3 "2024-08-11T11:22:39Z")

</div>

> [@mkitti](#):
>
> Perhaps `resize!` and `sizehint!` should be added to the [`AbstractArray` interface](https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-array) as an optional method to enable `push!` and `append!`.

That would also require re-adding `setindex!` to the interface, no? IIRC that has been removed from the interface a while ago, since not all `AbstractArray`s necessarily support mutation (e.g. `0:10`).

---

<div class="post-metadata">

**Author:** ![mkitti](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mkitti/32/12459_2.png) [@mkitti](https://discourse.julialang.org/u/mkitti)\
**Post date:** [August 11, 2024, 11:25am UTC](https://discourse.julialang.org/t/add-resizable-abstractarray-interface-for-push-and-append/118049/4 "2024-08-11T11:25:21Z")

</div>

`setindex!` is listed as an optional method of the interface. It seems clear to me that `push!` will not work if `setindex!` is not defined, but perhaps that could also be made explicit.

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [August 11, 2024, 11:33am UTC](https://discourse.julialang.org/t/add-resizable-abstractarray-interface-for-push-and-append/118049/5 "2024-08-11T11:33:27Z")

</div>

The other thing is that neither of `push!` nor `append!` work on actual N-dimensional arrays, they’re really only suitable for `AbstractVector` at best.

I personally don’t like that we have such “optional” parts of an interface at all. This is more indicative of a lack of formal interfaces.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [August 11, 2024, 1:06pm UTC](https://discourse.julialang.org/t/add-resizable-abstractarray-interface-for-push-and-append/118049/6 "2024-08-11T13:06:28Z")

</div>

> [@Sukera](#):
>
> neither of `push!` nor `append!` work on actual N-dimensional arrays

`append!` works on N-dimensional ElasticArrays.jl, but you can only `append!` elements of a particular number and shape so that the last dimension increments, as if the last dimension could be the length of a vector that holds N-1-dimension arrays with a shape omitting the last dimension.