# When will a vector of structs be contiguous in memory?

**URL:** <https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181>\
**Category:** Performance\
**Created:** [October 21, 2021, 10:32pm UTC](https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181 "2021-10-21T22:32:47Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [October 21, 2021, 10:32pm UTC](https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181/1 "2021-10-21T22:32:47Z")

</div>

[Checking if a vector of structs is contiguous in memory](https://discourse.julialang.org/t/checking-if-a-vector-of-structs-is-contiguous-in-memory/2759) 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)

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [October 21, 2021, 11:49pm UTC](https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181/2 "2021-10-21T23:49:37Z")

</div>

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

```julia
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
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

```

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [October 22, 2021, 12:04am UTC](https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181/3 "2021-10-22T00:04:15Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [October 22, 2021, 12:48am UTC](https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181/4 "2021-10-22T00:48:31Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [October 22, 2021, 9:01am UTC](https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181/5 "2021-10-22T09:01:25Z")

</div>

It looks like `allocatedinline` is strongly related to `isbits`?

---

<div class="post-metadata">

**Author:** ![c42f](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/c42f/32/52842_2.png) [@c42f](https://discourse.julialang.org/u/c42f)\
**Post date:** [October 22, 2021, 9:52am UTC](https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181/6 "2021-10-22T09:52:15Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [October 22, 2021, 10:19pm UTC](https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181/7 "2021-10-22T22:19:05Z")

</div>

> [@c42f](#):
>
> `Unions` of bits types are not bits types, but can often be allocated inline.

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
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

```

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [October 22, 2021, 10:29pm UTC](https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181/8 "2021-10-22T22:29:45Z")

</div>

Type tags in `Array{Union{T1,T2}}` are stored elsewhere as `Array{UInt8}`. See: [First-Class Statistical Missing Values Support in Julia 0.7](https://julialang.org/blog/2018/06/missing/)

You can easily observe this with

```julia-repl
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

```llvm
; @ 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
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

```

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [October 23, 2021, 4:29am UTC](https://discourse.julialang.org/t/when-will-a-vector-of-structs-be-contiguous-in-memory/70181/10 "2021-10-23T04:29:38Z")

</div>

Huh. Who is this `pointer`? Interesting. Is there some `null`? OK, found out about C\_NULL.