Python Matrix Multiplication and Caching
<p>I am investigating caching behavior in different languages. I create two matrices in python using lists (yes, I know it's a linked list but bear with me here). I then multiply these matrices together in three ways:</p>

<pre><code>def baseline_matrix_multiply(a, b, n):
    '''
    baseline multiply
    '''
    c = zero_matrix(n)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c[i][j] += a[i][k] * b[k][j]
    return c


def baseline_matrix_multiply_flipjk(a, b, n):
    '''
    same as baseline but switch j and k loops
    '''
    c = zero_matrix(n)
    for i in range(n):
        for k in range(n):
            for j in range(n):
                c[i][j] += a[i][k] * b[k][j]
    return c


def fast_matrix_multiply_blocking(a, b, n):
    '''
    use blocking
    '''
    c = zero_matrix(n)

    block = 25;
    en = int(block * n/block)

    for kk in range(0, en, block):
        for jj in range(0, en, block):
            for i in range(n):
                for j in range(jj, jj + block):
                    sum = c[i][j]
                    for k in range(kk, kk + block):
                        sum += a[i][k] * b[k][j]
                    c[i][j] = sum
    return c
</code></pre>

<p>My timings are as follows:</p>

<pre><code>Baseline:
3.440004294627216

Flip j and k:
3.4685347505603144
100.83% of baseline

Blocking:
2.729924394035205
79.36% of baseline
</code></pre>

<p>Some things to note:</p>

<ol>
<li><p>I am familiar with CPU caching behavior. To see my experiment in C see <a href="http://codereview.stackexchange.com/questions/143061/cache-conscious-simd-matrix-multiply-of-unsigned-integers">here</a> though I havent gotten any reviews for it.</p></li>
<li><p>I've done this in Javascript and C# and the flip-j-k function provides significant performance gains using arrays (JS run on chrome browser)</p></li>
<li><p>Python implementation is Python 3.5 by way of Anaconda</p></li>
<li><p>Please dont tell me about numpy. My experiment is not about absolute performance but rather understanding caching behavior.</p></li>
</ol>

<p><strong>Question</strong>:
Anyone know what is going on here? Why does flip-j-k not provide speedup? Is it because it's a linked list? But then why does blocking provide a non-marginal improvement in performance?</p>

<p>Python tends to not cache the results of its functions. It requires explicit notice of when you want build a cache for a function. You can do this using the <code>lrc_cache</code> decorator.</p>

<p>The following is code I threw together the other day and I've just added some readability. If there's something wrong, comment and I'll sort it out:</p>

<pre><code>from functools import lru_cache

from random import randint as rand
from time import clock as clk

recur = 0

#@lru_cache(maxsize=4, typed=False)
def Func(m, n):
    global recur
    recur += 1
    if m == 0:
        return n + 1
    elif n == 0:
        return Func(m - 1, 1)
    else:
        return Func(m - 1, Func(m, n - 1))


n = []
m = 0

ITER = 50
F1 = 3
F2 = 4


staTime = clk()
for x in range (ITER):
    n.append(Func(F1, F2))

m += clk()-staTime

print("Uncached calls of Func:: "+str(recur//ITER))
print("Average time per solving of Ackerman's function:: "+str(m/ITER))
print("End result:: "+str(n[0]))
</code></pre>

<p>BTW: "#" indicates a comment, in case you're unfamiliar with Python.</p>

<p>So try running this and try AGAIN without the "#" on the line <code>#@lru_cache(maxsize=4, typed=False)</code> </p>

<p>Additionally, maxsize is the maximum size of the cache (works best in powers of two according to the docs) and typed just makes the cache add a new cached condition whenever a different type of the same value is passed as an argument.</p>

<p>Finally, the "Func" function is known as Ackermann's function. A stupidly deep amount of recursion goes on so be aware of stackoverflows (lol) if you should change the max recursion depth.</p>

python caching matrix