On arrays with inline elements (vs pointer indirection)

[torrance]

I was answering another question here and realised how shaky my knowledge of Julia array storage is, regarding inline storage.

Somewhere (?) I read that if your struct is isbits and immutable, it can be stored directly inline in an array. This precludes a struct that stores an array, or a reference (but not a pointer, interestingly).

I have two questions: The first is regarding the isbits requirement: why is this needed? Why, for example, can’t my struct, which contains a vector, be stored inline? Sure, accesses to the child vector will require indirection off the heap somewhere, but the metadata for this child vector is constant in size and type.

The second question: is there are way to determine which type of array I currently have? Is there some sort of function like isstoredinline()?

[Benny]

@torrance

The first is regarding the isbits requirement: why is this needed?

Being stored inline exactly means that all of the data for the element is in one place with a fixed size; when the data is not all in one place, like a struct holding a Vector, then it’s just not considered inline. By the way, all isbits types are immutable because mutability, whether of the struct itself or its fields, requires some pointer indirection to allow references sharing an instance to also share its mutation.

@torrance

is there are way to determine which type of array I currently have? Is there some sort of function like isstoredinline()?

isbitstype(eltype(your_array))

[torrance]

@Benny

Being stored inline exactly means that all of the data for the element is in one place with a fixed size; when the data is not all in one place, like a struct holding a Vector, then it’s just not considered inline.

That doesn’t really answer my question, sorry. Consider this struct:

struct MyStruct
    a::Float64,
    b::Vector{Float64}
end

In this example I understand that the contents of b won’t be stored inline, but internally, b is just a struct itself, with a length, dimension, capacity and pointer, and those are fixed in size. It (seems) entirely possible that the size and types of MyStruct and its children types can be known a compile time.

So I’m asking why when I create a vector Vector{MyStruct}, why this isn’t stored inline, such that a is stored in the array, and the vector metadata of b is stored directly in the array? Meanwhile, accessing mystruct.b[100] for example, still requires pointer indirection, but that’s ok.

(As a counter example, a C++ vector can trivially be stored in an array of vectors, since it similarly just stores a length, capacity and pointer, in the same way as Julia arrays.)

[jar1]

Immutables with reference-fields: Why boxed?

One of the most painful things in julia is that there is no zero-cost abstraction for bundling gc-visible references with anything. This manifests in allocating views, allocating Tuple{Vector{Int}, Int}, etc. More than just making some code slow, this severely constrains APIs and design of data layouts. A priori there is no reason at all that immutable types cannot be always inline (self-referential / circular immutables make no sense and don’t even work in C); TBH, I see no point in immutabili…

GitHub - tkf/Restacker.jl: Put immutables back in the stack

[torrance]

@jar1 Right, so this is a limitation imposed by the GC?

[Benny]

@torrance

b is just a struct itself, with a length, dimension, capacity and pointer, and those are fixed in size.

Well, not for Julia Vectors. You can push! and pop! elements onto or off from the end of Vectors (length changes, capacity always increases), for instance, and when it starts running out of the allocated space, the memory buffer is reallocated to a different bigger spot (pointer changes). But that’s not actually the general reason that mutable objects aren’t stored inline, just an Array implementation detail. For example, you can make a mutable type with a fixed size: mutable struct MutInt num::Int end, which won’t be stored inline either.

Again, the reason is mutability. Bear in mind that Julia’s concept of mutability isn’t shared by all languages because Julia treats variables and other references like names to be attached to objects (like Python does). So you can attach two references to the same instance: x = MutInt(3); A[1] = x. Mutability doesn’t only mean the instance can change; if you think about it, you don’t actually need that all too often, you can just reassign variables to different instances e.g. count += 1. It also means that all the references access the change, so x.num = 5 changes x and A[1]. To pull that off, the actual num field cannot be stored directly in x or A, but in a neutral 3rd-party location on the heap or stack. By definition, MutInt(3) is not stored inline in A because some of its data is not in A’s array buffer.

@torrance

such that a is stored in the array, and the vector metadata of b is stored directly in the array? Meanwhile, accessing mystruct.b[100] for example, still requires pointer indirection, but that’s ok.

That’s essentially what happens. Very much like instances of MyStruct outside of arrays, the fixed-size chunk in the array’s buffer contains a Float64 for the a field and a pointer for the b field. That’s not considered inline. I’m not actually sure where vector metadata is stored, Base.summarysize doesn’t even count that bit of memory.

[Benny]

That is a really old thread, I think v1.5 (August 2020) fixed that issue. But there are issues that Restack seems to still help with, just not the stated purpose of stack-allocating “immutable” structs containing heap references (quotes because many non-mutable struct are in fact semantically mutable, like views).