Reinterpreting Vector{Union{T,Missing}} as Vector{T}

[haampie]

A general and hopefully elegant way to solve the problem of sorting a vector with missing data (#27781) is to pre-proces it by partitioning the vector as

# Vector{Union{T,Missing}} --> [Vector{T}; Vector{Missing}]
#                                        ^-- mid
mid = partition!(v)

# Sort the non-missing part using the standard best sorting algorithm for T's
sort!(reinterpret(T, v), 1, mid, ...)

Partitioning is just an O(n) operation, and in principle equivalent to the first step of QuickSort when the initial pivot value is fixed to be missing.

Unfortunately the idea breaks down because

julia> reinterpret(Float64, Vector{Union{Float64,Missing}}(rand(10)))
ERROR: ArgumentError: cannot reinterpret `Union{Missing, Float64}` `Float64`, type `Union{Missing, Float64}` is not a bits type

fails.

Is it technically possible to allow this kind of reinterpret(T, Vector{Union{T,Missing}}) in such a way that getindex and setindex! are without overhead?

[chethega]

I think this will become reasonably possible once ddf6d9f has landed, for julia arrays of Base.isbitsunion. I don't see how to properly do this for abstract arrays, without incurring the check of the type at every access; and then, copying into a temporary non-union array would probably be faster.

[vtjnash]

I suspect ddf6d9f will either generate incorrect code, or significantly worse code. These arrays don't have a concept of pointer that is compatible with C, so we can usually assume that they can't alias anything else.

However, sorting already makes O(log n) copies, so making two additional copies (e.g. O(1)) to modify the type will not impact performance (e.g. copyto!(array, sort!(copyto!(similar(T, array), array))))

[StefanKarpinski]

Quicksort doesn't make any copies, and that's the algorithm that should be used here.

[nalimilan]

A low-level solution is to access the data part of the array via unsafe_wrap(Array, Ptr{Base.nonmissingtype(eltype(x))}(pointer(x)), length(x) - count(ismissing, x)). AFAICT it should work if missing values are at the end. Maybe that's OK for internal use, but that's not the kind of thing we should advertize.

[StefanKarpinski]

I think it's fine if internal Base implementations of something as performance-critical as this use dirty tricks; others can do the same at their own risk but yes, not something to advertise.

[haampie]

Ok, thanks for the ideas! I'm closing this for now