# Dot(x, inv.(y)) vs non-allocating one, the former is faster?

**URL:** <https://discourse.julialang.org/t/dot-x-inv-y-vs-non-allocating-one-the-former-is-faster/21338>\
**Category:** Performance\
**Created:** [March 1, 2019, 11:31am UTC](https://discourse.julialang.org/t/dot-x-inv-y-vs-non-allocating-one-the-former-is-faster/21338 "2019-03-01T11:31:09Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![tlienart](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tlienart/32/7640_2.png) [@tlienart](https://discourse.julialang.org/u/tlienart)\
**Post date:** [March 1, 2019, 11:31am UTC](https://discourse.julialang.org/t/dot-x-inv-y-vs-non-allocating-one-the-former-is-faster/21338/1 "2019-03-01T11:31:09Z")

</div>

In looking at some recent updates in Distributions I saw code like this `dot(w, inv.(x))` and thought that better could be done to avoid allocating `inv.(x)` however what I came up with was always slower and I’m not sure why.

```julia
julia> x = randn(100_000) .+ 100
julia> y = randn(100_000) .+ 100
julia> f(x, y) = dot(x, inv.(y))
julia> g(x, y) = sum(@inbounds x[i]/y[i] for i in eachindex(x))
julia> @btime f($x, $y)
  74.495 μs (2 allocations: 781.33 KiB)
100011.86751975697
julia> @btime g($x, $y)
  111.424 μs (2 allocations: 64 bytes)
100011.86751975746

```

Any idea why the second one is slower? purely in terms of flops it should be about the same shouldn’t it?

---

<div class="post-metadata">

**Author:** ![tomaklutfu](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tomaklutfu/32/2411_2.png) [@tomaklutfu](https://discourse.julialang.org/u/tomaklutfu)\
**Post date:** [March 1, 2019, 11:35am UTC](https://discourse.julialang.org/t/dot-x-inv-y-vs-non-allocating-one-the-former-is-faster/21338/2 "2019-03-01T11:35:53Z")

</div>

`dot` is BLAS call so it is threaded(I see 4 core usage) but I don’t see that dramatic difference in my laptop.

---

<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:** [March 1, 2019, 11:36am UTC](https://discourse.julialang.org/t/dot-x-inv-y-vs-non-allocating-one-the-former-is-faster/21338/3 "2019-03-01T11:36:59Z")

</div>

Locally I see

```julia
> @btime f($x, $y)
  78.900 μs (2 allocations: 781.33 KiB)
100006.09856166482

> @btime g($x, $y)
  81.599 μs (2 allocations: 64 bytes)
100006.09856166548

```

but just writing out the loop can get some speedup:

```julia
 function h(x, y)
    @assert length(x) == length(y) 
    s = zero( one(eltype(x)) / one(eltype(y)) )
    @inbounds @simd for i in 1:length(x)
        s += x[i] / y[i]
    end
    return s
end

> @btime h($x, $y)
  40.799 μs (0 allocations: 0 bytes)
100006.09856166487

```

---

<div class="post-metadata">

**Author:** ![tlienart](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tlienart/32/7640_2.png) [@tlienart](https://discourse.julialang.org/u/tlienart)\
**Post date:** [March 1, 2019, 12:10pm UTC](https://discourse.julialang.org/t/dot-x-inv-y-vs-non-allocating-one-the-former-is-faster/21338/4 "2019-03-01T12:10:17Z")

</div>

thanks yes I had thought of using @simd as well but it was to replace a one-liner and seemed a bit overkill. (the factor 2 speedup is quite impressive though)

It does seem there’s something to do with the laptop and not the algorithm though as I can definitely reproduce a ~50-60% time difference but others (as per your results) don’t seem to get the same difference. Versioninfo below fwiw.

```julia
Julia Version 1.2.0-DEV.376
Commit de48421024 (2019-02-25 22:13 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin14.5.0)
  CPU: Intel(R) Core(TM) i5-7360U CPU @ 2.30GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

```

---

<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:** [March 1, 2019, 12:15pm UTC](https://discourse.julialang.org/t/dot-x-inv-y-vs-non-allocating-one-the-former-is-faster/21338/5 "2019-03-01T12:15:46Z")

</div>

If compute speed is relatively slower compared to memory then perhaps multithreading gives you a speedup.

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [March 2, 2019, 12:01am UTC](https://discourse.julialang.org/t/dot-x-inv-y-vs-non-allocating-one-the-former-is-faster/21338/6 "2019-03-02T00:01:19Z")

</div>

Indeed, this problem is very amenable to parallelization:

```julia
function dot_threaded(x, y; N = Threads.nthreads())
    M = length(x)
    @assert M == length(y)
    z = one(eltype(x)) / one(eltype(y))
    acc = zeros(typeof(z), N)
    Threads.@threads for t = 1:N
        s = zero(z)
        @inbounds @simd for i = M*(t-1)÷N+1 : M*t÷N
            s += x[i] / y[i]
        end
        acc[t] = s
    end
    return sum(acc)
end

```

Performance:

```julia
julia> x, y = 1:2 .|>_-> randn(100_000) .+ 100;

julia> @btime dot_inv($x, $y) # "f" from above: dot(x, inv.(y))
  74.980 μs (2 allocations: 781.33 KiB)
100007.82225468596

julia> @btime dot_simd($x, $y) # kristoffer's "h" from above
  57.328 μs (0 allocations: 0 bytes)
100007.822254686

julia> @btime dot_threaded($x, $y)
  15.452 μs (5 allocations: 240 bytes)
100007.82225468596

julia> 57.328 / 15.452
3.710069893864872

julia> Threads.nthreads()
4

```

With that said, I generally don’t think it’s a good idea to parallelize your inner-most loops this way. It tends to lead to complex bug-fraught code, and poor overall parallelization. I think parallelization is better applied on as coarse of a level as possible.