Unintuitive behavior for iterator of views of a vector

General Usage Performance
1

We are creating a simple iterator whose goal is to generate views of a given vector (something like a sliding window). However, the Julia behavior on this object is rather unituitive to me, with weird type instabilities and unexpected map! behavior. Here is the object as a MWE:

struct WindowViewer{T, V<:AbstractVector{T}, I<:AbstractVector{Int}}
    timeseries::V
    halfwidth::Int
    stride::Int
    strided_indices::I
end

function WindowViewer(
        timeseries::V, halfwidth::Int, stride::Int,
    ) where {T<:Real, V<:AbstractVector{<:T}}
    n = length(timeseries)
    strided_indices = 2*halfwidth+1:stride:n
    I = typeof(strided_indices)
    return WindowViewer{T,V,I}(timeseries, halfwidth, stride, strided_indices)
end

# extend iterator interface:
function Base.iterate(wv::WindowViewer, state::Int = 1)
    if state > length(wv.strided_indices)               # Stop condition: end of vector containing strided indices.
        return nothing
    else
        k = wv.strided_indices[state]
        i1, i2 = (k-2*wv.halfwidth, k)
        return (view(wv.timeseries, i1:i2), state + 1)  # Else: return a view of time series.
    end
end

function Base.eltype(::Type{WindowViewer{T,V}}) where {T,V}
    return SubArray{T, 1, V, Tuple{UnitRange{Int64}}, true}
end
Base.length(wv::WindowViewer) = length(wv.strided_indices)
Base.size(wv::WindowViewer) = (length(wv),)

Now, when I create this object, I get some very weird behavior. Even though the actual iteration works as planned, e.g.,

julia> wv = WindowViewer(collect(1:1_000_000), 2, 2)
WindowViewer{Int64, Vector{Int64}, StepRange{Int64, Int64}}([1, 2, 3, 4, 5, 6, 7, 8, 9, 10  …  999991, 999992, 999993, 999994, 999995, 999996, 999997, 999998, 999999, 1000000], 2, 2, 5:2:999999)

julia> [x for x in wv]
499998-element Vector{SubArray{Int64, 1, Vector{Int64}, Tuple{UnitRange{Int64}}, true}}:
 [1, 2, 3, 4, 5]
 [3, 4, 5, 6, 7]
 [5, 6, 7, 8, 9]
 [7, 8, 9, 10, 11]
 [9, 10, 11, 12, 13]
 [11, 12, 13, 14, 15]
 [13, 14, 15, 16, 17]
 [15, 16, 17, 18, 19]
 [17, 18, 19, 20, 21]

(notice this is type stable)

map!, and collect, don’t work as expected, and iteration is allocating. Examples:

var_x = zeros(length(wv))
map!(var, var_x, wv)

ERROR: MethodError: no method matching map!(::typeof(var), ::Vector{Float64}, ::WindowViewer{Int64, Vector{Int64}, StepRange{Int64, Int64}})
Closest candidates are:
  map!(::F, ::AbstractArray, ::AbstractArray) where F at abstractarray.jl:2924     
  map!(::F, ::AbstractArray, ::AbstractArray, ::AbstractArray) where F at abstractarray.jl:2967
  map!(::F, ::AbstractArray, ::AbstractArray...) where F at abstractarray.jl:3024  
  ...

and

julia> eltype(wv)
Any

and

using BenchmarkTools
function inplace_map!(f::Function, y::Vector{T}, wv::WindowViewer) where {T<:Real}
    @inbounds for (i, windowview) in enumerate(wv)
        y[i] = f(windowview)
    end
end
@btime inplace_map!($var, $var_x, $wv)

  12.057 ms (1 allocation: 64 bytes)

(notice the 1 allocation).

So my questions are:

  1. Why isn’t map! working out of the box.
  2. Why is the iterator type unstable when it comes to eltype and collect even though I’ve defined its element type correctly
  3. Why is my inplace_map! allocating?
2

Looks like map! is only defined for AbstractArray in the third argument.

Because you didn’t define its element type correctly :):

julia> @which eltype(typeof(wv))
eltype(::Type) in Base at abstractarray.jl:204

You need

function Base.eltype(::Type{<:WindowViewer{T,V}}) where {T,V}
    return SubArray{T, 1, V, Tuple{UnitRange{Int64}}, true}
end

julia> @btime inplace_map!(Statistics.var, $var_x, $wv)
  11.026 ms (0 allocations: 0 bytes)

julia> VERSION
v"1.8.2"

I think fixing the eltype takes care of the one allocation.

1 Like