Умножение и кеширование матрицы Python

Question

Я изучаю поведение кэширования на разных языках. Я создаю две матрицы в python, используя списки (да, я знаю, что это связанный список, но со мной здесь). Затем я перемножить эти матрицы вместе тремя способами:

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 

Мои тайминги заключаются в следующем:

Baseline: 
3.440004294627216 

Flip j and k: 
3.4685347505603144 
100.83% of baseline 

Blocking: 
2.729924394035205 
79.36% of baseline 

Некоторые вещи, чтобы отметить:

1. Я знаком с поведением кэширования процессора. Чтобы увидеть мой эксперимент в C, см. here, хотя я не получил никаких отзывов.

2. Я сделал это в Javascript и C# и функция флип-JK обеспечивает значительный прирост производительности, используя массивы (JS работать на хром браузер)

3. реализация Python является Python 3.5 путем Anaconda

4. Пожалуйста, не говорите мне о numpy. Мой эксперимент - это не абсолютная производительность, а понимание поведения кеширования.

Вопрос: Каждый знает, что здесь происходит? Почему flip-j-k не обеспечивает ускорение? Это потому, что это связанный список? Но почему же блокирование обеспечивает не-маргинальное улучшение производительности?

Answer 1

Последняя версия (умножение блока) выполняется только на 30%, потому что вы сохраняете 30% индекса, используя локальную переменную во внутреннем цикле!

(и FYI это не C++: list Тип подобен C++ vector, иначе люди будут тратить время на попытки доступа к элементам по индексу.Так что это самый быстрый стандартный контейнер с произвольным доступом, доступный в python)

Я только что сделал пробную программу на основе вашего кода, чтобы доказать свою точку зрения и то, что я подозревал (мне пришлось заполнить ваш код, извините за большой блок, но по крайней мере, минимально полный & подлежит проверке для всех).

def zero_matrix(sz): 
    return [[0]*sz for i in range(sz)] 

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 baseline_matrix_multiply_flipjk_faster(a, b, n): 
    ''' 
    same as baseline but switch j and k loops 
    ''' 
    c = zero_matrix(n) 
    for i in range(n): 
     ci = c[i] 
     for k in range(n): 
      bk = b[k] 
      aik = a[i][k] 
      for j in range(n): 
       ci[j] += aik * bk[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 

def fast_matrix_multiply_blocking_faster(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): 
       ai = a[i] 
       ci = c[i] 
       for j in range(jj, jj + block): 
        s = ci[j] 
        for k in range(kk, kk + block): 
         s += ai[k] * b[k][j] 
        ci[j] = s 
    return c 

def init_ab(sz): 
    return [list(range(sz)) for i in range(sz)],[[3]*sz for i in range(sz)] 

sz=200 


import time 

a,b = init_ab(sz) 

start_time=time.time() 
baseline_matrix_multiply(a,b,sz) 
print("baseline_matrix_multiply: "+str(time.time()-start_time)) 

a,b = init_ab(sz) 

start_time=time.time() 
baseline_matrix_multiply_flipjk(a,b,sz) 
print("baseline_matrix_multiply_flipjk: "+str(time.time()-start_time)) 

a,b = init_ab(sz) 


start_time=time.time() 
fast_matrix_multiply_blocking(a,b,sz) 
print("fast_matrix_multiply_blocking: "+str(time.time()-start_time)) 

a,b = init_ab(sz) 

start_time=time.time() 
baseline_matrix_multiply_flipjk_faster(a,b,sz) 
print("**baseline_matrix_multiply_flipjk_faster**: "+str(time.time()-start_time)) 

a,b = init_ab(sz) 

start_time=time.time() 
fast_matrix_multiply_blocking_faster(a,b,sz) 
print("**fast_matrix_multiply_blocking_faster**: "+str(time.time()-start_time)) 

результаты на моем компьютере (последние результаты в окружении звезд мои версии):

baseline_matrix_multiply: 2.578160047531128 
baseline_matrix_multiply_flipjk: 2.5315518379211426 
fast_matrix_multiply_blocking: 1.9359750747680664 
**baseline_matrix_multiply_flipjk_faster**: 1.4532990455627441 
**fast_matrix_multiply_blocking_faster**: 1.7031919956207275 

Как вы можете видеть, моя версия вашего baseline_matrix_multiply_flipjk (четвертый) быстрее, чем даже блок умножить, что означает, что проверка индекса &, обращаясь к гномам эффекта кеша, который вы можете испытать на скомпилированных языках &, используя прямые указатели, такие как C или C++.

Я просто сохранил значения, которые не менялись во внутреннем цикле (тот, который оптимизирован для большинства), чтобы избежать доступа к индексу.

Обратите внимание, что я попытался применить один и тот же рецепт к блоку умножить, и я получил некоторое время по сравнению с вашей версией, но по-прежнему избивается версией flipjk_faster из-за неспособности избежать доступа к индексу.

Возможно, компиляция кода с помощью Cython и падение чеков приведет к желаемому результату. Но предварительные вычисления индексов никогда не болят.

Answer 2

Python не кэширует результаты своих функций. Это требует явного уведомления о том, когда вы хотите создать кеш для функции. Вы можете сделать это, используя декоратор lrc_cache.

Следующий код, который я сбросил на другой день, и только что добавил некоторую читаемость. Если есть что-то неправильно, комментарий и я разберутся:

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])) 

КСТАТИ: «#» указывает на комментарий, в случае, если вы не знакомы с Python.

Так что попробуйте запустить это и попробуйте еще раз без «#» на линии #@lru_cache(maxsize=4, typed=False)

Кроме того, MAXSIZE максимального размера кэша (лучше всего работает в степенях двойки в соответствии с Документами) и напечатал только делает кэш добавляет новое состояние кэширования всякий раз, когда в качестве аргумента передается другой тип того же значения.

И, наконец, функция «Func» известна как функция Аккермана. Глупо глубокое количество рекурсии продолжается, поэтому будьте в курсе stackoverflows (lol), если вам нужно изменить максимальную глубину рекурсии.