# Comprehension vs map and filter unexpected speeds

**URL:** <https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314>\
**Category:** General Usage\
**Tags:** question\
**Created:** [November 20, 2019, 1:02pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314 "2019-11-20T13:02:23Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![stakaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stakaz/32/4740_2.png) [@stakaz](https://discourse.julialang.org/u/stakaz)\
**Post date:** [November 20, 2019, 1:02pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/1 "2019-11-20T13:02:23Z")

</div>

Hello, I have the following comparison and I wonder why the last way to achieve the result is the fastest as i should create an additional array whereas the fist two don’t.

```julia
julia> const A = rand(10000);
WARNING: redefining constant A

julia> @time [a^2 for a ∈ A if a > 0.5];
  0.138524 seconds (80.82 k allocations: 3.978 MiB)

julia> @time map(x -> x^2, filter(x -> x > 0.5, A));
  0.130198 seconds (69.27 k allocations: 3.601 MiB)

julia> @time [a^2 for a ∈ A[A .> 0.5]];
  0.099821 seconds (51.53 k allocations: 2.623 MiB)

```

I have tested it with a few array sizes and several tries – the behavior remains the same…

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:06pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/2 "2019-11-20T13:06:53Z")

</div>

You want to use `@btime`, notice the `b`

---

<div class="post-metadata">

**Author:** ![stakaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stakaz/32/4740_2.png) [@stakaz](https://discourse.julialang.org/u/stakaz)\
**Post date:** [November 20, 2019, 1:09pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/3 "2019-11-20T13:09:56Z")

</div>

Yeah, I have tried but the result is even more pronounced:

```julia
julia> const A = rand(10000);
WARNING: redefining constant A

julia> using BenchmarkTools

julia> @btime [a^2 for a ∈ A if a > 0.5];
  188.852 μs (16 allocations: 128.69 KiB)

julia> @btime map(x -> x^2, filter(x -> x > 0.5, A));
  193.042 μs (16 allocations: 167.36 KiB)

julia> @btime [a^2 for a ∈ A[A .> 0.5]];
  88.000 μs (10 allocations: 83.14 KiB)

```

The problem here is probably that `@btime` explicitly tries to not to measure the time for creating `A[A .> 0.5]`. But in this case this is unfair than.

I have forgotten to remove `BenchmarkTools` in the previous example.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:11pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/4 "2019-11-20T13:11:26Z")

</div>

> [@stakaz](#):
>
> The problem here is probably that `@btime` explicitly tries to not to measure the time for creating `A[A .> 0.5]` .

I don’t think that’s the case. It would be the case if you interpolated that expression, which you don’t.

---

<div class="post-metadata">

**Author:** ![stakaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stakaz/32/4740_2.png) [@stakaz](https://discourse.julialang.org/u/stakaz)\
**Post date:** [November 20, 2019, 1:13pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/5 "2019-11-20T13:13:54Z")

</div>

However, the time is roughly the half in the last case so something very useful is optimized here.

I have tried to remove the `^` and the result persists.

```julia
julia> @btime [a for a ∈ A if a > 0.5];
  186.337 μs (16 allocations: 128.69 KiB)

julia> @btime map(x -> x, filter(x -> x > 0.5, A));
  192.763 μs (16 allocations: 167.36 KiB)

julia> @btime [a for a ∈ A[A .> 0.5]];
  88.280 μs (10 allocations: 83.14 KiB)

```

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:14pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/6 "2019-11-20T13:14:43Z")

</div>

The first one is probably slow because the length of the final result is unknown, which it is not in the last two. Not sure why second is slower than third though

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:15pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/7 "2019-11-20T13:15:47Z")

</div>

Ah the filter does not know the length of the result. The binary indexing probably does then…?

---

<div class="post-metadata">

**Author:** ![stakaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stakaz/32/4740_2.png) [@stakaz](https://discourse.julialang.org/u/stakaz)\
**Post date:** [November 20, 2019, 1:17pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/8 "2019-11-20T13:17:18Z")

</div>

> [@baggepinnen](#):
>
> binary indexing

I don’t know this one, could you explain, please…

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:20pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/9 "2019-11-20T13:20:11Z")

</div>

I was referring to indexing with a BitArray, my choice of wording is perhaps nonstandard 😛

```julia
julia> i = a .> 0.5
100-element BitArray{1}

```

---

<div class="post-metadata">

**Author:** ![stakaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stakaz/32/4740_2.png) [@stakaz](https://discourse.julialang.org/u/stakaz)\
**Post date:** [November 20, 2019, 1:21pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/10 "2019-11-20T13:21:47Z")

</div>

Ah, ok, but still, in the above example it has to first go through the whole array to get A[A .\> 0.5] why is it so much faster?

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:22pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/11 "2019-11-20T13:22:55Z")

</div>

> [@baggepinnen](#):
>
> The binary indexing probably does then

Yeah, the last line in this snippet

```julia
function _unsafe_getindex(::IndexStyle, A::AbstractArray, I::Vararg{Union{Real, AbstractArray}, N}) where N
    # This is specifically not inlined to prevent excessive allocations in type unstable code
    shape = index_shape(I...)
    dest = similar(A, shape)

```

the shape is of type `Base.OneTo(length)` there, so this will be more efficient as only one new array is created with the correct size from the beginning

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:24pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/12 "2019-11-20T13:24:05Z")

</div>

The other two methods incrementally build the result array, starting with a small array, not knowing how long it will end up. Growing the array when it has reached it’s maximum capacity is costly in this setting.

---

<div class="post-metadata">

**Author:** ![stakaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stakaz/32/4740_2.png) [@stakaz](https://discourse.julialang.org/u/stakaz)\
**Post date:** [November 20, 2019, 1:26pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/13 "2019-11-20T13:26:00Z")

</div>

Yeah, thanks, this is the explanation I have searched for.

However, it lets me a little bit unsatisfied in the since that it makes a difference which method to use ☹

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:27pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/14 "2019-11-20T13:27:06Z")

</div>

yeah I have no good answer there, other than benchmarking is simple and often worth it 🙂 (if this code is performance sensitive and a bottleneck, otherwise no need to bother)

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:28pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/15 "2019-11-20T13:28:40Z")

</div>

The relative timing may vary based on how many elements of `A` passes through the filter. If almost no elements satisfies the condition, the first two might be faster. If most elements fit, the last one will win.

---

<div class="post-metadata">

**Author:** ![stakaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stakaz/32/4740_2.png) [@stakaz](https://discourse.julialang.org/u/stakaz)\
**Post date:** [November 20, 2019, 1:28pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/16 "2019-11-20T13:28:50Z")

</div>

> [@baggepinnen](#):
>
> benchmarking is simple and often worth it

that’s for sure 😉

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:32pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/17 "2019-11-20T13:32:27Z")

</div>

With different number of elements passing through the filter, I get these timings

```julia
julia> @btime [a^2 for a ∈ A if a > 0.5];

  99.445 μs (16 allocations: 128.69 KiB)

julia> @btime map(x -> x^2, filter(x -> x > 0.5, A));
  15.326 μs (6 allocations: 117.86 KiB)

julia> @btime [a^2 for a ∈ A[A .> 0.5]];
  24.956 μs (10 allocations: 84.89 KiB)

julia> @btime [a^2 for a ∈ A if a > 0.95];
  17.587 μs (13 allocations: 16.50 KiB)

julia> @btime map(x -> x^2, filter(x -> x > 0.95, A));
  10.624 μs (5 allocations: 82.41 KiB)

julia> @btime [a^2 for a ∈ A[A .> 0.95]];
  15.191 μs (8 allocations: 13.98 KiB)

```

There is indeed a difference in relative timing. I have the second version as the fastest on julia v1.3-rc5, maybe it has seen performance improvements

---

<div class="post-metadata">

**Author:** ![stakaz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stakaz/32/4740_2.png) [@stakaz](https://discourse.julialang.org/u/stakaz)\
**Post date:** [November 20, 2019, 1:42pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/18 "2019-11-20T13:42:31Z")

</div>

By the way, if used as a generator, the timing is different:

```julia
julia> @btime sum(a for a ∈ A if a > 0.5);
  61.740 μs (2 allocations: 32 bytes)

julia> @btime sum(map(x -> x, filter(x -> x > 0.5, A)));
  194.161 μs (16 allocations: 167.36 KiB)

julia> @btime sum(a for a ∈ A[A .> 0.5]);
  84.090 μs (8 allocations: 44.38 KiB)

```

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:51pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/19 "2019-11-20T13:51:11Z")

</div>

Those are all expected though, as the sum does not have to construct a vector. The last two does construct the vector, which is expensive, whereas the first one does not.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [November 20, 2019, 1:53pm UTC](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314/20 "2019-11-20T13:53:32Z")

</div>

> [@stakaz](#):
>
> @btime sum(a for a ∈ A if a \> 0.5);

Here, you can speed thing up further

```julia
julia> @btime sum(a for a ∈ A if a > 0.5);
  36.884 μs (2 allocations: 32 bytes)

julia> @btime sum(a->ifelse(a>0.5, a, zero(a)), A);
  2.263 μs (0 allocations: 0 bytes)

```

[Next page](https://discourse.julialang.org/t/comprehension-vs-map-and-filter-unexpected-speeds/31314.md?page=2)