Remove indirection by defaulting to `MemoryView`, not `Memory`

[jakobnissen]

A Discourse post by foobar_v2 mentioned an important fact I've never considered: Memory access has more indirections when accessed through a Memory as opposed to a MemoryRef:

• Memory
  • Load the address of the Memory struct (mutable struct, so has its own address)
  • The memory struct contains a pointer to the buffer referred to by the Memory struct. Load the value from here
• MemoryRef
  • Load the value directly from the pointer in MemoryRef without indirection

Therefore, a FixedSizeArray wrapping a MemoryView is more efficient than one wrapping a Memory, as it elides one pointer chase:

julia> using FixedSizeArrays, MemoryViews;

julia> v = [1,2,3];

julia> A = FixedSizeArray(v);

julia> B = FixedSizeArrays.new_fixed_size_array(MemoryView(v), (3,));

julia> f(x) = @inbounds x[3];

julia> @code_native debuginfo=:none dump_module=false f(A)
        .section        __TEXT,__text,regular,pure_instructions
        ldr     x8, [x1]
        ldr     x9, [x20, #16]
        ldr     x9, [x9, #16]
        ldr     xzr, [x9]
        ldr     x8, [x8, #8]
        ldr     x0, [x8, #16]
        ret

julia> @code_native debuginfo=:none dump_module=false f(B)
        .section        __TEXT,__text,regular,pure_instructions
        ldr     x8, [x20, #16]
        ldr     x8, [x8, #16]
        ldr     xzr, [x8]
        ldr     x8, [x0]
        ldr     x0, [x8, #16]
        ret

The tradeoff is that it's 32 bytes in size, as opposed to 16. The reason is that the MemoryView inlines into the FixedSizeArray, which is also the reason we safe a pointer load.
Eliding one pointer chase at the cost of 2 integers of memory is almost certainly a performance benefit.

I suggest that certain constructors like FixedSizeArray(::Array) and FixedSizeArray(::Memory) uses MemoryViews internally.

[giordano]

The very first version of this package used MemoryRef:

FixedSizeArrays.jl/src/FixedSizeArrays.jl

Lines 5 to 8 in a08ce50

	mutable struct FixedSizeArray{T,N} <: DenseArray{T,N}
	ref::MemoryRef{T}
	const size::NTuple{N,Int}
	end

That was changed to Memory in #1. My understanding is that Base doesn't expose many methods for MemoryRef, which makes it awkward to use from outside Base, isn't that the case?

The tradeoff is that it's 32 bytes in size, as opposed to 16.

I presume that means an empty vector isn't "empty" (i.e. zero size) anymore?

[nsajko]

Make a PR and give benchmarks.

I have looked into this issue somewhat, and I feel the only right answer for "which representation is more efficient?" is "it depends, and most often it does not matter".

This repo implements all the different representations (Memory vs MemoryView, const field) for the DenseVector case:

• https://github.com/JuliaArrays/NonResizableVectors.jl

There are also relevant benchmarks in my tuple sorting PR to JuliaLang/julia, will link in following comment (AFK).

[nsajko]

The promised link with somewhat relevant benchmarks:

• sorting short homogeneous tuples: avoid allocation for more tuple lengths JuliaLang/julia#60951 (comment)

[oscardssmith]

Since the initial version, we've added some nicer MemoryRef interaction in Julia.

[jakobnissen]

Here are some benchmarks on Julia master:

Instantiation

Similar to using Memory backing. W.r.t

I presume that means an empty vector isn't "empty" (i.e. #62 (comment)) anymore?

I mean that the FixedSizeArray struct itself is larger. The backing memory is the same (ultimately, a Memory object). The larger size may translate to more register pressure.

Expand: Instantiation benchmarks

Code:

using Random: rand!
using Benchmarktools, MemoryViews, FixedSizeArrays

for n in (0, 2^0, 2^5, 2^10, 2^15, 2^20, 2^25)
    @info "n = $(n)"
    @btime Vector{Float64}(undef, $(n))
    @btime FixedSizeVectorDefault{Float64}(undef, $(n))
    @btime FixedSizeArrays.new_fixed_size_array(MemoryView(Memory{Float64}(undef, $(n))), ($(n),))
end

Results:

[ Info: n = 0
  4.168 ns (1 allocation: 32 bytes)
  2.554 ns (0 allocations: 0 bytes)
  2.154 ns (0 allocations: 0 bytes)
[ Info: n = 1
  7.772 ns (2 allocations: 64 bytes)
  5.721 ns (1 allocation: 32 bytes)
  5.521 ns (1 allocation: 32 bytes)
[ Info: n = 32
  11.192 ns (2 allocations: 320 bytes)
  8.134 ns (1 allocation: 288 bytes)
  8.545 ns (1 allocation: 288 bytes)
[ Info: n = 1024
  43.425 ns (3 allocations: 8.07 KiB)
  40.723 ns (2 allocations: 8.04 KiB)
  40.156 ns (2 allocations: 8.04 KiB)
[ Info: n = 32768
  273.969 ns (3 allocations: 256.07 KiB)
  270.661 ns (2 allocations: 256.04 KiB)
  269.729 ns (2 allocations: 256.04 KiB)
[ Info: n = 1048576
  1.697 μs (3 allocations: 8.00 MiB)
  3.900 μs (2 allocations: 8.00 MiB)
  3.361 μs (2 allocations: 8.00 MiB)
[ Info: n = 33554432
  4.359 μs (3 allocations: 256.00 MiB)
  4.007 μs (2 allocations: 256.00 MiB)
  4.118 μs (2 allocations: 256.00 MiB)

Pointer chasing

This is a little hard to benchmark. A single pointer chase is quite cheap, especially in benchmark settings where the cache is artificially hot and you don't see page faults etc.

A benchmark where we load repeatedly from the same array in a tight loop will show zero difference, because the extra pointer load imposed by Memory backing is hoisted.

But that doesn't mean the extra load isn't there! For example, we can construct a benchmark where the compiler can't hoist, where we see a meaningful difference (around 2x)

Expand: Pointer chasing

Code:

function do_work(vectors::Vector{<:FixedSizeArray})
	x = 0
	@inbounds for _ in 1:1_000_000
		v = vectors[(x & 0xffff) + 1]
		x = v[((x >> 16) & 0x3ff) + 1]
	end
	x
end 

for v in [
		[FixedSizeArray(rand(Int, 2^10)) for _ in 1:2^16],
		[FixedSizeArrays.new_fixed_size_array(MemoryView(rand!(Memory{Int}(undef, 2^10))), (2^10,)) for _ in 1:2^16]
	]
	@show typeof(v)
	@btime do_work($v)
end

Results

typeof(v) = Vector{FixedSizeArray{Int64, 1, Memory{Int64}}}
  34.525 ms (0 allocations: 0 bytes)
typeof(v) = Vector{FixedSizeVector{Int64, MutableMemoryView{Int64}}}
  18.035 ms (0 allocations: 0 bytes)

An even better layout

Actually MemoryView is suboptimal for FixedSizeArrays, because it stores its own length, which is useless and just adds register pressure. Ideally, a FixedSizeArray could get its length information from only its .size field, and use its wrapped array only for its pointer.
However, I don't believe current FixedSizeArray design can do this, because the design currently forwards array operations to its wrapped array, which necessitates the size must be stored twice.

[jakobnissen]

One solution could be to provide the following struct in FixedSizeArrays:

struct UnsafeRefArray{T} <: DenseVector{T}
    ref::MemoryRef{T}
end

which does no bounds checking. Then, default FixedSizeArray can wrap this type, the FSA itself would of course boundscheck. That would probably be optimal from a codegen / efficiency point of view.

I'm willing to pitch a PR. I can also implement a small package UnsafeRefArrays for experimentation if you want.

[giordano]

I'm definitely interested in seeing a prototype. If there are clear performance wins I'd be happy to switch. My only concern is that I liked the fact that allocating an empty fixed-size array wouldn't allocate any memory, but being still leaner than Array would be a net improvement.

Based on a quick test I did yesterday with MemoryViews, examples in #62 (reply in thread) would still allocate some memory, which feels unnecessary, but perhaps with a more complete prototype that'd be different.

[jakobnissen]

My only concern is that I liked the fact that allocating an empty fixed-size array wouldn't allocate any memory

To be clear, this property will be unchanged. No heap allocation would occur for zero-sized arrays even if backed by a MemoryRef. The extra memory burden is only for the immutable struct itself (as opposed to the heap is points to), meaning that it consumes 1 integer more stack memory or 1 extra register (similar to an Int). This is not nothing though and the extra stack pop/push instructions will cost a little bit. When operations are inlined the extra integer will be unused and might be optimized away by the compiler.

Edit: Sorry, I didn't see the right benchmark you were pointing to. Yes, that will still allocate, unnecessarily. I don't know why but clearly something is lacking in the escape analysis.

Edit2: It's got something to do with how rand!'s escape analysis is very brittle. Changing the rand! call to other operations changes the picture.