logo标签列表

为什么在连接两个字符串时Python比C更快？

pythoncstringperformance
14

目前我想比较Python和C在处理字符串时的速度。 我认为C应该比Python表现更好，但是我得到了完全相反的结果。

这里是C程序：

#include <unistd.h>
#include <sys/time.h>

#define L (100*1024)

char s[L+1024];
char c[2*L+1024];

double time_diff( struct timeval et, struct timeval st )
{
    return 1e-6*((et.tv_sec - st.tv_sec)*1000000 + (et.tv_usec - st.tv_usec ));
}

int foo()
{
    strcpy(c,s);
    strcat(c+L,s);
    return 0;
}

int main()
{
    struct timeval st;
    struct timeval et;
    int i;
    //printf("s:%x\nc:%x\n", s,c);

    //printf("s=%d c=%d\n", strlen(s), strlen(c));
    memset(s, '1', L);
    //printf("s=%d c=%d\n", strlen(s), strlen(c));
    foo();
    //printf("s=%d c=%d\n", strlen(s), strlen(c));
    //s[1024*100-1]=0;

    gettimeofday(&st,NULL);
    for( i = 0 ; i < 1000; i++ ) foo();
    gettimeofday(&et,NULL);

    printf("%f\n", time_diff(et,st));
    return 0;
}

这是Python的代码：

import time

s = '1'*102400
def foo():
    c = s + s
    #assert( len(c) == 204800 )

st = time.time()
for x in xrange(1000):
    foo()
et = time.time()

print (et-st)

我得到的结果是:

root@xkqeacwf:~/lab/wfaster# python cp100k.py 
0.027932882309
root@xkqeacwf:~/lab/wfaster# gcc cp100k.c
root@xkqeacwf:~/lab/wfaster# ./a.out 
0.061820

这有意义吗？还是我犯了什么愚蠢的错误？

3
有几件事情会让我对结果产生质疑。在一个函数中进行字符串连接是个不好的主意。构建函数的栈帧比连接本身要耗费更多的时间，而且谁知道它是否被优化掉了。你没有使用任何优化来编译 C 代码。所以那是无效的。整个测试太短了，不能进行有意义的比较。运行一些需要一两分钟的东西。 - desimusxvii
2
在Linux下，你可以使用与内核相关联的time命令，它会给出更可靠的结果，而不必在代码中瞎搞。只需编写应用程序所需的代码并使用time即可。 - Ken
3
除非你喜欢冒险，否则不应该以root身份编程，特别是学习编程。在普通用户身份下可以被视为无害的错误，在root身份下可能会致命。尽量避免使用root账户！ - Jonathan Leffler
2
@Marcus，strcat()在开始时较慢，因为它必须查找字符串终止符号，然后才能开始将另一个字符串添加到连接的末尾。 - Richard Chambers
3
我没有查看Python源代码，但几乎可以确定它会跟踪其字符串的长度（它们以null结尾，但Python始终知道字符串的活动部分有多长）。 知道长度使Python能够使用memmove（）或memcpy（）（区别在于memmove（）即使源和目标重叠也可以正常工作；如果它们重叠，memcpy（）不一定能正常工作）。 相对而言，他们很可能没有比memmove / memcpy更快的东西可用。 - Jonathan Leffler
显示剩余17条评论
2个回答
18

累积的评论（主要来自我）转化成了一个答案：

  • 如果使用字符串长度的知识并使用 memmove()或 memcpy()而不是 strcpy()和 strcat()会发生什么？ （我注意到 strcat()可以替换为 strcpy()而没有任何结果差异-检查时间可能很有趣。）此外，您没有包含< string.h>（或< stdio.h>），因此您错过了< string.h>提供的任何优化！

Marcus：是的， memmove()比 strcpy()和Python更快，但为什么？ memmove()每次是否执行一次字宽复制？

  • 是的，在64位机器上，针对良好对齐的数据，它可以每次移动64位而不是每次移动8位，在32位机器上，可能每次移动32位。它还具有仅一个在每个迭代（计数）上进行更简单的测试，而不需('count or is it null byte') 'is this a null byte'。

Marcus：但是，即使我使 L = L-13 ， memmove()仍然运行良好，而 sizeof(s)输出 L + 1024-13 。我的机器的 sizeof（int）== 4。

  • memmove() 的代码是高度优化的汇编程序，可能是内联的（没有函数调用开销，尽管对于100KiB的数据，函数调用开销很小）。好处在于更大的移动和简单的循环条件。

Marcus：那么Python也使用 memmove()还是其他魔法？

  • 我还没有查看过Python源码，但可以确定它跟踪其字符串的长度（它们是空终止的，但Python始终知道字符串的活动部分有多长）。知道该长度允许Python使用 memmove()或 memcpy()（区别在于 memmove()即使源和目标重叠也能正常工作； memcpy()不必在它们重叠时正确工作）。它相对不太可能拥有比 memmove/memcpy 更快的东西。

我修改了C代码，以在我的机器上产生更稳定的时间（Mac OS X 10.7.4，8 GiB 1333 MHz RAM，2.3 GHz Intel Core i7，GCC 4.7.1），并比较 strcpy() 和 strcat() 与 memcpy() 和 memmove()。请注意，我将循环计数从1000增加到10000以提高定时的稳定性，并且我重复测试所有三种机制10次。可以说，定时循环计数应该再增加5-10倍，以便定时超过一秒钟。

#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/time.h>

#define L (100*1024)

char s[L+1024];
char c[2*L+1024];

static double time_diff( struct timeval et, struct timeval st )
{
    return 1e-6*((et.tv_sec - st.tv_sec)*1000000 + (et.tv_usec - st.tv_usec ));
}

static int foo(void)
{
    strcpy(c,s);
    strcat(c+L,s);
    return 0;
}

static int bar(void)
{
    memcpy(c + 0, s, L);
    memcpy(c + L, s, L);
    return 0;
}

static int baz(void)
{
    memmove(c + 0, s, L);
    memmove(c + L, s, L);
    return 0;
}

static void timer(void)
{
    struct timeval st;
    struct timeval et;
    int i;

    memset(s, '1', L);
    foo();

    gettimeofday(&st,NULL);
    for( i = 0 ; i < 10000; i++ )
        foo();
    gettimeofday(&et,NULL);
    printf("foo: %f\n", time_diff(et,st));

    gettimeofday(&st,NULL);
    for( i = 0 ; i < 10000; i++ )
        bar();
    gettimeofday(&et,NULL);
    printf("bar: %f\n", time_diff(et,st));

    gettimeofday(&st,NULL);
    for( i = 0 ; i < 10000; i++ )
        baz();
    gettimeofday(&et,NULL);
    printf("baz: %f\n", time_diff(et,st));
}

int main(void)
{
    for (int i = 0; i < 10; i++)
        timer();
    return 0;
}

编译时不会产生任何警告：

gcc -O3 -g -std=c99 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
    -Wold-style-definition cp100k.c -o cp100k

我记录的时间是：

foo: 1.781506
bar: 0.155201
baz: 0.144501
foo: 1.276882
bar: 0.187883
baz: 0.191538
foo: 1.090962
bar: 0.179188
baz: 0.183671
foo: 1.898331
bar: 0.142374
baz: 0.140329
foo: 1.516326
bar: 0.146018
baz: 0.144458
foo: 1.245074
bar: 0.180004
baz: 0.181697
foo: 1.635782
bar: 0.136308
baz: 0.139375
foo: 1.542530
bar: 0.138344
baz: 0.136546
foo: 1.646373
bar: 0.185739
baz: 0.194672
foo: 1.284208
bar: 0.145161
baz: 0.205196

奇怪的是，如果我不使用'no warnings'选项并省略<string.h>和<stdio.h>头文件，就像最初发布的代码一样，我得到的时间如下:

foo: 1.432378
bar: 0.123245
baz: 0.120716
foo: 1.149614
bar: 0.186661
baz: 0.204024
foo: 1.529690
bar: 0.104873
baz: 0.105964
foo: 1.356727
bar: 0.150993
baz: 0.135393
foo: 0.945457
bar: 0.173606
baz: 0.170719
foo: 1.768005
bar: 0.136830
baz: 0.124262
foo: 1.457069
bar: 0.130019
baz: 0.126566
foo: 1.084092
bar: 0.173160
baz: 0.189040
foo: 1.742892
bar: 0.120824
baz: 0.124772
foo: 1.465636
bar: 0.136625
baz: 0.139923
眼观这些结果，似乎比“更干净”的代码快，尽管我没有对这两组数据进行学生t检验，并且计时有非常大的变化（但我有像Boinc这样在后台运行8个进程的东西）。当初测试只涉及到strcpy()和strcat()函数时，效果似乎更加显著。如果这是一个真正的效应，我无法解释它！ 由mvds进行后续跟进： 由于问题已关闭，我无法正常回答。在Mac上不做任何事情时，我得到以下计时结果：（带有标题）
foo: 1.694667 bar: 0.300041 baz: 0.301693
foo: 1.696361 bar: 0.305267 baz: 0.298918
foo: 1.708898 bar: 0.299006 baz: 0.299327
foo: 1.696909 bar: 0.299919 baz: 0.300499
foo: 1.696582 bar: 0.300021 baz: 0.299775

(不包含标题，忽略警告)

foo: 1.185880 bar: 0.300287 baz: 0.300483
foo: 1.120522 bar: 0.299585 baz: 0.301144
foo: 1.122017 bar: 0.299476 baz: 0.299724
foo: 1.124904 bar: 0.301635 baz: 0.300230
foo: 1.120719 bar: 0.300118 baz: 0.299673

预处理器输出（-E标志）显示，包括头文件会将strcpy翻译成内建调用，例如：

((__builtin_object_size (c, 0) != (size_t) -1) ? __builtin___strcpy_chk (c, s, __builtin_object_size (c, 2 > 1)) : __inline_strcpy_chk (c, s));
((__builtin_object_size (c+(100*1024), 0) != (size_t) -1) ? __builtin___strcat_chk (c+(100*1024), s, __builtin_object_size (c+(100*1024), 2 > 1)) : __inline_strcat_chk (c+(100*1024), s));

所以libc版本的strcpy函数表现优于gcc内置函数。（使用gdb可以轻松验证，如果包含头文件，在strcpy调用上设置断点确实不会中断）

在Linux上（Debian 5.0.9，amd64），差异似乎可以忽略不计。 生成的汇编代码（-S标志）仅在包含的调试信息方面存在差异。

有趣。但是这些数字都很混乱，在看似相同的运行之间存在2倍的因素（请参见条形图：0.10秒-0.20秒）。在一台什么也不做的机器上，结果非常稳定。与/没有标题的差异似乎也很稳定。我会发布一篇带有一些发现的答案。 - mvds
ps. 由于问题已关闭，我已在此答案下方放置了我的发现。 - mvds
1
@mvds：感谢提供额外的信息，这很有趣。我对上述各组测试数据以及我的机器数据进行了学生 t 检验，结果显示除了 'strcpy' 和 'memcpy() 或 memmove()' 之间明显的差异外，其他各组结果之间没有显著差异。当我关闭 Boinc 时，得到了稳定且紧密分组的结果：带有 headers 的情况下，strcpy() 的结果为 0.7346±0.0042，memcpy() 的结果为 0.0972±0.0014，memmove() 的结果为 0.0967±0.0011；不带 headers 的情况下，strcpy() 的结果为 0.7415±0.0045，memcpy() 的结果为 0.0977±0.0016，memmove() 的结果为 0.0978±0.0014（样本量为 20）。 - Jonathan Leffler
1
如果没其他的话，这至少展示了进行良好基准测试所面临的一些问题。 - Jonathan Leffler
1
进一步的研究表明，对于 strcat，实际运行的汇编代码不同之处在于内置版本使用了额外的寄存器来检查它是否越界，就像 strncat 一样。但是由于长度参数设置为 SIZE_T_MAX，这是一个无用的测试。 - mvds
7
我认为这是因为Python字符串没有以null结尾。在Python中，字符串长度与字符串一起存储，可以跳过在连接字符串时使用的隐含strlen()。另外，Python的字符串连接实现直接使用C语言，可能造成这种情况。编辑：好吧，现在我看了看C代码，并看到它使用静态缓冲区，我也感到困惑，因为我不知道Python如何避免动态分配，这应该会慢得多...
1
Python版本确实需要动态分配内存。虽然新的字符串立即变成垃圾，而且CPython大量使用自由列表，所以也许情况并不那么糟糕。 - user395760
这个测试结果是错误的，所以我不会去猜测它的结果。 - Ed S.
@EdS。您是否愿意详细说明这个测试有什么不正确的地方？ - Jonathan Leffler
1
@JonathanLeffler：它包括设置和调用函数所需的时间。它只执行1000次迭代。我们甚至不知道C版本是否是优化构建（以及编译器设置是什么）。它是不完整的，也不是一个好的测试案例。 - Ed S.
@EdS。我同意1000次迭代太少了。我不确定函数开销是否是一个主要问题（如果函数为空且在同一源文件中，说服编译器不优化调用空函数可能会很困难-至少计时空函数以了解开销的情况会很棘手）。同意编译环境没有详细说明。我见过更好的（我的一些答案解决了这些问题），但我也见过更糟糕的。 - Jonathan Leffler
显示剩余3条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接