# Alternative to computation in a loop for distances for fast performance

**URL:** <https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642>\
**Category:** Performance\
**Created:** [December 6, 2021, 10:52am UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642 "2021-12-06T10:52:49Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![nagda95](https://avatars.discourse-cdn.com/v4/letter/n/9fc348/32.png) [@nagda95](https://discourse.julialang.org/u/nagda95)\
**Post date:** [December 6, 2021, 10:52am UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642/1 "2021-12-06T10:52:49Z")

</div>

Hello Everyone,  
I want to compute the distance (SqEuclidean) of a new point (newP) from the existing neighboring points in a specific order. I have the following code:

```julia
newP=[x y z]
for i in eachindex(order)
	Dist[i]=sum((Points[order[i], :]' - newP) .^ 2)
end

```

However, the above piece of code comparatively takes too much time and I would like to speed up this computation. Is there some way I can optimize this loop?  
Thank you.

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [December 6, 2021, 12:06pm UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642/2 "2021-12-06T12:06:50Z")

</div>

Please make [an MWE](https://discourse.julialang.org/t/please-read-make-it-easier-to-help-you/14757) and clarify what you mean by too much time.

Some potential low-hanging fruit could be removing allocations, using StaticArrays for your point vectors, and avoiding access to variables in global scope, but all of this is hard to tell without a working example.

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [December 6, 2021, 1:20pm UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642/3 "2021-12-06T13:20:50Z")

</div>

> [@PSA: how to quote code with backticks](https://discourse.julialang.org/t/psa-how-to-quote-code-with-backticks/7530):
>
> This is a short post on how to use backticks (` and ```) to quote code, so it is easy to read. This post can be linked to new users who are confused by this feature. Why By quoting your code, you get a monospaced font (which preserves indentation) and syntax highlighting. This makes it easier to read your code and help you. Displayed code looks like this: function displayed\_code(x::Int, y::Int) if x \< y println("x is smaller") else println("or not") end end Inline…

---

<div class="post-metadata">

**Author:** ![nagda95](https://avatars.discourse-cdn.com/v4/letter/n/9fc348/32.png) [@nagda95](https://discourse.julialang.org/u/nagda95)\
**Post date:** [December 6, 2021, 1:32pm UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642/4 "2021-12-06T13:32:37Z")

</div>

Here is an MWE

```julia
Points=rand(Float64, (6700, 3))
newP=[0.2 0.3 0.4]
order=collect(1:6700) #order can be different but for simple example I use regular sequence here
Dist=zeros(size(order,1),1)
for i in eachindex(order)
	Dist[i]=sum((Points[order[i], :]' - newP) .^ 2)
end

```

I want to find Dist (distances) for a lot of newP so I want to speed up this computation in for loop (or rather not use for loop for fast performance)

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [December 6, 2021, 1:49pm UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642/5 "2021-12-06T13:49:12Z")

</div>

The page on [performance tips](https://docs.julialang.org/en/v1/manual/performance-tips/) is very important.

I put the code you’d like to time in a function, so that it can be timed.

Making the identifiers (variables) `const`, increases performance in this case by a factor of ten.

Using `@inbounds` improves performance further by a few percent

```julia
const Points = rand(Float64, (6700, 3))

const newP = [0.2 0.3 0.4]

const order = collect(1:6700) #order can be different but for simple example I use regular sequence here

const Dist = zeros(size(order,1),1)

function fillDist()
    @inbounds for i in eachindex(order)
	Dist[i]=sum((Points[order[i], :]' - newP) .^ 2)
    end
end

```

You can get another factor of two or more this way:

```julia
const newP2 = [0.2, 0.3, 0.4]

function fillDist2()
    for i in eachindex(order)
	Dist[i]=sum((Points[order[i], :] .- newP2) .^ 2)
    end
end

```

Here, I have avoided doing a transpose. Also the `.-` and `.^` are “fused” into a single loop, resulting in fewer allocations.

You get another factor of two by replacing the line in the loop by

```julia
 Dist[i]=sum(( @view(Points[order[i], :]) .- newP2) .^ 2)

```

---

<div class="post-metadata">

**Author:** ![roflmaostc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/roflmaostc/32/30123_2.png) [@roflmaostc](https://discourse.julialang.org/u/roflmaostc)\
**Post date:** [December 6, 2021, 2:17pm UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642/6 "2021-12-06T14:17:02Z")

</div>

And instead of using excessive global variables, maybe pass them explicitly to the function.

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [December 6, 2021, 3:03pm UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642/7 "2021-12-06T15:03:49Z")

</div>

Some ways to do this are:

```julia
pairwise2(x::AbstractMatrix, y::AbstractMatrix) = sum(abs2, x; dims=1)' .+ sum(abs2, y; dims=1) .- 2 .* (x'*y) # written to use columns
Dist ≈ pairwise2(Points[order, :]', newP')

using Distances
Dist ≈ pairwise(SqEuclidean(), Points[order, :], newP; dims=1) # dims=1 means rows here

using Tullio
Dist ≈ @tullio dist_t[i] := (Points[order[i], k] - newP[k])^2

```

Times:

```julia
julia> using BenchmarkTools

julia> @btime for i in eachindex($order)
               $Dist[i] = sum(($Points[$order[i], :]' - $newP) .^ 2)
       end
  min 514.084 μs, mean 577.836 μs (20100 allocations, 1.53 MiB)

julia> @btime pairwise2($Points[$order, :]', $newP');
  min 31.833 μs, mean 64.153 μs (11 allocations, 471.55 KiB)

julia> @btime pairwise(SqEuclidean(), $Points[$order, :], $newP; dims=1)
  min 27.459 μs, mean 45.095 μs (7 allocations, 262.02 KiB)

julia> @btime @tullio dist_t[i] := ($Points[$order[i], k] - $newP[k])^2;
  min 20.000 μs, mean 24.760 μs (2 allocations, 52.42 KiB)

julia> using LoopVectorization

julia> @btime @tullio dist_t[i] := ($Points[$order[i], k] - $newP[k])^2;
  min 13.375 μs, mean 17.343 μs (2 allocations, 52.42 KiB)

```

---

<div class="post-metadata">

**Author:** ![nagda95](https://avatars.discourse-cdn.com/v4/letter/n/9fc348/32.png) [@nagda95](https://discourse.julialang.org/u/nagda95)\
**Post date:** [December 6, 2021, 11:13pm UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642/8 "2021-12-06T23:13:08Z")

</div>

@mcabbott Hello Michael,  
Thank you for your response.  
I am not able to implement the script using Tullio. When I run this code, I get the output as false.

```julia
Points=rand(Float64, (6700, 3))
newP=[0.2 0.3 0.4]
order=collect(1:6700) 
Dist=zeros(size(order,1),1)
using Tullio
Dist ≈ @tullio dist_t[i] := (Points[order[i], k] - newP[k])^2

```

I am sorry but I don’t understand. Could you please help?

---

<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:** [December 7, 2021, 12:31am UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642/9 "2021-12-07T00:31:55Z")

</div>

A few points:

> [@nagda95](#):
>
> `Points=rand(Float64, (6700, 3))`  
> `Points[order[i], :]'`

Julia Arrays are _column major_, so make sure to work along columns, not rows:

```julia
Points=rand(Float64, (3, 6700))
Points[:, order[i]]

```

Wrap your code in functions(!)

A matter of style: it is good to distinguish between matrices and vectors, so instead of

> [@nagda95](#):
>
> `Dist=zeros(size(order,1),1)`

write

```julia
Dist = zeros(size(order, 1))

```

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [December 7, 2021, 2:17am UTC](https://discourse.julialang.org/t/alternative-to-computation-in-a-loop-for-distances-for-fast-performance/72642/10 "2021-12-07T02:17:38Z")

</div>

> [@nagda95](#):
>
> `Dist ≈ `

I think you’re testing here whether zero (from two lines up) is approximately equal to a result. My code above ought to return `true` if you have already run yours – it check that each method is getting the same result as your loop wrote into `Dist`.