为什么我的Python NumPy代码比C++快?

16

为什么这段Python NumPy代码,

import numpy as np
import time

k_max = 40000
N = 10000

data = np.zeros((2,N))
coefs = np.zeros((k_max,2),dtype=float)

t1 = time.time()
for k in xrange(1,k_max+1):
    cos_k = np.cos(k*data[0,:])
    sin_k = np.sin(k*data[0,:])
    coefs[k-1,0] = (data[1,-1]-data[1,0]) + np.sum(data[1,:-1]*(cos_k[:-1] - cos_k[1:]))
    coefs[k-1,1] = np.sum(data[1,:-1]*(sin_k[:-1] - sin_k[1:]))
t2 = time.time()

print('Time:')
print(t2-t1)

比以下的C++代码更快吗?

#include <cstdio>
#include <iostream>
#include <cmath>
#include <time.h>

using namespace std;

// consts
const unsigned int k_max = 40000;
const unsigned int N = 10000;

int main()
{
    time_t start, stop;
    double diff;
    // table with data
    double data1[ N ];
    double data2[ N ];
    // table of results
    double coefs1[ k_max ];
    double coefs2[ k_max ];
    // main loop
    time( & start );
    for( unsigned int j = 1; j<N; j++ )
    {
        for( unsigned int i = 0; i<k_max; i++ )
        {
            coefs1[ i ] += data2[ j-1 ]*(cos((i+1)*data1[ j-1 ]) - cos((i+1)*data1[ j ]));
            coefs2[ i ] += data2[ j-1 ]*(sin((i+1)*data1[ j-1 ]) - sin((i+1)*data1[ j ]));
        }
    }
    // end of main loop
    time( & stop );
    // speed result
    diff = difftime( stop, start );
    cout << "Time: " << diff << " seconds";
    return 0;
}

第一个显示:"时间:8秒",而第二个显示:"时间:11秒"

我知道NumPy是用C编写的,但我仍然认为C++示例会更快。我有什么遗漏的吗?有没有办法改进C++代码(或Python代码)?

代码版本2

如建议中所述,我已将C++代码更改为动态表格为静态表格。现在C++代码速度更快了,但仍比Python版本慢得多。

代码版本3

我已从调试模式更改为发布模式,并将“k”从4000增加到40000。现在NumPy略微更快(8秒到11秒)。


2
可能是因为您正在使用指向动态分配数组的指针数组,而不是单个内存块。 - juanchopanza
4
我在我的机器上得到了 Time: 1 sekund。你有没有碰巧以调试模式运行C++代码? - Bo Persson
2
@Mateusz 在你的numpy示例中,我相信所有的数据都是0(我认为这就是.zeros的作用)。如果你先将C++应用程序中的所有数据设置为0会发生什么? - RyanP
3
我也运行了这段 C++ 代码,结果也是1秒,而 Python 代码的时间与所述相同 - 所以很可能是调试模式的原因。 - Gwidryj
2
@Gwidryj 我的电脑上没有安装Python,所以我选择了ideone来测试它。我可以理解为什么Python版本会超时(考虑到问题中提到的时间范围),但由于C++代码在不到一秒钟的时间内完成,它显然比Python版本更快。这就是我评论的全部意义。 - Algirdas Preidžius
显示剩余9条评论
5个回答

54

我觉得这个问题很有趣,因为每次我遇到类似 NumPy 速度(与 C/C++ 相比)的话题时,总会有答案说“它只是一个薄薄的包装层,其核心是用 C 编写的,所以它很快”,但这并不能解释为什么带有额外层(即使是薄的一层)的 C 应该比 C 更慢。

答案是:当正确编译时,你的 C++ 代码不会比你的 Python 代码慢

我做了一些基准测试,起初 NumPy 似乎更快。但我忘记了使用GCC优化编译。

我重新计算了所有内容,并将结果与你的代码的纯 C++ 版本进行了比较。 我正在使用 GCC 版本4.9.2 和Python 2.7.9(使用相同的 GCC 从源代码编译)。 编译你的 C++ 代码时,我使用了g++ -O3 main.cpp -o main,编译我的 C 代码时,我使用了gcc -O3 main.c -lm -o main。 在所有示例中,我使用一些数字(0.1、0.4)填充了data变量,因为它会改变结果。 我也将 np.arrays 更改为使用双精度浮点数 (dtype=np.float64),因为 C++ 示例中有双精度浮点数。我的纯 C 代码版本(类似于你的代码):

#include <math.h>
#include <stdio.h>
#include <time.h>

const int k_max = 100000;
const int N = 10000;

int main(void)
{
    clock_t t_start, t_end;
    double data1[N], data2[N], coefs1[k_max], coefs2[k_max], seconds;
    int z;
    for( z = 0; z < N; z++ )
    {
        data1[z] = 0.1;
        data2[z] = 0.4;
    }

    int i, j;
    t_start = clock();
    for( i = 0; i < k_max; i++ )
    {
        for( j = 0; j < N-1; j++ )
        {
            coefs1[i] += data2[j] * (cos((i+1) * data1[j]) - cos((i+1) * data1[j+1]));
            coefs2[i] += data2[j] * (sin((i+1) * data1[j]) - sin((i+1) * data1[j+1]));
        }
    }
    t_end = clock();

    seconds = (double)(t_end - t_start) / CLOCKS_PER_SEC;
    printf("Time: %f s\n", seconds);
    return coefs1[0];
}

对于k_max=100000,N=10000的结果如下:

  • Python 70.284362 s
  • C++ 69.133199 s
  • C 61.638186 s

Python和C++的时间基本相同,但请注意Python有一个长度为k_max的循环,应该比C/C++的循环慢得多。确实如此。

对于k_max=1000000,N=1000,我们有:

  • Python 115.42766 s
  • C++ 70.781380 s

对于k_max=1000000,N=100:

  • Python 52.86826 s
  • C++ 7.050597 s

因此,差异随着k_max/N的分数而增加,但即使是Nk_max大得多,例如k_max=100,N=100000,Python也不会更快:

  • Python 0.651587 s
  • C++ 0.568518 s

显然,C/C++和Python之间的主要速度差异在于for循环。但我想找出NumPy中数组上简单操作与C中数组操作之间的差异。在代码中使用NumPy的优点包括:1. 用一个数乘以整个数组,2. 计算整个数组的sin/cos,3. 对数组的所有元素求和,而不是对每个单独项目进行这些操作。因此,我准备了两个脚本来仅比较这些操作。

Python脚本:

import numpy as np
from time import time

N = 10000
x_len = 100000

def main():
    x = np.ones(x_len, dtype=np.float64) * 1.2345

    start = time()
    for i in xrange(N):
        y1 = np.cos(x, dtype=np.float64)
    end = time()
    print('cos: {} s'.format(end-start))

    start = time()
    for i in xrange(N):
        y2 = x * 7.9463
    end = time()
    print('multi: {} s'.format(end-start))

    start = time()
    for i in xrange(N):
        res = np.sum(x, dtype=np.float64)
    end = time()
    print('sum: {} s'.format(end-start))

    return y1, y2, res

if __name__ == '__main__':
    main()

# results
# cos: 22.7199969292 s
# multi: 0.841291189194 s
# sum: 1.15971088409 s

C脚本:

#include <math.h>
#include <stdio.h>
#include <time.h>

const int N = 10000;
const int x_len = 100000;

int main()
{
    clock_t t_start, t_end;
    double x[x_len], y1[x_len], y2[x_len], res, time;
    int i, j;
    for( i = 0; i < x_len; i++ )
    {
        x[i] = 1.2345;
    }

    t_start = clock();
    for( j = 0; j < N; j++ )
    {
        for( i = 0; i < x_len; i++ )
        {
            y1[i] = cos(x[i]);
        }
    }
    t_end = clock();
    time = (double)(t_end - t_start) / CLOCKS_PER_SEC;
    printf("cos: %f s\n", time);

    t_start = clock();
    for( j = 0; j < N; j++ )
    {
        for( i = 0; i < x_len; i++ )
        {
            y2[i] = x[i] * 7.9463;
        }
    }
    t_end = clock();
    time = (double)(t_end - t_start) / CLOCKS_PER_SEC;
    printf("multi: %f s\n", time);

    t_start = clock();
    for( j = 0; j < N; j++ )
    {
        res = 0.0;
        for( i = 0; i < x_len; i++ )
        {
            res += x[i];
        }
    }
    t_end = clock();
    time = (double)(t_end - t_start) / CLOCKS_PER_SEC;
    printf("sum: %f s\n", time);

    return y1[0], y2[0], res;
}

// results
// cos: 20.910590 s
// multi: 0.633281 s
// sum: 1.153001 s

Python结果:

  • 余弦:22.7199969292 秒
  • 乘法:0.841291189194 秒
  • 求和:1.15971088409 秒

C结果:

  • 余弦:20.910590 秒
  • 乘法:0.633281 秒
  • 求和:1.153001 秒

正如您所看到的,NumPy非常快,但始终比纯C慢一些。


@JerryCoffin 我认为这只是一个小错误,而不是“甚至似乎没有尝试做相同的事情”。你可以只说“在j循环中放入N-1”而不是重复“未定义的行为”。无论如何,时间几乎相同 - 我刚刚检查了修正后的版本。 - Gwidryj
2
@JerryCoffin 我认为我在上面的一段话中已经解释清楚了,但让其他人来评判吧。 - Gwidryj
点赞。感谢您对cos、乘法和求和函数进行比较!对于C语言而言,代码比Python版本要多得多。因此,如果Python的制表符不会让人烦恼,那么这是一种增加约2秒时间的方法... - analytical_prat
2
@analytical_prat 一般规则是使用最简单、最表达力强和最高级的语言,同时保证足够快速。这样做会更容易,因为它生成的代码更小,具有更少的错误机会,并且使用更高级别的操作进一步减少了错误的可能性(例如,执行标量乘以矩阵与使用for循环实现相同的效果)。直接转向C++可能意味着您可能正在进行过早的优化(或者您可能最擅长该语言)。我怀疑对于非平凡情况,C++模板表达式比标量乘以矩阵要快得多。 - user904963
2
基准测试有缺陷:coefs2y1y2被写入但未被读取或使用。因此,优化编译器可以将循环删除,因为它们没有任何“副作用”(在C/C++中称为“as if rule”)。实际上,一些编译器如Clang确实这样做!例如,带有-O3的Clang 13不计算y2。ICC进行了更多的优化:它不计算y1y2。尽管OP代码已经存在这个问题,但希望主流编译器还没有聪明到优化这部分。 - Jérôme Richard
显示剩余3条评论

9

我很惊讶没有人提到 BLAS、 LAPACK、MKL 等线性代数库......

Numpy 使用复杂的线性代数库! 实际上,Numpy 大多数情况下不是基于纯 C/C++/Fortran 代码构建的...... 它实际上是建立在复杂的库之上的,这些库利用最有效的算法和思想来优化代码。与经典的线性代数计算的朴素实现相比,这些复杂的库几乎是无法匹配的。最简单的第一个改进示例是阻塞技巧。

我从 ETH 的 CSE 实验室中获取了以下图片,他们比较了不同实现的矩阵向量乘积。y 轴表示计算强度(以 GFLOPs 为单位);长话短说,就是计算速度有多快。x 轴是矩阵的维度。

enter image description here

C 和 C++ 是快速的语言,但实际上,如果您想模拟这些库的速度,您可能需要更深入地使用 Fortran 或 intrinsic 指令(它们可能是您在 C++ 中可以编写的最接近汇编代码的东西)。

考虑问题Benchmarking (python vs. c++ using BLAS) and (numpy),其中来自 @Jfs 的非常好的答案,我们观察到:"在我的机器上,C++和numpy没有区别。"

一些更多参考:

为什么朴素的 C++ 矩阵乘法比 BLAS 慢 100 倍?


1
需要注意的一点是,即使是看似简单的东西,比如数组.max,实际上也是由INTEL/AMD/APPLE直接编写的极其优化(汇编)代码。因此,一般来说,只要数组很大,朴素的c代码就会变慢。 - felix-ht

7

在我的电脑上,你的(当前的)Python代码运行了14.82秒(是的,我的电脑相当慢)。

我重新编写了你的C++代码,使其更合理(基本上,我几乎忽略了你的C++代码,只是将你的Python代码改写成C++)。这样就得到了下面的代码:

#include <cstdio>
#include <iostream>
#include <cmath>
#include <chrono>
#include <vector>
#include <assert.h>

const unsigned int k_max = 40000;
const unsigned int N = 10000;

template <class T>
class matrix2 {
    std::vector<T> data;
    size_t cols;
    size_t rows;
public:
    matrix2(size_t y, size_t x) : cols(x), rows(y), data(x*y) {}
    T &operator()(size_t y, size_t x) {
        assert(x <= cols);
        assert(y <= rows);
        return data[y*cols + x];
    }

    T operator()(size_t y, size_t x) const {
        assert(x <= cols);
        assert(y <= rows);
        return data[y*cols + x];
    }
};

int main() {
    matrix2<double> data(N, 2);
    matrix2<double> coeffs(k_max, 2);

    using namespace std::chrono;

    auto start = high_resolution_clock::now();

    for (int k = 0; k < k_max; k++) {
        for (int j = 0; j < N - 1; j++) {
            coeffs(k, 0) += data(j, 1) * (cos((k + 1)*data(j, 0)) - cos((k + 1)*data(j+1, 0)));
            coeffs(k, 1) += data(j, 1) * (sin((k + 1)*data(j, 0)) - sin((k + 1)*data(j+1, 0)));
        }
    }

    auto end = high_resolution_clock::now();
    std::cout << duration_cast<milliseconds>(end - start).count() << " ms\n";
}

这个程序运行大约需要14.4秒,所以它比Python版本稍微快了一点——但考虑到Python主要是一些C代码的薄包装,只有轻微的改进基本上是我们应该期望的。

下一步显而易见的是使用多核。在C++中,我们可以添加这行代码:

#pragma omp parallel for

在外层for循环之前:

#pragma omp parallel for
for (int k = 0; k < k_max; k++) {
    for (int j = 0; j < N - 1; j++) {
        coeffs(k, 0) += data(j, 1) * (cos((k + 1)*data(j, 0)) - cos((k + 1)*data(j+1, 0)));
        coeffs(k, 1) += data(j, 1) * (sin((k + 1)*data(j, 0)) - sin((k + 1)*data(j+1, 0)));
    }
}

使用编译器命令行添加-openmp参数(当然,确切的标志取决于您使用的编译器),这个程序运行时间约为4.8秒。如果您有超过4个内核,您可能会看到更大的改进(相反地,如果您有少于4个内核,则可以期望改进较小 - 但现在,多于4个内核比少于4个内核更常见)。


2
嗯...这很有趣。你的版本使用了更多的c++结构,但是主要的计算是相同的。我不会期望c++代码(带有不必要的结构)比纯c更快(而在此,它比python版本更快)。所以我运行了你的版本和原始版本,并平均了10次运行的结果。结果:原始的c++:10.8秒,原始的python 8.5秒,你的c++版本:32.8秒。所以,如预期的那样,我不能复制你的改进。 - Gwidryj
1
@JerryCoffin 是的,我指的是有限的值,而不是零。 - Gwidryj
1
@Gwidryj:零是离无穷远的最远点。 - Jerry Coffin
@JerryCoffin 我不确定谈论无限距离是否有意义,因为无限的问题通常会产生令人费解的结果,例如集合{0, ±1, ±2, ...}与{0, 1, 2, ...}大小相同。然而,如果你想直观地理解这个概念,-1比0更远离无穷大。 - user904963
有点道理,但如果我们处理的是带符号的数字,那么我们可能也想要带符号的无穷大,这种情况下-1更接近负无穷大。任何非零数都比0更接近一个无穷大(当然,谈论到无穷远的距离是否有意义)。 - Jerry Coffin
显示剩余8条评论

3

我试图理解你的Python代码并在C++中复现它。我发现你没有正确表示for循环以便正确计算coeffs,因此应该交换你的for循环。如果是这样的话,你应该有以下内容:

#include <iostream>
#include <cmath>
#include <time.h>

const int k_max = 40000;
const int N = 10000;

double cos_k, sin_k;

int main(int argc, char const *argv[])
{
    time_t start, stop;
    double data[2][N];
    double coefs[k_max][2];

    time(&start);

    for(int i=0; i<k_max; ++i)
    {
        for(int j=0; j<N; ++j)
        {
            coefs[i][0] += data[1][j-1] * (cos((i+1) * data[0][j-1]) - cos((i+1) * data[0][j]));
            coefs[i][1] += data[1][j-1] * (sin((i+1) * data[0][j-1]) - sin((i+1) * data[0][j]));
        }
    }
    // End of main loop

    time(&stop);

    // Speed result
    double diff = difftime(stop, start);
    std::cout << "Time: " << diff << " seconds" << std::endl;

    return 0;
}

将for循环交换后,使用-O3进行优化的C++代码运行时间为3秒,而Python代码则需要7.816秒。


我尝试了相同的思路,即引用局部性在这里适用。我尝试了许多k_maxN的值,使用data中的零值和非零值,但结果始终几乎相同,无论循环的顺序如何。 - Gwidryj
“我发现你没有正确地表示for循环以进行系数的正确计算” - 这是不正确的,改变for循环的顺序不会改变结果。在两种情况下,您都会遍历相同的(i, j)对集合,只是顺序不同而已。 - Gwidryj
@Gwidryj,当然,这会导致相同的计算时间。这是我的观察结果,为了完全尊重在纸上找到的公式。你没有做的是优化标志:g++ main.cpp -o main -O3 - quark
@Gwidryj,或者使用-O2。检查哪个对您更有效。 - quark

1
Python 代码不能比正确编码的 C++ 代码更快,因为 Numpy 是用 C 编写的,而 C 通常比 C++ 慢,因为 C++ 可以进行更多的优化。当大部分计算在 Python 推迟到编译二进制文件进行计算时,它们只会在彼此附近,Python 运行时间将介于与 C++ 相同的时间到两倍 C++ 之间。除了大矩阵乘法、加法、标量矩阵乘法等之外,大多数其他操作在 Python 中执行效果都会差得多。例如,看看 the Benchmark Game,人们在其中提交各种语言的各种算法解决方案,该网站跟踪每个(算法、语言)对的最快提交。您甚至可以查看每个提交的源代码。对于大多数测试用例,Python 比 C++ 慢 2-15 倍。如果您做的不仅仅是简单的数学运算,而是涉及到链表、二叉搜索树、过程式代码等任何东西,这也是有道理的。Python 的解释性质以及它为每个对象存储元数据(甚至是 intdoublefloat 等)显着拖慢了速度,这是任何 Python 程序员都无法解决的问题。

C++并不比纯C做更多的优化,这是不正确的说法,也表明了对这些语言的一些怀疑:编译器会对你的代码进行优化,而C和C++的编译器通常是相同的(如clang、gcc等)。 - Marine Galantin
2
@MarineGalantin C++有模板。看看C++中的std::sort与C中的qsort的速度比较。该语言允许进行更多的优化。在这里,编译器可以内联比较函数,因为它知道正在使用的类型。C语言的解决方案则不行。事情并不像我想象的那么清晰。如果你看一下Benchmark Game网站,C++在某些测试中严重击败了C,但C在其他测试中又严重击败了C++。有些则是平局。C赢得彻底的那些似乎是并行化的,而C++的解决方案则没有。当它们都被并行化时,C++获胜。 - user904963
1
那个基准测试网站展示了比较编程语言的复杂性,如果没有其他的话。有些解决方案并行化得很好,有些并行化得很差,还有一些手动使用SIMD指令和各种编码技巧,这些都不是标准程序与另一个标准程序之间的比较,只依赖于编译器进行优化。有时,使用的算法也是不同的。 - user904963

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