问为什么在Python中使用numpy进行矩阵乘法要比使用ctype快？

EN

我对Numpy不是很熟悉，但它的源码在Github上。部分点积是用https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/arraytypes.c.src，实现的，我假设它被转换成每种数据类型的特定C实现。例如：

这似乎是在计算一维点积，即对向量进行计算。在我浏览Github的几分钟内，我无法找到矩阵的源代码，但它可能会对结果矩阵中的每个元素使用一次对FLOAT_dot的调用。这意味着这个函数中的循环对应于最里面的循环。

它们之间的一个区别是“步幅”-输入中连续元素之间的差异-在调用函数之前显式计算一次。在你的例子中没有步幅，每次输入的偏移量都是计算出来的，例如a[i *n+ k]。我曾期望一个好的编译器能将它优化成类似于Numpy stride的东西，但它可能无法证明步长是一个常数(或者它没有被优化)。

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

Numpy还包含代码，用于从不同的基本实现中选择特定操作的实现，包括“点”。例如，它可以使用BLAS库。从上面的讨论看，似乎使用了CBLAS。这是从Fortran翻译成C的。我认为你的测试中使用的实现应该是在这里找到的: http://www.netlib.org/clapack/cblas/sdot.c.

请注意，此程序是由一台机器编写的，以供另一台机器读取。但您可以在底部看到，它使用一个展开的循环一次处理5个元素：

这个展开因子很可能是在分析了几个之后选择的。但它的一个理论优势是在每个分支点之间进行更多的算术操作，编译器和CPU有更多的选择来优化它们，以获得尽可能多的指令流水线。

NumPy使用高度优化、精心调整的BLAS方法进行矩阵乘法(另请参阅: ATLAS)。本例中的特定函数是GEMM (用于通用矩阵乘法)。你可以通过搜索dgemm.f (它在Netlib中)来查找原文。

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

换句话说，您的matmult算法是微不足道的实现。有更快的方法来做同样的事情。

用来实现某种功能的语言本身就不能很好地衡量性能。通常，使用更合适的算法是决定性因素。

在您的例子中，您使用的是学校教授的简单的矩阵乘法，它在O(n^3)中。然而，对于某些类型的矩阵，你可以做得更好，例如方阵，备用矩阵等等。

看看Coppersmith-Winograd算法(O(n^2.3737)中的方阵乘法)，作为快速矩阵乘法的良好起点。另请参阅“参考”一节，其中列出了一些指向更快方法的指针。

有关惊人性能提升的更真实示例，请尝试编写一个fast strlen()，并将其与glibc实现进行比较。如果你不能击败它，请阅读glibc的strlen()源代码，它有相当不错的评论。