When will a vector of structs be contiguous in memory?

General Usage Performance
1

Checking if a vector of structs is contiguous in memory gives some tips for how to check, but would like to know the general pattern.

My specific use case is a sort of nested dictionary. I have an iterator of key-value pairs, and I’d like to keep track of the (ordered) list of values associated with every key. I expect that most of the time most keys will only have a single value, but they could have an unbounded number (up to the length of the iterator).

I’d like to use a Dict{K, Tuple{V, Vector{V}}}, but d.vals uses indirection, so each initial assignment results in an allocation. For a 64 bit V, I’d like d.vals to be an array of 128 bit structs, for the first occurrence of a key I’d like to set the first half to the value and the second to a null pointer, for the second occurrence, I’d like to allocate a vector with an element, each subsequent occurrence push! into the vector, but I don’t know how to achieve this.

(I have benchmarked & profiled and this is the bottleneck)

2

Maybe you can try Pair{V, Union{Nothing,Vector{V}}} or a similar named tuple instead of a tuple

julia> Base.allocatedinline(Tuple{Int,Union{Vector{Int},Nothing}})
false

julia> Base.allocatedinline(Pair{Int,Union{Vector{Int},Nothing}})
true

julia> Base.allocatedinline(@NamedTuple{first::Int,second::Union{Vector{Int},Nothing}})
true

julia> sizeof(Pair{Int,Union{Vector{Int},Nothing}})
16

Using a null pointer would mean using an undef field. However, you don’t get inlined allocation with this approach

julia> struct P{K,V}
           a::K
           b::V
           P{K,V}(a, b) where {K,V} = new{K,V}(a,b)
           P{K,V}(a) where {K,V} = new{K,V}(a)
       end

julia> P{Int,Vector{Int}}(1)
P{Int64, Vector{Int64}}(1, #undef)

julia> Base.allocatedinline(P{Int,Vector{Int}})
false
2 Likes
3

Thank you. That should solve my problem (yet to test & benchmark it).

Thank you for the Base.allocatedinline function. That is nice to have for easier experimentation.

Do you also happen to have a clean description of the types for which Base.allocatedinline will return true?

4

I think concretely typed immutable with no uninitialized “boxed” fields would be pretty safe. But there are other conditions that I don’t fully follow.

1 Like
5

It looks like allocatedinline is strongly related to isbits?

6

It’s related but not the same. Unions of bits types are not bits types, but can often be allocated inline.

2 Likes
7

I don’t see how this is possible. There are 2^65 possible values of type Union{Int64, Float64} and it should be impossible to store that inline in 64 bits. On the other hand:

julia> Base.allocatedinline(Union{Int, Float64})
true

julia> x = Union{Int, Float64}[1, 1.0, 3]
3-element Vector{Union{Float64, Int64}}:
 1
 1.0
 3

julia> pointer(x, 2)-pointer(x, 1)
0x0000000000000008
8

Type tags in Array{Union{T1,T2}} are stored elsewhere as Array{UInt8}. See: First-Class Statistical Missing Values Support in Julia 0.7

You can easily observe this with

julia> function f(xs)
           x = @inbounds xs[123456789]
           x + 0.0
       end
f (generic function with 1 method)

julia> @code_llvm f(Union{Int, Float64}[])

which prints

;  @ REPL[8]:1 within `f'
define double @julia_f_303({}* nonnull align 16 dereferenceable(40) %0) {
top:
;  @ REPL[8]:2 within `f'
; ┌ @ array.jl:801 within `getindex'
   %1 = bitcast {}* %0 to [1 x i64]**
   %2 = load [1 x i64]*, [1 x i64]** %1, align 8
   %3 = bitcast {}* %0 to { i8*, i64, i16, i16, i32 }*
   %4 = getelementptr inbounds { i8*, i64, i16, i16, i32 }, { i8*, i64, i16, i16, i32 }* %3, i64 0, i32 4
   %5 = load i32, i32* %4, align 4
   %6 = zext i32 %5 to i64
   %7 = bitcast {}* %0 to {}**
   %8 = getelementptr inbounds {}*, {}** %7, i64 4
   %9 = bitcast {}** %8 to i64*
   %10 = load i64, i64* %9, align 8
   %11 = sub nsw i64 %10, %6
   %12 = getelementptr inbounds [1 x i64], [1 x i64]* %2, i64 %11
   %13 = bitcast [1 x i64]* %12 to i8*
   %14 = sext i32 %5 to i64
   %15 = getelementptr inbounds i8, i8* %13, i64 %14
   %16 = getelementptr inbounds i8, i8* %15, i64 123456788
   %17 = load i8, i8* %16, align 1
   %18 = getelementptr inbounds [1 x i64], [1 x i64]* %2, i64 123456788, i64 0
   %19 = load i64, i64* %18, align 8
; └
;  @ REPL[8]:3 within `f'
  %switch.not = icmp eq i8 %17, 1
  %20 = bitcast i64 %19 to double
  %21 = sitofp i64 %19 to double
  %value_phi.in = select i1 %switch.not, double %21, double %20
;  @ REPL[8] within `f'
  %value_phi = fadd double %value_phi.in, 0.000000e+00
;  @ REPL[8]:3 within `f'
  ret double %value_phi
}

Notice that there are two loads %17 and %19.

If you want to observe the case where the type tag sits next to the Julia value itself, wrap it in, e.g., Some:

julia> Base.allocatedinline(Some{Union{Int, Float64}})
true

julia> sizeof(Some{Union{Int, Float64}})
16

julia> xs = Some{Union{Int, Float64}}[];

julia> pointer(xs, 2) - pointer(xs, 1)
0x0000000000000010
4 Likes
10

Huh. Who is this pointer? Interesting. Is there some null? OK, found out about C_NULL.