Repository: JuliaLang/julia
File: base/array.jl (Julia)

Code before:
    # for large n, we grow at O(n/8)
    # and as we reach O(memory) for memory>>1MB,
    # this means we end by adding about 10% of memory each time
    exp2 = sizeof(maxsize) * 8 - Core.Intrinsics.ctlz_int(maxsize)
    maxsize += (1 << div(exp2 * 7, 8)) * 4 + div(maxsize, 8)
    return maxsize
end

array_new_memory(mem::Memory, newlen::Int) = typeof(mem)(undef, newlen) # when implemented, this should attempt to first expand mem

function _growbeg_internal!(a::Vector, delta::Int, len::Int)
    @_terminates_locally_meta
    ref = a.ref
    mem = ref.mem
    offset = memoryrefoffset(ref)
    newlen = len + delta
    memlen = length(mem)
    if offset + len - 1 > memlen || offset < 1
        throw(ConcurrencyViolationError("Vector has invalid state. Don't modify internal fields incorrectly, or resize without correct locks"))
    end
    # Since we will allocate the array in the middle of the memory we need at least 2*delta extra space
    # the +1 is because I didn't want to have an off by 1 error.
    # Check if we can reuse existing memory without allocating
    # This is especially important for empty arrays where overallocation(0) might be larger than memlen
    newmemlen = len + 2 * delta + 1
    if newmemlen <= memlen
        # Reuse existing memory
        newoffset = div(memlen - newlen, 2) + 1
        newmem = mem
        unsafe_copyto!(newmem, newoffset + delta, mem, offset, len)
        for j in offset:newoffset+delta-1
            @inbounds _unsetindex!(mem, j)
        end
    else
        # Allocate new memory with overallocation
        newmemlen = max(overallocation(memlen), newmemlen)
        newoffset = div(newmemlen - newlen, 2) + 1
        newmem = array_new_memory(mem, newmemlen)
        unsafe_copyto!(newmem, newoffset + delta, mem, offset, len)
    end
    if ref !== a.ref
        throw(ConcurrencyViolationError("Vector can not be resized concurrently"))
    end
    setfield!(a, :ref, @inbounds memoryref(newmem, newoffset))
end

function _growbeg!(a::Vector, delta::Integer)
    @_noub_meta
    delta = Int(delta)
    delta == 0 && return # avoid attempting to index off the end
    delta >= 0 || throw(ArgumentError("grow requires delta >= 0"))

Review comment (suggestion):
This isn't quite strict enough. We want to ensure that we only move the start of the array if there remains proportional space at both ends of the array (since otherwise you are signing up for potential quadratic behavior)

Code after:
    # and as we reach O(memory) for memory>>1MB,
    # this means we end by adding about 10% of memory each time
    # most commonly, this will take steps of 0-3-9-34 or 1-4-16-66 or 2-8-33
    exp2 = sizeof(maxsize) * 8 - Core.Intrinsics.ctlz_int(maxsize)
    maxsize += (1 << div(exp2 * 7, 8)) * 3 + div(maxsize, 8)
    return maxsize
end

array_new_memory(mem::Memory, newlen::Int) = typeof(mem)(undef, newlen) # when implemented, this should attempt to first expand mem

function _growbeg_internal!(a::Vector, delta::Int, len::Int)
    @_terminates_locally_meta
    ref = a.ref
    mem = ref.mem
    offset = memoryrefoffset(ref)
    newlen = len + delta
    memlen = length(mem)
    if offset + len - 1 > memlen || offset < 1
        throw(ConcurrencyViolationError("Vector has invalid state. Don't modify internal fields incorrectly, or resize without correct locks"))
    end
    # since we will allocate the array in the middle of the memory we need at least 2*delta extra space
    # the +1 is because I didn't want to have an off by 1 error.
    newmemlen = max(overallocation(len), len + 2 * delta + 1)
    newoffset = div(newmemlen - newlen, 2) + 1
    # If there is extra data after the end of the array we can use that space so long as there is enough
    # space at the end that there won't be quadratic behavior with a mix of growth from both ends.
    # Specifically, we want to ensure that we will only do this operation once before
    # increasing the size of the array, and that we leave enough space at both the beginning and the end.
    if newoffset + newlen < memlen
        newoffset = div(memlen - newlen, 2) + 1
        newmem = mem
        unsafe_copyto!(newmem, newoffset + delta, mem, offset, len)
        for j in offset:newoffset+delta-1
            @inbounds _unsetindex!(mem, j)
        end
    else
        newmem = array_new_memory(mem, newmemlen)
        unsafe_copyto!(newmem, newoffset + delta, mem, offset, len)
    end
    if ref !== a.ref
        throw(ConcurrencyViolationError("Vector can not be resized concurrently"))
    end
    setfield!(a, :ref, @inbounds memoryref(newmem, newoffset))
end

function _growbeg!(a::Vector, delta::Integer)
    @_noub_meta
    delta = Int(delta)
    delta == 0 && return # avoid attempting to index off the end
    delta >= 0 || throw(ArgumentError("grow requires delta >= 0"))
    ref = a.ref