# For loop optimization

**URL:** <https://discourse.julialang.org/t/for-loop-optimization/70700>\
**Category:** Performance\
**Tags:** performance, memory-allocation, loops\
**Created:** [October 31, 2021, 6:55pm UTC](https://discourse.julialang.org/t/for-loop-optimization/70700 "2021-10-31T18:55:10Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![claudio20497](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/claudio20497/32/36602_2.png) [@claudio20497](https://discourse.julialang.org/u/claudio20497)\
**Post date:** [October 31, 2021, 6:55pm UTC](https://discourse.julialang.org/t/for-loop-optimization/70700/1 "2021-10-31T18:55:10Z")

</div>

Hello,

I’m not sure how to optimize the following for loop.

`array_1` and `array_2` are two `Vector{Vector{Int64}}`s, and I’m interested in evaluating which combinations (of 2 elements) of their vector components has an element-wise sum equal to a specified `sum_target`, which of course is a `Vector{Int64}`.

The code I’m currently using is the following:

```julia
using BenchmarkTools

function f()

    n_elements = 50

    array_1 = [Int64.(rand(Int8,500)) for i in 1:n_elements]
    array_2 = [Int64.(rand(Int8,500)) for i in 1:n_elements]

    sum_target = Int64.(rand(Int8,500)) 

    solutions = Vector{Vector{Int64}}[]

    iterator_over_combinations = Iterators.product(array_1,array_2)

    for combination in iterator_over_combinations
        if all(sum(combination) .== sum_target)
            push!(solutions, combination )
        end
    end

    return solutions

end

```

The number of vector elements of `array_1` and `array_2` is here set to `n_elements::Int64 = 50` in order for `@btime` to work, but in the real application I have like `n_elements::Int64 = 10^11` and combine ten arrays instead of just two.

Right now I get:

```julia
julia> @btime f() ;
  2.587 ms (10205 allocations: 21.02 MiB)

```

Thank you very much in advance.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [October 31, 2021, 7:33pm UTC](https://discourse.julialang.org/t/for-loop-optimization/70700/2 "2021-10-31T19:33:41Z")

</div>

You can (and should) remove all type assertions on the left hand sides. They do not help performance, but make the code harder to read.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [October 31, 2021, 7:36pm UTC](https://discourse.julialang.org/t/for-loop-optimization/70700/3 "2021-10-31T19:36:54Z")

</div>

`all(sum(combination) .== sum_target)` This is really slow because you are computing all the equalities and then seeing if they are all true rather than only computing until you find a place where they aren’t equal.

---

<div class="post-metadata">

**Author:** ![jipolanco](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jipolanco/32/12129_2.png) [@jipolanco](https://discourse.julialang.org/u/jipolanco)\
**Post date:** [October 31, 2021, 7:39pm UTC](https://discourse.julialang.org/t/for-loop-optimization/70700/4 "2021-10-31T19:39:39Z")

</div>

The main issue is that `all(sum(combination) .== sum_target)` allocates two arrays at each iteration of the `for` loop, which ends up being very costly. You could instead do the comparisons lazily, in a way that fully avoids allocations. Most importantly, as @Oscar_Smith suggested, this would also allow you to terminate the computations as soon as there is a disagreement, instead of having to compute the whole sum before doing the comparisons.

Below are a few alternatives. Note that I have moved the allocation of the large arrays to outside of the function.

```julia
function f2(array_1, array_2, sum_target)
    solutions = Tuple{eltype(array_1), eltype(array_2)}[]

    iterator_over_combinations = Iterators.product(array_1, array_2)

    for combination in iterator_over_combinations
        if all(sum(combination) .== sum_target)
            push!(solutions, combination)
        end
    end

    solutions
end

function f3(array_1, array_2, sum_target)
    solutions = Tuple{eltype(array_1), eltype(array_2)}[]

    iterator_over_combinations = Iterators.product(array_1, array_2)

    for combination in iterator_over_combinations
        success = all(
            vs -> vs[1] + vs[2] == vs[3],
            zip(combination..., sum_target),
        )
        if success
            push!(solutions, combination)
        end
    end

    solutions
end

function f4(array_1, array_2, sum_target)
    solutions = Tuple{eltype(array_1), eltype(array_2)}[]

    iterator_over_combinations = Iterators.product(array_1, array_2)

    for combination in iterator_over_combinations
        success = true
        a, b = combination
        for i ∈ eachindex(sum_target)
            if a[i] + b[i] ≠ sum_target[i]
                success = false
                break
            end
        end
        if success
            push!(solutions, combination)
        end
    end

    solutions
end

n_elements = 50
m = 500
array_1 = [Int64.(rand(Int8, m)) for i in 1:n_elements]
array_2 = [Int64.(rand(Int8, m)) for i in 1:n_elements]
sum_target = Int64.(rand(Int8, m))

@btime f() # 5.152 ms (10205 allocations: 20.98 MiB)

@btime f2($array_1, $array_2, $sum_target) # 5.142 ms (10001 allocations: 20.52 MiB)
@btime f3($array_1, $array_2, $sum_target) # 14.733 μs (1 allocation: 64 bytes)
@btime f4($array_1, $array_2, $sum_target) # 10.009 μs (1 allocation: 64 bytes)

```

Note that `f2` is nearly the same as `f`, and the performance is the same, while the `f3` and `f4` variants are almost 3 orders of magnitude faster. Moreover, `f4` is (in my opinion) more readable and ends up being the fastest option.