Illustration of "cache blocking" optimization technique on a 10000x10000 matrix fill.

cache_blocking.py

import numpy as np
import matplotlib.pyplot as plt
import timeit

plt.ion()

n=10000
block=[i+1 for i in range(1000)]
time=[]
tab=[[0 for i in range(n)] for j in range(n)]
for b in block:
    start_time=timeit.default_timer()
    for i in range(b):
        for j in range(b):
            for ii in range(i, min(i + b, n) + 1, b):
                for jj in range(j, min(j + b, n) + 1, b):
                    tab[ii][jj] = np.random.rand()
                ii += b
    elapsed = timeit.default_timer() - start_time
    print("block: " + str(b) + ", elapsed: " + str(elapsed))
    time.append(elapsed)
    plt.scatter(b, elapsed)
    plt.pause(0.05)
    
while True:
    plt.pause(0.05)