Copying a NTuple{UInt8} into a Memory{UInt8} or Vector{UInt8}

General Usage
1

In reviewing changes lead to StaticStrings.jl v0.3 I noticed the following code pattern would out perform other approaches including a plain for loop which does appear to vectorize.

To led to the following code which seemed to outperform other approaches:

@inline function bulk_copyto!(dest::AbstractVector{T}, doffs::Int,
                              src::NTuple{N,T}, soffs::Int, n::Int) where {T,N}
    @boundscheck begin
        isbitstype(T) && sizeof(NTuple{N,T}) == N*sizeof(T) || throw(ArgumentError("layout mismatch"))
        1 <= soffs && soffs+n-1 <= N && 1 <= doffs && doffs+n-1 <= length(dest) || throw(BoundsError())
    end
    ref = Ref(src)
    GC.@preserve ref dest begin
        p = Ptr{T}(Base.unsafe_convert(Ptr{Cvoid}, ref)) + (soffs-1)*sizeof(T)
        unsafe_copyto!(pointer(dest, doffs), p, n)
    end
    return dest
end

It seems that using this approach should be available via safe methods so I create the following issue:

I wanted to have a more general discussion here in case there is a reason for the current compiler behavior or the lack of a method to accelerate copying from a NTuple to Vector or Memory.

2

Semantically, sounds like a good idea. Your implementation should be just a memmove in the bitstype case.

Some issues:

  • IIUC, you shouldn’t use pointers to copy non-bitstypes, you should use the unsafe_copyto!(::MemoryRef, ::MemoryRef, ::Any) implementation.
  • This method only applies to dense vectors, or views of dense vectors, but not to Base.CodeUnits (which is dense, but immutable). There is currently no internal abstraction in Base for statically dispatching to dense, mutable memory, so you will have to either a) dispatch on a hodge podge of big-Unions and with local helper Holy traits, and/or b) throw your shoulder into the wheel of getting a good abstraction for dense memory in Julia (which we absolutely should have).

So, the ideal solution may not be practically feasible in the short term. I think the ideal solution is to make a TupleMemory{N, T} <: DenseVector{T} type which wraps an RefValue{NTuple{N, T}}. Then, you call the hypothetical Base copyto! code that automatically dispatches based on you working with two dense arrays, and which handles the copying. You can maybe use @assume_effects to help the compiler understand that the ref does not escape.

The poor but practical solution might be to implement Base.copyto!(::MutableDenseArrayType{T}, ::Tuple{Vararg{T}}) and do a check for bitstypes, then uses your pointer method.

3

Can you post complete copy-pasteable code that benchmarks your bulk_copyto! against the naive version, in order to reproduce your observation and make clear what you refer to?

There is a natural mismatch: NTuple wants to be stored in a (wide) register, but these cannot be accessed with byte-offsets (needed for soffs/n). In other words, the natural sequence would be: Store the NTuple to memory (on the stack), then copy from that to the destination (ideally using store forwarding).

However, in the real world you probably have the situation that your NTuple is already stored on the heap somewhere. So it is important to check whether

  1. Bad: Julia loads the NTuple into a register, then stores it to the stack, then copies part of it
  2. Good: Julia never loads the NTuple into a register, and instead does memory-to-memory movement.

With your API, you cannot see this. You could see this with e.g.

function bulk_copyto!(dest::Memory{T}, doffs::Int,
                              src::Memory{NTuple{N,T}}, soffs::Int, n::Int, srcIdx::Int) where {T,N}
...
4

The latest version of Strided array traits - Pull Request #60964 - JuliaLang/julia - GitHub can be used for this since it can distinguish between just dense layout, and dense layout that can be safely mutated in CPU memory.

5

I posted a reproducible script to Copying from an NTuple into an Array/Memory neither vectorizes nor forms a memcpy · Issue #63335 · JuliaLang/julia · GitHub

6

Yeah, you posted that link before; I was hoping for a less sloppy variant. Regardless, the short of it (i.e. only the things that are needed to verify the problem):

julia> using BenchmarkTools
julia> @noinline function tuple_to_memory_fast(dst::Memory{UInt8}, src::NTuple{N,UInt8}) where N
         reinterpret(typeof(src),dst)[1]=src
       end
tuple_to_memory_fast (generic function with 1 method)

julia> @noinline function tuple_to_memory_slow(dst::Memory{UInt8}, src::NTuple{N,UInt8}) where N
         for i=1:N
         @inbounds dst[i] = src[i]
         end
       end
tuple_to_memory_slow (generic function with 1 method)

julia> @noinline function tuple_to_memory_fast2(dst::Memory{UInt8}, src::NTuple{N,UInt8}) where N
         @simd ivdep for i=1:N
         @inbounds dst[i] = src[i]
         end
       end
tuple_to_memory_fast2 (generic function with 1 method)

julia> N=256;s=ntuple(i->UInt8(1), N);d=Memory{UInt8}(undef,N);

julia> @btime tuple_to_memory_slow($d,$s);
  26.331 ns (0 allocations: 0 bytes)

julia> @btime tuple_to_memory_fast($d,$s);
  9.640 ns (0 allocations: 0 bytes)

julia> @btime tuple_to_memory_fast2($d,$s);
  4.130 ns (0 allocations: 0 bytes)

The issue becomes clear when viewing the code for tuple_to_memory_slow: The auto-vectorizer messes up and this is a horror-show of single-byte copies.

I vaguely remember that this used to work without problems. And indeed on 1.8.5:

julia> using BenchmarkTools

julia> @noinline function tuple_to_memory_slow(dst::Vector{UInt8}, src::NTuple{N,UInt8}) where N
         for i=1:N
         @inbounds dst[i] = src[i]
         end
       end
tuple_to_memory_slow (generic function with 1 method)

julia> N=256;s=ntuple(i->UInt8(1), N);d=Vector{UInt8}(undef,N);

julia> @btime tuple_to_memory_slow($d,$s);
  5.060 ns (0 allocations: 0 bytes)

So this is a severe regression / compiler-bug. Good on finding that! I recommend @simd ivdep as a work-around, and would hope that we get that fixed and get regression tests to prevent future fails.