# Fast small integer matrix multiplication

**URL:** <https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981>\
**Category:** Performance\
**Created:** [September 9, 2022, 11:12am UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981 "2022-09-09T11:12:18Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Fabrice\_Rosay](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fabrice_rosay/32/15689_2.png) [@Fabrice\_Rosay](https://discourse.julialang.org/u/Fabrice_Rosay)\
**Post date:** [September 9, 2022, 11:12am UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/1 "2022-09-09T11:12:18Z")

</div>

Hi,  
I need to multiply a lot of times a vector B of integers of size 64 by a 24x64 integer matrix B.  
Currently the fastest way I found is simply `A*B`, which is very fast if the matrix are converted to Float32 (which I’d rather not as the numbers inside the result are indices to another matrix).  
I tried Octavian, writing directly the loop with LoopVectorization and it is way slower (2 times), and it seems that setting the type to Int also incurs a penalty.  
I was wondering as sizes are fixed if it would be possible to directly unroll the multiplication using avx instructions.  
Any idea if it would be faster, or where to start ?

Current benchmark is:

````julia
@btime $A*$B
 115.134 ns (1 allocation: 160 bytes)

@btime mul!($C,$A,$B)
  94.759 ns (0 allocations: 0 bytes)

with Ocatvian

@btime matmul($A,$B)   
  270.896 ns (1 allocation: 160 bytes)

 @btime matmul!($C,$A,$B)
  221.195 ns (0 allocations: 0 bytes)

And if I set the type to say Int32
@btime $A*$B
  678.194 ns (1 allocation: 160 bytes) 6 times slower 

and with Octavian:
@btime matmul($A,$B)
  254.516 ns (1 allocation: 160 bytes) almost the same time, 
though slightly slower```
````

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 9, 2022, 11:18am UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/2 "2022-09-09T11:18:25Z")

</div>

> [@Fabrice\_Rosay](#):
>
> fast if the matrix are converted to Float32 (which I’d rather not as the numbers inside the result are indices to another matrix)

Note that `Float32` is exact for integers up to `maxintfloat(Float32) == 16777216`, so as long as your indices (or intermediate calculations in the matrix–vector multiplication) never get larger than this you won’t have any roundoff errors to worry about.

---

<div class="post-metadata">

**Author:** ![Fabrice\_Rosay](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fabrice_rosay/32/15689_2.png) [@Fabrice\_Rosay](https://discourse.julialang.org/u/Fabrice_Rosay)\
**Post date:** [September 9, 2022, 11:34am UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/3 "2022-09-09T11:34:32Z")

</div>

It seems to work, but conversion incurs a penalty of something like 15-20 ns. I would rather note use this, if possible( it is inside an alphabeta search so any time saved is precious).

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 9, 2022, 11:46am UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/4 "2022-09-09T11:46:57Z")

</div>

> [@Fabrice\_Rosay](#):
>
> I was wondering as sizes are fixed if it would be possible to directly unroll the multiplication using avx instructions.

Yes, an unrolled and optimized kernel for your specific sizes should in principle be faster than any generic code, and you can certainly do this in Julia. The caveat is that optimizing such a beast may requires a lot of time and specialized knowledge.

[LoopVectorization.jl](https://github.com/JuliaSIMD/LoopVectorization.jl/blob/main/Project.toml) and [SIMDTypes.jl](https://github.com/JuliaSIMD/SIMDTypes.jl) or [SIMD.jl](https://github.com/eschnett/SIMD.jl) are possible starting points.

---

<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:** [September 9, 2022, 11:52am UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/5 "2022-09-09T11:52:25Z")

</div>

it doesn’t require anything special. loopvextorization +staticarrays should generate the right code for you.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [September 9, 2022, 11:57am UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/6 "2022-09-09T11:57:58Z")

</div>

Is it feasible to stack all `B` vectors horizontally, i.e.,

```julia
allB = [B1 B2 B3 ...]

```

and perform a single matrix-matrix multiplication

```julia
A*allB

```

?

---

<div class="post-metadata">

**Author:** ![Fabrice\_Rosay](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fabrice_rosay/32/15689_2.png) [@Fabrice\_Rosay](https://discourse.julialang.org/u/Fabrice_Rosay)\
**Post date:** [September 9, 2022, 2:13pm UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/7 "2022-09-09T14:13:03Z")

</div>

It is indeed possible but requires to slightly change the algorithm. Also not every leaf needs to be evaluated so it needs thorough testing to know if the gain obtained by parallelizing is greater than having to evaluate all leaf.

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [September 9, 2022, 2:26pm UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/8 "2022-09-09T14:26:55Z")

</div>

Matrix-matrix multiplication is an _extremely_ well-optimized operation, so if a problem can be expressed as one (even if that means that you’ll multiply a few vectors extra), you might very well be better off doing that than doing several matrix-vector multiplications.

---

<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:** [September 9, 2022, 2:35pm UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/9 "2022-09-09T14:35:10Z")

</div>

Note that you only need batches of roughly 8 at a time to get most of the speedup.

---

<div class="post-metadata">

**Author:** ![Fabrice\_Rosay](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fabrice_rosay/32/15689_2.png) [@Fabrice\_Rosay](https://discourse.julialang.org/u/Fabrice_Rosay)\
**Post date:** [September 9, 2022, 2:38pm UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/10 "2022-09-09T14:38:11Z")

</div>

Oscar Smith was right. Simple multiplication using loopvectorization is the fastest way. I did try it before but I had forgotten the @turbo macro …, what an idiot. Also to be fair, using StaticArrays is a huge winner. This is already a 6 times improvement over my previous attempt: whole evaluation in 72ns instead of 420ns. Great.  
Thank you, long live Ataxx

---

<div class="post-metadata">

**Author:** ![mikmoore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikmoore/32/31109_2.png) [@mikmoore](https://discourse.julialang.org/u/mikmoore)\
**Post date:** [September 9, 2022, 2:45pm UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/11 "2022-09-09T14:45:50Z")

</div>

`LoopVectorization.jl` is probably your best bet. But `StaticArrays.jl` can probably get pretty close. Your matrix is too big to be a good candidate for a `SMatrix` from `StaticArrays.jl`, but could work as a `Vector{SVector}`.

`StaticArrays` can do unrolled native-precision linear algebra so you don’t need to write it yourself. Although to make it work correctly here, we have to reorder the operands in a slightly weird way.

```julia
using StaticArrays
m,n = 24,64
A = rand(Int16,m,n)
b = rand(Int16,n)
As = [SVector{m,Int16}(a) for a in eachcol(A)] # copy to Vector{SVector}
bs = SVector{n,Int16}(b) # copy to SVector

using BenchmarkTools
@btime $A * $b
# 267.925 ns (1 allocation: 96 bytes)
@btime $bs' * $As # bizarre phrasing but equivalent to the above
# 50.963 ns (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![Fabrice\_Rosay](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/fabrice_rosay/32/15689_2.png) [@Fabrice\_Rosay](https://discourse.julialang.org/u/Fabrice_Rosay)\
**Post date:** [September 9, 2022, 3:03pm UTC](https://discourse.julialang.org/t/fast-small-integer-matrix-multiplication/86981/12 "2022-09-09T15:03:38Z")

</div>

On my computer for Int32 LoopVectorization is slightly faster, but for Int16 pure static arrays seems faster unless another mistake, by a large margin. Unfortunately I need at least Int32.