A performance-oriented C project exploring how memory locality, CPU cache behavior, loop organization, block size, and compiler optimization affect dense matrix multiplication.
The project compares:
- Naive matrix multiplication
- Cache-blocked / tiled matrix multiplication
- Different block-size strategies
- L1-cache-aware blocking
-O0vs.-O3compiler optimization- Matrix sizes of 2,000 × 2,000 and 4,000 × 4,000
- Performance behavior on Apple Silicon
The experiments were performed on an Apple M4 Pro.
Dense matrix multiplication is mathematically simple:
[ C = AB ]
with:
[ c_{ij} = \sum_{k=1}^{n} a_{ik}b_{kj} ]
but its real performance depends heavily on how data is accessed in memory.
This project studies why two implementations performing essentially the same arithmetic can have dramatically different execution times.
Matrix Multiplication
│
┌──────────┴──────────┐
│ │
▼ ▼
Naive Blocked
implementation implementation
│ │
▼ ▼
Poor B locality Cache reuse
│ │
└──────────┬──────────┘
▼
Compiler options
-O0 / -O3
│
▼
Performance study
The baseline implementation uses the traditional three nested loops:
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
C[i][j] = 0.0;
for (int k = 0; k < N; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}Its computational complexity is:
[ O(N^3) ]
For N = 4000, this requires approximately:
[ 4000^3 = 64 \times 10^9 ]
inner-loop multiply-accumulate operations.
C stores multidimensional arrays in row-major order.
For a matrix:
A
the elements of each row are contiguous in memory:
A[0][0]
A[0][1]
A[0][2]
...
This has important consequences for CPU-cache behavior.
The naive implementation reads:
A[i][k]while k changes in the innermost loop.
Therefore the access pattern is:
A[i][0]
A[i][1]
A[i][2]
A[i][3]
...
This is contiguous memory access.
It has good spatial locality because consecutive elements are likely to belong to the same cache line.
The situation is very different for:
B[k][j]When k changes:
B[0][j]
B[1][j]
B[2][j]
B[3][j]
...
the program traverses a column of B.
Since C uses row-major storage, these values are far apart in memory.
Conceptually:
Row-major memory
B[0][0] B[0][1] B[0][2] ...
B[1][0] B[1][1] B[1][2] ...
B[2][0] B[2][1] B[2][2] ...
▲
│
column traversal requires large jumps
This produces substantially worse spatial locality and can generate many more cache misses.
Modern processors execute arithmetic far faster than they can retrieve arbitrary data from main memory.
The effective hierarchy is approximately:
Registers
↓
L1 cache
↓
L2 cache
↓
System-level cache
↓
RAM
The farther data must travel through this hierarchy, the greater the latency.
Therefore, improving data reuse in cache can dramatically reduce execution time even when the number of arithmetic operations remains similar.
The main optimization explored in the project is matrix blocking, also known as:
- Tiling
- Cache blocking
- Blocked matrix multiplication
Instead of operating on complete rows and columns, the matrices are divided into smaller blocks:
A = B =
┌─────┬─────┐ ┌─────┬─────┐
│ A11 │ A12 │ │ B11 │ B12 │
├─────┼─────┤ ├─────┼─────┤
│ A21 │ A22 │ │ B21 │ B22 │
└─────┴─────┘ └─────┴─────┘
The objective is to make the active portions of:
A
B
C
small enough to remain in cache while they are being reused.
A representative blocked implementation follows:
for (int ii = 0; ii < N; ii += BS) {
for (int kk = 0; kk < N; kk += BS) {
for (int jj = 0; jj < N; jj += BS) {
for (int i = ii; i < i_max; i++) {
for (int k = kk; k < k_max; k++) {
double a = A[i][k];
for (int j = jj; j < j_max; j++) {
C[i][j] += a * B[k][j];
}
}
}
}
}
}The internal:
i → k → j
ordering is particularly useful because:
B[k][j]is now traversed across a row when j changes.
That provides much better spatial locality.
The optimized implementation also stores:
A[i][k]in a local variable:
double a_value = A[i][k];and reuses it across multiple values of j.
Instead of repeatedly loading:
A[i][k]
from memory, the processor can potentially keep it in a register.
One implementation explicitly chooses a block size based on L1 cache capacity.
The approximate assumption is that three blocks must coexist:
A block
+
B block
+
C block
For matrices of double values:
8 bytes / element
the approximate storage requirement is:
[ 3 \times BS^2 \times 8 ]
The implementation reserves only part of the cache to avoid filling it completely:
sqrt(0.8 * L1_size / 24)and rounds the result to a multiple of 16.
An additional implementation is specifically adapted for macOS and Apple Silicon.
It uses:
sysctlbyname()to inspect cache properties such as:
hw.perflevel0.l1dcachesize
hw.perflevel1.l1dcachesize
hw.l1dcachesize
Because Apple Silicon contains heterogeneous performance and efficiency cores, the implementation chooses the minimum detected L1-data-cache size.
Conceptually:
Performance-core L1
│
├──► minimum L1 size
│
Efficiency-core L1
│
▼
Calculate safe block size
│
▼
Blocked matrix multiplication
A manual block size can also be supplied from the command line.
The report includes measurements for:
N = 2000
N = 4000
on an Apple M4 Pro.
| Matrix size | Naive | Blocked | Improvement |
|---|---|---|---|
| 2000 × 2000 | 15.113 s | 7.890 s | ~47.8% |
| 4000 × 4000 | 429.011 s | 64.626 s | ~84.9% |
The benefit of blocking becomes particularly visible for the larger matrix.
For N = 4000, execution time decreases from approximately:
429 s
to:
65 s
which is around a:
6.6× speedup
in the stored -O0 experiment.
The project also studies compiler optimization using:
-O3Typical optimizations enabled at high optimization levels include:
- Automatic vectorization
- Loop transformations
- Loop unrolling
- Register allocation improvements
- Instruction scheduling
- Common-subexpression elimination
- Dead-code elimination
- Better inlining
- Strength reduction
The stored blocked benchmarks report:
| Matrix size | -O0 |
-O3 |
|---|---|---|
| 2000 × 2000 | 7.890 s | 1.020 s |
| 4000 × 4000 | 64.626 s | 8.469 s |
This corresponds to roughly:
7.7× speedup
for the blocked version when moving from the stored -O0 build to the stored -O3 build.
The naive -O3 experiment originally produced execution times around:
0.000002 s
0.000004 s
for matrices of size 2000 and 4000.
These values are not valid matrix-multiplication benchmarks.
The most likely explanation is compiler dead-code elimination.
The program computes:
C = A × B
but never uses the resulting matrix afterward.
From the compiler's perspective, the calculation may therefore have no observable effect.
At high optimization levels, the compiler can legally eliminate much or all of the computation.
To ensure that matrix multiplication is actually executed, the resulting matrix should have an observable use.
For example:
double checksum = 0.0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
checksum += C[i][j];
}
}
printf("Checksum: %.10f\n", checksum);This prevents the compiler from trivially removing the calculation.
The project report explicitly identifies this issue, which is an important lesson in performance engineering:
Benchmarking optimized code requires verifying that the compiler has not optimized away the workload itself.
Some implementations use:
clock()while the Apple M4 Pro-specific version uses:
clock_gettime(CLOCK_MONOTONIC, ...)A monotonic wall-clock timer is generally preferable for benchmarking elapsed execution time.
Example:
static double walltime(void) {
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return ts.tv_sec + ts.tv_nsec * 1e-9;
}Several additional optimization strategies are discussed.
Instead of repeatedly accessing columns:
B[k][j]a transposed matrix could transform the access into contiguous row traversal.
Changing loop order can significantly improve data reuse.
For example:
i → k → j
often provides better memory behavior than:
i → j → k
for row-major arrays.
High-performance builds can explore:
-O3and architecture-specific optimization options where supported.
Modern CPUs can perform several floating-point operations simultaneously using SIMD instructions.
Compiler vectorization can take advantage of this when memory layouts and aliasing rules permit it.
Aligning arrays to cache-line or SIMD boundaries may further improve performance.
A cleaned public version could use:
cache-aware-matrix-multiplication/
│
├── src/
│ ├── naive.c
│ ├── blocked.c
│ ├── blocked_optimized.c
│ └── blocked_apple_silicon.c
│
├── docs/
│ ├── assignment.pdf
│ └── report.pdf
│
├── README.md
└── .gitignore
The original submission includes multiple intermediate source versions and compiled Apple Silicon executables.
Without compiler optimization:
cc -O0 src/naive.c -o naive_O0With optimization:
cc -O3 src/naive.c -o naive_O3cc -O0 src/blocked_optimized.c -o blocked_O0and:
cc -O3 src/blocked_optimized.c -o blocked_O3On platforms supporting architecture-specific compiler options, additional tuning flags may also be evaluated.
Example:
./naive_O0or:
./blocked_O3The Apple Silicon cache-aware implementation also supports matrix size and block size parameters:
./blocked_apple_silicon 2000or:
./blocked_apple_silicon 2000 64where:
2000 = matrix dimension
64 = manually selected block size
If no block size is supplied, the program attempts to derive one from the detected L1 data-cache size.
This project demonstrates:
- Dense Matrix Multiplication
- Computational Complexity
- Memory Hierarchy
- Cache Locality
- Cache Misses
- Spatial Locality
- Temporal Locality
- Cache Blocking
- Loop Tiling
- Loop Reordering
- Data Reuse
- L1 Cache
- Compiler Optimization
- Dead-Code Elimination
- Automatic Vectorization
- Benchmarking
- Apple Silicon
- C Performance Programming
The naive algorithm performs the required arithmetic correctly, but its traversal of matrix B has poor spatial locality.
For the stored N = 4000, -O0 experiment, blocking reduces execution time from approximately 429 seconds to 65 seconds.
As the working set moves farther beyond cache capacity, memory locality becomes increasingly important.
-O3 substantially improves the blocked implementation, but compiler flags do not replace thoughtful cache-aware algorithm design.
The near-zero naive -O3 result demonstrates why optimized workloads need an observable result such as a checksum.
Developed for:
Arquitecturas para el Procesamiento Masivo de Datos
Academic year:
2025–2026
Authors:
- Junjing Wu
- Yixuan Lu Guo
Benchmark platform:
Apple M4 Pro
macOS
ARM64
The original experiments were designed as an academic performance study rather than a production BLAS implementation.
Benchmark results are hardware- and compiler-dependent.
The naive -O3 measurements in the original report should not be interpreted as real matrix-multiplication performance because the compiler appears to have eliminated unused computation.
The project also does not attempt to compete with highly optimized libraries such as BLAS implementations, which may use:
- Architecture-specific assembly
- SIMD microkernels
- Multithreading
- Packing
- Multiple cache levels
- Advanced prefetching
Future work could include:
- Add a checksum to every benchmark
- Use one common monotonic timer
- Automate repeated benchmark runs
- Report median and variance
- Calculate GFLOPS
- Sweep multiple block sizes automatically
- Compare L1-, L2-, and L3-aware tiling
- Explicitly transpose matrix B
- Add SIMD intrinsics
- Compare compiler-generated assembly
- Use
restrictpointers - Experiment with aligned allocation
- Compare GCC and Clang
- Compare against OpenBLAS
- Compare against Apple Accelerate
- Add multithreaded OpenMP multiplication
- Profile cache misses using hardware performance counters
Benchmark results are specific to the hardware, compiler, source version, matrix size, and compilation flags used in each experiment.