比较Python、Numpy、Numba和C++在矩阵乘法方面的表现。

27
在我正在开发的程序中,我需要反复相乘两个矩阵。由于其中一个矩阵的大小,这个操作需要一些时间,因此我想知道哪种方法是最有效的。这些矩阵的维度为 (m x n)*(n x p),其中 m = n = 3,且 10^5 < p < 10^6
除了我认为会使用优化算法的Numpy之外,每个测试都包括对矩阵乘法的简单实现。

Matrix multiplication

以下是我的各种实现:
Python
def dot_py(A,B):
    m, n = A.shape
    p = B.shape[1]

    C = np.zeros((m,p))

    for i in range(0,m):
        for j in range(0,p):
            for k in range(0,n):
                C[i,j] += A[i,k]*B[k,j] 
    return C

Numpy

def dot_np(A,B):
    C = np.dot(A,B)
    return C

Numba

这段代码与Python代码相同,但在使用之前会即时编译:

dot_nb = nb.jit(nb.float64[:,:](nb.float64[:,:], nb.float64[:,:]), nopython = True)(dot_py)

到目前为止,每个方法调用都使用timeit模块计时10次。保留最佳结果。矩阵是使用np.random.rand(n,m)创建的。 C++
mat2 dot(const mat2& m1, const mat2& m2)
{
    int m = m1.rows_;
    int n = m1.cols_;
    int p = m2.cols_;

    mat2 m3(m,p);

    for (int row = 0; row < m; row++) {
        for (int col = 0; col < p; col++) {
            for (int k = 0; k < n; k++) {
                m3.data_[p*row + col] += m1.data_[n*row + k]*m2.data_[p*k + col];
            }
        }
    }

    return m3;
}

这里,mat2是我定义的自定义类,dot(const mat2& m1, const mat2& m2)是该类的友元函数。使用Windows.h中的QPFQPC进行计时,程序使用g++命令在MinGW下编译。同样,从10次执行中获得的最佳时间被保留。

结果

Results

正如预期的那样,简单的Python代码虽然比Numpy慢,但对于非常小的矩阵仍然胜过Numpy。对于最大的情况,Numba比Numpy快约30%。
我对C++的结果感到惊讶,其中乘法所需的时间几乎比Numba长一个数量级。事实上,我原以为它们需要相似的时间。
这引出了我的主要问题:这是正常现象吗?如果不是,为什么C++比Numba慢?我刚开始学习C++,所以可能做错了什么。如果是这样,我的错误是什么,或者我能做些什么来提高代码的效率(除了选择更好的算法)?
编辑1:
这是mat2类的头文件。
#ifndef MAT2_H
#define MAT2_H

#include <iostream>

class mat2
{
private:
    int rows_, cols_;
    float* data_;

public: 
    mat2() {}                                   // (default) constructor
    mat2(int rows, int cols, float value = 0);  // constructor
    mat2(const mat2& other);                    // copy constructor
    ~mat2();                                    // destructor

    // Operators
    mat2& operator=(mat2 other);                // assignment operator

    float operator()(int row, int col) const;
    float& operator() (int row, int col);

    mat2 operator*(const mat2& other);

    // Operations
    friend mat2 dot(const mat2& m1, const mat2& m2);

    // Other
    friend void swap(mat2& first, mat2& second);
    friend std::ostream& operator<<(std::ostream& os, const mat2& M);
};

#endif

编辑2

正如许多人建议的那样,使用优化标志是与Numba匹配的缺失元素。以下是新曲线与先前曲线的比较。标记为v2的曲线通过交换两个内部循环获得,并显示出另外30%至50%的改进。

Results v2


4
很惊讶......我无法想象你将会看到极其巨大的速度提升,但你是否尝试使用编译器优化标志例如"-O3"?基本用法是"g++ *.cpp -std=c++11 -O3"。 - MS-DDOS
2
你是否以任何方式从Python中调用这个C++函数,还是直接调用已编译的程序? - MS-DDOS
1
@Eric:这是一个希望,但不能成为编写代码的借口。这有点像期望你的妻子替你整理房间一样 :-) - cdarke
1
查找缓存未命中,这很可能是你的 C++ 失败的地方之一。 - Reblochon Masque
1
@TylerS 我更新了我的问题(请参见第二次编辑),并使用“-O3”列出了结果。这是你要找的吗? - JD80121
显示剩余13条评论
5个回答

11

一定要使用-O3进行优化。这会开启向量化功能,应该显著加快代码速度。

Numba 已经可以做到这一点了。


10

我的建议

如果你想实现最大效率,应使用专用的线性代数库,其中经典的是BLAS/LAPACK库。有许多实现方式,例如Intel MKL。你自己写的代码不可能比超级优化的库更快。

矩阵-矩阵乘法将使用dgemm例程:d表示double,ge表示general,mm表示matrix matrix multiply(矩阵-矩阵乘法)。 如果你的问题具有更多的结构,则需要调用更特定的函数以获得额外的加速。

注意,Numpy点乘已经调用了dgemm!你可能做不到更好。

为什么你的C++很慢

对于矩阵-矩阵乘法,您经典、直观的算法变得相对较慢。编写利用处理器缓存等方面的代码可以获得重要的性能提升。意思是,许多聪明的人都致力于使矩阵-矩阵乘法变得非常快,你应该使用他们的成果而不是重复发明轮子。


谢谢您的回答!我知道Numpy正在使用dgemm(实际上我已经查看了Fortran代码)。因此,我期望它能表现得更好。我使用O(n ^ 3)算法是为了简单起见,因为我已经用它比Numpy获得了更好的结果。最终,我的代码将包含更多自定义函数和嵌套循环,这些在优化库中不可用,现在我对如何实现它们有了更好的想法。 - JD80121
我认为优化的 dgemm 程序之所以比朴素实现更快,主要是因为利用了缓存和其他技术来充分利用处理器的实际工作方式,而不是 O(n^3) 的部分。虽然我并不是专家,对细节也不是很了解。 - Matthew Gunn

3
在您目前的实现中,最内层循环的大小为3,很可能编译器无法自动向量化。此外,m2 的访问方式比较“跳跃”。将循环交换,使得迭代 p 成为最内层循环,可以使其更快(col 不会造成“跳跃”数据访问),而编译器应该能够做得更好(自动向量化)。
for (int row = 0; row < m; row++) {
    for (int k = 0; k < n; k++) {
        for (int col = 0; col < p; col++) {
            m3.data_[p*row + col] += m1.data_[n*row + k] * m2.data_[p*k + col];
        }
    }
}

在我的计算机上,使用 g++ dot.cpp -std=c++11 -O3 -o dot 标志构建的原始C ++实现(p = 10 ^ 6)需要 12ms,而交换循环的以上实现则需要 7ms


1
你仍然可以通过改进内存访问来优化这些循环,你的函数可能如下所示(假设矩阵为1000x1000):
CS = 10
NCHUNKS = 100

def dot_chunked(A,B):
    C = np.zeros(1000,1000)

    for i in range(NCHUNKS):
        for j in range(NCHUNKS):
            for k in range(NCHUNKS):
                for ii in range(i*CS,(i+1)*CS):
                    for jj in range(j*CS,(j+1)*CS):
                        for kk in range(k*CS,(k+1)*CS):
                            C[ii,jj] += A[ii,kk]*B[kk,jj] 
    return C

说明:循环i和ii显然一起执行与之前的i相同,j和k也是如此,但这次可以在缓存中保留大小为CSxCS的A和B区域(我猜),并且可以多次使用。
您可以尝试使用CS和NCHUNKS进行操作。对于我来说,CS=10和NCHUNKS=100效果很好。使用numba.jit时,将代码加速了从7秒到850毫秒(请注意,我使用的是1000x1000,上面的图形是以3x3x10^5运行的,因此情况有所不同)。

0
Numba默认使用多线程,将Numba与单线程的C++代码进行比较是不公平的。我经常使用Numpy和Numba快速原型化科学应用程序,然后将计算密集部分转移到具有多线程的C++中,以获得更好的速度。有几个线程库可供选择 - OpenMP、pthreads和MPI。我发现OpenMP对我的需求来说既简单又有效。
在任何并行代码中,您必须注意竞争条件、虚假共享和关键或原子操作。一旦您理解了这些概念,利用OpenMP就非常简单。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接