Type Stability: Collections of Abstract Types

I’ve been struggling with vectors of abstract types and making them type stable. Here is an example:

abstract type Home{T<:String} end

mutable struct Condo{T} <: Home{T}
    color::T
end

struct Apartment{T} <: Home{T}
    color::T
end

myHomes = [Condo("Red"), Apartment("Blue")]


function getFirstColor(A::Vector{Home{String}})
    return A[1].color
end

Here the function getFirstColor() works as intended, but when I check type stability I get this:

@code_warntype getFirstColor(myHomes)
Variables
  #self#::Core.Const(getFirstColor)
  A::Vector{Home{String}}

Body::Any
1 ─ %1 = Base.getindex(A, 1)::Home{String}
│   %2 = Base.getproperty(%1, :color)::Any
└──      return %2

Julia can’t determine the type of color. I’ve tried reading the documentation and this section seems to relevant, but no variations I try seem to work. Any help is appreciated!

1 Like

You can inform the return type of getproperty, and that improves a little bit things:

function getFirstColor2(A::Vector{<:Home{String}})
    return A[1].color::String
end

julia> @code_warntype getFirstColor2(myHomes)
Variables
  #self#::Core.Const(getFirstColor2)
  A::Vector{Home{String}}

Body::String
1 ─ %1 = Base.getindex(A, 1)::Home{String}
│   %2 = Base.getproperty(%1, :color)::Any
│   %3 = Core.typeassert(%2, Main.String)::String
└──      return %3

At least the return type is correct and possible instabilities won’t scape this function.

It gets a little bit better if the list is defined with a union of a small number of types, such as:

myHomes2 = Union{Condo{String},Apartment{String}}[Condo("Red"), Apartment("Blue")]

You get a better output even with your original function:

julia> @code_warntype getFirstColor(myHomes2)
Variables
  #self#::Core.Const(getFirstColor)
  A::Vector{Union{Apartment{String}, Condo{String}}}

Body::String
1 ─ %1 = Base.getindex(A, 1)::Union{Apartment{String}, Condo{String}}
│   %2 = Base.getproperty(%1, :color)::String
└──      return %2

But arrays of mixed types result to never be ideal, at some point the compiler will quit trying to infer the return types.

Note that nothing prevents you from defining

struct House{T} <: Home{T}
   color::Int
end

thus, there in an intrinsic indefinition of the type of color, even with the parameter T.

1 Like

Fundamentally getindex on Vectors of abstract types isn’t type stable.
The point of type stability is that the compiler should be able to know which concrete type it will get.
That way it can know which method instance it will dispatch to and can do a static dispatch (or even inline the code for it).
You can’t do that for an abstract type.
Even if there is 1 method for the abstract type there will still be 1 method instance for each concrete subtype).

Further up in the page you linked it explicit tells you to avoid them for performance.
https://docs.julialang.org/en/v1/manual/performance-tips/#man-performance-abstract-container

Firstly though, profile your code to see if this is actually your bottleneck.
A bit of type instability is no big deal, unless it is in a hot-loop.

Assuming you have profiled and found that this is a problem:

If you collection size is small, and you are not mutating the collection use a Tuple. They are designed for small heterogeneous collections.

Otherwise, use the Vector and introduce a function barrier.
I.e. a function that taked the result of getindex as an input.

It would be surprising if after that it is still your bottleneck.
But if it is then you might have to look it not a fancier datastructure than a single array. E.g. using 1 array per type.

6 Likes

Both of these solutions have their pros and cons and I would probably go with the Union solution if the number of sub-types was fixed and small. I’m a little confused by the last code snippet with the House struct. If I give a color a concrete type it doesn’t seem to help.

No, no. That was only to illustrate that the type of color cannot be inferred, in principle, for every subtype of Home{String}. Thus the intrinsic instabilities that arise.

By the way, one could make that type stable if instead of an abstract type you had a composed type, with color being a concrete field of Home, and other field being a parametric field with additional data for the specific type of home.

struct Home{T}
  color::String
  type::T
end
struct Apartment
  stage::Int
end

Home{Apartment}("Red", Apartment(3))

Sort off… on my phone. Still that won’t solve possible run time dispatch costs for a vector of mixed types.

Ultimately I think this is my problem and I should try to avoid vectors of abstract types unless completely necessary. This pattern does end up in a pretty computationally expensive part of the code and the uncertainty in the type propagates down which I think slows everything down. I think I’ll have to try one the methods you mentioned, hopefully it doesn’t come down to changing data structure.

2 Likes