This repository explores multiple implementations of performing a squared matrix multiplication and documents the performance of each implementation.

The implementations are written in C++ with CMAKE as the build system to offer portability. The Google benchmark and test frameworks are used to evaluate the performance of the implementations. To profile the memory and cache usage of each implementation, the implementations are cross-compiled to linux and Valgrind in WSL is used to profile the executables manually.

The naive implementation is the most straightforward implementation of matrix multiplication. It iterates over all elements of the result matrix and calculates the value by summing up the products of the corresponding row and column of the input matrices.

In Python the algorithm for multiplying two square row-major matrices with each other would look like the following:

for i in range(n):
  for j in range(n):
    for k in range(n):
      outputMatrix[i][j] += leftMatrix[i][k] * rightMatrix[k][j]

Note that in my implementation the input matrices are one dimensional row-major as opposed to the usual two dimensions row-major in a matrix.

Two implementations are provided, one using a vector and one using a raw array:

// Vector implementation
std::vector<int_fast64_t> naive_vector_matrix_mul(std::vector<int_fast64_t> A, std::vector<int_fast64_t> B, uint_fast32_t n);

// Array implementation
std::unique_ptr<int_fast64_t[]> naive_array_matrix_mul(int_fast64_t* A, int_fast64_t* B, uint_fast32_t n);

Inspecting the assembly in compiler explorer shows that both the vector implementation and the array implementation both enable some form of vectorization in their inner loops.

To make use of the cache, we can reorder the loops to iterate over the matrix in a cache-friendly way. In the naive implementation the k index on the inner-most loop causes a cache miss on the right matrix on every iteration. If the k and j indices are swapped, the output matrix and right matrix will both be accessed contiguously. Instead of completing the dot product of a row and a column in one operation, it is now performed in a cache-friendly manner, where the partial sums are stored in the output matrix.

for i in range(n):
  for k in range(n):
    for j in range(n):
      outputMatrix[i][j] += leftMatrix[i][k] * rightMatrix[k][j]

Only one implementation is provided since it was concluded that the array implementation was faster than the vector implementation:

std::unique_ptr<int_fast64_t[]> cache_optimized_array_matrix_mul(int_fast64_t* A, int_fast64_t* B, uint_fast32_t n);