# Pairwise distance using matrix or Vector{SVector}: The first is faster!

**URL:** <https://discourse.julialang.org/t/pairwise-distance-using-matrix-or-vector-svector-the-first-is-faster/17312>\
**Category:** Performance\
**Created:** [November 8, 2018, 4:34pm UTC](https://discourse.julialang.org/t/pairwise-distance-using-matrix-or-vector-svector-the-first-is-faster/17312 "2018-11-08T16:34:19Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Datseris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datseris/32/13406_2.png) [@Datseris](https://discourse.julialang.org/u/Datseris)\
**Post date:** [November 8, 2018, 4:34pm UTC](https://discourse.julialang.org/t/pairwise-distance-using-matrix-or-vector-svector-the-first-is-faster/17312/1 "2018-11-08T16:34:19Z")

</div>

I am facing a really unexpected result, that is that the pairwise distance computation using a matrix is actually faster than a vector of _static_ vectors, for _small_ dimensions. here is my simple setup:

```julia
using Distances, StaticArrays
D = 10
data = [rand(SVector{D}) for i in 1:1000]
metrix = Chebyshev()

datam = zeros(D, 1000)
for i in 1:1000
    datam[:, i] .= data[i]
end

```

let’s now use the `pairwise` implementation of `Distances`. For reference, the generic method has the amazingly small source code:

```julia
function pairwise!(r::AbstractMatrix, metric::PreMetric, a::AbstractMatrix, b::AbstractMatrix)
    na = size(a, 2)
    nb = size(b, 2)
    size(r) == (na, nb) || throw(DimensionMismatch("Incorrect size of r."))
    @inbounds for j = 1:size(b, 2)
        bj = view(b, :, j)
        for i = 1:size(a, 2)
            r[i, j] = evaluate(metric, view(a, :, i), bj)
        end
    end
    r
end

```

and compare it with the just as simple:

```julia
const VV = Vector{<:SVector}

function pairwiseDS(x::VV, y::VV, metric::Metric)
    d = zeros(eltype(eltype(x)), length(x), length(y))
    for i in 1:length(x)
        for j in 1:length(y)
            @inbounds d[i,j] = evaluate(metric, x[i], y[j])
        end
    end
    return d
end

```

Benchmarks:

```julia
julia> @btime pairwiseDS($data, $data, $metric)
  47.305 ms (2 allocations: 7.63 MiB

# method from Distances:
julia> @btime pairwise($metric, $datam, $datam)
  36.199 ms (2 allocations: 7.63 MiB)

```

Even though the actual distance evaluation is faster:

```julia
v = rand(D)
sv = SVector{D}(v)

@btime evaluate($metric, $v, $v)
  30.293 ns (0 allocations: 0 bytes)
@btime evaluate($metric, $sv, $sv)
  25.173 ns (0 allocations: 0 bytes)

```

Was it just an unreasonable expectation from my side that the method with Vector{SVector} should be faster? But I mean, the actual distance evaluations _are_ faster. Why isn’t the entire result faster?

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [November 8, 2018, 4:53pm UTC](https://discourse.julialang.org/t/pairwise-distance-using-matrix-or-vector-svector-the-first-is-faster/17312/2 "2018-11-08T16:53:33Z")

</div>

I know that Distances uses BLAS operations for many of its pairwise distance computations, which is one of the reasons it is so much faster than the naive code you might write to do this. Is it possible that the package doesn’t recognize that a vector of SVectors is memory-compatible with BLAS and is therefore using a slower fallback implementation instead of the clever BLAS-based one?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 8, 2018, 5:02pm UTC](https://discourse.julialang.org/t/pairwise-distance-using-matrix-or-vector-svector-the-first-is-faster/17312/3 "2018-11-08T17:02:05Z")

</div>

Chebyshev is not amenable to the BLAS optimization but this is likely just

[https://docs.julialang.org/en/v1/manual/performance-tips/#Access-arrays-in-memory-order,-along-columns-1](https://docs.julialang.org/en/v1/manual/performance-tips/#Access-arrays-in-memory-order,-along-columns-1)

---

<div class="post-metadata">

**Author:** ![Datseris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/datseris/32/13406_2.png) [@Datseris](https://discourse.julialang.org/u/Datseris)\
**Post date:** [November 8, 2018, 5:29pm UTC](https://discourse.julialang.org/t/pairwise-distance-using-matrix-or-vector-svector-the-first-is-faster/17312/4 "2018-11-08T17:29:50Z")

</div>

@kristoffer.carlsson I thought the same, and I was testing it. Indeed putting the `j` loop first gives

```julia
  37.050 ms (2 allocations: 7.63 MiB)

```

versus the `Distances` timing:

```julia
  35.395 ms (2 allocations: 7.63 MiB)

```

The later is still faster, I guess the reasons may not be even identifyable?

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [November 8, 2018, 5:55pm UTC](https://discourse.julialang.org/t/pairwise-distance-using-matrix-or-vector-svector-the-first-is-faster/17312/5 "2018-11-08T17:55:11Z")

</div>

> [@Datseris](#):
>
> I guess the reasons may not be even identifyable?

All reasons are identifiable if you’re willing to work hard enough to figure out what’s going on. The question is if it’s worth it to someone or not 🙂