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):
            ii=i
            jj=j
            while (ii < min(i + b, n)):
                while (jj < min(j + b, n)):
                    tab[ii][jj] = np.random.rand()
                    jj += b
                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)