Understanding specialization and parametric types

New to Julia
,
1

EDITSTART
The following link @Tamas_Papp posted in the solution might help everyone with similar questions.
https://docs.julialang.org/en/v1/manual/methods/#Design-Patterns-with-Parametric-Methods-1
EDITEND

Right now I try to understand how specialization and parametric types interact. The following all came up when trying to design a sliding window iterator (iterator that shall return a slided view of an array in each iteration step)
Code so far, not yet working as we are missing an iterate function etc:

using IdentityRanges

struct SlidingWindowIterator #1
    array::AbstractArray #2
    range::CartesianIndices #3
    validindices::CartesianIndices #3
end

#3 is the set of indices of array that have all needed indices forrange as valid indices around them.

Objectives: Make it specialize for the array type and the dimension (Are there other attributes that should be parametrized for performance reasons?). Also enforce all 3 arguments to be of the same dimension. And have a constructor that fills in all parameter types automatically. How to do that?

2

I think something like this is what you’re after:

struct SlidingWindowIterator{T<:AbstractArray} #1
    array::T #2
    range::CartesianIndices #3
    validindices::CartesianIndices #3
    function SlidingWindowIterator(array::T, range, validindices) where T <: AbstractArray
        if false # do your validation here
            error("invalid indices")
        end
        return new{T}(array, range, validindices)
    end
end

By parameterizing the type on the specific type of AbstractArray that array is, you define a family of types, each with a storage layout optimized for the specific array type that gets passed in.

The function inside the struct definition is an inner constructor, which becomes the only way to construct the type. You can perform any needed validation there.

Actually, you should also specialize the types of the indices, since CartesianIndices is also an abstract type. Here I gave both index ranges the same type, since they’re both supposed to be indices for the same array:

struct SlidingWindowIteratorTwo{T<:AbstractArray, I<:CartesianIndices} #1
    array::T #2
    range::I #3
    validindices::I #3
    function SlidingWindowIteratorTwo(array::T, range::I, validindices::I) where {T <: AbstractArray, I <: CartesianIndices}
        if false # do your validation here
            error("invalid indices")
        end
        return new{T, I}(array, range, validindices)
    end
end
3

Assuming that I can collect the iteration values after collapsing each window into a single value, the validindices field will become the indices of the newly collected array. Thus they probably need to support non-1-based indexing. Likewise for range. Thus I will probably need different types for them.

Now, I need access to the dimensions of the array in order to implement the

Base.IteratorSize(::Type{SlidingWindowIterator}) = HasShape{N} #6

How can I solve that best?

4

I now did it that way:

Base.IteratorSize(::Type{SlidingWindowIterator{AT,A,B}}) where {T,N,AT<:AbstractArray{T,N},A,B} = Base.HasShape{N}() #6

Ist there any possibility to somehow prevent specialization on T, A and B? Or maybe even to not list them. Something like {AT,_,_} would be cool

5

If you don’t need the type parameters, you can just do

Base.IteratorSize(::Type{<:SlidingWindowIterator}) = ...
6

I need the AT parameter because I need the N parameter for the dimension. Is there a better solution that doesn’t force me to have 5 type parameters (some of them nested) to use a single type parameter? Maybe even preventing to specialize on unneeded type params.

7

If you just need the N from the AT, you can do

Base.IteratorSize(::Type{<:SlidingWindowIterator{AT}}) = somehow_use(ndims(AT))
8

Like that?:

Base.IteratorSize(::Type{<:SlidingWindowIterator{AT}}) where AT = Base.HasShape{ndims(AT)}()

or that

Base.IteratorSize(::Type{<:SlidingWindowIterator{AT}}) where {AT<:AbstractArray} = Base.HasShape{ndims(AT)}()

It feels quite weird to use functions in the type parameters. Can this be efficiently compiled? Because the dimension is available at compiletime due to the type parameter but some functions are first called at runtime so this might cannot be optimized to the end. Is that correct?

Also, what to do if AT is not the first type parameter of SlidingWindowIterator?

9

No, it is not weird. The compiler should be able to optimize it out for concrete types.

Include other type parameters before it, rewrite your code that it is the first one, or define an accessor function (eg like ndims). See

https://docs.julialang.org/en/v1/manual/methods/#Design-Patterns-with-Parametric-Methods-1

10

I didn’t know that page. Very much thanks for it!! I’ll link it at the first post for everyone else who might arrive here :slight_smile: