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

**URL:** <https://discourse.julialang.org/t/proving-that-copyto-is-allocation-free-on-a-view-using-alloccheck/121318>\
**Category:** General Usage\
**Tags:** views, allocations, alloccheck\
**Created:** [October 15, 2024, 8:30am UTC](https://discourse.julialang.org/t/proving-that-copyto-is-allocation-free-on-a-view-using-alloccheck/121318 "2024-10-15T08:30:51Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [October 15, 2024, 8:30am UTC](https://discourse.julialang.org/t/proving-that-copyto-is-allocation-free-on-a-view-using-alloccheck/121318/1 "2024-10-15T08:30:51Z")

</div>

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\]:

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

```

```julia
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.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [October 15, 2024, 9:17am UTC](https://discourse.julialang.org/t/proving-that-copyto-is-allocation-free-on-a-view-using-alloccheck/121318/2 "2024-10-15T09:17:56Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [October 15, 2024, 9:39am UTC](https://discourse.julialang.org/t/proving-that-copyto-is-allocation-free-on-a-view-using-alloccheck/121318/3 "2024-10-15T09:39:32Z")

</div>

This works on v1.10:

```julia
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-repl
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.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [October 15, 2024, 9:50am UTC](https://discourse.julialang.org/t/proving-that-copyto-is-allocation-free-on-a-view-using-alloccheck/121318/4 "2024-10-15T09:50:08Z")

</div>

You can replace

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

```

by

```julia
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).

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [October 15, 2024, 11:56am UTC](https://discourse.julialang.org/t/proving-that-copyto-is-allocation-free-on-a-view-using-alloccheck/121318/5 "2024-10-15T11:56:48Z")

</div>

> [@baggepinnen](#):
>
> You can still check that the only allocation that can occur is this known allocation, implying that no other allocation can occur.

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!`.

> [@nsajko](#):
>
> Making it work on v1.11 and v1.12 would require PRs to Julia.

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

> [@foobar\_lv2](#):
>
> 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).

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.

---

<div class="post-metadata">

**Author:** ![nsajko](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nsajko/32/221187_2.png) [@nsajko](https://discourse.julialang.org/u/nsajko)\
**Post date:** [October 15, 2024, 2:38pm UTC](https://discourse.julialang.org/t/proving-that-copyto-is-allocation-free-on-a-view-using-alloccheck/121318/6 "2024-10-15T14:38:38Z")

</div>

> [@gdalle](#):
>
> > [@nsajko](#):
> >
> > Making it work on v1.11 and v1.12 would require PRs to Julia.
> 
> Indeed I tried it and I get the same errors as before. Do you have any idea why?

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

v1.10:

> <https://github.com/JuliaLang/julia/blob/v1.10.5/base/abstractarray.jl#L1540-L1540>

master (v1.11 is the same):

> <https://github.com/JuliaLang/julia/blob/d09abe55f1c979df347fa682037c4f68f69b48c0/base/abstractarray.jl#L1587-L1588>

A reproducer independent of `copyto!`:

```julia
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?

---

<div class="post-metadata">

**Author:** ![danielwe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielwe/32/35657_2.png) [@danielwe](https://discourse.julialang.org/u/danielwe)\
**Post date:** [October 15, 2024, 3:18pm UTC](https://discourse.julialang.org/t/proving-that-copyto-is-allocation-free-on-a-view-using-alloccheck/121318/7 "2024-10-15T15:18:05Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [October 15, 2024, 3:21pm UTC](https://discourse.julialang.org/t/proving-that-copyto-is-allocation-free-on-a-view-using-alloccheck/121318/8 "2024-10-15T15:21:11Z")

</div>

> [@nsajko](#):
>
> but should `pointer` not _just work_ in that case, too?

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