# Micro benchmarks of kron for vectors

**URL:** <https://discourse.julialang.org/t/micro-benchmarks-of-kron-for-vectors/71689>\
**Category:** Performance\
**Created:** [November 17, 2021, 10:51pm UTC](https://discourse.julialang.org/t/micro-benchmarks-of-kron-for-vectors/71689 "2021-11-17T22:51:13Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [November 17, 2021, 10:51pm UTC](https://discourse.julialang.org/t/micro-benchmarks-of-kron-for-vectors/71689/1 "2021-11-17T22:51:13Z")

</div>

Edit: corrected according to @jling `s comment

Inspired by another thread here is a micro benchmark of `Base.kron` for `Vector`

```julia
using LinearAlgebra
using BenchmarkTools

function _kron(A::Matrix, B::Matrix)
    C = zeros(size(A,1) * size(B,1), size(A,2) * size(B,2))
    for i = 1:size(A, 1)
        for j = 1:size(A, 2)
            @views C[(i-1)*size(B,1)+1:i*size(B,1),(j-1)*size(B,2)+1:j*size(B,2)] .= A[i,j] * B
        end
    end
    C
end

function _kron!(C::Matrix, A::Matrix, B::Matrix)
    for i = 1:size(A, 1)
        for j = 1:size(A, 2)
            @views mul!(C[(i-1)*size(B,1)+1:i*size(B,1),(j-1)*size(B,2)+1:j*size(B,2)], A[i,j], B)
        end
    end
    C
end

function _kron(A::Vector, B::Vector)
    C = zeros(size(A,1) * size(B,1))
    for i = 1:size(A, 1)
        @views C[(i-1)*size(B,1)+1:i*size(B,1)] .= A[i] * B
    end
    C
end

function _kron!(C::Vector, A::Vector, B::Vector)
    for i = 1:size(A, 1)
        @views mul!(C[(i-1)*size(B,1)+1:i*size(B,1)], A[i], B)
    end
    C
end

A = Matrix([[1.0, 2.0] [3.0, 4.0]])
B = Matrix([[1.0, 2.0] [3.0, 4.0]])

C1 = _kron(A, B)
C2 = kron(A, B)
@assert C1 ≈ C2

C1 = Matrix{Float64}(undef, 4, 4)
_kron!(C1, A, B)
C2 = Matrix{Float64}(undef, 4, 4)
kron!(C2, A, B)
@assert C1 ≈ C2

@btime _kron($A, $B)
@btime kron($A, $B)

C = Matrix{Float64}(undef, 4, 4)
@btime _kron!($C, $A, $B)
@btime kron!($C, $A, $B)

A = Vector([1.0, 2.0])
B = Vector([1.0, 2.0])

C1 = _kron(A, B)
C2 = kron(A, B)
@assert C1 ≈ C2

C1 = Vector{Float64}(undef, 4)
_kron!(C1, A, B)
C2 = Vector{Float64}(undef, 4)
kron!(C2, A, B)
@assert C1 ≈ C2

@btime _kron($A, $B)
@btime kron($A, $B)

C = Vector{Float64}(undef, 4)
@btime _kron!($C, $A, $B)
@btime kron!($C, $A, $B)

```

with

```julia
  273.597 ns (5 allocations: 656 bytes)
  49.034 ns (1 allocation: 208 bytes)
  67.695 ns (0 allocations: 0 bytes)
  25.201 ns (0 allocations: 0 bytes)
  108.141 ns (3 allocations: 304 bytes)
  128.485 ns (7 allocations: 384 bytes)
  20.783 ns (0 allocations: 0 bytes)
  108.172 ns (6 allocations: 288 bytes)

```

Is this a defect?

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [November 17, 2021, 10:53pm UTC](https://discourse.julialang.org/t/micro-benchmarks-of-kron-for-vectors/71689/2 "2021-11-17T22:53:21Z")

</div>

use `SVector` for your kernel A and B

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [November 17, 2021, 10:56pm UTC](https://discourse.julialang.org/t/micro-benchmarks-of-kron-for-vectors/71689/3 "2021-11-17T22:56:16Z")

</div>

Vectors are quite big in the original example and please notice the runtime and additional allocations in the vector case in contrast to the matrix case.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [November 17, 2021, 10:57pm UTC](https://discourse.julialang.org/t/micro-benchmarks-of-kron-for-vectors/71689/4 "2021-11-17T22:57:43Z")

</div>

isn’t it just in-place vs. not?

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [November 17, 2021, 10:58pm UTC](https://discourse.julialang.org/t/micro-benchmarks-of-kron-for-vectors/71689/5 "2021-11-17T22:58:21Z")

</div>

No, it tries to compare both (inplace and allocated) of `Base.kron` to naive versions.

---

<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:** [November 18, 2021, 1:37am UTC](https://discourse.julialang.org/t/micro-benchmarks-of-kron-for-vectors/71689/6 "2021-11-18T01:37:12Z")

</div>

I think there’s no implementation for `kron` of vectors, it just reshapes to use the one for matrices. And there’s some overhead to that which, for very very small arrays, becomes the dominant time.

```julia
julia> size© # vector case
(4,)

julia> @btime _kron!($C, $A, $B);
  min 11.136 ns, mean 11.307 ns (0 allocations)

julia> @btime kron!($C, $A, $B);
  min 71.422 ns, mean 93.837 ns (6 allocations, 288 bytes. GC mean 21.04%)

julia> @less kron!(C, A, B); # this reshapes to make matrices

julia> @btime reshape(reshape($C,2,2),4); # in fact it needs 3 reshapes, not 2
  min 43.939 ns, mean 59.453 ns (4 allocations, 176 bytes. GC mean 22.68%)

```

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [November 18, 2021, 12:05pm UTC](https://discourse.julialang.org/t/micro-benchmarks-of-kron-for-vectors/71689/7 "2021-11-18T12:05:03Z")

</div>

Thanks for the explanation!