Proving that copyto! is allocation-free on a view, using AllocCheck

General Usage
, ,
1

Hi there,
I wanted to add allocation checks to the DifferentiationInterface.jl test suite, but the code for my in-place jacobian! involves copying a vector into a matrix column. Unfortunately, AllocCheck.jl cannot guarantee that this operation happens without allocations[1]:

using AllocCheck
x = ones(2)
y_view = view(zeros(2, 2), 1:2, 1)

julia> check_allocs(copyto!, typeof.((y_view, x)))
1-element Vector{Any}:
 Allocation of Array in ./array.jl:411
  | copy(a::T) where {T<:Array} = ccall(:jl_array_copy, Ref{T}, (Any,), a)

Stacktrace:
 [1] copy
   @ ./array.jl:411 [inlined]
 [2] unaliascopy
   @ ./abstractarray.jl:1497 [inlined]
 [3] unalias
   @ ./abstractarray.jl:1481 [inlined]
 [4] copyto!(dest::SubArray{Float64, 1, Matrix{Float64}, Tuple{UnitRange{Int64}, Int64}, true}, src::Vector{Float64})
   @ Base ./abstractarray.jl:1067

The reason is that copyto! performs an aliasing check between source and destination, which cannot be statically proven to pass (because it depends on memory addresses). So even though this never allocates in my use case, I cannot use AllocCheck.jl to ensure it.
Does anyone have a workaround? Maybe another method of copyto! would be better suited?

  1. This is run on 1.10 but the same phenomenon happens on 1.11, the warnings are just different because of the new Memory type. ↩︎

1 Like
2

You can still check that the only allocation that can occur is this known allocation, implying that no other allocation can occur.

2 Likes
3

This works on v1.10:

struct NotSupported <: Exception end

function copyto_no_aliasing!(dst, src)
    @inline if isempty(src)
        dst
    elseif Base.mightalias(dst, src)
        throw(NotSupported())
    else
        copyto!(dst, src)
    end
end

julia> check_allocs(copyto_no_aliasing!, typeof.((y_view, x)))
Any[]

Making it work on v1.11 and v1.12 would require PRs to Julia.

1 Like
4

You can replace

col = view(mat::Matrix, :, idx)
copyto!(col, vec::Vector)

by

copyto!(mat,  1 + (idx-1)*size(AA,1),  vec, 1, length(vec))

copyto! aka memmove between arrays works fine with aliasing and without aliascopies, the code simply checks indices to decide whether to copy forwards or backwards.

Unfortunately nobody implemented a copyto! specialization for linear views that hits this codepath.

On the other hand, you may need to consider what kind of weird array types you need to support (e.g. autodiff, gpu, lazy Transpose, etc).

2 Likes
5

That’s a good idea but unfortunately this is meant to become part of the DifferentiationInterfaceTest.jl anaylsis toolkit. It may also apply to other jacobian functions not written by me, in which case it would seem arbitrary to only exclude that very specific copyto!.

Indeed I tried it and I get the same errors as before. Do you have any idea why?

Thanks for the advice to specialize on Array! But indeed I need to support whatever the user throws at me in terms of matrices, so I can’t get away with that.

6

Base.dataids(::Array) is more complicated now:

v1.10:

master (v1.11 is the same):

A reproducer independent of copyto!:

function dataid(x)
    @inline only(Base.dataids(x))
end

function dataids_match(x, y)
    @inline dataid(x) == dataid(y)
end

struct SomeException <: Exception end

function reproducer(x, y)
    @inline begin
        if dataids_match(x, y)
            throw(SomeException())
        end
        if dataids_match(x, y)
            17
        else
            13
        end
    end
end

# this results in only a bit of code on v1.10, while on master it results in a monstrosity
code_llvm(reproducer, Tuple{Vararg{Vector{Float32}, 2}})

@Oscar_Smith why is calling jl_genericmemory_owner even necessary in the dataids(::Memory) method? When is pointer(A) not correct? I figured out that the owner of a Memory is sometimes String, but should pointer not just work in that case, too?

7

Since you know there’s no aliasing in your use case, I suppose you could replace copyto!(dest, src) with map!(identity, dest, src). map! doesn’t check for aliasing, as you know better than most.

1 Like
8

I guess the reason is the following:

pointer points to the first array element, so it will advance when you popfirst!. Old style arrays afaiu did not permit situations where two different arrays overlap with different pointer (it unalias-copied if you reshape-then-popfirst!).

Now this is possible, with subsequent behavioral changes if you reshape-then-popfirst!-then-mutate (technically a breaking change in 1.11, but seems pretty harmless and like a strict improvement).

2 Likes