Why do we need `iteratoreltype()`?

Question

I am not sure I understand why IteratorEltype() is needed. Every iterable is guaranteed to produce objects of type Any, so if you don't know any better then you can always default to that. What is the point of distinguishing between "I know it could be anything" (IteratorEltype == HasEltype && eltype = Any) and "I don't know what it is, hence it could be anything" (IteratorEltype == EltypeUnknown)?

The only type in Base Julia which uses EltypeUnknown() I could find is Generator, which is the tool behind the (f(i) for i in iter) syntax. I can imagine that it is hard / impossible to find the eltype of such a generator if eltype(iter) is a non-leaf type, but what is the advantage of not simply setting the eltype to Any in this case? Of course, you wouldn't want it to be Any if eltype(iter) is a leaf-type and f is type-stable, but those two cases should be distinguishable at compile-time.

user_1734710 · Answer

The difference between the two IteratorEltype() options is as follows:

HasEltype() says that the values of the iterator should be treated as objects of type eltype(), even if eltype() is more general than the types actually encountered in the iterator.
EltypeUnknown() asks functions like collect() to figure out the most specific type applicable to all elements.

Example:

julia> abstract type Wrapper end
       Base.length(w::Wrapper) = length(w.data)
       Base.iterate(w::Wrapper, s...) = iterate(w.data, s...)

       struct EltypeWrapper{T,D} <: Wrapper
           data::D
       end
       EltypeWrapper{T}(data) where T = EltypeWrapper{T,typeof(data)}(data)
       Base.eltype(::Type{<:EltypeWrapper{T}}) where T = T

       struct EltypeUnknownWrapper{D} <: Wrapper
           data::D
       end
       Base.IteratorEltype(::Type{<:EltypeUnknownWrapper}) = Base.EltypeUnknown()

julia> collect(EltypeWrapper{Any}(Any[1,2.0]))
2-element Array{Any,1}:
 1  
 2.0

julia> collect(EltypeUnknownWrapper(Any[1,2.0]))
2-element Array{Real,1}:
 1  
 2.0

Note that the two arrays have the same entries, but the first has type Vector{Any} while the second has type Vector{Real}.

It may seem that HasEltype() should be more efficient because it allows for preallocation of the output in functions like collect(). Julia is pretty good at inferring the iterator eltype, however, and EltypeUnknown() can be as fast as (or for some weird reason even faster than) HasEltype():

julia> using BenchmarkTools

       abstract type AbstractIterable end
       struct TypedIterable <: AbstractIterable; end
       struct UntypedIterable <: AbstractIterable; end
           
       Base.length(::AbstractIterable) = 100000

       Base.eltype(::Type{TypedIterable}) = Int
       Base.IteratorEltype(::Type{UntypedIterable}) = Base.EltypeUnknown()

       function Base.iterate(f::AbstractIterable,i = 1)
           i > length(f) && return nothing
           return i, i+1
       end

       @btime collect(UntypedIterable())
       @btime collect(TypedIterable())
       ;
  43.033 μs (2 allocations: 781.33 KiB)
  56.772 μs (2 allocations: 781.33 KiB)

IteratorEltype() thus not necessarily impacts the performance of working with the iterator, but it may heavily impact the performance further up in the call stack. Almost all code is order of magnitudes faster if it operates on leaf types, thus in can be much faster to put EltypeUnknown() as the IteratorEltype() and hope that the eltype() boils down to a concrete type rather than to set IteratorEltype() = HasEltype() and then set eltype() to some abstract type.

Why do we need `iteratoreltype()`?

1 Answers