# Type stability and heterogeneous collections

**URL:** <https://discourse.julialang.org/t/type-stability-and-heterogeneous-collections/112293>\
**Category:** Performance\
**Tags:** question\
**Created:** [March 29, 2024, 2:38pm UTC](https://discourse.julialang.org/t/type-stability-and-heterogeneous-collections/112293 "2024-03-29T14:38:05Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![andreapasquale94](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/andreapasquale94/32/37559_2.png) [@andreapasquale94](https://discourse.julialang.org/u/andreapasquale94)\
**Post date:** [March 29, 2024, 2:38pm UTC](https://discourse.julialang.org/t/type-stability-and-heterogeneous-collections/112293/1 "2024-03-29T14:38:05Z")

</div>

I am working on a library where I cannot avoid heterogeneous collections, and I want type-stable code.  
I’m trying to improve my understanding of how the compiler behaves in those cases (and in general).

There are already different discussions here related to this topic:

- [Type stable accumulator over heterogeneous collection](https://discourse.julialang.org/t/type-stable-accumulator-over-heterogeneous-collection/5448)
- [Type instability with Union or heterogenous array/tuple](https://discourse.julialang.org/t/type-instability-with-union-or-heterogenous-array-tuple/78122)
- [How is the type of a heterogeneous vector determined when splatting and doing list comprehension?](https://discourse.julialang.org/t/how-is-the-type-of-a-heterogeneous-vector-determined-when-splatting-and-doing-list-comprehension/92572)

But they do not fully address my doubts.

My question is associated with the following MWE, divided into two parts.

```julia
# First part
abstract type BaseType{T} end

getvalue(::BaseType, t) = error("Not implemented") 
Base.eltype(::Type{<:BaseType{T}}) where T = T
veltype(::AbstractVector{<:BaseType{T}}) where T = T

struct A{T} <: BaseType{T}
    x::T
end
A(x::T) where T = A{T}(x) 
getvalue(s::A, t) = s.x + cos(t)

struct B{T} <: BaseType{T}
    x::T
end
B(x::T) where T = B{T}(x) 
getvalue(s::B, t) = s.x + sin(t)

function loop(v, t) 
    val = zero(veltype(v))
    for vi in v 
        val += getvalue(vi, t)
    end
    return val
end

N = 10
v = [i % 2 == 0 ? A(1.0) : B(1.0) for i in 1:N];
t = 1.0

loop(v, t);
@btime loop($v, $t);

# Second part
struct C{T, N} <: BaseType{T}
    x::T
end
C(x::T, n) where T = C{T, n}(x) 
getvalue(s::C{T, N}, t) where {T, N} = s.x + t

loop(v, 0.0);
@btime loop($v, $t);

```

I believe the **first** part is a _fine_ implementation that exploits function barriers, although I’m not sure if can be improved further. My understanding is that within the `loop` function the `getvalue` return type is statically dispatched, which is also what I got from `@code_warntype` (e.g. in this case `Body::Float64`).

Now adding the **second** part messes up the type stability completely, the `Body` now is `Any` and the whole program allocates, although `C` is not used at all here, and `veltype(v)` returns the correct type (e.g. `Float64`).

Can someone help with this? 🙂

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [March 29, 2024, 3:01pm UTC](https://discourse.julialang.org/t/type-stability-and-heterogeneous-collections/112293/2 "2024-03-29T15:01:14Z")

</div>

It’s the vector `v`. It has type `BaseType{Float64}`. That is an abstract type, and I believe there is some special casing when there are very few subtypes. So the compiler can figure out that even if `vi` in the loop is only known to be the abstract `BaseType{Float64}`, it can look at the two possible concrete types and figure out that `getvalue(vi, t)` will be a `Float64`. I believe it gives up on this if there are too many subtypes. (Though I thought “too many” was larger than 3. Five or something). If you use `v = Union{A{Float64}, B{Float64}}[...]`, it is still able to infer the type correctly.

I had a similar problem some years ago, and solved it by letting `BaseType{T}` be concrete, but with a field `type::Symbol` which I used for dispatch where needed. There could be better ways, I’m not sure.

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [March 29, 2024, 3:08pm UTC](https://discourse.julialang.org/t/type-stability-and-heterogeneous-collections/112293/3 "2024-03-29T15:08:18Z")

</div>

Actually, it even infers if `v = Union{B{Float64}, A{Float64}, C{Float64}}[...]`.

---

<div class="post-metadata">

**Author:** ![andreapasquale94](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/andreapasquale94/32/37559_2.png) [@andreapasquale94](https://discourse.julialang.org/u/andreapasquale94)\
**Post date:** [March 29, 2024, 3:17pm UTC](https://discourse.julialang.org/t/type-stability-and-heterogeneous-collections/112293/4 "2024-03-29T15:17:22Z")

</div>

Thank you @sgaure! Indeed the previous case happens to be a lucky case as just inserting more concrete types does present the same issue:

```julia
abstract type BaseType{T} end

getvalue(::BaseType, t) = error("Not implemented") 
Base.eltype(::Type{<:BaseType{T}}) where T = T
veltype(::AbstractVector{<:BaseType{T}}) where T = T

for s in [:A, :B, :C, :D, :E, :F, :G]
    @eval begin 
        struct $s{T} <: BaseType{T}
            x::T
        end
        $s(x::T) where T = $s{T}(x) 
        getvalue(s::$s, t) where T = s.x + t
    end
end

function loop(v, t) 
    val = zero(veltype(v))
    for vi in v 
        val += getvalue(vi, t)
    end
    return val
end

N = 10
v = [i % 2 == 0 ? A(1.0) : B(1.0) for i in 1:N];
t = 1.0

loop(v, t);
@btime loop($v, $t);

```

The approach you proposed is the one I already have used in [FramesTransformation.jl](https://github.com/JuliaSpaceMissionDesign/FrameTransformations.jl/blob/4d17dc8dd5cf51f28506a1e265f8bc31def1ee01/src/Frames/types.jl#L206). That was an acceptable solution for that case, but here the idea is to have concrete types that share an interface only, e.g. could be radically different inside.

Some time ago I also wrote down a relatively simple package to avoid that ([MixedTypesContainers.jl](https://github.com/JuliaSpaceMissionDesign/MixedTypesContainers.jl)), that is similar to [Unrolled.jl](https://github.com/cstjean/Unrolled.jl) but I was looking for alternative solutions and trying to understand how inference works here.

---

<div class="post-metadata">

**Author:** ![Tortar](https://avatars.discourse-cdn.com/v4/letter/t/6bbea6/32.png) [@Tortar](https://discourse.julialang.org/u/Tortar)\
**Post date:** [March 29, 2024, 4:57pm UTC](https://discourse.julialang.org/t/type-stability-and-heterogeneous-collections/112293/5 "2024-03-29T16:57:24Z")

</div>

I created this package some time ago: [MixedStructTypes.jl](https://github.com/JuliaDynamics/MixedStructTypes.jl). It should allow you to keep type-stability when operating on multiple types, the only downside is that you need to use branching instead of dispatch for operating differently based on the type if you want to keep max performance. Also, if your types are radically different, with many fields and instances, I would use the `@sum_structs` in the package, it is a little slower but much better on the memory side, it is a sum type under the hood. I tried to make it possible to operate with the types defined by the package as similar as possible to normal structs, so It should be easy to work with them as well. Let me know if this helps you 🙂

---

<div class="post-metadata">

**Author:** ![sgaure](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sgaure/32/14779_2.png) [@sgaure](https://discourse.julialang.org/u/sgaure)\
**Post date:** [March 29, 2024, 5:36pm UTC](https://discourse.julialang.org/t/type-stability-and-heterogeneous-collections/112293/6 "2024-03-29T17:36:09Z")

</div>

I think the dispatch of `getvalue(vi, t)` looks at `methods(getvalue, (eltype(v), typeof(t)))`, or rather the instantiations of the methods. The compiler creates fast dispatch code if there are three or less choices in the list, otherwise it dispatches at runtime. So, if you ditch the `getvalue(::BaseType, t)` your first example will actually work. But it quickly grows too large.

Compared to runtime dispatch of virtual methods in C++, julia is slow. I think I read a discussion somewhere. It’s not as easy as in C++ with a quick lookup in a vtable, because of multiple dispatch and dynamic things. Though, I’m uncertain whether it could be speeded up; possibly at a compile time cost with the invalidations when new subtypes are introduced.