Nested Parametric Types and Collections

General Usage
1

I’m having trouble understand parametric types and mixing parameters in collections. For example,

struct Foo{T, S}
    a::T
    b::S
end

If I have this definition I can do the following:

a = Foo(1, 2)
b = Foo(1., 2)
c = Foo(1., 2.)

v = Foo[]
push!(v, a)
push!(v, b)
push!(v, c)

I know v is going to be filled with items of type Foo, but not the specific type parameters ahead of time. That’s okay, this works.

3-element Vector{Foo}:
Foo{Int64, Int64}(1, 2)
Foo{Float64, Int64}(1.0, 2)
Foo{Float64, Float64}(1.0, 2.0)

Now if I extend this with another wrapper type

struct Bar{T}
    a::T
end

The following fails and I’m unclear why

v = Bar{Foo}[]
push!(v, Bar(a))

ERROR: MethodError: Cannot convert an object of type
Bar{Foo{Int64, Int64}} to an object of type
Bar{Foo}
Closest candidates are:
convert(::Type{T}, ::T) where T at /Applications/Julia-1.7.app/Contents/Resources/julia/share/julia/base/essentials.jl:218
Bar{T}(::Any) where T at REPL[11]:2

I’m not clear why the second fails and the first does not. Any tips on how to get this sort of pattern working?

2

I’m not good enough at Julia to tell whether this is a good idea but defining

v = Bar{<:Foo}[]
push!(v,Bar(a))

does work. The <:denotes that the type parameter for Bar should subtype Foo

3 Likes
3

Note that in both cases the resulting vector is a container associated to abstract types, and that can be detrimental for performance.

2 Likes
4

Is the performance detriment because the length of the vector and the type doesn’t tell you number of bits?

In general, is there a “best way” to approach this problem? Specifically, having a collection different types and dispatching on each element individually?

5

Although the concrete type Foo{Int64, Int64} is subtype of the parametric type Foo, the concrete type Bar{Foo{Int64, Int64}} is not a subtype of the concrete type Bar{Foo}. Look up “even though Float64 <: Real we DO NOT have Point{Float64} <: Point{Real}” in the docs.

Bar{<:Foo} is syntactic sugar for Bar{T} where T<:Foo, and Bar{Foo{Int64, Int64}} is very much a subtype of that.

6

You’re on the right track, it’s related to why I specified “concrete type Bar{Foo}”. Let’s use Vector{T} as an example, 1-dimensional arrays are familiar.

When T is concrete (and isbits) e.g. Vector{Int64}, each element has a known layout and size (Int64 is 8 bytes), so the array’s elements can be laid next to each other in 1 contiguous block of memory. This makes linear memory accesses efficient and can enable SIMD to save time (simultaneous operations on multiple elements).

When T is abstract e.g. Vector{Real}. each element can be any subtype of Real, so the size is unfixed. An array’s O(1)-indexing really relies on each element’s size being the same, so pointers are laid next to each other in 1 contiguous block. Each pointer specifies the memory address of a separately allocated instance. Because the array’s data is scattered all over the memory, access and calculations need to spend more time doing more work.

Note that each Vector{Int64} and Vector{Real} have specific implementations, and these implementations are different. In other words, they are both concrete types, and concrete types cannot subtype each other, even if their parameters do (Int64<:Real). They are both subtypes of the iterated union type Vector{T} where T<:Real. You can probably draw the parallels to your Foo{Int64, Int64}, Foo, Bar{Foo{Int64, Int64}}, and Bar{Foo}.

1 Like
7

This is incredibly helpful. Thank you for taking the time. A few followup questions as I digest this.

I understand that O(1) indexing doesn’t work if element sizes aren’t the same. Is there also a penalty for iteration?

The use case I’m grappling with is something like the following:

I have a collection of data of different types - let’s say it’s different subtypes of AbstractMatrix - Diagonal, Sparse, etc. At run time I don’t know how many of each to expect, however I have specialized methods that efficiently process each subtype. I then iterate over the collection dispatching to the correct method for each element.

It seems like a trade between the performance penalty of having a collection of a Abstract Type and the benefit of having specialized methods. I could promote each type, but there’s a penalty in the promotion and also the extra processing from losing specialized methods. Is there another approach I’m missing that avoids this trade?

8

If the time to process each Matrix dominates, you should not worry.

9

Maybe this wasn’t made clear, but Vector{Real} does have O(1) indexing because it has a contiguous block of pointers of a fixed size, even if the actual instance of an element is allocated elsewhere and can be any size.

AFAIK, iteration is generally easier to implement as O(1). Think of linked lists where each scattered element is attached to a pointer to the next element, accessing that pointer is O(1). With arrays, you move a fixed number of bytes to the next element, and sometimes the element is implemented as a pointer you access to get the actual instance; that’s also O(1).

Indexing is harder, and it’s easy to see why. What happens when you’re currently on index 1 of a linked list and you want index 8? You have to access the pointer to index 2, then the one to index 3, then to index 4, etc. The amount of work you need to do depends on where you started, that’s not O(1). If you want to access the index (3,1,2) of a multidimensional array, based on the dimensions you know that you need move N bytes 2 times, M bytes 1 time, and L bytes 3 times, or move(a, b, c) = N*a + M*b + L*c. You do the same calculation for any index, so it’s O(1).

10

All this makes sense in theory - I’m usually confused with how it works under the hood in Julia. For example, where does the logic of Vector{X} being an continuous block of pointers with O(1) indexing break down? Perhaps naively, it seems like my original example of v = Bar{<:Foo}[] might also be implemented as contiguous pointers vs a linked list? How would I test this? Or are there general rules to learn for Julia?

11

Core.Array is a subtype of Core.DenseArray, which is documented to have contiguous elements in memory, so you can absolutely count on that. It’s unusual for implementation details to be documented or ingrained in the type system because it locks the language into something, but this is just how multidimensional arrays are implemented across many languages for decades.
Pointers implementing fields and elements restricted by abstract types is also documented in the “Parametric Composite Types” section I linked earlier. It doesn’t always happen though, there is an optimization for a kind of abstract type: isbits Unions (implied <= 256 isbits types). This being documented in the devdocs makes it apparent this is the more typical internal implementation detail you’re not supposed to control or count on. I’m pretty sure the @code_llvm of indexing an array can reveal if this is happening, but I’ve never been able to read assembly.

1 Like