Make an `isdense` trait

[LilithHafner]

Density is orthogonal to many types (e.g. StaticArray, CodeUnits, SubArray, etc) so it makes more sense as a trait instead of an abstract type.

As a starting point,

isdense(::DenseArray) = true
isdense(::Array) = false
isdense(::String) = true # Maybe

Maybe also applies to strings?

See also:

• Switch supertype of CodeUnits from DenseVector to AbstractVector #54002

[Seelengrab]

Duplicate of #54581?

[jariji]

From Core.DenseArray

The elements of a dense array are stored contiguously in memory.

isdense isn't specific enough a term, imo. I'd consider contiguous_storage or contiguous_memory or is_memory_contiguous.

[jakobnissen]

A few comments off the top of my head:

Denseness should also be documented to say that it has a stride of 1. E.g. dense things should not be stored in reverse order, such that subsequent elements are placed on lower memory addresses.

My proposal in #54581 is related. However, in that proposal, I don't include a trait like isdense. Such a trait would make sense both with and without the existence of a memory view type.
However, I propose the IsMemory trait, which signifies that an object is equal to its memory. For example, a dense view of a Vector is equal to a Memory with the same element type and content. In contrast, a string is not equal to the content of its memory. Which sense of the word "dense" is meant here? Merely that the data of an object is stored contiguous in memory, or also that the object is semantically equal to its own memory?
The distinction is important, because:

• The former definition includes strings, and as such means something like "I can take a pointer to this object and copy it". However, because it carries little semantic meaning, there isn't much else you can do with this isdense definition.
• The latter definition allows you to treat the memory of the object as actually being the object (i.e. the object is an AbstractArray and is interchangeable with a Memory object pointing to the same memory), which then again allows you to e.g. pass the object into C functions. This is more useful, but it then leaves strings a little in the dust.

I think the latter, more restrictive, IsMemory-like definition is the most useful, in which case we would also need to say that an object implementing isdense should be an AbstractArray and equal to Memory with the same content.
Can anyone think of a counterexample, where it would be useful to have an object which is not IsMemory, but still isdense, and where such an object wouldn't be handled in a custom function anyway, such that its implementation of isdense is actually used for dispatch?

[nhz2]

If isdense(A) returns true, I think that should guarantee write(io::IOBuffer, A) writes the same bytes out as GC.@preserve A unsafe_write(io::IOBuffer, pointer(A), UInt(elsize(A)) * UInt(length(A))).

This could include Matrix{Float64}, even though it might not be isequal equal to a Memory{Float64} with the same content, due to the different shape.

Though I think also restricting isdense to only AbstractVector with one-based indexing could be more useful.

[Seelengrab]

I think that should guarantee write(io::IOBuffer, A) writes the same bytes out as GC.@preserve A unsafe_write(io::IOBuffer, pointer(A), UInt(elsize(A)) * UInt(length(A))).

I don't think that's possible, since that would write out SIMD alignment/padding in objects too.

[nhz2]

What about if isdense(A) returning true guarantees:

@assert isbitstype(eltype(A))
Base.require_one_based_indexing(A)
B = Memory{eltype(A)}(undef, length(A))
GC.@preserve A B unsafe_copyto!(pointer(B), pointer(A), length(A))
@assert isequal(A, B)

I think this is the same as the IsMemory-like definition.

[oscardssmith]

The first of these requirements definitely seems wrong.

[nhz2]

Without that there is a problem with Union vectors.

A = Union{Float64,Int64}[1,2.5,3]
B = Memory{eltype(A)}(undef, length(A));
GC.@preserve A B unsafe_copyto!(pointer(B), pointer(A), length(A));
isequal(A,B)

[nsajko]

Earlier issue: #10889

[quildtide]

Working on making a mutating vectorized rand call as efficient for a custom type as Base implementations caused me to witness the mess that is currently MutableDenseArrayType, a frankenstein Union const (that I do not believe is exported in any way) that I also do not wish to recreate in an external package.

I felt the immediate urge to start a pull request for this if no one had somehow already started one. All of tomorrow's Hackathon plans are now replaced with this.