# ANN: ReduceWindows.jl

**URL:** <https://discourse.julialang.org/t/ann-reducewindows-jl/98094>\
**Category:** General Usage\
**Tags:** announcement\
**Created:** [April 29, 2023, 5:17pm UTC](https://discourse.julialang.org/t/ann-reducewindows-jl/98094 "2023-04-29T17:17:05Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [April 29, 2023, 5:17pm UTC](https://discourse.julialang.org/t/ann-reducewindows-jl/98094/1 "2023-04-29T17:17:05Z")

</div>

I am happy to announce [ReduceWindows.jl](https://github.com/jw3126/ReduceWindows.jl/tree/main). The package allows to apply `reduce` over a sliding window. From the Readme:

# Usage

```julia
using ReduceWindows
x = [1,2,3,4,5]
reduce_window(+, x, (-1:1,))
# [3, 6, 9, 12, 9]
reduce_window(max, x, (-1:1,))
# [2, 3, 4, 5, 5]
reduce_window(min, x, (-3:0,))
# [1, 1, 1, 1, 2]

x = [1 2 3; 4 5 6]
reduce_window(*, x, (0:1,0:1))
# 40 180 18
# 20 30 6

```

# Speed

This package has very competitive performance, especially for large windows.

```julia
arr = randn(500,500)
window = (-50:50, -50:50)
using ImageFiltering: mapwindow
mapwindow(maximum, arr, window) # warmup
out1 = @showtime mapwindow(maximum, arr, window)

using ReduceWindows
reduce_window(max, arr, window) # warmup
out2 = @showtime reduce_window(max, arr, window)
@assert out1 == out2

```

```julia-auto
mapwindow(maximum, arr, window): 2.075822 seconds (1.26 M allocations: 227.561 MiB, 0.76% gc time)
reduce_window(max, arr, window): 0.002320 seconds (14 allocations: 7.630 MiB)

```

Naively reducing a windows of size `k` over an array of size `n` is `O(k*n)`.  
However the algorithm implemented here is `O(log(k)*n)` making it practical to reduce over large windows.

```julia
arr = randn(500,500)
window = (-50:50, -50:50)
using ImageFiltering: mapwindow
using ReduceWindows
const OPCOUNT = Ref(0)
function mymax(x,y)
    OPCOUNT[] += 1
    max(x,y)
end

mapwindow(w->reduce(mymax, w), arr, window)
opcount_naive = OPCOUNT[]
OPCOUNT[] = 0
reduce_window(mymax, arr, window)
opcount_reduce_window = OPCOUNT[]
@show opcount_naive
@show opcount_reduce_window

```

```julia-auto
opcount_naive = 2550010200
opcount_reduce_window = 4775000

```

# Alternatives

- [ImageFiltering.jl](https://github.com/JuliaImages/ImageFiltering.jl) much more features than  
this packge, but slow for large windows.
- [MeanFilters.jl](https://github.com/jw3126/MeanFilters.jl) fast, lightwight but very narrow usecase.

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [April 29, 2023, 6:04pm UTC](https://discourse.julialang.org/t/ann-reducewindows-jl/98094/2 "2023-04-29T18:04:27Z")

</div>

Pay attention that the documentation links doesn’t work in both [MeanFilters.jl](https://github.com/jw3126/MeanFilters.jl) and [ReduceWindows.jl](https://github.com/jw3126/ReduceWindows.jl/tree/main).

I think you should mention what’s `0` index is or other way to describe the anchor of the window.  
Also it would be nice to have non allocating ability to set the boundary (Replicate, Constant, etc…).

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [April 29, 2023, 6:22pm UTC](https://discourse.julialang.org/t/ann-reducewindows-jl/98094/3 "2023-04-29T18:22:38Z")

</div>

> [@RoyiAvital](#):
>
> Pay attention that the documentation links doesn’t work in both [MeanFilters.jl](https://github.com/jw3126/MeanFilters.jl) and [ReduceWindows.jl](https://github.com/jw3126/ReduceWindows.jl/tree/main).

Thanks, ~~but for me both of them work.~~ Now I see what you mean. I removed them.

> [@RoyiAvital](#):
>
> I think you should mention what’s `0` index is or other way to describe the anchor of the window.  
> Also it would be nice to have non allocating ability to set the boundary (Replicate, Constant, etc…).

That would be nice. Do you have a good suggestion what you want to read about “anchor” and zero index?

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [April 29, 2023, 6:34pm UTC](https://discourse.julialang.org/t/ann-reducewindows-jl/98094/4 "2023-04-29T18:34:53Z")

</div>

This is what I get:

 ![image](https://global.discourse-cdn.com/julialang/original/3X/3/9/395d2d6bacadc2610af7cc97c5724bb0bcfdd8f7.png)

Could it be that the address is available only to you as a user of GitHub and the owner of the domain?

From what I saw if the input and output arrays are the same size.  
Also if I got it right, the anchor is the zero index. If I got it right, I think it should be mentioned.

On top of that, it would be great to be able to chose how to handle boundaries.  
If I got it right, for now, you just ignore them. Which is OK.  
But it would be great to have something like other modes. You may have a look on [`StaticKernels.jl`](https://github.com/stev47/StaticKernels.jl).  
You also should compare performance with it. [As far as I could see `ImageFiltering.jl` is not fast in some cases](https://github.com/JuliaImages/image_benchmarks/issues/1), so `StaticKernels.jl` might be a better reference (For small windows).

---

<div class="post-metadata">

**Author:** ![jw3126](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jw3126/32/3086_2.png) [@jw3126](https://discourse.julialang.org/u/jw3126)\
**Post date:** [April 29, 2023, 8:08pm UTC](https://discourse.julialang.org/t/ann-reducewindows-jl/98094/5 "2023-04-29T20:08:03Z")

</div>

> [@RoyiAvital](#):
>
> Could it be that the address is available only to you as a user of GitHub and the owner of the domain?

I misunderstood you. You were right. The readme is the only docs. I removed the links.

> [@RoyiAvital](#):
>
> From what I saw if the input and output arrays are the same size.  
> Also if I got it right, the anchor is the zero index. If I got it right, I think it should be mentioned.

Yes you got that right.

> [@RoyiAvital](#):
>
> On top of that, it would be great to be able to chose how to handle boundaries.

Sure that would be a great PR.

> [@RoyiAvital](#):
>
> You may have a look on [`StaticKernels.jl`](https://github.com/stev47/StaticKernels.jl).  
> You also should compare performance with it. [As far as I could see `ImageFiltering.jl` is not fast in some cases](https://github.com/JuliaImages/image_benchmarks/issues/1), so `StaticKernels.jl` might be a better reference (For small windows).

Ah great. Yeah this package was designed with big windows in mind. For small windows no doubt `StaticKernels.jl` is better. Will add it to the README.

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [May 14, 2023, 8:56am UTC](https://discourse.julialang.org/t/ann-reducewindows-jl/98094/6 "2023-05-14T08:56:46Z")

</div>

By the way, I can’t find the announcement of [`MeanFilters.jl`](https://github.com/jw3126/MeanFilters.jl).