Base alias checking kills performance (on 0.7)

[KristofferC]

Trying out the example in https://discourse.julialang.org/t/avoiding-memory-allocation-for-vector-operations/12447/3 with this package we get:

function gram_schmidt1!(U::Matrix{T}) where {T <: Real}
    m = size(U, 2)
    @inbounds for k = 1:m
        uk = uview(U,:,k)
        @inbounds for j = 1:k-1
            uj = uview(U,:,j)
            uk .-= (uj ⋅ uk) .* uj
        end
        uk ./= norm(uk)
    end
end

N = 100;
A = randn(N, N);

julia> @btime gram_schmidt1!($A)
  1.002 ms (9900 allocations: 309.38 KiB)

Disabling the aliasing detection (which falls back to objectid which is slow):

julia> @eval Base begin
           mightalias(A::AbstractArray, B::AbstractArray) = false
       end
mightalias (generic function with 3 methods)

julia> @btime gram_schmidt1!($A)
  297.718 μs (0 allocations: 0 bytes)

which is almost as good as the handwritten loop version. For normal SubArrays, Base has a custom written version of mightalias: https://github.com/JuliaLang/julia/blob/b6a60dd6601a6947e00a0a77decd283248ba8a7f/base/multidimensional.jl#L703-L717, perhaps one could be added here?
Or in the unsafe manner disable this and document that unsafe views are not allowed to alias.

[oschulz]

Try using the @uviews macro - I may actually deprecated the uview() function at some point, as the macro allows you to use your code almost unmodified:

function gram_schmidt1!(U::Matrix{T}) where {T <: Real}
    @uviews U begin
    m = size(U, 2)
        @inbounds for k = 1:m
            uk = view(U,:,k)
            @inbounds for j = 1:k-1
                uj = view(U,:,j)
                uk .-= (uj ⋅ uk) .* uj
            end
            uk ./= norm(uk)
        end
    end
end

N = 100;
A = randn(N, N);

@btime gram_schmidt1!($A)

Also, the UnsafeArray is created only once, which saves a little bit of time in the loops.

Regarding mightalias(), I'll see if I can add direct support for UnsafeArray - after all, with pointer-based data, a decisive and cheap check should be easy.

[oschulz]

This seems to do the trick:

function Base.mightalias(A::UnsafeArray, B::UnsafeArray)
    pfA = pointer(A, firstindex(A))
    plA = pointer(A, lastindex(A))
    pfB = pointer(B, firstindex(B))
    plB = pointer(B, lastindex(B))

    (pfA <= pfB <= plA) || (pfA <= plB <= plA)
end

Could you test/confirm, @KristofferC ? If it works fine for you as well, I'll add it to UnsafeArrays.jl.

[oschulz]

Probably will need to specialize Base.mightalias for SubArray{T,N,<:UnsafeArray} as well ...

[oschulz]

Fixed in e76a847.

[oschulz]

Thanks again for pointing me to mightalias, @KristofferC.