Seeing allocations only when assigning to a Vector of Union{Nothing, Struct} when Struct is immutable, but contains mutable data

Lars_Wander · August 12, 2021, 1:31pm

Hello Julia folks,

Context: while writing code to search for aperiodic tilings of the plane, I noticed that every assignment to an element of Vector{Union{Nothing, Tile}} was causing an allocation according to --track-allocation=user. Tile is an immutable struct, but contains mutable data (a Vector). I’ve reduced this behavior down to a simple example showing the extra allocations only occurring when assigning to a Vector of Union{Nothing, T} where T is immutable, but contains mutable data.

Julia Version: Version 1.6.2 (2021-07-14)
OS: Description: Ubuntu 20.04.2 LTS

Here is a contrived example:

#!/usr/bin/env julia
# example.jl

struct VectorItem
    data::Vector{Int64}
end

struct IntItem
    data::Int64
end

function fill_vector(container::Vector{VectorItem}, item::VectorItem)
    for i in 1:length(container)
        container[i] = item
    end
end

function fill_int(container::Vector{IntItem}, item::IntItem)
    for i in 1:length(container)
        container[i] = item
    end
end

function fill_vectorunion(container::Vector{Union{Nothing, VectorItem}}, item::VectorItem)
    for i in 1:length(container)
        container[i] = item
    end
end

function fill_intunion(container::Vector{Union{Nothing, IntItem}}, item::IntItem)
    for i in 1:length(container)
        container[i] = item
    end
end

function doprofile()
    times = 1000

    vectoritem = VectorItem(Int64[])
    intitem = IntItem(0)

    vector = [vectoritem for i in 1:times]
    int = [intitem for i in 1:times]

    vectorunion::Vector{Union{Nothing, VectorItem}} = [nothing for i in 1:times]
    intunion::Vector{Union{Nothing, IntItem}} = [nothing for i in 1:times]

    @time fill_vector(vector, vectoritem)
    @time fill_int(int, intitem)
    @time fill_vectorunion(vectorunion, vectoritem)
    @time fill_intunion(intunion, intitem)
end

doprofile()

Running this shows that only the fill_vectorunion causes any allocations at all:

$ julia example.jl
  0.000001 seconds
  0.000000 seconds
  0.000010 seconds (1000 allocations: 15.625 KiB)
  0.000001 seconds

Intuitively, I would expect none of these examples to cause any allocations, as all the data we are manipulating is already allocated before doing any profiling. (Running doprofile() twice to ensure we aren’t capturing any JIT-related allocations results in the same behavior).

Lars_Wander · August 12, 2021, 6:48pm

After some more reading, I’m guessing the isbits optimization doesn’t apply here: isbits Union Optimizations · The Julia Language.

isbitstype(VectorItem) == false, and isbitstype(IntItem) == true.

Intuitively this seems odd, as I don’t understand why we can’t blindly copy the contents of an immutable struct rather than use a boxed type. Maybe someone with more insight can explain this?

Sukera · August 12, 2021, 7:12pm

15_625 KiB == 16_000 Bytes, so that’s 16 Bytes / allocation. I’m guessing that’s a type tag and a pointer? Not sure though Would make sense, because the non-uniform data requires some kind of type tag to distinguish Nothing from VectorItem, plus you can’t store it inline anymore because it isn’t isbits.

I’d expect this to be either 12 or 8 bytes on a 32-bit system (smaller pointer, probably the former since I don’t expect type tags to change size with different architecture)

Henrique_Becker · August 12, 2021, 7:17pm

I have two comments:

If the problem was just that VectorItem is not isbitstype then the problem would occur with fill_vector too not fill_vectorunion. In fact, I do believe that fill_vector really blindly copy the contents of immutable struct VectorItem to a position in Vector{VectorItem} as you want, however, fill_vectorunion cannot do the same, because there need to be some boxing in the container to distinguish between the two possible types. For me, the surprising part is that fill_intunion does not allocate, what may be some optimization for Nothing and immutable types that just wrap a primitive.
fill_vector does not make a lot of sense to me because, in the end, all positions of the container will share the same data field. If you add an element to any VectorItem in any position of container then it will be show up in the VectorItems in all positions of container.

Sukera · August 12, 2021, 7:19pm

That’s most likely the isbits optimization at play here, storing everything inline.

Lars_Wander · August 12, 2021, 7:28pm

@Sukera – good observation – that makes sense. I don’t understand why that type tag needs to be allocated for every assignment though. I would have guessed that my declaration of vectorunion would have allocated the necessary space already, and that the subsequent assignments would be free.

@Henrique_Becker – re comment #1: I had the same thought, but don’t understand why we need to do an allocation to handle the boxing. fill_vector shows us that we can bindly copy the immutable struct, and fill_intunion shows us we can copy the bits into the union without allocating. re comment #2: It’s just a MWE; you’re right it’s not doing anything useful

Perhaps it’s a shortcoming of the isbits optimization?

lmiq · August 12, 2021, 7:33pm

Yet that is what Base.fill does:

julia> x = fill(rand(2),5)
5-element Vector{Vector{Float64}}:
 [0.2553936445168197, 0.3833650853568562]
 [0.2553936445168197, 0.3833650853568562]
 [0.2553936445168197, 0.3833650853568562]
 [0.2553936445168197, 0.3833650853568562]
 [0.2553936445168197, 0.3833650853568562]

julia> x[1] .= [0.,0.]
2-element Vector{Float64}:
 0.0
 0.0

julia> x
5-element Vector{Vector{Float64}}:
 [0.0, 0.0]
 [0.0, 0.0]
 [0.0, 0.0]
 [0.0, 0.0]
 [0.0, 0.0]

that is quite confusing for many people, but sort of off topic here.

Sukera · August 12, 2021, 7:33pm

The declaration of vectorunion probably only allocates the space for individual pointers to objects - the box itself has the typetag and a pointer to the real data. I bet you’ll see no (or maybe half? not sure) the allocations when assigning nothing, because nothing still has to be boxed (though the data may be stored inline in the box itself, that’s the part I’m not 100% sure about).

Lars_Wander · August 12, 2021, 7:39pm

You’re right, the assignment of nothing into vectorunion creates 0 allocations, according to --track-allocation=user. I suppose I’ll have to live with this for now, and stop using Union{Nothing, T} to avoid extra allocations!

Thanks all.

lmiq · August 12, 2021, 7:42pm

Since there is no direct solution, you may try to use a structure like:

struct A
  isnothing::Bool
  x::Vector{Int}
end

Base.isnothing(a::A) = a.isnothing

work with containers of that type instead of containers of Union types, and adapt the code accordingly.

Well, if that turns out to be critical and you can deal with that data structure instead.

Sukera · August 12, 2021, 7:53pm

Since you’ve mentioned you have a Vector{Tile}, may I ask what the Nothing was supposed to represent in the first place? The absence of a tile? No tile? An empty tile?

Lars_Wander · August 12, 2021, 8:05pm

@lmiq – that is roughly what I wound up doing. Didn’t know about Base.isnothing though, that’s neat! Thanks, will also mark that as a solution.

@Sukera – exactly, it represents the absence of a tile.

Sukera · August 12, 2021, 8:36pm

Discourse can only have one solution per topic, sorry

Hm – if accessing that Vector is performance critical, I’d explicitly model an “absence” tile and not render/draw/use it when it occurs. If speed is not critical (though you’ll have to test if this is really too slow), I’d either invert the organizational structure (i.e., use a sorted Dict of coordinates to tiles, which may be constants and not save the “absence” of a tile at all) or add the absence field like @lmiq suggested (this of course comes at the cost of making the struct larger, if that’s a concern).

How many tiles are we talking about?