为什么矩阵乘法比numpy更快而不是Python中的ctypes？

Question

我试图找出最快的矩阵乘法方法,尝试了3种不同的方法:

• 纯python实现:这里没有惊喜.
• Numpy实现使用 numpy.dot(a, b)
• 使用ctypesPython中的模块与C连接.

这是转换为共享库的C代码:

#include <stdio.h>
#include <stdlib.h>

void matmult(float* a, float* b, float* c, int n) {
    int i = 0;
    int j = 0;
    int k = 0;

    /*float* c = malloc(nay * sizeof(float));*/

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            int sub = 0;
            for (k = 0; k < n; k++) {
                sub = sub + a[i * n + k] * b[k * n + j];
            }
            c[i * n + j] = sub;
        }
    }
    return ;
}

以及调用它的Python代码:

def C_mat_mult(a, b):
    libmatmult = ctypes.CDLL("./matmult.so")

    dima = len(a) * len(a)
    dimb = len(b) * len(b)

    array_a = ctypes.c_float * dima
    array_b = ctypes.c_float * dimb
    array_c = ctypes.c_float * dima

    suma = array_a()
    sumb = array_b()
    sumc = array_c()

    inda = 0
    for i in range(0, len(a)):
        for j in range(0, len(a[i])):
            suma[inda] = a[i][j]
            inda = inda + 1
        indb = 0
    for i in range(0, len(b)):
        for j in range(0, len(b[i])):
            sumb[indb] = b[i][j]
            indb = indb + 1

    libmatmult.matmult(ctypes.byref(suma), ctypes.byref(sumb), ctypes.byref(sumc), 2);

    res = numpy.zeros([len(a), len(a)])
    indc = 0
    for i in range(0, len(sumc)):
        res[indc][i % len(a)] = sumc[i]
        if i % len(a) == len(a) - 1:
            indc = indc + 1

    return res

我敢打赌,使用C的版本会更快......而且我已经输了!下面是我的基准测试,似乎表明我numpy做错了,或者说是愚蠢的快:

我想理解为什么numpy版本比版本更快ctypes,我甚至都没有谈论纯Python实现,因为它很明显.

Answer 1

NumPy使用高度优化,经过精心调整的BLAS方法进行矩阵乘法(另请参见:ATLAS).这种情况下的具体功能是GEMM(用于通用矩阵乘法).您可以通过搜索dgemm.f(它在Netlib中)来查找原始文件.

顺便说一句,优化超越了编译器优化.上面,菲利普提到了Coppersmith-Winograd.如果我没记错的话,这就是在ATLAS中用于大多数矩阵乘法的算法(尽管评论者指出它可能是Strassen的算法).

换句话说,您的matmult算法是简单的实现.有更快的方法来做同样的事情.

Answer 2

我对Numpy不太熟悉,但是源代码是Github.dot产品的一部分在https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/arraytypes.c.src中实现,我假设它被转换为每个特定的C实现数据类型.例如:

/**begin repeat
 *
 * #name = BYTE, UBYTE, SHORT, USHORT, INT, UINT,
 * LONG, ULONG, LONGLONG, ULONGLONG,
 * FLOAT, DOUBLE, LONGDOUBLE,
 * DATETIME, TIMEDELTA#
 * #type = npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int, npy_uint,
 * npy_long, npy_ulong, npy_longlong, npy_ulonglong,
 * npy_float, npy_double, npy_longdouble,
 * npy_datetime, npy_timedelta#
 * #out = npy_long, npy_ulong, npy_long, npy_ulong, npy_long, npy_ulong,
 * npy_long, npy_ulong, npy_longlong, npy_ulonglong,
 * npy_float, npy_double, npy_longdouble,
 * npy_datetime, npy_timedelta#
 */
static void
@name@_dot(char *ip1, npy_intp is1, char *ip2, npy_intp is2, char *op, npy_intp n,
           void *NPY_UNUSED(ignore))
{
    @out@ tmp = (@out@)0;
    npy_intp i;

    for (i = 0; i < n; i++, ip1 += is1, ip2 += is2) {
        tmp += (@out@)(*((@type@ *)ip1)) *
               (@out@)(*((@type@ *)ip2));
    }
    *((@type@ *)op) = (@type@) tmp;
}
/**end repeat**/

这似乎是计算一维点积,即在矢量上.在Github浏览的几分钟内,我无法找到矩阵的来源,但它可能会对FLOAT_dot结果矩阵中的每个元素使用一次调用.这意味着此函数中的循环对应于最内层循环.

它们之间的一个区别是"步幅" - 输入中连续元素之间的差异 - 在调用函数之前显式计算一次.在您的情况下,没有步幅,并且每次计算每个输入的偏移,例如a[i * n + k].我本来期望一个好的编译器可以将其优化到类似于Numpy步幅的东西,但也许它不能证明该步骤是一个常量(或者它没有被优化).

Numpy也可能在调用此函数的高级代码中使用缓存效果做一些聪明的事情.一个常见的技巧是考虑每一行是连续的还是每一列 - 并尝试首先迭代每个连续的部分.似乎很难完美地优化,对于每个点积,一个输入矩阵必须由行遍历,另一个输入矩阵必须由列遍历(除非它们碰巧以不同的主要顺序存储).但它至少可以为结果元素做到这一点.

Numpy还包含用于从不同的基本实现中选择某些操作(包括"dot")的实现的代码.例如,它可以使用BLAS库.从上面的讨论来看,听起来像使用了CBLAS.这是从Fortran转换为C.我认为您的测试中使用的实现将是这里找到的实现:http://www.netlib.org/clapack/cblas/sdot.c.

请注意,该程序是由另一台机器读取的机器编写的.但你可以在底部看到它使用一个展开的循环来一次处理5个元素:

for (i = mp1; i <= *n; i += 5) {
stemp = stemp + SX(i) * SY(i) + SX(i + 1) * SY(i + 1) + SX(i + 2) * 
    SY(i + 2) + SX(i + 3) * SY(i + 3) + SX(i + 4) * SY(i + 4);
}

在分析几个之后,可能已经选择了这个展开因子.但它的一个理论优势是在每个分支点之间进行了更多的算术运算,并且编译器和CPU在如何最佳地调度它们以获得尽可能多的指令流水线方面有更多的选择.

Answer 3

用于实现某种功能的语言本身就是一种糟糕的性能衡量标准.通常,使用更合适的算法是决定因素.

在你的情况下,你正在使用学校教授的矩阵乘法的天真方法,即O(n ^ 3).但是,对于某些类型的矩阵,您可以做得更好,例如方形矩阵,备用矩阵等.

看看Coppersmith-Winograd算法(O(n ^ 2.3737)中的方阵乘法)是快速矩阵乘法的良好起点.另请参阅"参考"部分,其中列出了更快速方法的一些指示.

对于一个惊人的性能提升的更朴实的例子,尝试编写一个快速strlen()并将其与glibc实现进行比较.如果你没有设法击败它,请阅读glibc的strlen()来源,它有相当不错的评论.

Answer 4

编写 NumPy 的人显然知道他们在做什么。

有很多方法可以优化矩阵乘法。例如，遍历矩阵的顺序会影响内存访问模式，从而影响性能。
充分利用 SSE 是另一种优化方法，NumPy 可能会采用这种方法。
可能还有更多方法，NumPy 的开发人员知道而我不知道。

顺便说一句，你编译你的 C 代码了吗？

您可以尝试对 C 进行以下优化。它确实可以并行工作，而且我认为 NumPy 也可以做同样的事情。
注意：仅适用于均匀尺寸。通过额外的工作，您可以消除此限制并保持性能改进。

for (i = 0; i < n; i++) {
        for (j = 0; j < n; j+=2) {
            int sub1 = 0, sub2 = 0;
            for (k = 0; k < n; k++) {
                sub1 = sub1 + a[i * n + k] * b[k * n + j];
                sub1 = sub1 + a[i * n + k] * b[k * n + j + 1];
            }
            c[i * n + j]     = sub;
            c[i * n + j + 1] = sub;
        }
    }
}

Answer 5

Numpy 也是高度优化的代码。在《美丽的代码》一书中有一篇关于它的部分内容的文章。

ctypes 必须经历从 C 到 Python 的动态转换，然后再返回，这会增加一些开销。在 Numpy 中，大多数矩阵运算完全在其内部完成。