Init windowing

[JanJereczek]

Implements:

• bracketing (left, center, right)
• WindowViewer struct and underlying iterator
• test for windowing with variance operation

[Datseris]

Is this ready to review?

[Datseris]

remember that you have to push the commits here

[JanJereczek]

Everything should be corrected. Commits are pushed correctly, right?

[JanJereczek]

Added benchmarks.jl to compare performance of mapping over WindowViewer. For now no use of PkgBenchmark.jl (not sure how to set up properly - any examples you can recommend?)

[Datseris]

do not worry about PkgBenchmarks.jl now. IN the future, we will use https://github.com/JuliaDynamics/Agents.jl/tree/main/benchmark as the role model. It even has CI integration to run benchmarks automaticaly on a chosen commit.

[Datseris]

can you please paste here the output of

    @btime map($StatsBase.var, $wv)
    @btime map!($StatsBase.var, $var_x, $vectorized_window)

---

I am confused. Why isn't wv used in the second call to map!? That's the thing we need to be benchmarkiung.... if you can't use map! make your own function that takesi n a pre-allocated vector, loops over the iterator and calls astd like so:

function inplace_map!(p, f, wv)
for (i ,x) in enumerate(wv)
p[i] = f(x)
end
end

and benchmark this.

---

Although you still haven't said why map! doesn't work. If something doesn't work, please always be explcit bout it. As exact as possible. What exactly doesn't work and what exactly is the error. A method arror and a bounds error are two completely different things that qualify as "doesn't work".

[JanJereczek]

Output of

    @btime map($StatsBase.var, $wv)
    @btime map!($StatsBase.var, $var_x, $vectorized_window)

yields:

  125.981 ms (5997433 allocations: 156.36 MiB)
  8.917 ms (0 allocations: 0 bytes)

---

I had implemented the in-place function you suggest. However this implementation was the slowest among all. Here goes the code:

function inplace_map!(f::Function, y::Vector{T}, wv::WindowViewer) where {T<:Real}
    for (i, windowview) in enumerate(wv)
        y[i] = f(windowview)
    end
end

var_x = zeros(length(wv.strided_indices))
@btime inplace_map!($StatsBase.var, $var_x, $wv)

And its output:

  193.759 ms (8496395 allocations: 251.71 MiB)

Next time I will include this kind of information in the comments.

---

map! had not worked because of a MethodError, here goes the full error message:

MethodError: no method matching map!(::typeof(var), ::Vector{Float64}, ::WindowViewer{Int64, Vector{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

That's why I had turned the last input into a vector of vectors (vectorized_window). We could redefine map! for WindowViewer as last input by defining vectorized_window in WindowViewer.

[Datseris]

I had implemented the in-place function you suggest. However this implementation was the slowest among all. Here goes the code:

That's exactly why we do these benchmarks. This shows us that the current implementation of the window mapper is inccorect. This in place function should have zero allocations by definition: it does views, computes only real nuimbers, and assigns them in pre-allocated place in memory. There is no operation that "should" be generatiung allocations.

It's probably because you define Base.eltype(::Type{WindowViewer}) = AbstractVector{<:Real} which is type unstable. Have you had a look at the Julia documentation on type stability and performance tips? (I also say therse things in the first chapter of my Zero2Hero tutorial).

In any case I propose tha we have a 30 minute live call omorrow morning, e.g. 10am, and optimize the code live. I will checkout the pr and do the commits and you can learn along the way?

[JanJereczek]

Sure, let's do this. 10am CET?

I had a look at the performance tips. In fact all the stuff I programmed in my fork are type-stable. I am just inexperienced in redefining Base.iterate. I think I understand why Base.eltype(::Type{WindowViewer}) = AbstractVector{<:Real} leads to a type instability but I don't know how to correct this. So your help is welcome and appreciated.

[Datseris]

ok 10 am CET

[JanJereczek]

Just saw that there is a pretty interesting talk at PIK at 10 am. Would 11 am work for you too? If not, I can also skip it :) Let's use the link from last time?

[Datseris]

11 is ok

[Datseris]

Yeah, some pretty major type instabilities here:

Any is the worst possible type youcan have here. Use the macro @code_warntype when you develop code. Over time you will have memorized all the rules :D I'll show you the solution to our problem in our call in an hour,.